ทฤษฎีบทของออยเลอร์เกี่ยวข้องกับ RSA อย่างไร

สำหรับที่กำหนด $n>1$ให้จำนวนเต็ม $f>0$ เป็นอย่างนั้นสำหรับทุกคน $m$ ใน $[0,น)$ กับ $\gcd(m,n)\ne1$ มันถือ $m^f\bmod n=1$. หนึ่งจำนวนเต็มดังกล่าว $f$ คือ ออยเลอร์ totient ของ $n$, $\operatorname{phi}(n)$ อาคา $\varphi(n)$, $\พี(n)$ หรือ $\phi(n)$. ในบรรดาทฤษฎีบทออยเลอร์หลายๆ ทฤษฎี หนึ่งในคำถามน่าจะเกี่ยวกับคุณสมบัตินั้นของโทเทียนออยเลอร์ ที่เล็กที่สุด $f$ เป็น $\แลมบ์ดา(n)$, ที่ไหน $\แลมบ์ดา$ คือ ฟังก์ชันคาร์ไมเคิล.

สมมติ $e$ และ $d$ ได้รับเลือกเช่นนั้น $e\cdot d\bmod f=1$. ตามนิยามของสิ่งที่ตัวดำเนินการ$\bmod$ คือเมื่อไม่มีวงเล็บเปิดทางด้านซ้าย หมายความว่า มีจำนวนเต็มอยู่ $k$ ดังนั้น $e\cdot d=k\cdot f+1$ (และ $0\le1<f$ซึ่งย่อมาจาก).

ตอนนี้สมมติว่า $\gcd(m,n)=1$, $$\begin{จัด} \left(m^e\right)^d\bmod n&=m^{e\cdot d}&\bmod n\ &=m^{k\cdot f+1}&\bmod n\ &=m^{k\cdot f}\cdot m^1&\bmod n\ &=m^{f\cdot k}\cdot m&\bmod n\ &=\left(m^f\right)^k\cdot m&\bmod n\ &=1^k\cdot ม&\bmod n\ &=1\cdot ม&\bmod n\ &=m&\bmod n\ \end{แนว} $$ เราได้พิสูจน์สิ่งนี้ภายใต้เงื่อนไข $\gcd(m,n)=1$ซึ่งเป็นสิ่งที่ กระดาษ RSA ต้นฉบับ ไม่และการแนะนำ RSA มากมาย แต่นั่นจะเกิดขึ้นจริงภายใต้เงื่อนไขที่ไม่เกี่ยวข้อง $m$: นั่น $n$ เป็น ไร้เหลี่ยม, ดู นี้.

นี้ "ปราศจากสี่เหลี่ยม $n$"สภาพน่าอยู่กว่าเยอะ $\gcd(m,n)=1$ ในบริบทของการเข้ารหัสข้อความโดยพลการ $m$โดยเฉพาะอย่างยิ่งเมื่อเราใช้เทียมขนาดเล็ก $n$ตั้งแต่นั้นมาเราไม่สามารถสรุปได้ $\gcd(m,n)\ne1$ ไม่น่าเป็นไปได้ ในคำถาม $n=33$, ดังนั้น $\gcd(m,n)\ne1$ เกิดขึ้นเพื่อ $m$ หนึ่งใน $0$, $3$, $6$, $9$, $11$, $12$, $15$, $18$, $21$, $22$, $24$, $27$, $30$จึงรวมถึง $m=15$ ที่พิจารณา!

¹ สำหรับจำนวนเต็ม $s$ และจำนวนเต็ม $t>0$, คำจำกัดความเทียบเท่าของสิ่งที่ผู้ประกอบการ$\bmod$ คือเมื่อไม่มีวงเล็บเปิดทันทีที่ด้านซ้ายรวม

• $s\bmod t$ เป็นจำนวนเต็มที่กำหนดไม่ซ้ำกัน $r$ กับ $0\le r<t$ และ $s-r$ หลายรายการ $t$
• $s\bmod t$ เป็นจำนวนเต็มที่กำหนดไม่ซ้ำกัน $r$ กับ $0\le r<t$ ที่มีอยู่จำนวนเต็ม $k$ กับ $s=k\cdot t+r$
• ขึ้นอยู่กับเครื่องหมายของ $s$, $s\bmod t$ เป็น
  • ถ้า $s\ge0$ส่วนที่เหลือของการหารแบบยุคลิดของ $s$ โดย $t$
  • ถ้า $s<0$, ทั้ง
    • $t-((-s)\bmod เสื้อ)$ ถ้านั่นไม่ใช่ $t$
    • $0$, มิฉะนั้น

นี้ไม่ต้องสับสนกับสัญกรณ์² $r\equiv s\pmod t$ โดยเปิดวงเล็บไว้ทางด้านซ้ายของ$\bmod$ซึ่งคำจำกัดความที่เทียบเท่ารวมถึง:

• $s-r$ เป็นทวีคูณของ $t$
• มีจำนวนเต็มอยู่ $k$ กับ $s=k\cdot t+r$

² $r\equiv s\pmod t$ ควรอ่านร่วมกับตัวใดตัวหนึ่งในหลายตัว $\equiv$ ด้านซ้ายของ$\pmod t$ อ่านเป็น สอดคล้องกัน หรือ เทียบเท่า ค่อนข้างมากกว่า เท่ากับและหยุดชั่วคราวเมื่อวงเล็บเปิดอยู่ การหยุดชั่วคราวนั้นเป็นการทำเครื่องหมายว่า$\pmod t$ มีคุณสมบัติตามที่พูด ใช้กันทั่วไป $=$ แทน $\equiv$ที่จะละเว้น$\pmod t$หรือเว้นวงเล็บเปิดไว้ก่อน$\bmod$. นั่นเป็นสาเหตุทั่วไปของความสับสนเมื่อความแตกต่างระหว่าง$\bmod t$ และ$\pmod t$ เรื่องซึ่งรวมถึงการคำนวณไซเฟอร์เท็กซ์ใน RSA