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

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

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

А чем Ферма не угодил?

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

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

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

Решето Эратосфена (и все производные от него) http://ru.wikipedia.org/wiki/Решето_Эратосфена

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

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

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

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

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

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

Вам вообще для каких целей?

>> Вам вообще для каких целей?

Подозреваю, что для реферата/курсовика :))

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

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

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

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

Результаты выложи потом куда нибудь в свободный доступ ^_^

http://cr.yp.to/primegen.html

Ок, выложу конечно :)

Спасиб, гляну обязательно.