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

14.9.BPP algorithm

First, in all the algorithms we will assume that n is odd, not a prime

power, and not a perfect square. (These are fine to assume since we

can always begin by checking if the square-root, cube-root, etc. of n

is an integer, and if so saying "composite".)

Here's a BPP algorithm for primality testing. This one is probably the

easiest to analyze, and I think is due to Lehmer.

Repeat k times:

* Pick a in {1,...,n-1} at random.

* If gcd(a,n) != 1, then output COMPOSITE.

[this is actually unnecessary but conceptually helps]

* If a^{(n-1)/2} is not congruent to +1 or -1 (mod n),

then output COMPOSITE.

Now, if we ever got a "-1" above output "PROBABLY PRIME" else output

"PROBABLY COMPOSITE".

Theorem: this procedure has error probability at most 1/2^k.
Proof: if n is really prime, then in each iteration we get

a^{(n-1)/2} = -1 (mod n) with probability 1/2, so we get a -1 at least

once with probability 1 - 1/2^k. If n is composite, the proof of

success will follow from the lemma below with t = (n-1)/2.

Key Lemma: Let n be an odd composite, not a prime power, and let t <

n. If there exists a in Z_n^* such that a^t = -1 (mod n), then at

most half of the x's in Z_n^* have x^t = {-1,+1} (mod n). In fact, we

can weaken the condition to simply that there exists a in Z_n^* such

that a^t is not congruent to +1 (mod n).
Proof: Let S = {x in Z_n^* : x^t = +1 or -1 (mod n)}. S is a subgroup

of Z_n^* since it's closed under multiplication (xy)^t = (x^t)(y^t)

and inverse (x^{-1})^t = (x^t)^{-1}. So we just need to find some b

in Z_n^* not in S. (So, the "weakened condition" is equivalent to the

stronger condition because if a^t is not congruent to -1 (mod n), then

we're done.) Let n = q * r, where q and r are relatively prime

and greater than 1. Let b = (a,1), where we're using CRT notation:

b = a (mod q) and b = 1 (mod r). Note that b^t = (a^t, 1^t) = (-1,1).

Therefore, b is not in S since 1 = (1,1) and -1 = (-1, -1). QED.

========================================================================

An aside: it's clear that primality is in co-NP: if a number is

composite, there is a short witness: namely, a factor. Is primality

in NP? Yes. Here's an idea due to Pratt:
The certificate that n is prime will be a generator g of Z_n^*, a

prime factorization of n-1, and then (recursively) a proof

that each of those prime factors is really prime.
The idea is that if n is prime, then g^{n-1} = 1 (mod n) and g^t is

not congruent to 1 (mod n) for any 0 < t < n-1. On the other hand, if

n is composite, then phi(n) < n-1 so this cannot be the case. So, to

verify that n is prime, we just verify that g^{n-1} = 1 (mod n) and

then verify that g^{(n-1)/p} is not congruent to 1 for any prime

factor p of n, and then recursively verify that each of these factors

is prime (and, of course, verify that the prime factorization really

is a factorization of n). We can see that this certificate is not too

large since if you draw out the recursive "tree", the width is at most

log(n) (since the product of all primes on any given level is at most n)

and the depth is at most log(n) since the primes are dropping by at

least a factor or 2. QED.

14.10.Baillie and Wagstaff Method

14.11.Chen--Kao and Lewin--Vadhan tests

[Chen and Kao 1997;

Lewin and Vadhan 1998].

14.12.Chinese Primality Test

14.13.Chinese Remaindering

Primality and Identity Testing via Chinese Remaindering.

[DBLP_Link] [Online_Version] CitedBy 72

Authors:

http://arnetminer.org/pictures/thumb/489/1225201608105.jpeg

Manindra Agrawal social network

Professor

Department of Computer Science and Engineering Indian Institute of Technology Kanpur

http://arnetminer.org/images/no_photo.jpg

Somenath Biswas social network

Professor

Computer Science and Engineering Indian Institute of Technology, Kanpur

Abstract:
We give a simple and new randomized primality testing algorithm by reducing primality testing for number n to testing if a specific univariate identity over Zn holds.We also give new randomized algorithms for testing if a multivariate polynomial, over a finite field or over rationals, is identically zero. The first of these algorithms also works over Zn for any n. The running time of the algorithms is polynomial in the size of arithmetic circuit representing the input polynomial and the error parameter. These algorithms use fewer random bits and work for a larger class of polynomials than all the previously known methods, for example, the Schwartz--Zippel test [Schwartz 1980; Zippel 1979], Chen--Kao and Lewin--Vadhan tests [Chen and Kao 1997; Lewin and Vadhan 1998].

14.14.Cohen-Lenstra Method

14.15.Colin Plumb primality test (Euler Criterion)

14.16.Combination Algorithm

Recall that ECPP produces a certificate of

primality. Thus, using a combination of

Rabin-Miller and ECPP, we can get a

randomized algorithm that produces a

certificate to prove that its result (whether

“prime” or “composite”) is correct.

All we have to do is run the Rabin-Miller and

ECPP algorithms in “parallel” until one of

them produces a certificate7. The expected

running time is believed to be eO (§4), although

we can’t prove this.

To be guaranteed an expected polynomial

runtime, add a parallel thread for the

Adelman-Huang algorithm.

14.17.Cyclotomic Probabilistic Primality Test

14.18.ECPP Elliptic Curve Primality Proving

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

http://calistamusic.dreab.com/p-Elliptic_curve_primality_proving
Elliptic Curve Primality Proving (ECPP) is a method based on elliptic curves to prove the primality of a number (see Elliptic curve primality testing). It is a general-purpose algorithm, meaning it does not depend on the number being of a special form. ECPP is currently in practice the fastest known algorithm for testing the primality of general numbers, but the worst-case execution time is not known. ECPP heuristically runs in time:

for some . This exponent may be decreased to 4+\epsilon for some versions by heuristic arguments. ECPP works the same way as most other primality tests do, finding a group and showing its size is such that p is prime. For ECPP the group is an elliptic curve over a finite set of quadratic forms such that p − 1 is trivial to factor over the group.
ECPP generates an Atkin-Goldwasser-Kilian-Morain certificate of primality by recursion and then attempts to verify the certificate. The step that takes the most CPU time is the certificate generation, because factoring over a class field must be performed. The certificate can be verified quickly, allowing a check of operation to take very little time.
In 2006 the largest prime that has been proved with ECPP is the 20,562-digit Mills' prime:
(((((((((2³ + 3)3 + 30)³ + 6)³ + 80)³ + 12)³ + 450)³ + 894)³ + 3636)³ + 70756)³ + 97220.
The distributed computation with software by François Morain started in September 2005 and ended in June 2006. The cumulated time corresponds to one AMD Opteron 250 processor at 2.39 GHz for 2219 days (near 6 years).
As of 2011 the largest prime that has been proved with ECPP is the 26,643-digits LR prime. The distributed computation with software by François Morain started in January 2011 and ended in April 2011. The cumulated time corresponds to one processor for 2255 days (more than 6 years).