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

Revision ru3, by alexvim, 2024-04-01 13:08:34

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

Рассмотрим тривиальный и, наверное, кратчайший (но не эффективный) алгоритм наождения протых чисел $$$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!})$$$, так что общая асимптотика

$$$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})$$$

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

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

$$$\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})$$$ (можно явно проверить по правилу Лопиталя) получаем, что сумма асимптотически стремиться к:

$$$\sum_{k=2}^n{k\log^2{k}}$$$

Известна формула суммирования Эйлера-Маклорена, в асимптотическом виде представимая как $$$\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. Заключение

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

Tags математика, простые числа, асимптотика, юмор

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian alexvim 2024-04-01 13:08:34 108
en4 English alexvim 2024-04-01 13:07:44 27
ru2 Russian alexvim 2024-04-01 12:38:27 0 (опубликовано)
en3 English alexvim 2024-04-01 12:37:46 0 (published)
ru1 Russian alexvim 2024-04-01 12:37:22 3504 Первая редакция перевода на Русский (сохранено в черновиках)
en2 English alexvim 2024-04-01 11:52:36 1898
en1 English alexvim 2024-04-01 01:47:00 4427 Initial revision (saved to drafts)