Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 21 стр.

                                                                        22

выяснится, что n–составное число, то выберем новое значение R и повторим
вычисления.

      Оценка   эффективности     этого   метода   зависит   от   плотности
распределения простых чисел и расстояния между соседними простыми
числами. Вопрос этот является вовсе не простым (см.разд.1.13) и зависит
от справедливости обобщенной гипотезы Римана (ОГР). Если допустить
справедливость ОГР, то этот алгоритм является полиномиальным.

Генерация простых чисел с использованием решета Эратосфена

      Способ, описанный в предыдущем параграфе, дает большой разброс
в поиске простых чисел. Иногда, требуется найти простое число p(x),
следующее за данным целым числом x (в пакете Wolfram Mathematica есть
специальная функция, вычисляющая p(x) для очень больших чисел x).
Для нахождения простых чисел, следующих за заданным числом x, можно
использовать следующий алгоритм:

      1. Выписываем множество чисел {n, n + 2, n + 4, ..., n + 2m}, где
n ≥ x– наименьшее нечетное число, n + 2m – верхняя граница интервала.
      2. Выполним просеивание этого интервала с использованием решета
Эратосфена или Аткина (см. с.16) с помощью множества небольших простых
чисел {3, 5, ..., pk }, ограниченного сверху границей B . При B = 10,
отсеется примерно половина кандидатов. При pk < 1000, будет отсеяно 5/6
всех кандидатов.
      3. Далее, проверим оставшиеся кандидаты с помощью теста Миллера–
Рабина.

      Пример. При x ≈ 10260 была выбрана база для просеивания,
ограниченная сверху числом B = 1000. После 67 попыток было найдено
простое число x + 782. При B = 8000 число попыток уменьшилось до
50, а при B = 50 000 до 36. Значит, большое увеличение границы B не
обеспечивает выигрыша алгоритма в целом, т.к. время, сэкономленное за счет
уменьшения числа проб, не компенсирует время, затраченное на выполнение