Мы хотим учитывать $n=900$ используя это $\varphi(n)=240$, и в более общем плане фактор $n$ зная Эйлер тотиент $\varphi(n)$.
Оставляя в стороне пробное деление, мы можем использовать три техники
- Взяв наибольший общий делитель этих двух данных, что, если $n$ делится на квадрат, а в некоторых других редких случаях выявляется множитель $n$, и (после факторизации самого НОД) выявит все факторы $n$, или оставить без квадратов $n$ учитывать (т. $n$ произведение различных простых чисел).
- Техника, применимая к $n$ произведение любого количества различных простых чисел: зная любое (ненулевое) кратное $ф$ из $\лямбда(п)$ ( Функция Кармайкла), в том числе $f=\varphi(n)$ или же $f=e\,d-1$ в ЮАР позволяет факторинг $n$ с этот алгоритм .
- Более простая техника применима к $n$ произведение двух различных простых чисел $р$, $q$: мы можем найти $\sigma=p+q=n-\varphi(n)+1$, затем найдите $р$ и $q$ как два корня квадратного уравнения $x^2-\sigma\,x+n=0$.
Использование НОД
Напомним, что если факторизация $n$ является $n=\prod\left({p_i}^{k_i}\right)$ с различными простыми числами $p_i$, тогда $\varphi(n)=\prod\left(\left(p_i-1\right)\,{p_i}^{k_i-1}\right)$. Таким образом, для всех $я$ с $k_i>1$, ${p_i}^{k_i-1}$ делит $n$ и $\varphi(n)$.
Это мотивирует вычисление $g:=\gcd(n,\varphi(n))$. Если $g\ne1$ (что имеет крайне малую вероятность, если $n$ является фактическим модулем RSA), то $г$ является нетривиальным фактором $n$ и мы добились прогресса: мы можем учитывать $г$ и $n/g$ в отдельности. Далее, как только мы нашли факторизацию $г$, мы можем извлечь эти факторы из $n$ уход $n':=n/\prod\left({p_j}^{k_j}\right)$ на фактор, и с известным $\varphi(n'):=\varphi(n)/\prod\left(\left(p_j-1\right)\,{p_j}^{k_j-1}\right)$, и сейчас $\gcd(n',\varphi(n'))=1$.
Если $г=1$, тогда $n$ бесквадратный (то есть каждый $k_i=1$или эквивалентно $n$ является произведением различных простых чисел).
Здесь $\gcd(900 240)=60=2^2\cdot3\cdot5$. Вытягивание этих факторов $2$, $3$, $5$ снаружи $n$, мы получаем его полную факторизацию $900=2^2\cdot3^2\cdot5^2$ и проблема решена.
Таким образом, далее мы перейдем к более крупному примеру: фактор $n=12790396087027$, зная $\varphi(n)=11797951366656$.
$\gcd(12790396087027,11797951366656)=13$, и это главный фактор $n$. Вытаскивая $13$ и его полномочия, мы упростили задачу до факторинга $n'=n/13^2=75682817083$ зная $\varphi(n')=\varphi(n)/\big(13\,(13-1)\big)=11797951366656/\big(13\cdot 12\big)=75627893376$. Теперь нам нужны дальнейшие методы.
Общая техника для безквадратичного $n$
Зная любое (ненулевое) кратное $ф$ из $\лямбда(п')$ (функция Кармайкла) помогает разложить на множители бесквадратные $n'$, используя алгоритм там. У нас есть $f=75627893376=2^7\cdot590842917$ таким образом $s=7$, $т=590842917$.
- $а:=2$, $b=a^t\bmod n'=2^{590842917}\bmod 11797951366656=17605996164$
- $c:=b^2\bmod n'=17605996164^2\bmod 11797951366656=8570506209$, таким образом $б:=с$.
- $c:=b^2\bmod n'=8570506209^2\bmod 11797951366656=1$, успех!
- $p:=\gcd(b-1,n')=\gcd(8570506209-1,11797951366656)=4327$ что является главным фактором $n'$, $q:=n'/p=11797951366656/4327=17490829$ который составной и не является квадратом.
Остается факторинг $\тильда n=17490829$ зная $\varphi(\tilde n)=\varphi(n')/(p-1)=17482176=\tilde\varphi$. Мы могли бы снова использовать общую технику, описанную выше, но мы также можем надеяться на этот раз $\тильда п$ имеет только два (различных) простых множителя $р$ и $q$.
$n$ произведение двух различных простых множителей $р$ и $q$
Мы знаем $p\,q=\тильда n=17490829$ и $(p-1)(q-1)=\тильда\varphi=17482176$. Это система двух уравнений с двумя неизвестными. Следует $p+q=\тильда n-\тильда\varphi+1=\sigma=8654$, таким образом $р$ и $q$ являются решениями уравнения второй степени $x^2-\sigma\,x+\тильда n=0$, таким образом $p=(\sigma-\sqrt{\sigma^2-4\,\tilde n})/2=(8654-\sqrt{8654^2-4\cdot17490829})/2=3217$ и $q=(\sigma+\sqrt{\sigma^2-4\,\tilde n})/2=(8654+\sqrt{8654^2-4\cdot17490829})/2=5437$. Обе $р$ и $q$ являются простыми, таким образом, наши надежды были оправданы, и в конце концов желаемая факторизация $n=12790396087027=13^2\cdot3217\cdot4327\cdot5437$.
