информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяЗа кого нас держат?Где водятся OGRы
BugTraq.Ru
Русский BugTraq
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Модель надежности отказоустойчивой... 
 Oracle выпустила срочный патч для... 
 Атака на WPA2 
 Outlook полгода отправлял зашифрованные... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
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
регистрация





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

Первое. Я не понимаю фразы "NP-полнота неизвестна". Все же следует более корректно обращаться с формулировками.
Второе. Если я правильно понял, то читать это следует как "неизвестно сведение задачи факторизация к одной из известных NP-полных задач". Если так, то Вы неправы. Задача факторизации очень легко и просто сводится к задаче Выполнимость. И существует по меньшей мере два варианта такого сведения. Самое интересное заключается в том, что исходное число сводится к некоторой задаче ВЫП так, что данная задача имеет решение тогда и только тогда, когда исходное чмсло не простое, а множество решений данной задачи представляет собой множество вариантов разложения исходного числа на сомножители (не обязательно простые).
Третье. В целом по делу все сказано верно - отомрут только те методы, которые основаны на проблеме факторизации чисел. Но это только то, что нам известно сейчас и о чем мы уверенно можем говорить. Следует помнить о том, ежедневно появляются все новые и новые NP-полные задачи. И кто может поручиться, что завтра мы не сведем случайно еще одну проблему, лежащую в основе какого-либо алгоритма криптографии, к задаче 3-ВЫП.
<theory> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2017 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach