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

11.Recent developments in primality testing

11.1.Recent developments in primality testing

Carl Pomerance1

(Joint work with Hendrik Lenstra.)

In August, 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, all from the Indian Institute

of Technology in Kanpur, announced a new algorithm to distinguish between prime numbers and

composite numbers. Unlike earlier methods, their test is completely rigorous, deterministic, and

runs in polynomial time. If n is prime and a is an integer, then the polynomials (x+a)n and xn+a

are congruent modulo n. Therefore they are also congruent modulo n and f(x) for any integer

polynomial f(x). The heart of the procedure for testing n involves verifying such a congruence

where a runs over a small set of integers, and f(x) is a (craftily chosen) polynomial. In the original

paper f(x) is of the form xr

−1, where r is a prime with some additional properties. We have found

a way to instead use polynomials like those that arise in the argument of Gauss for constructible

regular polygons. It is important that the degree of f(x) be large enough so that the primality test is

valid, but not so large that the running time suffers.We are able to choose the degree fairly precisely

using some tools from analytic number theory and a new result, due to Daniel Bleichenbacher and

Vsevolod Lev, from combinatorial number theory. We thus achieve a rigorous and effective running

time of about (log n)6, the heuristic complexity of the original test.

12.Comparison / Benchmarking for Primality Testing

12.1.Comparison study for Primality testing using Mathematica

Hailiza Kamarulhaili & Ega Gradini

[e-mail]

School of Mathematical Sciences, Universiti Sains Malaysia, Minden 11800 Penang, MALAYSIA

13.Deterministic Primality Testing

13.1.AKS primality test

13.2.APR - Adleman–Pomerance–Rumely primality test

Adleman–Pomerance–Rumely primality test

The Jacobi Sums algorithm

http://calistamusic.dreab.com/p-Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test

Unlike other algorithms, it avoids the use of random numbers, so it is a deterministic primality test. It is named after its discoverers, Leonard Adleman, Carl Pomerance, and Robert Rumely. The test involves arithmetic in cyclotomic fields.

It was later improved by Henri Cohen and Hendrik Willem Lenstra and called APRT-CL (or APRCL). It is often used with UBASIC under the name APRT-CLE (APRT-CL extended) and can test primality of an integer n in time:

Randomized (Probalistic) Provable Primality Testing

Deterministic Primality Testing

13.3.Atkin sieve

In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes, but does some preliminary work and then marks off multiples of primes squared, rather than multiples of primes. It was created by A. O. L. Atkin and Daniel J. Bernstein.

13.3.1.Contents 1 Algorithm 2 Pseudocode 3 Explanation 4 Computational complexity 5 See also 6 References 7 External links

13.3.2.Algorithm

In the algorithm:

• 
  All remainders are modulo-sixty remainders (divide the number by sixty and return the remainder).
  
• 
  All numbers, including x and y, are whole numbers (positive integers).
  
• 
  Flipping an entry in the sieve list means to change the marking (prime or nonprime) to the opposite marking.
  

1. 
   Create a results list, filled with 2, 3, and 5.
   
2. 
   Create a sieve list with an entry for each positive integer; all entries of this list should initially be marked nonprime.
   
3. 
   For each entry number n in the sieve list, with modulo-sixty remainder r :
   
   • 
     If r is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to 4x² + y² = n.
     
   • 
     If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x² + y² = n.
     
   • 
     If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x² − y² = n when x > y.
     
   • 
     If r is something else, ignore it completely.
     
4. 
   Start with the lowest number in the sieve list.
   
5. 
   Take the next number in the sieve list still marked prime.
   
6. 
   Include the number in the results list.
   
7. 
   Square the number and mark all multiples of that square as nonprime.
   
8. 
   Repeat steps five through eight.
   

• 
  This results in numbers with an odd number of solutions to the corresponding equation being prime, and an even number being nonprime.
  

13.3.3.Pseudocode

The following is pseudocode for a straightforward version of the algorithm:

// arbitrary search limit

limit ← 1000000
// initialize the sieve

is_prime(i) ← false, ∀ i ∈ [5, limit]

// put in candidate primes:

// integers which have an odd number of

// representations by certain quadratic forms

for (x, y) in [1, √limit] × [1, √limit]:

n ← 4x²+y²

if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5):

is_prime(n) ← ¬is_prime(n)

n ← 3x²+y²

if (n ≤ limit) and (n mod 12 = 7):

is_prime(n) ← ¬is_prime(n)

n ← 3x²-y²

if (x > y) and (n ≤ limit) and (n mod 12 = 11):

is_prime(n) ← ¬is_prime(n)

// eliminate composites by sieving

for n in [5, √limit]:

if is_prime(n):

// n is prime, omit multiples of its square; this is

// sufficient because composites which managed to get

// on the list cannot be square-free

is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit}

print 2, 3

for n in [5, limit]:

if is_prime(n): print n

This pseudocode is written for clarity. Repeated and wasteful calculations mean that it would run slower than the sieve of Eratosthenes. To improve its efficiency, faster methods must be used to find solutions to the three quadratics. At the least, separate loops could have tighter limits than [1, √limit].

13.3.4.Explanation

The algorithm completely ignores any numbers divisible by two, three, or five. All numbers with an even modulo-sixty remainder are divisible by two and not prime. All numbers with modulo-sixty remainder divisible by three are also divisible by three and not prime. All numbers with modulo-sixty remainder divisible by five are divisible by five and not prime. All these remainders are ignored.

All numbers with modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1. These numbers are prime if and only if the number of solutions to 4x² + y² = n is odd and the number is squarefree (proven as theorem 6.1 of ).

All numbers with modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime if and only if the number of solutions to 3x² + y² = n is odd and the number is squarefree (proven as theorem 6.2 of ).

All numbers with modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only if the number of solutions to 3x² − y² = n is odd and the number is squarefree (proven as theorem 6.3 of ).

None of the potential primes are divisible by 2, 3, or 5, so they can't be divisible by their squares. This is why squarefree checks don't include 2², 3², and 5².

13.3.5.Computational complexity

This sieve computes primes up to N using O(N/log log N) operations with only N^1/2 + o(1) bits of memory. That is a little better than the sieve of Eratosthenes which uses O(N) operations and O(N^1/2(log log N)/log N) bits of memory. These asymptotic computational complexities include simple optimizations, such as wheel factorization, and splitting the computation to smaller blocks.

13.3.6.See also

• 
  Sieve of Sundaram
  
• 
  Sieve theory
  

13.3.7.References

1. 
   ^ ^{a b c d e} A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030.[1]