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

13.4.Bhattacharjee and Pandey

http://www.cse.iitk.ac.in/research/btp2001/primality.html

The Ultimate PrimalityTest

Conjeture

(Bhattaharjeeand Pandey [8℄)

Ifris an odd

prime whih doesnot divide

n(n¾

1), and
(x

1)n= xn

1

in (Z=nZ)[x℄=(x

Remarks

an

r

1), then nisprime.

1.

We

whi

_nd anodd prime r = O(log n)

hdoesnotdividen¾ 1 simply by

heking r=3; 5; 7; 11; : : :.(Ifrjn then we

are

_nished.)

2.

The time

forthee

test is

e

O(rlog¾ n) =O(log¿n).

3. The onjeture has been
veri_ed for

r < 100, n < 10½¼,½6and also

numbersupto 10

(heking the

for Carmihael

smallest

appliable r).For partial results and

13.5.Brillhart, Lehmer, Selfridge Test based on Lucas Test

13.6.Cyclotomic Deterministic Primality Test Cyclotomy

13.7.Demytko deterministic primality test method

If “ 1 * 1 i i i p h p    ” meets the four following

conditions, then pi+1 is sure to be a prime number.

(a) Input a positive odd prime number pi . Let it be

regarded as a seed generating prime number. We also

look for them by using Look-Up Table (LUT) or

other primality test methods.

(b) For hi<4(pi+1) Hi, hi is an even number, so we must

use all of the even numbers from 2 to hi during the

test procedures.

(c) 1 2 1mod hi pi

i p   .

(d) 1 2 1mod hi

i p   .

13.8.Elliptic curve methods

ECPP is practical and has been used to prove

primality of a number 44052638 + 26384405 of

15071 decimal digits. The total CPU time was

5.1 Ghz-years (Franke, Kleinjung, Morain, and

Wirth, July 2004).

In practice ECPP is comparable to the Jacobi

Sums algorithm, but ECPP has the advantage

of producing an easily-checked certificate of

primality. In fact, ECPP produces a certificate

of size O(§2) that can be checked in

deterministic polynomial time eO (§3).

13.9.Eratosthenes Sieve

In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer. It is one of the most efficient ways to find all of the smaller primes (below 10 million or so). The algorithm is named after Eratosthenes, an ancient Greek mathematician; although none of Eratosthenes' works have survived, the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.

Sieve of Eratosthenes: algorithm steps for primes below 120 (including optimization of terminating when square of prime exceeds upper limit)

13.9.1.Contents 1 Algorithm description 1.1 Incremental sieve 1.2 Trial division 2 Example 3 Algorithm complexity 4 Implementation 5 Arithmetic progressions 6 Euler's sieve 7 See also 8 References 9 External links

13.9.2.Algorithm description

Sift the Two's and Sift the Three's,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

“

”

Anonymous

A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. 
   Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
   
2. 
   Initially, let p equal 2, the first prime number.
   
3. 
   Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
   
4. 
   Find the first number greater than p in the list that is not marked; let p now equal this number (which is the next prime).
   
5. 
   If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.
   

When the algorithm terminates, all the numbers in the list that are not marked are prime.

As a refinement, it is sufficient to mark the numbers in step 3 starting from p², as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 5 when p² is greater than n. This does not appear in the original algorithm.

Another refinement is to initially list odd numbers only (3, 5, ..., n), and count up using an increment of 2p in step 3, thus marking only odd multiples of p greater than p itself. This refinement actually appears in the original description. This can be generalized with wheel factorization, forming the initial list only from numbers coprime with the first few primes and not just from odds, i.e. numbers coprime with 2.

13.9.2.1.Incremental sieve

An incremental formulation of the sieve generates primes indefinitely (i.e. without an upper bound) by interleaving the generation of primes with the generation of their multiples (so that primes can be found in gaps between the multiples), where the multiples of each prime p are generated directly, by counting up from the square of the prime in increments of p (or 2p for odd primes).

13.9.2.2.Trial division

Trial division can be used to produce primes by filtering out the composites found by testing each candidate number for divisibility by its preceding primes. It is often confused with the sieve of Eratosthenes, although the latter directly generates the composites instead of testing for them. Trial division has worse theoretical complexity than that of the sieve of Eratosthenes in generating ranges of primes.

When testing each candidate number, the optimal trial division algorithm uses just those prime numbers not exceeding its square root. The widely known 1975 functional code by David Turner is often presented as an example of the sieve of Eratosthenes but is actually a sub-optimal trial division algorithm.

13.9.3.Example

To find all the prime numbers less than or equal to 30, proceed as follows.

First generate a list of integers from 2 to 30:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

First number in the list is 2; cross out every 2nd number in the list after it (by counting up in increments of 2), i.e. all the multiples of 2:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Next number in the list after 2 is 3; cross out every 3-rd number in the list after it (by counting up in increments of 3), i.e. all the multiples of 3:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Next number not yet crossed out in the list after 3 is 5; cross out every 5-th number in the list after it (by counting up in increments of 5), i.e. all the multiples of 5:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every 7-th number in the list after it, but they are all already crossed out at this point, as these numbers (14, 21, 28) are also multiples of smaller primes because 7*7 is greater than 30. The numbers left not crossed out in the list at this point are all the prime numbers below 30:

2 3 5 7 11 13 17 19 23 29

13.9.4.Algorithm complexity

Time complexity in random access machine model is O(nlog log n) operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches log log n.

The bit complexity of the algorithm is O(n(log n)(log log n)) bit operations with a memory requirement of O(n).

The segmented version of the sieve of Eratosthenes, with basic optimizations, uses O(n) operations and O(n^{1 / 2}log log n / log n) bits of memory.

13.9.5.Implementation

In pseudocode:

Input: an integer n > 1

Let A be an array of bool values, indexed by integers 2 to n,

initially all set to true.

for i = 2, 3, 4, ..., while i ≤ n/2:

if A[i] is true:

for j = 2i, 3i, 4i, ..., while j ≤ n:

A[j] = false

Now all i such that A[i] is true are prime.

Large ranges may not fit entirely in memory. In these cases it is necessary to use a segmented sieve where only portions of the range are sieved at a time. For ranges so large that the sieving primes could not be held in memory, space-efficient sieves like that of Sorenson are used instead.

13.9.6.Arithmetic progressions

The sieve may be used to find primes in arithmetic progressions.

13.9.7.Euler's sieve

Euler's proof of the zeta product formula contains version of the sieve of Eratosthenes in which each composite number is eliminated exactly once. It, too, starts with a list of numbers from 2 to n in order. On each step the first element is identified as the next prime and the results of multiplying this prime with each element of the list are marked in the list for subsequent deletion. The initial element and the marked elements are then removed from the working sequence, and the process is repeated:

[2] (3) 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 ...

[3] (5) 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 ...

[4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ...

[5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ...

[...]

Here the example is shown starting from odds, after the 1st step of the algorithm. Thus on k-th step all the multiples of the k-th prime are removed from the list. If generating a bounded sequence of primes, when the next identified prime exceeds the square root of the upper limit, all the remaining numbers in the list are prime. In the example given above that is achieved on identifying 11 as next prime, giving a list of all primes less than or equal to 80.

Note that numbers that will be discarded by some step are still used while marking the multiples, e.g. for the multiples of 3 it is 3 · 3 = 9, 3 · 5 = 15, 3 · 7 = 21, 3 · 9 = 27, ..., 3 · 15 = 45, ... .

13.9.8.See also

• 
  Sieve theory
  
• 
  Sieve of Atkin
  
• 
  Sieve of Sundaram
  

13.9.9.References