Абсурдный алгоритм нахождения простых чисел, использующий длинную арифметику

Рассмотрим тривиальный и, наверное, кратчайший (но не эффективный) алгоритм наождения протых чисел $$$p \in \mathbb{N}: p \leq n$$$, основанный на теореме Вильсона и длинной арифметике.

1. Теорема Вильсона

Алгоритм основан на известной в элементарной теории чисел теореме Вильсона. Часто она доказывается только слева направо, но важно доказать критерий.

Теорема (Вильсон).

$$$p \in \mathbb{N}: p \ge 2$$$ — простое тогда и только тогда, когда $$$(p-1)! \equiv -1 \pmod{p}.$$$

Доказательство.

$$$\rightarrow \quad$$$ p — простое, сл-но $$$\forall$$$ a $$$\in \mathbb{Z}/p\mathbb{Z}$$$ $$$\quad$$$ $$$\exists a^{-1} \in \mathbb{Z}/p\mathbb{Z}: a\cdot{a^{-1}}=1$$$. Следовательно, в произведении $$$1 \cdot 2 \cdot \dotso \cdot (p-1)$$$ все элементы разбиваются на пары $$$(a, b)$$$, такие что $$$ab=1$$$.
$$$\leftarrow$$$ $$$\quad$$$ Предположим, что p — составное. Если p — не полный квадрат: $$$p \neq a^2 \quad \forall a \in \mathbb{Z}$$$, тогда $$$\exists a,b \in \mathbb{N}: a,b < p$$$ и $$$ab=p$$$, сл-но $$$p=ab$$$ делит $$$(p-1)!$$$. Иначе если $$$p=a^2: a>1$$$, тогда a делит $$$gcd(p, (p-1)!)$$$, сл-но a делит $$$(p-1)!$$$ mod $$$p$$$ и как результат: $$$(p-1)! \not\equiv -1 \pmod{p}$$$ противоречие.

2. Алгоритм

Из теоремы Вильсона может быть выведен достаточно простой алгоритм нахождения простых чисел.

a = 1
for i in range(2, n):
    if a%i == i-1:
        pass #prime
    a *= i

3. Длинная арифметика

Легко видеть, что алгоритм требует наличие длинной арифметики, т.к. факториал растёт быстро. Одна из эффективных реализаций длинной арифметики использует FFT (Быстрое Преобразование Фурье) для перемножения чисел (многочленов). FFT умножает $$$a\cdot{b}$$$ за $$$O(n\log{n})$$$, где n — максимальная битовая длина чисел. Мы используем этот факт в анализе. P.S. FFT с эвристиками использован и в python.

4. Асимптотика

Заметим, что на k-й итерации длина $$$a$$$ $$$O(\log{k!})$$$, так что общая асимптотика

Утверждение.

$$$\sum_{k=2}^n{\log{k!}\cdot{\log{\log}k!}} = O(n^2\log^2{n})$$$

Доказательство.

Используя формулу Стирлинга для логарифма гамма-функции (факториала):

получаем:

Используя факт $$$\log{(f + o(f))} = \log{f} + o(\log{f})$$$ (можно явно проверить по правилу Лопиталя) получаем, что сумма асимптотически стремиться к:

Известна формула суммирования Эйлера-Маклорена, в асимптотическом виде представимая как $$$\sum_{k=a}^b{f(k)} = \int_a^b{f(x)dx} + O(f)$$$ для некоторого класса функций $$$f$$$, таких что $$$f'(x) = O(f)$$$ или $$$f'(x) = o(f)$$$. Поэтому мы можем приблизить сумму интегралом:

Применяя интегрирование по частям 2 раза, убеждаемся, что значение интеграла — $$$O(n^2\log^2{n})$$$, ч.т.д..

5. Заключение

Алгоритм довольно абсурдный, но показывает некоторые техники работы с суммами, встречающимися в алгоритмах длинной арифметики.