Study started since 2011年10月17日 素性测试算法，素性测定(11Y11) primality testing

13.10.Goldwasser Kilian Algorithm

13.11.Jacobi Sums

The Jacobi Sums algorithm runs in time

§O(log log §) .

This is almost polynomial time4.

We can be more precise: Odlyzko and

Pomerance have shown that, for all large n, the

running time is in

[§Alog log §, §B log log §] ,

where A,B are positive constants. The lower

bound shows that the Jacobi Sums algorithms

is definitely not polynomial-time (in theory

anyway).

The Jacobi sums algorithm is deterministic and

practical: it has been used for numbers of at

least 3395 decimal digits (Mihailescu: 6.5 days

on a 500 Mhz Dec Alpha).

13.12.Lucas素性测定算法

http://www.peach.dreab.com/p-Lucas_primality_test

Lucas

http://calistamusic.dreab.com/p-Lucas_primality_test

In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that n is prime.

13.12.1.Contents 1 Concepts 2 Example 3 Algorithm 4 See also 5 Notes

13.12.2.Concepts

Let n be a positive integer. If there exists an integer 1 < a < n such that

and for every prime factor q of n − 1

then n is prime. If no such number a exists, then n is composite.

The reason for the correctness of this claim is as follows: if the first equality holds for a, we can deduce that a and n are coprime. If a also survives the second step, then the order of a in the group (Z/nZ)* is equal to n−1, which means that the order of that group is n−1 (because the order of every element of a group divides the order of the group), implying that n is prime. Conversely, if n is prime, then there exists a primitive root modulo n, or generator of the group (Z/nZ)*. Such a generator has order |(Z/nZ)*| = n−1 and both equalities will hold for any such primitive root.

Note that if there exists an a < n such that the first equality fails, a is called a Fermat witness for the compositeness of n.

13.12.3.Example

For example, take n = 71. Then n − 1 = 70 and the prime factors of 70 are 2, 5 and 7. We randomly select an a < n of 17. Now we compute:

For all integers a it is known that

Therefore, the multiplicative order of 17 (mod 71) is not necessarily 70 because some factor of 70 may also work above. So check 70 divided by its prime factors:

Unfortunately, we get that 17¹⁰≡1 (mod 71). So we still don't know if 71 is prime or not.

We try another random a, this time choosing a = 11. Now we compute:

Again, this does not show that the multiplicative order of 11 (mod 71) is 70 because some factor of 70 may also work. So check 70 divided by its prime factors:

So the multiplicative order of 11 (mod 71) is 70, and thus 71 is prime.

(To carry out these modular exponentiations, one could use a fast exponentiation algorithm like binary or addition-chain exponentiation).

13.12.4.Algorithm

The algorithm can be written in pseudocode as follows:

Input: n > 2, an odd integer to be tested for primality; k, a parameter that determines the accuracy of the test

Output: prime if n is prime, otherwise composite or possibly composite;

determine the prime factors of n−1.

LOOP1: repeat k times:

pick a randomly in the range [2, n − 1]

if a^n-1 1 (mod n) then return composite

otherwise

LOOP2: for all prime factors q of n−1:

if a^(n-1)/q 1 (mod n)

if we did not check this equality for all prime factors of n−1

then do next LOOP2

otherwise return prime

otherwise do next LOOP1

return possibly composite.

13.12.5.See also

• 
  Édouard Lucas
  
• 
  Fermat's little theorem