Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Первое. Я не понимаю фразы "NP-полнота неизвестна". Все же... 13.09.04 15:36 Число просмотров: 4725
Автор: lime Статус: Незарегистрированный пользователь
|
> Насколько я помню, NP-полнота неизвестна только в отношении
> факторизации, а NP-полнота задачи дискретного
> логарифмирования доказана. Так что смерть грозит разве что
> RSA (ну так ему уже и годков-то сколько). Тот же эль-гамаль
> устоит. Да и стойкость алгоритмов на эллиптических кривых,
> насколько я помню не сильно зависит от факторизации.
Первое. Я не понимаю фразы "NP-полнота неизвестна". Все же следует более корректно обращаться с формулировками.
Второе. Если я правильно понял, то читать это следует как "неизвестно сведение задачи факторизация к одной из известных NP-полных задач". Если так, то Вы неправы. Задача факторизации очень легко и просто сводится к задаче Выполнимость. И существует по меньшей мере два варианта такого сведения. Самое интересное заключается в том, что исходное число сводится к некоторой задаче ВЫП так, что данная задача имеет решение тогда и только тогда, когда исходное чмсло не простое, а множество решений данной задачи представляет собой множество вариантов разложения исходного числа на сомножители (не обязательно простые).
Третье. В целом по делу все сказано верно - отомрут только те методы, которые основаны на проблеме факторизации чисел. Но это только то, что нам известно сейчас и о чем мы уверенно можем говорить. Следует помнить о том, ежедневно появляются все новые и новые NP-полные задачи. И кто может поручиться, что завтра мы не сведем случайно еще одну проблему, лежащую в основе какого-либо алгоритма криптографии, к задаче 3-ВЫП.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
