LINUX.ORG.RU
Форум — Development  

[Большие простые числа] генерация...


0

0

Всем привет. Меня интересует вопрос генерации больших простых чисел. Кто что может подсказать кроме малой теоремы Ферма? Какие ещё есть способы? Хотя бы просто названия, если будут ссылки (можно на англоязычные ресурсы), то буду очень благодарен!

Всем спасибо зарание!

Д. Кнут, "Искусство программирования", том 2, раздел 4.5.4, "Разложение на простые множители".

Правда, он там все-равно на Ферма ссылается.

eugine_kosenko ★★★
()

Ну дык вроде как пока ничего более быстрого не изобрели. Генерим случайное число и тестим на простоту. Можно использовать модификации т. Ферма, например тест Миллера-Рабина.

И еще вот интересный вариант: рекурсивный генератор, правда помимо чиел вываливает кучу мусора http://recursed.blogspot.com/2008/07/rutgers-graduate-student-finds-new.html

cathode ★
()

Извиняюсь, наверное я просто неполно высказал мои желания :) мне не нужен самый лучший/оптимальный/и т.д. алгоритм, мне просто нужно несколько самых известных (3-5 штук пойдёт), мне надо их сравнить... собсно и всё :) так что буду рад услышать любые кто какие знает :)

Cy6erBr4in ★★★
() автор топика

Вот, уже лучше, кроме Ферма появилось решето Эратосфена! Спасибо!

Буду ждать ещё ответов...

Cy6erBr4in ★★★
() автор топика
Ответ на: комментарий от Cy6erBr4in

> Вот, уже лучше, кроме Ферма появилось решето Эратосфена! Спасибо!

Я правильно понял, что слово "большие" в условии было лишним?

eugine_kosenko ★★★
()
Ответ на: комментарий от Cy6erBr4in

Решето Эрастофена не предназначено для больших чисел, а вообще решето Сундарама, решето Аткина, тест Миллера-Рабина, тест Люка-Лемера (тест на простоту чисел Мерсена, кстати самое большое известное простое число - одно из чисел Мерсена) и сюда посмотри http://ru.wikipedia.org/wiki/Список_простых_чисел

cathode ★
()

Воспользуйтесь каким то стандартом. Например в FIPS 186-3 есть ссылки на новые SP 800-xx. Вообще в FIPS 186-3 есть написанные английским по белому алгоритмы, достаточно шустрые

vasily_pupkin ★★★★★
()

OpenSSH можно глянуть. Там же RSA - как-то они генерируют большие простые числа.

Kpoxman ★★
()
Ответ на: комментарий от eugine_kosenko

Ну вообще в дальнейшем нужны будут и большие, но для начала и по-меньше пойдут... да и скорость не важна сейчас...

Cy6erBr4in ★★★
() автор топика
Ответ на: комментарий от cathode

Примерно так :) тут нежданно негаданно практику нам на лето на кой-то фиг поставили... и у научрука не нашлось интереснее задания как предложить мне сравнительный обзор алгоритмов генерации простых чисел... вообще я над RSA работаю, это так... сопутствующие проблемы :)

вот теперь и мучаюсь, вместо того чтобы делом заниматься :)

Cy6erBr4in ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development