Home Online Manual
Top
Back: SolowayStrassen
Forward: PollardRho
FastBack:
FastForward:
Up: crypto_lib
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

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