Fool algorithm for finding prime numbers based on long arithmetic↵
==================↵
↵
We will observe the trivial and probably the shortest (but not fast) algorithm for finding all prime numbers $p \in \mathbb{N}: p \leq n$ based on Wilson's theorem and long arithmetic.↵
↵
1. Wilson's theorem↵
------------------↵
Algorithm based on well-known in number theory Wilson's theorem. Often implication is being proved only from left to right but it is important to prove equivalence.↵
↵
#### Theorem (Wilson).↵
$p \in \mathbb{N}: p \ge 2$ is prime if and only if $(p-1)! \equiv -1 \pmod{p}.$↵
↵
#### _Proof._↵
$\rightarrow \quad$ p is prime so $\forall$ a $\in \mathbb{Z}/p\mathbb{Z}$ $\quad$ $\exists a^{-1} \in \mathbb{Z}/p\mathbb{Z}: a\cdot{a^{-1}}=1$. Therefore in product $1 \cdot 2 \cdot \dotso \cdot (p-1)$ all elements are divided in pairs $(a, b)$ such that $ab=1$. ↵
$\leftarrow$ $\quad$ Let's assume that p is composite. If p is not full square: $p \neq a^2 \quad \forall a \in \mathbb{Z}$ then $\exists a,b \in \mathbb{N}: a,b < p$ and $ab=p$ so $p=ab$ divides $(p-1)!$. Else if $p=a^2: a>1$ then a divides $gcd(p, (p-1)!)$ so a divides $(p-1)!$ mod $p$ and as a result: $(p-1)! \not\equiv -1 \pmod{p}$ — contradiction.↵
↵
↵
2. Algorithm↵
------------------↵
From Wilson's theorem can be derived very simple algorithm for finding prime numbers. ↵
↵
```python↵
a = 1↵
for i in range(2, n):↵
if a%i == i-1:↵
pass #prime↵
a *= i↵
```↵
↵
3. Long arithmetic↵
------------------↵
It is easy to notice that algorithm needs long arithmetic because factorial grows very fast. The one of fastest implementations of long arithmetic uses FFT (Fast Fourier Transform) for numbers (or polynomials) multiplication. FFT multiplies $a\cdot{b}$ in $O(n\log{n})$ where n is max bit-length of a and b. We will use this fact in analysis. P.S. FFT with heuristics is used in Python too.↵
↵
4. Asymptotic↵
------------------↵
Notice that at iteration $k$ $a$ length is $O(\log{k!})$ so entire complexity is ↵
$O(\sum_{k=2}^n{\log{k!}\cdot{\log{\log{k!}}})}$↵
↵
#### Statement.↵
$\sum_{k=2}^n{\log{k!}\cdot{\log{\log}k!}} = O(n^2\log^2{n})$↵
↵
#### _Proof._↵
Using <a href="https://mathworld.wolfram.com/StirlingsApproximation.html">Stirling's formula</a> for gamma function (factorial) logarithm ↵
$$\log{k!} = k\log{k} — k + O(\log{k}) = k\log{k} + O(k)$$ ↵
we get: ↵
$$\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))}}$$ ↵
Using fact $\log{(f + o(f))} = \log{f} + o(\log{f})$ (can be clearly checked according to the <a href="https://encyclopediaofmath.org/wiki/L%27Hospital_rule">L'Hospital rule</a>) we get that the sum <b>asymptotically</b> equals to: ↵
$$\sum_{k=2}^n{k\log^2{k}}$$ ↵
There is <a>Euler-Maclaurin's summation formula</a> $\sum_{k=a}^b{f(k)} = \int_a^b{f(x)dx} + O(f)$ for class functions $f$ such that $f'(x) = O(f)$ or $f'(x) = o(f)$. So we can approximate discrete sum with integral: ↵
$$\sum_{k=2}^n{k\log^2{k}} = O(\int_2^n{x\log^2{x}dx})$$ ↵
After applying integration by parts two times we get that value of this integral is $O(n^2\log^2{n})$, Q.E.D. ↵
↵
5. Conclusion↵
------------------↵
This algorithm is rather absurd but it shows some simple techniques in work with long arithmetic.
==================↵
↵
We will observe the trivial and probably the shortest (but not fast) algorithm for finding all prime numbers $p \in \mathbb{N}: p \leq n$ based on Wilson's theorem and long arithmetic.↵
↵
1. Wilson's theorem↵
------------------↵
Algorithm based on well-known in number theory Wilson's theorem. Often implication is being proved only from left to right but it is important to prove equivalence.↵
↵
#### Theorem (Wilson).↵
$p \in \mathbb{N}: p \ge 2$ is prime if and only if $(p-1)! \equiv -1 \pmod{p}.$↵
↵
#### _Proof._↵
$\rightarrow \quad$ p is prime so $\forall$ a $\in \mathbb{Z}/p\mathbb{Z}$ $\quad$ $\exists a^{-1} \in \mathbb{Z}/p\mathbb{Z}: a\cdot{a^{-1}}=1$. Therefore in product $1 \cdot 2 \cdot \dotso \cdot (p-1)$ all elements are divided in pairs $(a, b)$ such that $ab=1$. ↵
$\leftarrow$ $\quad$ Let's assume that p is composite. If p is not full square: $p \neq a^2 \quad \forall a \in \mathbb{Z}$ then $\exists a,b \in \mathbb{N}: a,b < p$ and $ab=p$ so $p=ab$ divides $(p-1)!$. Else if $p=a^2: a>1$ then a divides $gcd(p, (p-1)!)$ so a divides $(p-1)!$ mod $p$ and as a result: $(p-1)! \not\equiv -1 \pmod{p}$ — contradiction.↵
↵
↵
2. Algorithm↵
------------------↵
From Wilson's theorem can be derived very simple algorithm for finding prime numbers. ↵
↵
```python↵
a = 1↵
for i in range(2, n):↵
if a%i == i-1:↵
pass #prime↵
a *= i↵
```↵
↵
3. Long arithmetic↵
------------------↵
It is easy to notice that algorithm needs long arithmetic because factorial grows very fast. The one of fastest implementations of long arithmetic uses FFT (Fast Fourier Transform) for numbers (or polynomials) multiplication. FFT multiplies $a\cdot{b}$ in $O(n\log{n})$ where n is max bit-length of a and b. We will use this fact in analysis. P.S. FFT with heuristics is used in Python too.↵
↵
4. Asymptotic↵
------------------↵
Notice that at iteration $k$ $a$ length is $O(\log{k!})$ so entire complexity is ↵
$O(\sum_{k=2}^n{\log{k!}\cdot{\log{\log{k!}}})}$↵
↵
#### Statement.↵
$\sum_{k=2}^n{\log{k!}\cdot{\log{\log}k!}} = O(n^2\log^2{n})$↵
↵
#### _Proof._↵
Using <a href="https://mathworld.wolfram.com/StirlingsApproximation.html">Stirling's formula</a> for gamma function (factorial) logarithm ↵
$$\log{k!} = k\log{k} — k + O(\log{k}) = k\log{k} + O(k)$$ ↵
we get: ↵
$$\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))}}$$ ↵
Using fact $\log{(f + o(f))} = \log{f} + o(\log{f})$ (can be clearly checked according to the <a href="https://encyclopediaofmath.org/wiki/L%27Hospital_rule">L'Hospital rule</a>) we get that the sum <b>asymptotically</b> equals to: ↵
$$\sum_{k=2}^n{k\log^2{k}}$$ ↵
There is <a>Euler-Maclaurin's summation formula</a> $\sum_{k=a}^b{f(k)} = \int_a^b{f(x)dx} + O(f)$ for class functions $f$ such that $f'(x) = O(f)$ or $f'(x) = o(f)$. So we can approximate discrete sum with integral: ↵
$$\sum_{k=2}^n{k\log^2{k}} = O(\int_2^n{x\log^2{x}dx})$$ ↵
After applying integration by parts two times we get that value of this integral is $O(n^2\log^2{n})$, Q.E.D. ↵
↵
5. Conclusion↵
------------------↵
This algorithm is rather absurd but it shows some simple techniques in work with long arithmetic.
