ECM fase1& fase 2 a carte scoperte.

ecm(n,p,b1,N)=m=1;for(q=2,b1,if(isprime(q),\
t=1;while(t<b1,m=m*q;t=t*q),));\
q=nextprime(b1);mm=trunc(60*b1/ln(60*b1));\
aa=vector(mm);dmax=2;\
for(k=1,mm, q1=nextprime(q+1);dd=q1-q;q=q1;\
     if(dd>dmax,dmax=dd,);aa[k]=dd);\
print("b2= ",q1);\
bb=matrix(dmax/2,2);\
for(j=1,N,\
x=random(n);y=random(n);\
b=y^2-x^3-x;e=ellinit([0,0,0,1,b],1);\
ff=factor(p+1-ellap(e,p));\
ll=length(mattranspose(ff));\
r=ff[ll,1];\
if(r<q1,print1(j,": ",ff,","),print1(j,": ",ff[ll,1],","));\
e=e*mod(1,n);\
print1(" 1");\
p0=[mod(x,n),mod(y,n)];\
p0=ellpow(e,p0,m);\
print1(", 2");\
q=nextprime(b1);p2=ellpow(e,p0,q);\
pp=elladd(e,p0,p0);p3=pp;\
for(k=1,dmax/2,bb[k,1]=p3[1];bb[k,2]=p3[2];p3=elladd(e,p3,pp));\
q1=q;\
for(k=1,mm,kk=aa[k]/2; q1=q1+aa[k];\
p2=elladd(e,p2,[bb[kk,1],bb[kk,2]]);\
);\
print("."))

------------------------------------------------------------------------------------------------------

COSA FA:

Illustra l'algoritmo delle curve ellittiche a CARTE SCOPERTE,
perche'  noi a forniamo all'algoritmo un intero da fattorizzare, di cui conosciamo 
il fattore primo piu' piccolo.

INPUT: 
n il numero "da fattorizzare"
p fattore piu' piccolo
b1=primo bound
N=numero massimo di curve da usare

OUTPUT
- b2=secondo bound, b2 ~ 60*b1=secondo bound
- di ogni curva stampa:
  numero della  curva E;   M=il piu' grosso divisore primo di E(Z_p),  1,   2   (se fase1 & fase2 falliscono)

  la fattorizzazione completa del gruppo E(Z_p) ogni volta che  M<b2:
 
- se M < b1  (successo in fase1)
- se M sta in  [b1,b2] & tutti gli altri < b1 (successo in fase2)
- se M sta in  [b1,b2] ma NON e' UNICO o compare ad una potenza > 1 (insuccesso).

p=nextprime(10^15);\
q=nextprime(10^50);\
n=p*q;\
b1=2000;\
N=50;\
ecm(n,p,b1,N)
b2= 111341

p=nextprime(10^16);\
q=nextprime(10^50);\
n=p*q;\
b1=10000;\
N=50;\
ecm(n,p,b1,N)

b2= 563351

Mentre l'algoritmo procede con un ciclo
 
- random (E,P) curva ellittica E su Z_n e punto P in E(Z_n)
   etc…..

- calcola #E(Z_p)
- fattorizza #E(Z_p)
- individua e stampa il fattore piu' grosso  M di #E(Z_p)
 
- quando M > b2, allora #E(Z_p) non  e'  b1-smooth e nemmeno della forma 
  #E(Z_p)=m*Q, con m intero b1-smooth e Q=primo in [b1,b2].
  questo spiega perche'  sia la fase 1 che la fase 2  del ciclo falliscono.  

- quando M < b1, allora #E(Z_p) e'  b1-smooth.
  questo spiega perche' la fattorizzazione avviene nella fase 1.

- se b1 < M < b2, allora stampa la fattorizzazione completa di #E(Z_p), cosi' che possiamo vedere quanti fattori di  #E(Z_p) sono compresi nell'intervallo [b1,b2]:
 se ce ne e' uno solo, questo spiega perche'  la fattorizzazione avviene nella fase 2;
 se ce ne sono piu' di uno, sia la fase 1 che la fase 2  del ciclo falliscono.

OUTPUT
- b2=secondo bound
- di ogni curva:
  n. curva:  M=il piu' grosso divisore primo di E(Z_p),  1,   2   (se fase1 & fase2 falliscono)

  la fattorizzazione completa del gruppo E(Z_p) ogni volta che  M<b2:
 
- se M < b1  (successo in fase1)
- se M sta in  [b1,b2] & tutti gli altri < b1 (successo in fase2)
- se M sta in  [b1,b2] ma non e' UNICO  (no successo).

---------------------------------------------------------------------------------------------------------------------