TEN 2010    Esercizi 3
------------------------------------------------------------------------------------

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^2*107
%25 = 562140727723552623282
(23:31) gp > for(k=1,100,p=1+k*bb;if(isprime(p),print(p),))
p1=4497125821788420986257
p2=6183548004959078856103
p3=14053518193088815582051
p4=16864221831706578698461
p5=28107036386177631164101
p6=29793458569348289033947
p7=38787710212925131006459
p8=46657680401054867732407
 
(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=4497125821788420986257;\
p2=6183548004959078856103;\
p3=14053518193088815582051;\
p4=16864221831706578698461;\
p5=28107036386177631164101;\
p6=29793458569348289033947;\
p7=38787710212925131006459;\
p8=46657680401054867732407;\
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.