Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Не спора ради, но пониманья для 22.09.04 11:02 Число просмотров: 4178
Автор: amirul <Serge> Статус: The Elderman
|
Сразу же напишу пару дисклеймеров: 1) Во-первых, я действительно сильно не люблю спорить с людьми, компетентными в некоторой области, если я в этой области некомпетентен, посему прошу мои замечания расценивать не как возражения, а как просьбу о разъяснении 2) Мое знание математики ограничивается курсом вышки технического вуза на нематематической специальности (компьютерные системы и сети), и если в области мат анализа я еще могу правильно пользоваться терминогией, то в теории сложности или в конечных полях я совершенно не смыслю, так что прошу не стрелять в пианиста - он играет как умеет.
> Первое. Я не понимаю фразы "NP-полнота неизвестна". Все же
> следует более корректно обращаться с формулировками.
> Второе. Если я правильно понял, то читать это следует как
> "неизвестно сведение задачи факторизация к одной из
> известных NP-полных задач". Если так, то Вы неправы. Задача
> факторизации очень легко и просто сводится к задаче
> Выполнимость. И существует по меньшей мере два варианта
Во фразе "NP-полнота неизвестна" я имел в виду то, что до сих пор не известно к какому классу сложности относится задача факторизации. Более того, многие уверены в том, что эта задача не является NP-полной (кстати, хотел поинтересоваться, говорит ли полиномиальный алгоритм факторизации Шора, что либо об NP-полноте задачи факторизации?)
В своем высказывании я руководствуюсь исключительно чужими мнениями (вследствие того, что не могу сложить собственного по данному вопросу), неоднократно встречавшимися мне в сети. Самый авторитетный источник, который мне удалось сейчас найти - википедия:
http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity
Ну и ссылки в самой статье
> такого сведения. Самое интересное заключается в том, что
> исходное число сводится к некоторой задаче ВЫП так, что
> данная задача имеет решение тогда и только тогда, когда
> исходное чмсло не простое, а множество решений данной
> задачи представляет собой множество вариантов разложения
> исходного числа на сомножители (не обязательно простые).
Не могли бы Вы подробнее рассказать (или дать ссылки) об этом?
> Третье. В целом по делу все сказано верно - отомрут только
> те методы, которые основаны на проблеме факторизации чисел.
> Но это только то, что нам известно сейчас и о чем мы
> уверенно можем говорить. Следует помнить о том, ежедневно
Насколько я знаю, на сегодняшний день самым стойким ассиметричным шифрованием является шифрование на эллиптических кривых. Там даже рекомендуемая разрядность ключа на порядок меньше, чем в том же RSA при той же стойкости
|
|
|
подробно о проекте
Анализ криптографических сетевых...
