информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsСетевые кракеры и правда о деле Левина
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
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Не спора ради, но пониманья для 22.09.04 11:02  Число просмотров: 3065
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
Сразу же напишу пару дисклеймеров: 1) Во-первых, я действительно сильно не люблю спорить с людьми, компетентными в некоторой области, если я в этой области некомпетентен, посему прошу мои замечания расценивать не как возражения, а как просьбу о разъяснении 2) Мое знание математики ограничивается курсом вышки технического вуза на нематематической специальности (компьютерные системы и сети), и если в области мат анализа я еще могу правильно пользоваться терминогией, то в теории сложности или в конечных полях я совершенно не смыслю, так что прошу не стрелять в пианиста - он играет как умеет.

> Первое. Я не понимаю фразы "NP-полнота неизвестна". Все же
> следует более корректно обращаться с формулировками.
> Второе. Если я правильно понял, то читать это следует как
> "неизвестно сведение задачи факторизация к одной из
> известных NP-полных задач". Если так, то Вы неправы. Задача
> факторизации очень легко и просто сводится к задаче
> Выполнимость. И существует по меньшей мере два варианта
Во фразе "NP-полнота неизвестна" я имел в виду то, что до сих пор не известно к какому классу сложности относится задача факторизации. Более того, многие уверены в том, что эта задача не является NP-полной (кстати, хотел поинтересоваться, говорит ли полиномиальный алгоритм факторизации Шора, что либо об NP-полноте задачи факторизации?)
В своем высказывании я руководствуюсь исключительно чужими мнениями (вследствие того, что не могу сложить собственного по данному вопросу), неоднократно встречавшимися мне в сети. Самый авторитетный источник, который мне удалось сейчас найти - википедия:
http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity
Ну и ссылки в самой статье

> такого сведения. Самое интересное заключается в том, что
> исходное число сводится к некоторой задаче ВЫП так, что
> данная задача имеет решение тогда и только тогда, когда
> исходное чмсло не простое, а множество решений данной
> задачи представляет собой множество вариантов разложения
> исходного числа на сомножители (не обязательно простые).
Не могли бы Вы подробнее рассказать (или дать ссылки) об этом?

> Третье. В целом по делу все сказано верно - отомрут только
> те методы, которые основаны на проблеме факторизации чисел.
> Но это только то, что нам известно сейчас и о чем мы
> уверенно можем говорить. Следует помнить о том, ежедневно
Насколько я знаю, на сегодняшний день самым стойким ассиметричным шифрованием является шифрование на эллиптических кривых. Там даже рекомендуемая разрядность ключа на порядок меньше, чем в том же RSA при той же стойкости
<theory> Поиск 








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


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