BugTraq.Ru: форум / theory / отлично, но не то :(

информационная безопасность
без паники и всерьез

подробно о проекте

Анализ криптографических сетевых...

Модель надежности двухузлового...

Специальные марковские модели надежности...

Маск поддержал создателя Дилберта,...

Утечка сертификатов GitHub Desktop...

bugtraq.ru / форум / theory

Имя

Пароль


ФОРУМ


	все доски
	FAQ
	IRC
	новые сообщения

	site updates
	guestbook
	beginners
	sysadmin
	programming
	operating systems
	theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap

регистрация

Легенда:

новое сообщение

закрытая нитка

новое сообщение

в закрытой нитке

старое сообщение

Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
Новичкам также крайне полезно ознакомиться с данным документом.

отлично, но не то :( 11.01.05 14:09 Число просмотров: 4003
Автор: Lexy Статус: Незарегистрированный пользователь

<"чистая" ссылка>

Там написано, как свести "факторизацию" к "выполнимости". Я же просил показать сведение в обратную сторону.

Задача называется NP-полной, если к ней может быть сведена любая задача из класса NP. "Выполнимость" - как раз классичесикий пример NP-полной задачи. Если ее свести к "факторизации" -значит "факторизация" тоже NP-полна. Но этого как раз в указанном тексте нет.

===
Lexy

Поиск

Математики стоят на пороге уничтожения криптографии - TARASA 08.09.04 08:11 [9306]
- Каюсь. Я от криптографии и от высшей математики да... - TARASA 13.09.04 16:56 [5392]
- Задача журналиста - найти горячий материал. В принципе... - lime 13.09.04 16:11 [5193]
  - Существуют. Криптосистемы ЭльГамаля, Рабина, Нидер... - Heller 13.09.04 20:16 [6222]
    - Значит проблема будет только в быстром отказе от ставших... - lime 15.09.04 07:55 [4689]
- Интересно, с чего такой вывод? - cybervlad 10.09.04 08:36 [4984]
  - объясните пожалуйста еще раз - kata 22.09.04 08:31 [4592]
    - Попробую обобщить в двух словах все ранее сказанное - Heller 22.09.04 22:47 [4736]
      - скорость факторизации - kata 23.09.04 10:01 [4628]
        Pari/GP раскладывает за доли секунды [url] - RElf 23.09.04 14:46 [4721]
        Maple тоже - amirul 27.09.04 11:20 [4858]
        Согласно его хелпу: - RElf 27.09.04 12:20 [4393]
        Круто! Действительно, очень быстро. Если задача фа... - kata 24.09.04 06:57 [4339]
        В RSA сейчас используются модули порядка 2^1024, а то и... - RElf 24.09.04 10:19 [4501]
        Ахренеть! - kata 24.09.04 07:43 [4259]
        Ну что такое 100 битное число - малышка. А сколько... - DPP 24.09.04 10:18 [4684]
        скорость факторизации и лома - kata 23.09.04 11:53 [4528]
        Если речь о RSA, то 56 битными ключами никто не по... - DPP 23.09.04 19:13 [4343]
        немного путаницы - leo 23.09.04 13:07 [4534]
        При использовании алгоритма Ленстры сложность будет... - Heller 23.09.04 10:32 [4642]
        Эти формулы выдраны из O-нотации, поэтому верхняя оценка... - RElf 23.09.04 15:09 [4090]
        Сама функция задаётся непосредственно как L(n), а не как... - Heller 23.09.04 18:19 [3768]
        Выражение L(n)=(2+o(1))*f(n) - чуть более точное чем... - RElf 23.09.04 22:24 [4055]
        Странно, апплетовая факторизовалка на... - DPP 23.09.04 10:20 [3853]
        Попоробовал дать ей несколько разных коротких чисел вида... - Heller 23.09.04 10:52 [3754]
        А что значит короткое число? (-) - kata 23.09.04 11:27 [3754]
        Всмысле маленькое. Термин "короткое" несколько нек... (-) - Heller 23.09.04 17:51 [3741]
  - объясните пожалуйста - kata 21.09.04 16:28 [3824]
    - Ну, во-первых, не p, q и e, а на основе n и e - Heller 21.09.04 17:54 [4001]
      - попытка № 2 - kata 22.09.04 07:18 [3806]
        Спасибо, уже не надо. - kata 22.09.04 07:55 [3804]
        Про n=p1p2p3.. - Heller 22.09.04 09:46 [3962]
        чем дальше в лес... - kata 22.09.04 10:59 [3733]
        Вероятность этого при правильной реализации ничтожно мала. - RElf 22.09.04 15:56 [3830]
  - Ниже следующий автор по имени amirul упомянул еще... - lime 13.09.04 15:23 [4096]
  - Ну и мои 5 копеек - amirul 10.09.04 10:40 [4187]
    - Первое. Я не понимаю фразы "NP-полнота неизвестна"... - lime 13.09.04 15:36 [4526]
      - Не спора ради, но пониманья для - amirul 22.09.04 11:02 [3928]
        Эта задача уже несколько лет классифицируется как... - lime 30.09.04 14:37 [4125]
        Очень бы хотелось увидеть это доказательство. Т.е.,... - Lexy 17.12.04 22:40 [3763]
        http://bugtraq.ru/forum/faq/theory/fact2sat.html (-) - lime 28.12.04 09:01 [3738]
        отлично, но не то :( - Lexy 11.01.05 14:09 [4003]
        Я лучше расскажу, т.к. не встречал ни одной достаточно... - lime 30.09.04 14:04 [3776]
        Сведение - lime 08.10.04 09:29 [3917]
        Обо всём сразу - Heller 22.09.04 21:01 [5322]
        Что-то мне подсказывает, что Вы ошиблись в определении... - Lexy 17.12.04 22:43 [3612]
        Занимай очередь. :) (-) - lime 28.12.04 09:05 [3593]
        Ошибся-ошибся. Сам перечитал и не понял, что напис... (-) - Heller 28.12.04 18:10 [3703]
        И вновь каша в голове. - lime 01.10.04 12:40 [3905]
        IMHO про гипотезу Римана - leo 22.09.04 21:21 [3802]
- гонево - _йцукенг_ 08.09.04 14:46 [4358]
- Некоторые непонятки - nkiller 08.09.04 14:44 [4149]
  - я дилетант в криптографии, но пару линков дам. - _йцукенг_ 08.09.04 14:57 [4547]
    - Насчет источника, на который линк дан. Написано жу... - lime 13.09.04 15:56 [4333]
- Глупость, имхо - Heller 08.09.04 13:45 [4283]
  - просто сообщение Средств Массовой ДезИнформации (-) - kavkav@ukr.net 03.10.04 20:29 [3922]

Page build time: 0 s

Design: Vadim Derkach