กำหนด $Ï(n)$ เราจะหาชุดค่าผสมสำหรับ $p, q$ จำนวนเฉพาะได้อย่างไร

เราต้องการแยกตัวประกอบ $n=900$ ใช้สิ่งนั้น $\varphi(n)=240$และปัจจัยโดยทั่วไป $n$ รู้ว่า ออยเลอร์ totient $\varphi(n)$.

นอกเหนือจากการแบ่งการทดลองแล้ว เราสามารถใช้เทคนิคสามประการ

1. หาตัวหารร่วมมากของสองตัวนี้ซึ่งถ้า $n$ หารด้วยสี่เหลี่ยมจัตุรัส และบางกรณีหายากจะเผยให้เห็นตัวประกอบของ $n$และ (เมื่อแยกตัวประกอบ GCD แล้ว) จะเปิดเผยตัวประกอบทั้งหมดของ $n$หรือปล่อยให้ก ไร้เหลี่ยม $n$ เพื่อแยกตัวประกอบ (นั่นคือ $n$ ผลคูณของจำนวนเฉพาะที่แตกต่างกัน)
2. เทคนิคที่ใช้กับ $n$ ผลคูณของจำนวนเฉพาะเฉพาะ: การรู้ผลคูณ (ไม่ใช่ศูนย์) ใดๆ $f$ ของ $\แลมบ์ดา(n)$ (ที่ ฟังก์ชันคาร์ไมเคิล), รวมทั้ง $f=\varphi(n)$ หรือ $f=e\,d-1$ ใน RSA ช่วยให้การแยกตัวประกอบ $n$ กับ อัลกอริทึมนี้ .
3. เทคนิคง่ายๆ ที่ใช้ได้กับ $n$ ผลคูณของจำนวนเฉพาะสองตัว $p$, $คิว$: เราหาได้ $\sigma=p+q=n-\varphi(n)+1$แล้วหา $p$ และ $คิว$ เป็นรากสองตัวของสมการกำลังสอง $x^2-\sigma\,x+n=0$.

การใช้ GCD

จำได้ว่าถ้าการแยกตัวประกอบของ $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)$. ดังนั้นสำหรับทุกคน $i$ กับ $k_i>1$, ${p_i}^{k_i-1}$ แบ่ง $n$ และ $\varphi(n)$.

สิ่งนี้กระตุ้นให้เกิดการคำนวณ $g:=\gcd(n,\varphi(n))$. ถ้า $g\ne1$ (ซึ่งมีความเป็นไปได้ต่ำมากหาก $n$ เป็นโมดูลัส RSA จริง) ดังนั้น $g$ เป็นปัจจัยที่ไม่สำคัญของ $n$ และเราได้ก้าวหน้า: เราสามารถแยกตัวประกอบได้ $g$ และ $n/g$ แยกกัน นอกจากนี้ เมื่อเราพบการแยกตัวประกอบของ $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$.

ถ้า $g=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$

รู้ผลคูณใด ๆ (ที่ไม่ใช่ศูนย์) $f$ ของ $\แลมบ์ดา(n')$ (ฟังก์ชันคาร์ไมเคิล) ช่วยการแยกตัวประกอบแบบไม่มีกำลังสอง $n'$โดยใช้อัลกอริทึม ที่นั่น. เรามี $f=75627893376=2^7\cdot590842917$ ดังนั้น $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$, ดังนั้น $b:=c$.
• $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$ ซึ่งเป็นรูปประกอบ ไม่ใช่รูปสี่เหลี่ยมจัตุรัส

เราจะเหลือแฟ $\tilde n=17490829$ รู้ $\varphi(\tilde n)=\varphi(n')/(p-1)=17482176=\tilde\varphi$. เราสามารถใช้เทคนิคทั่วไปข้างต้นได้อีกครั้ง แต่คราวนี้เราก็หวังได้เช่นกัน $\tilde n$ มีตัวประกอบเฉพาะ (เฉพาะ) สองตัวเท่านั้น $p$ และ $คิว$.

$n$ ผลคูณของปัจจัยเฉพาะที่แตกต่างกันสองประการ $p$ และ $คิว$

พวกเรารู้ $p\,q=\tilde n=17490829$ และ $(p-1)(q-1)=\tilde\varphi=17482176$. นั่นคือระบบสมการสองสมการที่มีนิรนามสองตัว มันเป็นไปตาม $p+q=\tilde n-\tilde\varphi+1=\sigma=8654$, ดังนั้น $p$ และ $คิว$ เป็นคำตอบของสมการดีกรีสอง $x^2-\sigma\,x+\tilde 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$. ทั้งคู่ $p$ และ $คิว$ เป็นจำนวนเฉพาะ ดังนั้น ความหวังของเราจึงเกิดขึ้น และในที่สุด การแยกตัวประกอบที่ต้องการก็คือ $n=12790396087027=13^2\cdot3217\cdot4327\cdot5437$.