Teoria Elementare dei Numeri.   Esercizi 4.  Esercizi con PARI-GP 

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' piccolo 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' piccolo 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. POLLARD-RO con stampa delle successioni & FINTO POLLARD-RO:
prendere n da fattorizzare della forma  n=p*q, con p e q primi; 
p = fattore piu' piccolo (p molto piu' piccolo di q).

Il programma stampa i termini delle successioni x_i  e  y_i  e calcola  gcd(x_i-y_i,n). Si ferma quando gcd(x_i-y_i,n)>1, 
cioe' ha determinato un fattore di n. Con molta probabilita' tale fattore e' il divisore primo piu' piccolo di n, cioe' p.

pollard1(n)=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; print(lift(x),"  ", lift(y) ); xy= (y-x); d=gcd(lift(xy),n) );\    
   print(ii," steps: ",d,"*",n/d)

Una volta trovato p, inserire n e p nel programma qui sotto.
il programma fa vedere le successioni x_i  e  y_i  in Z_p, fino a che si verifica una 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)

 1) Il seguente programma in PARI/GP  stampa tutti i numeri B-smooth, con B=3000,
nell'intervallo [n-A,n+A], dove  n=10^15 ed A=1000.

for(k=-1000,1000 ,n=10^15+k;aa=factor(n);\
if(aa[length(mattranspose(aa)),1]<3000,\
print(n,": ",aa),))

(1.a) Confrontare il numero di interi B-smooth cosi' trovati, con il numero di interi B-smooth stimati mediante la funzione di Dickman.

(1.b) Ripetere l'esperimento con altri parametri.

(1.c) Il seguente programma in PARI/GP  stampa tutti i numeri  primi nell'intervallo [n-A,n+A], dove  n=10^15 ed A=1000.

for(k=-1000,1000,n=10^15+k; \
if(isprime(n),\
print(n ) ) )

Confrontare il numero di primi e di interi B-smooth  trovati (per vari valori di B).

2) CREARE NUMERI   primi   p  con   p-1   B-SMOOTH

 bb=13*2*9*49*29*31*41*101*103*127*97*107
%25 = 562140727723552623282
(23:31) gp > for(k=1,100,p=1+k*bb;if(isprime(p),print(p),))
p1=133291100388058869439
p2=191243752730693160499
p3=347715914055805746361
p4=365101709758596033679
p5=388282770695649750103
p6=405668566398440037421
p7=417259096866966895633
p8=504188075380918332223
 
(2.a)  Verificare che p1, …,p8 sono primi e che  p1-1,….p8-1 sono B-smooth, per B=130.

CREARE UN  NUMERO DA FATTORIZZARE

p1=133291100388058869439;\
p2=191243752730693160499;\
p3=347715914055805746361;\
p4=365101709758596033679;\
p5=388282770695649750103;\
p6=405668566398440037421;\
p7=417259096866966895633;\
p8=504188075380918332223;\
q=nextprime(10^100+6452735691278345612987651287364591287356492178365491287356491827356491872654981725364981723549187263549127635491267354912763549);\
n=p1*p2*p3*q;\
m=p1*q;\
l=p1*p2*q 

(2.b)  Il seguente programma in PARI/GP esegue l'algoritmo (p-1) di Pollard, dove n e' l'intero da fattorizzare e B e' l'ordine di B-smoothness fissato.
(qui come esponente B-smooth abbiamo preso per semplicita' k=B!, anche se non e' la scelta migliore)

pmeno(n,B)=
d=gcd(lift(mod(random,n)^(B!)-1),n);\
print(d,"*",n/d) 
 
provare con
n=p1*p2*p3*q,   m=p1*q,  l=p1*p2*q    e  B=100, 120, 130, …., 200.
verificare che l'algoritmo generalmente non separa i fattori primi p, con p-1 B-smooth, ma  gcd(a^k-1,n)  coincide col loro prodotto.