Быстрый алгоритм нахождения большого простого числа

[by_trojan]

Подскажите быстрый алгоритм нахождения большого простого числа. Желательно на Delphi

[Alexu007]

Насколько большого?

[Pavia]

by_trojan
Кнут том второй глава 4.5.4

[by_trojan]

Alexu007 в сообщении #549457 писал(а):

Насколько большого?

до 10.000

[Joker_vD]

by_trojan
Тьфу, это ж рази большое? Если до 10'000, то в таблице гляньте: http://oeis.org/A000040/a000040.txt — первые сто тысяч простых чисел.

[Alexu007]

topic55331.html

тут аж целых три исходника на С решета Эрастофена: с байтами, битами и с интеллектуальным методом оптимизации. Реально за секунды находят простые числа размерностью в миллиарды, особенно третий.

[Sonic86]

Согласно гипотезе Крамера (она не доказано, но можете считать ее за эмпирический факт, либо очень вероятное явление), расстояние между простыми $p_n,p_{n+1}$ оценивается как $O( \ln ^2 p_n)$ - что очень мало. Поэтому можно тупо делать так: выбираете число $a$, возле которого ищете простое число, строите множество $\{a,a+1,...,a+K\},K=O(\ln ^2 a)$ проходите по нему сначала мелким решетом, а оставшееся небольшое количество простых можете тестировать на простоту уже по одному обычными алгоритмами.
Скорость алгоритма не оценивал.

by_trojan в сообщении #549832 писал(а):

до 10.000

аааа,... а я для $p>10^{10}$ предлагаю
Погуглите решето Эратосфена, решето Сундарама.

[Alexu007]

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

1. Берём одно гарантированно простое число требуемого размера, второе число X, которое мы хотим проверить.

2. Зашифровываем с помощью этих двух чисел любое соразмерное тестовое число.

3. Расшифровываем. Если тестовое и расшифрованное числа совпадают - очевидно и наше второе число X является простым.