Primality testing and APR-CL algorithm.

There is a simple method for verify that the number is composite without it factorization. According to Fermat's little theorem, if the number $n$ is a prime then for any integer $a$, not divisible by $n$, satisfied: $$a^{n-1} \equiv 1 \pmod n$$ The first problem is that for all possible $a$ it works too long, the second and main - there is an infinite amount of numbers (Carmichael numbers) on which the test is wrong. In practice we can take many different $a$ and if condition satisfied, then most likely the number is prime.

We see that in the general case, we need a stronger condition. For example, we can use: $$a^{\frac{n-1}{2}} \equiv \left(\dfrac{a}{n}\right) \pmod n \text{ for all } a \in \mathbb{N} \text{ with } gcd(a, n) = 1$$ Its true for odd prime $n$. Another strengthening of Fermat's theorem: $$(a+b)^n \equiv a^n + b^n \pmod{nR} \text{ for all } a \text{, } b \in R$$ there $R$ any commutative ring. They work correct when the first algorithm is wrong, but we still have computational problem. And it is a problem that the APR-CL algorithm solves.

APR-CL by Cohen and Lenstra is an improvement of APR algorithm. Important idea of APR-CL is that we not only check the conditions, but also gather information about possible divisors of $n$. And finally we can say that only $n$ and $1$ divide $n$. Now I describe the common "workflow" of the algorithm.
The algorithm is divided into three stages:

Stage 1. Preparation.
We need to select integer values $s$ and $t$ with the following properties:

• $t$ is "small",
• $s > n^{1/2}$ or $s > n^{1/3}$,
• $a^{t} \equiv 1 \pmod s$ for all $a \in \mathbb{Z}$ with $gcd(a, s) = 1$,
• the factorization of t and s known. 

This part can be made once, and used for checking different numbers.
Here we also check that $gcd(n, st) = 1$; otherwise n is composite.

Stage 2. Tests.
We test number using tests similar to described above. If one of the tests failed then $n$ composite. If all test passed we can use obtained information and prove that for every divisor $r$ of $n$ there exists integer $i < t$ such that $r \equiv n^i \pmod s$.
This is the most difficult and algebraic part of algorithm. How to obtain and most importantly combine information?
First, for every prime power $p^k$ dividing $t$ select ideal of $\mathbb{Z}[\xi_{p^k}]$ (for example,  $n\mathbb{Z}[\xi_{p^k}]$).

Next, denote $$Y_q = \{\chi_{p, q} : p \text{ prime, } p|q-1\} \text{ and } Y_s = \bigcup_{\substack{q|s, q \text{ prime}}}Y_q$$ and checks that every $\chi \in Y_s$ satisfies some condition on Gauss sum $\tau (\chi)$. We can reformulate it in terms of Jacobi sums for better performance. Finally we check that every prime $p$ dividing $t$ satisfies:

for every prime divisor $r$ of $n$ there exists $l_p(r) \in \mathbb{Z}_p$ such that $r^{p-1}=(n^{p-1})^{l_p(r)}$ in the group $1 + p\mathbb{Z}_p$. 

If this is done, we can prove that for every divisor $r$ of $n$ there exists integer $i < t$ such that $r \equiv n^i \pmod s$.

Stage 3. Conclusion. 
Using obtained information we can fully factorize $n$. Practically always at this stage we see that  $n$ divisors is only $1$ and $n$.
To factor $n$ completely we only need to find all divisors $r \leq n^{1/2} < s$ of $n$. $r$ congruent to $n^i \pmod s$ for some $i < t$, so define $r_i \equiv n^i \pmod s$ and $0 \leq r_i < s$ for $0 \leq i < t$ we can check which of the $r_i$ divide $n$.

As we see our advantage to take smaller values $t$ and $s$.
In next post I will describe the implementation of algorithm proposed in "Primality Testing and Jacobi Sums" by Cohen and Lenstra.