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

D.12.3.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:
 


Top Back: SolowayStrassen Forward: PollardRho FastBack: atkins_lib FastForward: hyperel_lib Up: crypto_lib Top: Singular Manual Contents: Table of Contents Index: Index About: About this document
            User manual for Singular version 3-1-6, Dec 2012, generated by texi2html.