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

13.14.Lucas–Lehmer–Riesel

http://calistamusic.dreab.com/p-Lucas%E2%80%93Lehmer%E2%80%93Riesel_test

In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form N = k2ⁿ − 1, with 2ⁿ > k. The test was developed by Hans Riesel and it is based on the Lucas–Lehmer primality test. It is the fastest deterministic algorithm known for numbers of that form. The Brillhart–Lehmer–Selfridge test is the fastest deterministic algorithm for numbers of the form N = k2ⁿ + 1

13.14.1.Contents 1 The algorithm 2 Finding the starting value 3 How does the test work? 4 LLR software 5 References 6 External links

13.14.2.The algorithm

The algorithm is very similar to the Lucas–Lehmer test, but with a variable starting point depending on the value of k.

Define a sequence {u_i} for all i > 0 by:

Then N is prime if and only if it divides u_n−2.

13.14.3.Finding the starting value

• 
  If k = 1: if n is odd, then we can take u₀ = 4. If n = 3 mod 4, then we can take u₀ = 3. Note that if n is prime, these are Mersenne numbers.
  
• 
  If k = 3: if n = 0 or 3 mod 4 then u₀ = 5778.
  
• 
  If k = 1 or 5 mod 6 and 3 does not divide N, then we take .
  
• 
  Otherwise, we are in the case where k is a multiple of 3, and it is more difficult to select the right value of u₀
  

13.14.4.How does the test work?

The Lucas–Lehmer–Riesel test is a particular case of group-order primality testing; we demonstrate that some number is prime by showing that some group has the order that it would have were that number prime, and we do this by finding an element of that group of precisely the right order.

For Lucas-style tests on a number N, we work in the multiplicative group of a quadratic extension of the integers modulo N; if N is prime, the order of this multiplicative group is N² − 1, it has a subgroup of order N + 1, and we try to find a generator for that subgroup.

We start off by trying to find a non-iterative expression for the u_i. Following the model of the Lucas–Lehmer test, put , and by induction we have .

So we can consider ourselves as looking at the 2ⁱth term of the sequence v(i) = aⁱ + a ^{− i}. If a satisfies a quadratic equation, this is a Lucas sequence, and has an expression of the form v(i) = αv(i − 1) + βv(i − 2). Really, we're looking at the th term of a different sequence, but since decimations (take every kth term starting with the zeroth) of a Lucas sequence are themselves Lucas sequences, we can deal with the factor k by picking a different starting point.

13.14.5.LLR software

LLR is a program that can run the LLR tests. The program was developed by Jean Penné. Vincent Penné has modified the program so that it can obtain tests via the Internet. The software is both used by individual prime searchers and some distributed computing projects including Riesel Sieve and PrimeGrid.

13.14.6.References

• 
  Riesel, Hans (1969). "Lucasian Criteria for the Primality of N = h·2ⁿ − 1". Mathematics of Computation (American Mathematical Society) 23 (108): 869–875. doi:10.2307/2004975. JSTOR 2004975.
  

13.14.7.External links

• 
  Download Jean Penné's LLR
  

13.14.8.推广的Lucas型素性测定算法

13.14.9.Massey–Omura–Kryptosystem

Beispielsweise benötigt das Massey–Omura–Kryptosystem Primzahlen mit 2000 Bitstellen (Stand 2004), um endliche Körper zu konstruieren.

13.15.Miller-Primzahltest

Extended Riemann Hyperthesis

erweiterte Riemannsche Vermutung

erweiterte Riemann-Hypothese

13.16.Pocklington Lehmer primality test

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

http://www.peach.dreab.com/p-Pocklington_primality_test
In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer to decide whether a given number N is prime. The output of the test is a proof that the number is prime or that primality could not be established.

Pocklington primality test (deterministic)

Relies on (partial) factorization of p-1 to generate

recursive list of successive p

