ทฤษฎีบทออยเลอร์เป็นการสรุปทั่วไปของทฤษฎีบทเล็กๆ ของแฟร์มาต์ที่จัดการด้วยกำลังของจำนวนเต็ม โมดูโล จำนวนเต็มบวก มีการใช้ทฤษฎีจำนวนพื้นฐานเพิ่มขึ้น เช่น โครงสร้างสนับสนุนทางทฤษฎีสำหรับระบบการเข้ารหัส RSA
ทฤษฎีบทนี้ระบุว่าสำหรับทุก a และ n ที่เป็นจำนวนเฉพาะ -
$$\mathrm{a^{\phi \left ( n \right )}\, \equiv\, 1\left ( mod \, n \right ) }$$
โดยที่ ф(n) คือฟังก์ชันโทเชียนของออยเลอร์ ซึ่งนับจำนวนเต็มบวกน้อยกว่า n ที่ค่อนข้างเฉพาะกับ n
พิจารณาเซตของจำนวนเต็มดังกล่าว −
R ={x1 , x2 , … xф(n) } กล่าวคือ แต่ละองค์ประกอบ xi ของ R เป็นจำนวนเต็มบวกที่ไม่ซ้ำกันน้อยกว่า n โดยที่ ged(xi, n) =1 จากนั้นคูณแต่ละองค์ประกอบด้วย a และ โมดูโล n −
S ={(ขวาน1 mod n), (ขวาน2 mod n), … (ขวานф(n) mod n)}
เนื่องจาก a เป็นจำนวนเฉพาะของ n และ xi ค่อนข้างเฉพาะกับ n, axi จะต้องค่อนข้างเฉพาะกับ n ด้วย ดังนั้น สมาชิกทั้งหมดของ S จึงเป็นจำนวนเต็มที่น้อยกว่า n และค่อนข้างเฉพาะกับ n
ไม่มีรายการที่ซ้ำกันใน S.
ถ้าขวานผม mod n และ n =axj mod n แล้วก็ xi =xj
$$\mathrm{ดังนั้น,\, \Pi _{i=1}^{\phi \left ( n \right )}\left ( ax_{i}\, mod\, n \right )=\Pi _{ i=1}^{\phi \left ( n \right )}\, x_{i}}$$
$$\mathrm{\Pi _{i=1}^{\phi \left ( n \right )}\, ax_{i}\equiv \Pi _{i=1}^{\phi \left ( n \ right )}\, x_{i}\left ( mod\, n \right )}$$
$$\mathrm{a^{\phi \left ( n \right )}\, x\left [ \Pi _{i=1}^{\phi \left ( n \right )}\, x_{i} \right ]=\Pi _{i=1}^{\phi \left ( n \right )}\, x_{i}\left ( mod\, n \right )}$$
$$\mathrm{a^{\phi \left ( n \right )}\equiv 1\left ( mod\, n \right )}$$
ออยเลอร์ โทเธียนท์ ฟังก์ชัน
ฟังก์ชัน Totient ของออยเลอร์คือฟังก์ชันการคูณทางคณิตศาสตร์ซึ่งนับจำนวนเต็มบวกจนถึงจำนวนเต็มที่กำหนด ซึ่งเรียกกันทั่วไปว่า 'n' ซึ่งเป็นจำนวนเฉพาะของ 'n' และฟังก์ชันนี้สามารถนำมาใช้เพื่อทำความเข้าใจจำนวนไพรม์นัมเบอร์ที่ exi จนถึงจำนวนเต็มที่กำหนด 'n'
ฟังก์ชัน Totient ของออยเลอร์เรียกอีกอย่างว่าฟังก์ชันพีของออยเลอร์ มันมีบทบาทสำคัญในการเข้ารหัส มันสามารถค้นหาจำนวนเต็มที่น้อยกว่า n และค่อนข้างเฉพาะกับ n ชุดตัวเลขเหล่านี้กำหนดโดย $\mathrm{Z_{n}^{*}}$ (จำนวนที่น้อยกว่า n และค่อนข้างเฉพาะกับ n)
ฟังก์ชันโททีเอนต์ของออยเลอร์มีประโยชน์หลายประการ สามารถใช้ในระบบเข้ารหัส RSA ซึ่งสามารถใช้สำหรับเป้าหมายด้านความปลอดภัย ฟังก์ชันนี้เกี่ยวข้องกับทฤษฎีจำนวนเฉพาะ และมีประโยชน์ในการคำนวณการคำนวณจำนวนมากด้วย สามารถใช้ฟังก์ชันนี้ในการคำนวณเกี่ยวกับพีชคณิตและตัวเลขอย่างง่ายได้
สัญลักษณ์ที่ใช้ระบุฟังก์ชันคือ ϕ และเรียกอีกอย่างว่าฟังก์ชัน phi ฟังก์ชันนี้รวมการใช้งานเชิงทฤษฎีมากกว่าการใช้งานจริง ข้อกำหนดที่สมเหตุสมผลของฟังก์ชันมีจำกัด
สามารถเข้าใจฟังก์ชันนี้ได้ดีขึ้นผ่านตัวอย่างเชิงปฏิบัติหลายตัวอย่าง แทนที่จะเป็นเพียงคำอธิบายเชิงทฤษฎี มีกฎหลายข้อในการคำนวณฟังก์ชันโทเอนเชียนท์ของออยเลอร์ และสำหรับจำนวนที่ต่างกัน กฎจะใช้ต่างกัน
ฟังก์ชันออยเลอร์ totient ф(n) คำนวณจำนวนองค์ประกอบใน $\mathrm{Z_{n}^{*}}$ โดยใช้กฎต่อไปนี้ −
-
ф(1) =0.
-
ф(P) =P − 1 ถ้า P เป็นไพรม์
-
ф(m x n) =ф(m) x ф(n) ถ้า m และ n เป็นจำนวนเฉพาะ
-
ф(P อี ) =P อี − P e-1 (ถ้า P เป็นจำนวนเฉพาะ )
กฎสี่ข้อต่อไปนี้สามารถรวมกันเพื่อให้ได้ค่า ф(n) แยกตัวประกอบ n เป็น
$$\mathrm{n=P_{1}^{e1}\, x\,P_{2}^{e2}x\cdot \cdot \cdot P_{k}^{ek}}$$
$$\mathrm{\phi \left ( n \right )=\left ( P_{1}^{e1}-P_{1}^{e1-1} \right )\left ( P_{2}^{e2 }-P_{2}^{e2-1} \right )x\cdot \cdot \cdot x\left (P_{k}^{ek}-P_{k}^{ek-1} \right )}$ $
ความยากในการค้นหา ф(n) ขึ้นอยู่กับความยากในการค้นหาการแยกตัวประกอบของn
