|
|
D.12.3.33 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:
| | LIB "crypto.lib";
bigint N=1267985441;
ECPP(N);
==> P= [1]:
==> 780306204
==> [2]:
==> 1106324420
==> [3]:
==> 1
==> [1]:
==> [1]:
==> 67394594
==> [2]:
==> 380636642
==> [2]:
==> [1]:
==> 780306204
==> [2]:
==> 1106324420
==> [3]:
==> 1
==> [3]:
==> 1267993236
==> [4]:
==> 105666103
|
|
