Алгоритмы и их оптимизация: Проверка простоты числа

[loldop]

Здравствуйте!
Столкнулся с проблемой генерации простых чисел.
Имеется число длиной в 1024 бита. ( около 200 десятичных разрядов ).
Вопрос: как проверить его на простоту?
Обычные алгоритмы абсолютно не подходят и по времени, и по ресурсам.
А вот какие можно посмотреть алгоритмы на ускорение процесса проверки?
Была забавная идея проверить с помощью малой теоремы Ферма, но сразу отпала... вы сами знаете почему :)

[Ринат]

Может это даст какую-то наводку. ;)

[Sonic86]

Сначала Вам надо войти в текущее состояние дел:
http://ru.wikipedia.org/wiki/%D0%A2%D0% ... 1%82%D1%8B
Книжка: Василенко Теоретико-числовые алгоритмы в криптографии. Легко гуглится и скачивается.

loldop в сообщении #533939 писал(а):

Была забавная идея проверить с помощью малой теоремы Ферма,

с этого места на самом деле и началось все наиболее интересное

[loldop]

Простите за незнание, но:
некоторые алгоритмы, как, например, тест Агравала-Каяла-Саксены, используют квадратные корни и логарфмы.
Меня волнует только..
как вычислять эти величины? и это будет очень долго по времени! ( операция сложения уже использует О(n) простых сложений! )
А использовать разложение корня и логарифма не очень-то дешево в случае больших чисел.
( не говоря уже об операции возведения в степень )

[Sonic86]

loldop, я ведь их сам не реализовывал. Может venco придет и скажет чего-нибудь
Алгоритм Агравала-Каяла-Саксены - это наиболее навороченный алгоритм проверки на простоту, зато он точно детерминированный и полиномиальный. Однако, может оказаться, что он начинает работать быстрее, чем другие алгоритмы, начиная только с очень больших чисел (типа $10^{50}$ - я наугад пишу число). В книге Василенко вообще написано

Василенко писал(а):

Результаты практической реализации данного алгоритма пока неизвестны.

Как извлекать корень и считать логарифм оптимально я тоже не знаю Ну для корня еще можно использовать ряд, а для логарифма - ряд с двоичным уменьшением числа (типа так: $\ln (2n+r)= \ln 2 + \ln n + \ln (1+\frac{r}{2n}), r \in \{ 0;1\}$ - считаем точно $\ln 2$ один раз и $\ln (1+\frac{r}{2n})$ и тогда вычисление $\ln m$ сводится к вычислению $\ln \left[ \frac{m}{2}\right]$):
Попробуйте какой-нибудь более простой алгоритм проверки на простоты, пусть даже с бОльшей асимптотической сложностью. Метод Лемера легко можно запрограммировать (заодно и с факторизацией побаловаться). Вроде несложен алгоритм Миллера. Можете рискнуть здоровьем и попробовать алгоритм Ленстры.
Может Вам вероятностный алгоритм подойдет (их и комбинировать можно) - они еще проще.

[Joker_vD]

Обычно в криптографии используют метод Миллера-Рабина.

[Pavia]

loldop
Советую читать Кнута искусство программирования том 2. Читать с начала тома.
А да надо не просто читать, но и разбираться.

[loldop]

Спасибо за Кнута, конечно, очень полезная книжка.
Но проблема в том, что данная задача уже решена миллион раз, реализована в куче библиотек и не имеет для меня смысла более, чем интересная задача и алгоритмически сложная.

Спасибо, нашел Миллера-Рабина, действительно, простой метод.