Chúng tôi muốn nhân tố $n=900$ sử dụng cái đó $\varphi(n)=240$, và nói chung là yếu tố $n$ biết Euler totient $\varphi(n)$.
Bỏ phép chia thử sang một bên, chúng ta có thể sử dụng ba kỹ thuật
- Lấy ước chung lớn nhất của hai số đã cho, nếu $n$ chia hết cho bình phương và một số trường hợp hiếm hoi khác, sẽ tiết lộ một yếu tố của $n$và (một khi bản thân GCD được phân tích) sẽ tiết lộ tất cả các yếu tố của $n$, hoặc để lại một vuông miễn phí $n$ đến yếu tố (nghĩa là $n$ tích của các số nguyên tố phân biệt).
- Một kỹ thuật áp dụng cho $n$ tích của bất kỳ số nguyên tố phân biệt nào: biết bội số (khác 0) bất kỳ $f$ của $\lambda(n)$ (các chức năng carmichael), bao gồm $f=\varphi(n)$ hoặc $f=e\,d-1$ trong RSA, cho phép bao thanh toán $n$ với thuật toán này .
- Một kỹ thuật đơn giản hơn áp dụng cho $n$ tích của hai số nguyên tố phân biệt $p$, $q$: chúng tôi có thể tìm ra $\sigma=p+q=n-\varphi(n)+1$, sau đó tìm $p$ và $q$ là hai nghiệm của phương trình bậc hai $x^2-\sigma\,x+n=0$.
Sử dụng GCD
Nhớ lại rằng nếu phân tích thành thừa số của $n$ Là $n=\prod\left({p_i}^{k_i}\right)$ với các số nguyên tố phân biệt $p_i$, sau đó $\varphi(n)=\prod\left(\left(p_i-1\right)\,{p_i}^{k_i-1}\right)$. Như vậy đối với tất cả $i$ với $k_i>1$, ${p_i}^{k_i-1}$ phân chia $n$ và $\varphi(n)$.
Điều này thúc đẩy tính toán $g:=\gcd(n,\varphi(n))$. Nếu $g\ne1$ (có xác suất rất thấp nếu $n$ là một mô đun RSA thực), thì $g$ là một yếu tố không tầm thường của $n$ và chúng tôi đã đạt được tiến bộ: chúng tôi có thể tính đến $g$ và $n/g$ riêng biệt. Hơn nữa, một khi chúng ta đã tìm ra thừa số của $g$, chúng ta có thể lấy các yếu tố này từ $n$ rời đi $n':=n/\prod\left({p_j}^{k_j}\right)$ đến yếu tố, và với đã biết $\varphi(n'):=\varphi(n)/\prod\left(\left(p_j-1\right)\,{p_j}^{k_j-1}\right)$, và bây giờ $\gcd(n',\varphi(n'))=1$.
Nếu $g=1$, sau đó $n$ không vuông góc (có nghĩa là mọi $k_i=1$, hoặc tương đương $n$ là tích của các số nguyên tố phân biệt).
Đây $\gcd(900,240)=60=2^2\cdot3\cdot5$. Kéo các yếu tố này $2$, $3$, $5$ ra khỏi $n$, chúng tôi nhận được nó hoàn thành thừa số $900=2^2\cdot3^2\cdot5^2$ và vấn đề được giải quyết.
Do đó, sau đây chúng ta sẽ chuyển sang một ví dụ lớn hơn: thừa số $n=12790396087027$, biết $\varphi(n)=11797951366656$.
$\gcd(12790396087027,11797951366656)=13$, và đó là một yếu tố chính của $n$. Kéo ra $13$ và đó là quyền hạn, chúng tôi đã đơn giản hóa vấn đề thành bao thanh toán $n'=n/13^2=75682817083$ biết $\varphi(n')=\varphi(n)/\big(13\,(13-1)\big)=11797951366656/\big(13\cdot 12\big)=75627893376$. Bây giờ chúng ta cần các kỹ thuật hơn nữa.
Kỹ thuật chung cho hình vuông miễn phí $n$
Biết bội số (khác 0) bất kỳ $f$ của $\lambda(n')$ (hàm Carmichael) giúp phân tích bao thanh toán bình phương $n'$, bằng cách sử dụng thuật toán ở đó. Chúng ta có $f=75627893376=2^7\cdot590842917$ do đó $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$, do đó $b:=c$.
- $c:=b^2\bmod n'=8570506209^2\bmod 11797951366656=1$, thành công!
- $p:=\gcd(b-1,n')=\gcd(8570506209-1,11797951366656)=4327$ đó là một yếu tố chính của $n'$, $q:=n'/p=11797951366656/4327=17490829$ là hợp số và không phải là hình vuông.
Chúng tôi còn lại với bao thanh toán $\tilde n=17490829$ biết $\varphi(\tilde n)=\varphi(n')/(p-1)=17482176=\tilde\varphi$. Chúng ta có thể sử dụng lại kỹ thuật chung ở trên, nhưng chúng ta cũng có thể hy vọng lần này $\tilde n$ chỉ có hai thừa số nguyên tố (khác nhau) $p$ và $q$.
$n$ tích của hai thừa số nguyên tố phân biệt $p$ và $q$
Chúng tôi biết $p\,q=\dấu ngã n=17490829$ và $(p-1)(q-1)=\tilde\varphi=17482176$. Đó là một hệ hai phương trình với hai ẩn số. Nó theo sau $p+q=\tilde n-\tilde\varphi+1=\sigma=8654$, do đó $p$ và $q$ là nghiệm của phương trình bậc hai $x^2-\sigma\,x+\dấu ngã n=0$, do đó $p=(\sigma-\sqrt{\sigma^2-4\,\tilde n})/2=(8654-\sqrt{8654^2-4\cdot17490829})/2=3217$ và $q=(\sigma+\sqrt{\sigma^2-4\,\tilde n})/2=(8654+\sqrt{8654^2-4\cdot17490829})/2=5437$. Cả hai $p$ và $q$ là số nguyên tố, do đó hy vọng của chúng tôi đã được thành lập và cuối cùng, thừa số mong muốn là $n=12790396087027=13^2\cdot3217\cdot4327\cdot5437$.
