Top
Back: factorLenstraECM
Forward: hyperel_lib
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.35 ECPP

Procedure from library crypto.lib (see crypto_lib).

Usage:
ECPP(N);

Return:
message:N is not prime or {L,P,m,q} as certificate for N being prime
L a list (y^2=x^3+L[1]*x+L[2] defines an elliptic curve C)
P a list ((P[1]:P[2]:P[3]) is a point of C)
m,q integers

Assume:
gcd(N,6)=1

Note:
The basis of the algorithm is the following theorem:
Given C, an elliptic curve over Z/N, P a point of C(Z/N), m an integer, q a prime with the following properties:
- q|m
- q>(4-th root(N) +1)^2
- m*P=0=(0:1:0)
- (m/q)*P=(x:y:z) and z a unit in Z/N
Then N is prime.

Example:
 


Top Back: factorLenstraECM Forward: hyperel_lib 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.