Fattorizzazione di un numero di 309 cifre
Ciao a tutti!
Faccio riferimento a questo post del 2012 perché ho lo stesso problema e nonostante quando detto qui non sono riuscito a capire come fare il tutto.
Leggendo la risposta che aveva dato un altro utente, ho interpretato che l'intervallo per q dovesse essere 2^512
{fattori(n)=
forprime
(q=2^512,2^512+2^31-1,if(n%q==0,print(q)));
}
ma siccome ci sono troppi primi nell'intervallo, il programma non finisce mai e ci mette troppo. Volevo quindi chiederve se qualcuno potesse darmi una mano a capire cosa non va, grazie mille!!
Faccio riferimento a questo post del 2012 perché ho lo stesso problema e nonostante quando detto qui non sono riuscito a capire come fare il tutto.
"Pop":
Ciao a tutti!
Per un esame universitario, devo decriptare un testo cifrato in RSA con il programma PARI GP. Ho a disposizione il testo cifrato e la chiave pubblica (n,e), con e=7. Per riuscire a decriptare dovrei scomporre n nel prodotto di due fattori primi, in modo da poter calcolare phi=(p-1)(q-1).... il problema è che n ha questa forma:
2696539702293473861593957786183537100426965468413459859101451217365990137082514446990627159836113040
3168017081980709003648818465322162493373927117482598906778499871631698918865298366594924730461602984
0122835237504070219470348634520466163104766870315171763613871456868724845067546604426006754355551885
367348723
ovvero un numero di 309 cifre. L'unica cosa che so di p e q è che il professore ha generato questi numeri primi nel seguente modo:
p = nextprime( 2^512 + 2^511 + random() );
q = nextprime( 2^512 + random() );
Ho fatto diversi tentativi (ad esempio con l'algoritmo p-1 di Pollard), ma non riesco a trovare una strategia vincente per fattorizzare questo numero... qualcuno mi può dare una dritta? Grazie mille
Leggendo la risposta che aveva dato un altro utente, ho interpretato che l'intervallo per q dovesse essere 2^512
{fattori(n)=
forprime
(q=2^512,2^512+2^31-1,if(n%q==0,print(q)));
}
ma siccome ci sono troppi primi nell'intervallo, il programma non finisce mai e ci mette troppo. Volevo quindi chiederve se qualcuno potesse darmi una mano a capire cosa non va, grazie mille!!
Risposte
Sia $M=512$. Allora $p=2^M+2^{M-1}+a$ e $q=2^M+b$ per certi interi relativamente piccoli $a,b$.
Il prodotto $n=pq$ e’ quindi uguale a
$n=(2^M+2^{M-1}+a)(2^M+b)=2^{2M} + 2^{2M-1} + 2^{M-1}(2a+3b) + ab$.
Prima si calcola il quoziente $(n- 2^{2M} - 2^{2M-1})$/$2^{M-1}$.
Il risultato e’ uguale alla somma dell’intero $t=2a+3b$ $\ \ $ e $\ \ $ $ab$/$2^{M-1}$.
Poiche’ $ab$/$2^{M-1}$ e’ piccolissimo, e’ possibile calcolare l’intero $t$ arrotondando.
Poi si calcola
$n-2^{2M} - 2^{2M-1} - 2^{M-1}t $.
Il risultato e’ uguale a $ab$.
A questo punto si conosce la somma $t$ di $2a$ e $3b$ e il prodotto $s=6ab$.
Per trovare $a,b$ basta quindi calcolare le radici dell’equazione $X^2-tX+s$.
Il risultato e’ $a=1000289027$ e $b=768462417$.
Il prodotto $n=pq$ e’ quindi uguale a
$n=(2^M+2^{M-1}+a)(2^M+b)=2^{2M} + 2^{2M-1} + 2^{M-1}(2a+3b) + ab$.
Prima si calcola il quoziente $(n- 2^{2M} - 2^{2M-1})$/$2^{M-1}$.
Il risultato e’ uguale alla somma dell’intero $t=2a+3b$ $\ \ $ e $\ \ $ $ab$/$2^{M-1}$.
Poiche’ $ab$/$2^{M-1}$ e’ piccolissimo, e’ possibile calcolare l’intero $t$ arrotondando.
Poi si calcola
$n-2^{2M} - 2^{2M-1} - 2^{M-1}t $.
Il risultato e’ uguale a $ab$.
A questo punto si conosce la somma $t$ di $2a$ e $3b$ e il prodotto $s=6ab$.
Per trovare $a,b$ basta quindi calcolare le radici dell’equazione $X^2-tX+s$.
Il risultato e’ $a=1000289027$ e $b=768462417$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo