2.3.4. Lucas prime number test

The Lucas prime number test is based on the following 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.

For a faster calculation the "kleine Satz von Fermat" is useful:

Be p a prime number. For all 0<a<p applies: a^p-1 mod p = 1.

This means, that we can cancel the calculation with result "p is not prime", when we find a r that does not meet condition 1).

Lucas algorithm:

for r=2 to p-1
    if r^p-1 mod p = 1 then
        Calculate all prime factors Q of p-1
        for (all q in Q) do
            if r^(p-1)/q mod p=1 then
                next r
            else
                next q
            end
        end
        write "p is prime"
        goto ENDE
    else
        write "p is not prime"
        goto ENDE
    end
end
ENDE:

Applet Lucas prime number test:
The applet first computes alle r, which meet condition 1) and shows them in the left list. After that the user can select one r value from the list and the applet then displays the results for condition 2) and all prime factors q of p-1 in the right list.

Source code:
Lucas.java – GUI
Prime.java – Prime number functions

2.3.5 Pratt prime test