COSA FA IL PROGRAMMA  ECM fase 1

dato n=p*q
dato B
calcola K=B!
P=[x,y]  random
E curva ellittica che contiene P 

riduce la curva modulo p
calcola  e  fattorizza la sua cardinalita’ 
si puo’ vedere se e’ o meno B-smooth

riduce la curva modulo q
calcola  e  fattorizza la sua cardinalita’ 
si puo’ vedere se e’ o meno B-smooth

calcola il multiplo del punto K*P
ripetere fino a che non compare un inverso impossibile modulo n

controllare  che in caso di insuccesso:  
nessuna  delle  due curve ha ordine B-smooth 
(piu’ raramente puo’ succedere una delle curve abbia ordine B-smooth, ma 
alcuni fattori hanno esponenti piu’ grossi che in K)

controllare  che in caso di  successo almeno una   delle 
due curve ha ordine B-smooth 

==================================
ESEMPIO 1
==================================

n=1386493
B=20
K=2^4*3^2*5*7*11*13*17*19 
x=random(n);
y=random(n); 
b=y^2-x^3-x;
E=ellinit([0,0,0,1,b],n);
P=[x,y]

lift(ellpow(E,P,K))

p=1069
F=ellinit([0,0,0,1,b],p);
N=ellcard(F)
factor(N)

q=1297
G=ellinit([0,0,0,1,b],q);
M=ellcard(G)
factor(M)

==================================
ESEMPIO 2
==================================

n=28102844557
B=100
K=2^6*3^4*5^2*7^2*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97*101 
x=random(n);
y=random(n); 
b=y^2-x^3-x;
E=ellinit([0,0,0,1,b],n);
P=[x,y]
l 
lift(ellpow(E,P,K))

p=117763
F=ellinit([0,0,0,1,b],p);
N=ellcard(F)
factor(N)

q=238639
G=ellinit([0,0,0,1,b],q);
M=ellcard(G)
factor(M)

==================================
ESEMPIO 3
==================================
 
n=152415790054619754516987877943601900802097
B=100
K=2^6*3^4*5^2*7^2*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97*101
x=random(n);
y=random(n); 
b=y^2-x^3-x;
E=ellinit([0,0,0,1,b],n);
P=[x,y]
l 
lift(ellpow(E,P,K))

p=123456791
F=ellinit([0,0,0,1,b],p);
N=ellcard(F)
factor(N)

q=1234567890676987987780987098098167
G=ellinit([0,0,0,1,b],q);
M=ellcard(G)
factor(M)

---------------------------------------------------------------------------------------------
p=2,3,5,7,11,13,17,19,23,29,31,37,41, 43,47, 53, 59,61,67, 71, 73,79,83, 89,97,101.

B=10
K=2^3*3^2*5*7

B=20
K=2^4*3^2*5*7*11*13*17*19 

B=50
K=2^5*3^3*5^2*7^2*11*13*17*19*23*29*31*37*41*43*47

B=100
K=2^6*3^4*5^2*7^2*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97*101 

n=26167=137*191
n=1386493=1069*1297
n=28102844557=117763*238639
n=152415790054619754516987877943601900802097=123456791* 1234567890676987987780987098098167