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

13.17.Proth deterministic primality test method

For N  k *2n 1 with k odd and 2n  k , if there

exists an integer  such that

1

( )

2 1mod

N

 N



  ,

then N is prime.

The difference between probabilistic primality test

methods and deterministic primality test methods is that

the result of the later methods can be precisely accurate.

Namely, we are sure the number we calculate is a prime

number.

13.18.Sundaram sieve

In mathematics, the sieve of Sundaram is a simple deterministic algorithm for finding all prime numbers up to a specified integer. It was discovered in 1934 by S. P. Sundaram, an Indian student from Sathyamangalam.

13.18.1.Contents 1 Algorithm 2 Correctness 3 Computational complexity 4 See also 5 References

13.18.2.Algorithm

Start with a list of the integers from 1 to n. From this list, remove all numbers of the form i + j + 2ij where:

• 
  
  
• 
  
  

The remaining numbers are doubled and incremented by one, giving a list of the odd prime numbers (i.e., all primes except 2) below 2n + 2.

The sieve of Sundaram sieves out the composite numbers just as sieve of Eratosthenes does, but even numbers are not considered; the work of "crossing out" the multiples of 2 is done by the final double-and-increment step. Whenever Eratosthenes' method would cross out k different multiples of a prime 2i+1, Sundaram's method crosses out i + j(2i+1) for .

13.18.3.Correctness

The final list of doubled-and-incremented integers contains only odd integers; we must show that the set of odd integers excluded from the list is exactly the set of composite odd integers.

An odd integer is excluded from the final list if and only if it is of the form 2(i + j + 2ij) + 1, and we have

2(i + j + 2ij) + 1

= 2i + 2j + 4ij + 1

= (2i + 1)(2j + 1).

So, an odd integer is excluded from the final list if and only if it has a factorization of the form (2i + 1)(2j + 1) — which is to say, if it has a non-trivial odd factor. Since every odd composite number has a non-trivial odd factor, we may safely say that an odd integer is excluded from the final list if and only if it is composite. Therefore the list must be composed of exactly the set of odd prime numbers less than or equal to n.

13.18.4.Computational complexity

The sieve of Sundaram finds the primes less than n in Θ(n log n) operations using Θ(n) bits of memory.

13.18.5.See also

• 
  Sieve of Eratosthenes
  
• 
  Sieve of Atkin
  
• 
  Sieve theory
  

13.18.6.References

13.19.Trial division

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

13.20.Ward’s primality test

Lucas sequence Un

Sylvester cyclotomic number Qn

13.21.Wilson's Primality Test威尔逊判别法

n是素数的充要条件是

这里 是指 a-b 被p整除。

不过该算法的运算量为O(nlogn^2),计算量太大。

14.Randomized /Probabilistic/ Probable / Provable / Primality Testing

14.1.Adelman-Huang algorithm

Adelman-Huang

There is a complicated algorithm5, due to

Adleman and Huang (1992), that gives a

certificate of primality in expected polynomial

time. Thus

PRIMES ∈ RP.

It follows from Adelman-Huang and

Rabin-Miller that

PRIMES ∈ RP ∩ co-RP = ZPP.

Recall that ZPP is very close to P. The

difference is that for ZPP the expected running

time is polynomial in §, but for P the

worst-case running time is polynomial in §.

In practice no one uses the Adelman-Huang

algorithm because ECPP is much faster.

Adelman-Huang is of theoretical interest

because we can prove that its expected running

time is polynomial in §.

14.2.Agrawal-Biswas algorithm or Agarwal-Biswas Probabilistic Testing

14.3.AKS parallel sorting algorithm of Ajtai, Koml´os and Szemer´edi

14.4.ALI primality test

14.5.APR Test

14.6.APRT-CL (or APRCL)

14.7.素性测试的ARCL算法

１９８０年数学家Adleman, Rumely, Cohen和Lenstra研究出一种非常复杂、具有高度技巧的素数判别方法，检验一个２０位数的素性只需１０秒，对一个５０位数，只要１５秒，而一个１００位数只用４０秒。如果用试除法，判别一个５０位数的素性要一百亿年！

14.8.Baillie–PSW

http://calistamusic.dreab.com/p-Baillie%E2%80%93PSW_primality_test

The Baillie–PSW primality test is a probabilistic primality testing heuristic algorithm: it determines if a number is composite or a probable prime. The authors of the test offered $30 for the discovery of a composite number that passed this test. As of 1994, the value was raised to $620 and no pseudoprime was found up to 10¹⁷, consequently this can be considered a sound primality test on numbers below that upper bound.

A primality testing software PRIMO uses this algorithm to check for probable primes, and no certification of this test has yet failed. The author, Marcel Martin, estimates by those results that the test is accurate for numbers below 10000 digits. There is a heuristic argument (Pomerance 1984) suggesting that there may be infinitely many counterexamples.
The test

Optionally, perform trial division to check if the number isn't a multiple of a small prime number.

Perform a base 2 strong pseudoprimality test. If it fails; n is composite.

Find the first a in the sequence 5, −7, 9, −11, ... for which the Jacobi symbol

Perform a Lucas pseudoprimality test with discriminant a on n. If this test does not fail, n is likely a prime.