Vrem să factorăm $n=900$ folosind asta $\varphi(n)=240$, și mai general factor $n$ cunoscând Euler totient $\varphi(n)$.
Lăsând deoparte diviziunea de proces, putem folosi trei tehnici
- Luând cel mai mare divizor comun al acestor două date, care dacă $n$ este divizibil cu un pătrat, iar unele cazuri rare vor dezvălui un factor de $n$, și (odată ce GCD-ul însuși este factorizat) va dezvălui toți factorii de $n$, sau lăsați a fără pătrat $n$ a factor (adică $n$ produsul primelor distincte).
- O tehnică aplicabilă $n$ produsul oricărui număr de numere prime distincte: cunoscând orice multiplu (diferit de zero). $f$ de $\lambda(n)$ (cel Funcția Carmichael), inclusiv $f=\varphi(n)$ sau $f=e\,d-1$ în RSA, permite factoring $n$ cu acest algoritm .
- O tehnică mai simplă aplicabilă $n$ produsul a două numere prime distincte $p$, $q$: noi putem gasi $\sigma=p+q=n-\varphi(n)+1$, apoi găsiți $p$ și $q$ ca cele două rădăcini ale ecuației pătratice $x^2-\sigma\,x+n=0$.
Folosind GCD
Reamintim că dacă factorizarea lui $n$ este $n=\prod\left({p_i}^{k_i}\right)$ cu numere prime distincte $p_i$, atunci $\varphi(n)=\prod\left(\left(p_i-1\right)\,{p_i}^{k_i-1}\right)$. Asa pentru toti $i$ cu $k_i>1$, ${p_i}^{k_i-1}$ desparte $n$ și $\varphi(n)$.
Acest lucru motivează calculul $g:=\gcd(n,\varphi(n))$. Dacă $g\ne1$ (care are probabilitate extrem de scăzută dacă $n$ este un modul RSA real), atunci $g$ este un factor non-trivial al $n$ și am făcut progrese: putem factor $g$ și $n/g$ separat. Mai mult, odată ce am găsit factorizarea lui $g$, putem extrage acești factori din $n$ plecând $n':=n/\prod\left({p_j}^{k_j}\right)$ a factor, și cu cunoscut $\varphi(n'):=\varphi(n)/\prod\left(\left(p_j-1\right)\,{p_j}^{k_j-1}\right)$, si acum $\gcd(n',\varphi(n'))=1$.
Dacă $g=1$, atunci $n$ este fără pătrat (adică fiecare $k_i=1$, sau echivalent $n$ este produsul numerelor prime distincte).
Aici $\gcd(900.240)=60=2^2\cdot3\cdot5$. Atrăgând acești factori $2$, $3$, $5$ din $n$, obținem factorizarea completă $900=2^2\cdot3^2\cdot5^2$ si problema este rezolvata.
Astfel, în cele ce urmează vom trece la un exemplu mai mare: factor $n=12790396087027$, știind $\varphi(n)=11797951366656$.
$\gcd(12790396087027,11797951366656)=13$, și acesta este un factor primordial al $n$. Trăgând afară $13$ și puterile, am simplificat problema în factoring $n'=n/13^2=75682817083$ știind $\varphi(n')=\varphi(n)/\big(13\,(13-1)\big)=11797951366656/\big(13\cdot 12\big)=75627893376$. Acum avem nevoie de tehnici suplimentare.
Tehnica generală pentru pătrat-free $n$
Cunoașterea oricărui multiplu (diferit de zero). $f$ de $\lambda(n')$ (funcția Carmichael) ajută la factorizarea fără pătrat $n'$, prin utilizarea algoritmului Acolo. Avem $f=75627893376=2^7\cdot590842917$ prin urmare $s=7$, $t=590842917$.
- $a:=2$, $b=a^t\bmod n'=2^{590842917}\bmod 11797951366656=17605996164$
- $c:=b^2\bmod n'=17605996164^2\bmod 11797951366656=8570506209$, prin urmare $b:=c$.
- $c:=b^2\bmod n'=8570506209^2\bmod 11797951366656=1$, succes!
- $p:=\gcd(b-1,n')=\gcd(8570506209-1,11797951366656)=4327$ care este un factor prim al $n'$, $q:=n'/p=11797951366656/4327=17490829$ care este compus și nu este un pătrat.
Rămânem cu factoring $\tilde n=17490829$ știind $\varphi(\tilde n)=\varphi(n')/(p-1)=17482176=\tilde\varphi$. Am putea folosi din nou tehnica generală de mai sus, dar putem spera și de această dată $\tilde n$ are doar doi factori primi (distinți). $p$ și $q$.
$n$ produs a doi factori primi diferiți $p$ și $q$
Noi stim $p\,q=\tilde n=17490829$ și $(p-1)(q-1)=\tilde\varphi=17482176$. Acesta este un sistem de două ecuații cu două necunoscute. Urmează $p+q=\tilde n-\tilde\varphi+1=\sigma=8654$, prin urmare $p$ și $q$ sunt soluțiile ecuației de gradul doi $x^2-\sigma\,x+\tilde n=0$, prin urmare $p=(\sigma-\sqrt{\sigma^2-4\,\tilde n})/2=(8654-\sqrt{8654^2-4\cdot17490829})/2=3217$ și $q=(\sigma+\sqrt{\sigma^2-4\,\tilde n})/2=(8654+\sqrt{8654^2-4\cdot17490829})/2=5437$. Ambii $p$ și $q$ sunt prime, astfel speranțele noastre au fost întemeiate, iar în final factorizarea dorită este $n=12790396087027=13^2\cdot3217\cdot4327\cdot5437$.
