Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
Ясен пень от величины зависят. 24.08.05 01:02 Число просмотров: 2672
Автор: amirul <Serge> Статус: The Elderman
|
> > > В любом случае, ещё не доказано, что эффективных
> > алгоритмов
> >
> > Нет машин, которые бы исполнили этот алгоритм для
> > достаточно большого числа
Вот только если полиномиальное время (от величины) и логарифмический объем памяти это неэффективно, то я не знаю, что такое эффективно
> В том то и дело: все сущестующие алгоритмы - основаны на
> переборе. (ну может быть в наиболее эффективных таких
В том то и дело, что не все: http://en.wikipedia.org/wiki/Shor's_algorithm
Класс сложности BQP, о котором я говорил: http://en.wikipedia.org/wiki/BQP
BQP, in computational complexity theory, stands for "Bounded error, Quantum, Polynomial time". It denotes the class of problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/4 for all instances.
Полиномиальное время на квантовом компьютере (с вероятностью ошибки не больше 25%).
> алгоритмах используется совместно с перебором какие нибудь
> деревья, логика, и т.п.)
Никаких деревьев и логики. Самый быстрый из алгоритмов факторизации, который можно исполнить на тьюринг-эквивалентной машине - Решето обобщенного числового поля (General Number Field Sieve - GNFS): http://en.wikipedia.org/wiki/General_number_field_sieve
Модулярная арифметика. По куче модулей отсеиваются числа, которые никак не могут быть квадратами (чтобы представить факторизуемое число в виде разности квадратов).
> Но я всё же верю, что найдётся формула, которая будет
> позволять проводить подобные операции разложения даже на
> калькуляторе. :)))
Ага, на квантовом калькуляторе. А вообще сейчас даже прогнозы по поводу P=NP ничего конкретного не обещают. Одни уверены, что это выражение истинно (тогда криптография с открытым ключем умрет), другие уверены, что утверждение неверно (тогда могут умереть отдельные алгоритмы асимметричного шифрования, но сама она жить будет)
|
|
|
подробно о проекте
Анализ криптографических сетевых...
