Абсурдный алгоритм нахождения простых чисел, использующий длинную арифметику↵
==================↵
↵
Рассмотрим тривиальный и, наверное, кратчайший (но не эффективный) алгоритм наождения протых чисел $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. Алгоритм↵
------------------↵
Из теоремы Вильсона может быть выведен достаточно простой алгоритм нахождения простых чисел. ↵
↵
```python↵
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!})$, так что общая асимптотика ↵
$$O(\sum_{k=2}^n{\log{k!}\cdot{\log{\log{k!}}})}$$↵
↵
#### Утверждение.↵
$\sum_{k=2}^n{\log{k!}\cdot{\log{\log}k!}} = O(n^2\log^2{n})$↵
↵
#### _Доказательство._↵
Используя <a href="https://mathworld.wolfram.com/StirlingsApproximation.html">формулу Стирлинга</a> для логарифма гамма-функции (факториала): ↵
$$\log{k!} = k\log{k} — k + O(\log{k}) = k\log{k} + O(k)$$ ↵
получаем: ↵
$$\sum_{k=2}^n{\log{k!}\cdot{\log{\log{k!}}}} = \sum_{k=2}^n{(k\log{k} + O(k))\log{(k\log{k} + O(k))}}$$ ↵
Используя факт $\log{(f + o(f))} = \log{f} + o(\log{f})$ (можно явно проверить по <a href="https://encyclopediaofmath.org/wiki/L%27Hospital_rule">правилу Лопиталя</a>) получаем, что сумма <b>асимптотически</b> стремиться к: ↵
$$\sum_{k=2}^n{k\log^2{k}}$$ ↵
Известна <a>формула суммирования Эйлера-Маклорена</a>, в асимптотическом виде представимая как $\sum_{k=a}^b{f(k)} = \int_a^b{f(x)dx} + O(f)$ для некоторого класса функций $f$, таких что $f'(x) = O(f)$ или $f'(x) = o(f)$. Поэтому мы можем приблизить сумму интегралом: ↵
$$\sum_{k=2}^n{k\log^2{k}} = O(\int_2^n{x\log^2{x}dx})$$ ↵
Применяя интегрирование по частям 2 раза, убеждаемся, что значение интеграла — $O(n^2\log^2{n})$, ч.т.д.. ↵
↵
5. Заключение↵
------------------↵
Алгоритм довольно абсурдный, но показывает некоторые техники работы с суммами, встречающимися в алгоритмах длинной арифметики.
==================↵
↵
Рассмотрим тривиальный и, наверное, кратчайший (но не эффективный) алгоритм наождения протых чисел $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. Алгоритм↵
------------------↵
Из теоремы Вильсона может быть выведен достаточно простой алгоритм нахождения простых чисел. ↵
↵
```python↵
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!})$, так что общая асимптотика ↵
$$O(\sum_{k=2}^n{\log{k!}\cdot{\log{\log{k!}}})}$$↵
↵
#### Утверждение.↵
$\sum_{k=2}^n{\log{k!}\cdot{\log{\log}k!}} = O(n^2\log^2{n})$↵
↵
#### _Доказательство._↵
Используя <a href="https://mathworld.wolfram.com/StirlingsApproximation.html">формулу Стирлинга</a> для логарифма гамма-функции (факториала): ↵
$$\log{k!} = k\log{k} — k + O(\log{k}) = k\log{k} + O(k)$$ ↵
получаем: ↵
$$\sum_{k=2}^n{\log{k!}\cdot{\log{\log{k!}}}} = \sum_{k=2}^n{(k\log{k} + O(k))\log{(k\log{k} + O(k))}}$$ ↵
Используя факт $\log{(f + o(f))} = \log{f} + o(\log{f})$ (можно явно проверить по <a href="https://encyclopediaofmath.org/wiki/L%27Hospital_rule">правилу Лопиталя</a>) получаем, что сумма <b>асимптотически</b> стремиться к: ↵
$$\sum_{k=2}^n{k\log^2{k}}$$ ↵
Известна <a>формула суммирования Эйлера-Маклорена</a>, в асимптотическом виде представимая как $\sum_{k=a}^b{f(k)} = \int_a^b{f(x)dx} + O(f)$ для некоторого класса функций $f$, таких что $f'(x) = O(f)$ или $f'(x) = o(f)$. Поэтому мы можем приблизить сумму интегралом: ↵
$$\sum_{k=2}^n{k\log^2{k}} = O(\int_2^n{x\log^2{x}dx})$$ ↵
Применяя интегрирование по частям 2 раза, убеждаемся, что значение интеграла — $O(n^2\log^2{n})$, ч.т.д.. ↵
↵
5. Заключение↵
------------------↵
Алгоритм довольно абсурдный, но показывает некоторые техники работы с суммами, встречающимися в алгоритмах длинной арифметики.
