TEN 2010    Esercizi 2
------------------------------------------------------------------------------------

1. Fare un po' di esperimenti con l'algoritmo di fattorizzazione  per tentativi. 
Fattorizzare interi N=P*Q ottenuti prima aumentando l'ordine di grandezza del fattore Q tenedo fisso il fattore piu' piccolo P e successivamente  tenendo fisso Q e aumentando l'ordine di grandezza del fattore piu' picolo P.

naif(n)=if(n<4,print("prime"),\
        if(lift(mod(n,2))==0,print("2*",n/2),\
        if(lift(mod(n,3))==0,print("3*",n/3),\
        sq=sqrt(n);e=2;d=5;\
        while(d<sq,if(lift(mod(n,d))==0,\
           dd=d;d=n,d=d+e;e=6-e));\
        if(d==n,print(dd,"*",n/dd),print("prime")\
        ))))

2. Fare un po' di esperimenti con l'algoritmo di fattorizzazione  Rho di Pollard.
Fattorizzare interi N=P*Q ottenuti prima aumentando l'ordine di grandezza del fattore Q tenedo fisso il fattore piu' piccolo P e successivamente  tenendo fisso Q e aumentando l'ordine di grandezza del fattore piu' picolo P.

pollard(n)=x=mod(random,n);y=x;d=1;\
while(d==1,\
 for(j=1,10,x=x^2+2;y=y^2+2;y=y^2+2;d=d*(y-x));\
 d=gcd(lift(d),n));\
print(d,"*",n/d)

3. FINTO Pollard:
n=p*q intero da "fattorizzare"
p = fattore piu' piccolo
il programma fa vedere le successioni X_m e Y_m=X_2m in Z_p, fino a che si verifica la coincidenza... 

pollard2(n,p)=x=mod(random,n);\
print("starting point is ", lift(x)); y=x;d=1;ii=0;\
while(d==1,\
ii=ii+1;x=x^2+2;y=y^2+2;y=y^2+2;d=d*(y-x);\
 print(lift(mod(lift(x),p)),", ",lift(mod(lift(y),p)));\
 d=gcd(lift(d),n));\
print(ii," steps: ",   ,"n=",d,"*",n/d)