2.3.5 Pratt prime number test

The Pratt prime number test is very similar to the Lucas prime number test. Both are based on the same theorem:

A number p>1 is prime, exactly when: There is a number r with 1<r<p and
1) r^p-1 mod p = 1
2) for all prime factors q of p-1 applies: r^(p-1)/q mod p � 1.

A witness for p beeing prime is build as follows: Z(p) = (r;q₁; q₂; ...; q_n).

To check if all q_i are really prime, the formula is used recursively.

Z(2) = (1)

Z(p) = (r), if p-1 is prime

Z(p) = (r; q₁, Z(q₁); q₂, Z(q₂); ...; q_n, Z(q_n)), else.

The result is this sequence (r, q₁, Z(q₁₁, Z(q₁₁),...), ..., q_n, Z(q_n1, Z(q_n1), ...). For all elements the conditions of the above theorem have to be tested.

The Pratt algorithm guesses this sequence no deterministicly.

Example:

For p=31 the algorithm guesses: Z(31) = (3; 2, (1), 3, (2; 2, (1)), 5, (2; 2, (1), 2, (1))

or in a diffrent view:

Then it verifies:

Applet Pratt prime number test:

Source code:
Pratt.java � GUI
Prime.java � prime number functions

2.4.1 AKS Test