Fool's algorithm for finding prime numbers

Revision en3, by alexvim, 2024-04-01 12:37:46

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.

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 Stirling's formula 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 L'Hospital rule) we get that the sum asymptotically equals to:

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

There is Euler-Maclaurin's summation formula $$$\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.

Tags math, prime numbers, asymptotics, humour

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)