|
|
D.12.2.20 PocklingtonLehmer
Procedure from library crypto.lib (see crypto_lib).
- Usage:
- PocklingtonLehmer(N); optional: PocklingtonLehmer(N,L);
L a list of the first k primes
- Return:
- message N is not prime or {A,{p},{a_p}} as certificate for N being prime
- Note:
- assumes that it is possible to factorize N-1=A*B such that gcd(A,B)=1,
the factorization of A is completely known and A^2>N .
N is prime if and only if for each prime factor p of A we can find
a_p such that a_p^(N-1)=1 mod N and gcd(a_p^((N-1)/p)-1,N)=1
Example:
| | LIB "crypto.lib";
bigint N=105554676553297;
PocklingtonLehmer(N);
==> [1]:
==> 6442503168
==> [2]:
==> [1]:
==> [1]:
==> 2
==> [2]:
==> 2
==> [2]:
==> [1]:
==> 3
==> [2]:
==> 2
==> [3]:
==> [1]:
==> 2097169
==> [2]:
==> 2
list L=primList(1000);
PocklingtonLehmer(N,L);
==> [1]:
==> 3221246976
==> [2]:
==> [1]:
==> [1]:
==> 2
==> [2]:
==> 2
==> [2]:
==> [1]:
==> 3
==> [2]:
==> 2
==> [3]:
==> [1]:
==> 1048583
==> [2]:
==> 2
|
|