(uses Fermat's little theorem)

(isn't always able to work)

13.16.1.Contents 1 Pocklington criterion 1.1 Proof of this theorem 2 Generalized Pocklington method 3 The test 4 Example 5 References 6 External links

13.16.2.Pocklington criterion

The test relies on the Pocklington Theorem (Pocklington criterion) which is formulated as follows:

Let N > 1 be an integer, and suppose there exist numbers a and q such that

(1) q is prime, and

(2)

(3) gcd(a^{(N − 1) / q} − 1,N) = 1

Then N is prime.

13.16.2.1.Proof of this theorem

Suppose N is not prime. This means there must be a prime p, where that divides N.

Therefore, q > p − 1 which implies gcd(q,p − 1) = 1.

Thus there must exist an integer u with the property that

This implies by (1) and (2), and this contradicts (3)

The test is simple once the theorem above is established. Given N, seek to find suitable a and q. If they can be obtained, then N is prime. Moreover, a and q are the certificate of primality. They can be quickly verified to satisfy the conditions of the theorem, confirming N as prime.

A problem which arises is the ability to find a suitable q, that must satisfy (1)–(3) and be provably prime. It is even quite possible that such a q does not exist. This is a large probability, indeed only 57.8% of the odd primes, N, have such a q. To find a is not nearly so difficult. If N is prime, and a suitable q is found, each choice of a where will satisfy , and so will satisfy (2) as long as ord(a) does not divide (N − 1) / q. Thus a randomly chosen a is likely to work. If a is a generator mod N its order is N-1 and so the method is guaranteed to work for this choice.

13.16.3.Generalized Pocklington method

A generalized version of Pocklington's theorem covers more primes N.

Corollary:

Let N − 1 factor as N − 1 = AB, where A and B are relatively prime, and the factorization of A is known.

If for every prime factor p of A there exists an integer a_p so that

and then N is prime. The reverse implication also holds: If N is prime then every prime factor of A can be written in the above manner.

Proof of Corollary: Let p be a prime dividing A and let p^e be the maximum power of p dividing A. Let v be a prime factor of N. For the a_p from the corollary set . This means and because of also .

This means that the order of b(mod v) is p^e

Thus, . The same observation holds for each prime power factor p^e of A, which implies .

Specifically, this means

If N were composite, it would necessarily have a prime factor which is less than or equal to . It has been shown that there is no such factor, which implies that N is prime.

To see the converse choose a_p a generator of the integers modulo p.

13.16.4.The test

The Pocklington–Lehmer primality test follows directly from this corollary. We must first partially factor N − 1 into A and B. Then we must find an a_p for every prime factor p of A, which fulfills the conditions of the corollary. If such a_p's can be found, the Corollary implies that N is prime.

According to Koblitz, a_p = 2 often works.

13.16.5.Example

N = 11351

Choose , which means B = 2

Now it is clear that gcd(A,B) = 1 and .

Next find an a_p for each prime factor p of A. E.g. choose a₅ = 2.

.

So a₅ = 2 satisfies the necessary conditions. Choose a₂₂₇ = 7.

and

So both a_p's work and thus N is prime.

We have chosen a small prime for calculation purposes but in practice when we start factoring A we will get factors that themselves must be checked for primality. It is not a proof of primality until we know our factors of A are prime as well. If we get a factor of A where primality is not certain, the test must be performed on this factor as well. This gives rise to a so-called down-run procedure, where the primality of a number is evaluated via the primality of a series of smaller numbers.

In our case, we can say with certainty that 2, 5, and 227 are prime, and thus we have proved our result. The certificate in our case is the list of a_p's, which can quickly be checked in the corollary.

If our example had given rise to a down-run sequence, the certificate would be more complicated. It would first consist of our initial round of a_p's which correspond to the 'prime' factors of A; Next, for the factor(s) of A of which primality was uncertain, we would have more a_p's, and so on for factors of these factors until we reach factors of which primality is certain. This can continue for many layers if the initial prime is large, but the important thing to note, is that a simple certificate can be produced, containing at each level the prime to be tested, and the corresponding a_p's, which can easily be verified. If at any level we cannot find a_p's then we cannot say that N is prime.

The biggest difficulty with this test is the necessity of discovering prime factors of N - 1, in essence, factoring N − 1. In practice this could be extremely difficult. Finding a_p's is a less difficult problem.