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

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


0

0

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

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

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

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

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

eugine_kosenko ★★★ ()

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

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

nanonymous ()

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

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

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

cathode ★ ()

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

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

Cy6erBr4in ★★★ ()

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

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

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

Cy6erBr4in ★★★ ()
Ответ на: Re: [Большие простые числа] генерация... от Cy6erBr4in

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

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

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

eugine_kosenko ★★★ ()
Ответ на: Re: [Большие простые числа] генерация... от Cy6erBr4in

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

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

cathode ★ ()

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

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

vasily_pupkin ★★★★★ ()

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

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

Kpoxman ★★ ()
Ответ на: Re: [Большие простые числа] генерация... от eugine_kosenko

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

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

Cy6erBr4in ★★★ ()
Ответ на: Re: [Большие простые числа] генерация... от cathode

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

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

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

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