Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Обо всём сразу 22.09.04 21:01 Число просмотров: 5516
Автор: Heller <Heller> Статус: Elderman
Отредактировано 22.09.04 21:08 Количество правок: 1
|
Во-первых, все алгоритмы факторизации работают за полиномиальное время. Их можно условно разделить на две категории: алгоритмы, основанные на эллиптических кривых и алгоритмы, которые на этих кривых не основаны.
Для всех алгоритмов, про которые я читал, которые эллиптические кривые не применяют, существуют формулы для вычесления максимального количества совершенных операций для полной факторизации. Они имеют либо экспоненциальную сложность, либо субэкспоненциальную, что их и разделяет на две больших группы. Вариантов тут нет. Алгоритмы с субэкспоненциальной сложностью являются самымы быстрыми.
Что касается эллиптических кривых, то про них я знаю не так много, поэтому утверждать что-то не буду. Из таких алгоритмов известен алгоритм Ленстры, сложность для которого определена (правда, зависит от количества простых сомножителей, но верхний предел всегда известен). Существует ещё расширенный алгоритм Ленстры, про сложность вычисления которого я ничего не слышал, но надо полагать, что она всё равно будет не выше сложности обычного алгоритма.
Так же с использованием эллиптических кривых вычисляется порядок группы точек эллиптической кривой над конечным полем. Для этого так же существует несколько алгоритмов, самый трудоёмкий из которых (из тех, что известны мне, а я этим вопросом подробно не занимался никогда) - это алгоритм Шура, полиномиальная сложность которого так же определена: O((log p)^8). Все остальные алгоритмы либо имеют свои формулы для вычисления сложности, либо доказывается, что их сложность не выше чем у алгоритма Шура.
Как видно, сложность для всех алгоритмов определена либо точно, либо определена верхняя граница. Другое дело обстоит с тестированием числа на простоту, что так же полезно при факторизации (в основном это сводится к вопросу о необходимости дальнейшей факторизации при получении какого-то набора чисел). Тесты можно разделить опять же на две группы - статистические и не статистические. Не статистически работают так же за полиномиальное время (опять же здесь максимальная граница сложности - перебор всех делителей подряд от 2 до n^(1/2)), а статистические работают вообще за время совершенно не значительное , но дают не точные результаты.
Один из не статистических алгоритмов проверки числа на простоту - алгоритм Миллера. Он имеет сложность n^(1/7). И вот здесь начинается самое интересное. Имеется возможность модифицировать его так, что его сложность резко снизится до (log n)^4, но эта модификация (которая вроде как и названия не имеет), как раз и основана на справедливости расширенной гипотезы Римана.
Что существенно: как видно, модифицированный алгоритм Миллера, основаный на гипотезе Римана, работает за полиномиальное время O(L), однако, имхо, (log n)^4 - это вообще-то не мало. Причём это единственное пратическое применение гипотезы Римана, которое я знаю. Исходя из самой гипотезы Римана (кто-то выше ссылку давал) не совсем ясно, как факторизировать числа, поэтому имеется подозрение, что алгоритм Миллера это вообще единственный алгоритм на сегодняшний день, который эту гипотезу использует. К тому же, насколько мне известно, хоть гипотеза Римана и не доказана, модифицированный алгоритм Миллера применяется сегодня на практике достаточно широко и даёт очень хорошие результаты. Проверить его не удаётся - все оценки только на основе статистических тестов.
Во всяком случае, гипотеза Римана полезна ТОЛЬКО для проверки числа на простоту, а при факторизации проверка числа на простоту полезна ТОЛЬКО если n=P1P2...Pk, где k>2. Что касается RSA, то там k, причём неизвестно с какой вероятностью (только приближённые оценки), действительно больше двух, однако, полная факторизация в RSA и не требуется, что показано где-то в одном из постов этого же топика (чей пост не помню, но не мой точно - если кто искать будет). Хотя это может и кажется странным, но действительно, если посмотреть на существующие сегодня алгоритмы - они при разложении числа на множетели не пользуются свойством простоты числа - они именно раскладывают число на множетели, вместо того, что бы подбирать простые сомножители. Проверка на простоту нужна только для того, что бы выяснить, требуется ли далнейшая факторизация полученных сомножителей (неизвестно, простые ли они) далее или нет. В RSA, как известно, не требуется.
Вроде, всё изложил.
P.S. А что касается P=NP, то это при изучении вопросов факторизации и проверки на простоту не шибко важно. Во всяком случае, я никогда в научных изданиях не встречался с использованием (даже косвенным) данной гипотезы, когда речь идёт о простоте чисел. Как сказал классик, не помню какой, "не надо плодить сущности без надобности". Имхо.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
