ในคณิตศาสตร์โดยเฉพาะในสาขาเลขคณิตตัวผกผันการคูณแบบมอดูลาร์ของจำนวนเต็มaคือจำนวนเต็มxที่ผลคูณaxสอดคล้อง กับ 1 เมื่อเทียบกับมอดูลัสm [ ^{1 ] ใน}สัญลักษณ์มาตรฐานของเลขคณิตแบบมอดูลาร์ ความสอดคล้องนี้เขียนได้ดังนี้

${\displaystyle ax\equiv 1{\pmod {m}},}$

ซึ่งเป็นวิธีเขียนย่อของประโยคที่ว่าmหาร (ลงตัว) ปริมาณax − 1หรือกล่าวอีกนัยหนึ่งคือ เศษเหลือหลังจากหารaxด้วยจำนวนเต็มmคือ 1 ถ้าaมีตัวผกผันมอดูลัสmแล้วจะมีคำตอบอนันต์ของสมการนี้ ซึ่งก่อให้เกิดชั้นสมการ ที่ สัมพันธ์กับมอดูลัสนี้ ยิ่งไปกว่านั้น จำนวนเต็มใดๆ ที่สมมูลกับa (กล่าวคือ อยู่ใน ชั้นสมการของ a ) จะมีสมาชิกใดๆ ใน ชั้นสมการของ xเป็นตัวผกผันการคูณมอดูลัส การใช้สัญลักษณ์เพื่อระบุชั้นสมการที่ประกอบด้วยwสามารถแสดงได้โดยกล่าวว่าตัวผกผันการคูณมอดูลัสของชั้นสมการคือชั้นสมการที่: ${\displaystyle {\overline {w}}}$${\displaystyle {\overline {a}}}$${\displaystyle {\overline {x}}}$

${\displaystyle {\overline {a}}\cdot {\overline {x}}={\overline {1}},}$

โดยที่สัญลักษณ์แสดงถึงการคูณของชั้นสมมูลโมดูลm [ ^{2 ] เมื่อเขียนในลักษณะ นี้} ความคล้ายคลึงกับแนวคิดปกติของตัวผกผันการคูณในเซตของจำนวนตรรกยะหรือจำนวนจริงจะถูกแสดงอย่างชัดเจน โดยแทนที่ตัวเลขด้วยชั้นความสอดคล้องและเปลี่ยนแปลงการดำเนินการทวิภาคให้เหมาะสม ${\displaystyle \cdot }$

เช่นเดียวกับการดำเนินการที่คล้ายคลึงกันบนจำนวนจริง การใช้งานพื้นฐานของการดำเนินการนี้คือการแก้สมการเชิงเส้นในรูปแบบต่างๆ เมื่อเป็นไปได้

${\displaystyle ax\equiv b{\pmod {m}}.}$

การค้นหาตัวผกผันการคูณแบบโมดูลาร์ยังมีการประยุกต์ใช้ในทางปฏิบัติในด้านการเข้ารหัสลับเช่น การเข้ารหัส ลับแบบกุญแจสาธารณะและอัลกอริทึม RSA ^{[ 3 ] [ 4 ] [ 5 ]}ข้อดีสำหรับการนำแอปพลิเคชันเหล่านี้ไปใช้ในคอมพิวเตอร์คือมีอัลกอริทึมที่เร็วมาก ( อัลกอริทึมยุคลิดแบบขยาย ) ที่สามารถใช้ในการคำนวณตัวผกผันการคูณแบบโมดูลาร์ได้

สำหรับจำนวนเต็มบวกm ที่กำหนดให้ จำนวนเต็มสองจำนวนaและbจะเรียกว่าสมมูลกันมอดูลmถ้าmหารผลต่างของจำนวนเต็ม ทั้งสองลงตัว ความสัมพันธ์ทวิภาค นี้ เขียนแทนด้วย

${\displaystyle a\equiv b{\pmod {m}}.}$

นี่คือความสัมพันธ์สมมูลบนเซตของจำนวนเต็มและชั้นสมมูลเรียกว่าชั้นความสอดคล้องมอดูล^mหรือชั้นเศษเหลือมอดูลmให้แทนชั้นความสอดคล้องที่มีจำนวนเต็มa [ ^{6 ]}แล้ว ${\displaystyle \mathbb {Z} }$${\displaystyle {\overline {a}}}$

${\displaystyle {\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.}$

ความสอดคล้องเชิงเส้นคือความสอดคล้องแบบมอดูลาร์ในรูปแบบ

${\displaystyle ax\equiv b{\pmod {m}}.}$

ต่างจากสมการเชิงเส้นบนจำนวนจริง ความสอดคล้องเชิงเส้นอาจมีคำตอบเป็นศูนย์ หนึ่ง หรือหลายคำตอบ ถ้าxเป็นคำตอบของความสอดคล้องเชิงเส้นแล้ว ทุกองค์ประกอบในก็เป็นคำตอบเช่นกัน ดังนั้น เมื่อพูดถึงจำนวนคำตอบของความสอดคล้องเชิงเส้น เราจึงหมายถึงจำนวนชั้นความสอดคล้องที่แตกต่างกันซึ่งมีคำตอบอยู่ ${\displaystyle {\overline {x}}}$

ถ้าdเป็นตัวหารร่วมมากที่สุดของaและmแล้วสมการเชิงเส้นax ≡ b (mod m )จะมีคำตอบก็ต่อเมื่อdหารb ลงตัว ถ้าdหารb ลงตัว จะมี คำตอบอยู่ dคำตอบ พอดี ^{[ 7 ]}

ตัวผกผันการคูณแบบโมดูลาร์ของจำนวนเต็มaเทียบกับโมดูลัสmคือคำตอบของสมการความสอดคล้องเชิงเส้น

${\displaystyle ax\equiv 1{\pmod {m}}.}$

ผลลัพธ์ก่อนหน้านี้ระบุว่ามีคำตอบอยู่ก็ต่อเมื่อgcd( a , m ) = 1 เท่านั้น นั่นคือaและmต้องเป็นจำนวนเฉพาะสัมพัทธ์ (กล่าวคือเป็นจำนวนเฉพาะสัมพัทธ์) ยิ่งไปกว่านั้น เมื่อเงื่อนไขนี้เป็นจริง จะมีคำตอบเพียงหนึ่งเดียวเท่านั้น กล่าวคือ เมื่อมีคำตอบอยู่ ตัวผกผันการคูณแบบโมดูลาร์จะมีเพียงหนึ่งเดียว: ^{[ 8 ]}ถ้าbและb'เป็นตัวผกผันการคูณแบบโมดูลาร์ของaเทียบกับโมดูลัสmแล้ว

${\displaystyle ab\equiv ab'\equiv 1{\pmod {m}},}$

ดังนั้น

${\displaystyle a(bb')\equiv 0{\pmod {m}}.}$

ถ้าa ≡ 0 (mod m )แล้วgcd( a , m ) = mและaจะไม่มีตัวผกผันการคูณแบบมอดูลาร์ด้วย ดังนั้นb ≡ b' (mod m )

เมื่อax ≡ 1 (mod m )มีคำตอบ มักจะแสดงด้วยสัญลักษณ์นี้ −

${\displaystyle x\equiv a^{-1}{\pmod {m}},}$

แต่การใช้สัญลักษณ์แบบนี้อาจถือได้ว่าเป็นการใช้สัญลักษณ์ที่ ไม่ถูกต้อง เนื่องจากอาจถูกตีความผิดว่าเป็นส่วนกลับของ(ซึ่งตรงกันข้ามกับตัวผกผันการคูณแบบโมดูลาร์ ซึ่งไม่ใช่จำนวนเต็ม ยกเว้นเมื่อaเป็น 1 หรือ −1) สัญลักษณ์จะถูกต้องก็ต่อเมื่อ ตีความว่า aเป็นสัญลักษณ์แทนชั้นความสอดคล้องเนื่องจากตัวผกผันการคูณของชั้นความสอดคล้องคือชั้นความสอดคล้องที่มีการคูณตามที่นิยามไว้ในส่วนถัดไป ${\displaystyle a}$${\displaystyle {\overline {a}}}$

ความสัมพันธ์สมมูล โมดูลัสmแบ่งเซตของจำนวนเต็มออกเป็นmชั้นสมมูล การดำเนินการบวกและการคูณสามารถกำหนดได้บน วัตถุ m เหล่านี้ ในลักษณะต่อไปนี้: ในการบวกหรือคูณชั้นสมมูลสองชั้น ขั้นแรกให้เลือกตัวแทน (ด้วยวิธีใดก็ได้) จากแต่ละชั้น จากนั้นดำเนินการตามปกติสำหรับจำนวนเต็มกับตัวแทนทั้งสอง และสุดท้ายเลือกชั้นสมมูลที่ผลลัพธ์ของการดำเนินการกับจำนวนเต็มอยู่เป็นผลลัพธ์ของการดำเนินการบนชั้นสมมูล ในเชิงสัญลักษณ์ นิยามเหล่านี้คือ

${\displaystyle {\overline {a}}+{\overline {b}}={\overline {a+b}}}$

และ

${\displaystyle {\overline {a}}\cdot {\overline {b}}={\overline {ab}},}$

โดยที่และทางด้านซ้าย แสดงถึงการบวกและการคูณของชั้นความสอดคล้องกันแบบมอดูลmการดำเนินการเหล่านี้มีความชัดเจนหมายความว่าผลลัพธ์สุดท้ายไม่ขึ้นอยู่กับการเลือกตัวแทนที่ใช้เพื่อให้ได้ผลลัพธ์นั้น ${\displaystyle +}$${\displaystyle \,\!\cdot }$

ชั้น ความสอดคล้อง mชั้นที่มีการดำเนินการที่กำหนดไว้สองอย่างนี้ก่อให้เกิดวงแหวน สลับที่ได้ เรียกว่าวงแหวนของจำนวนเต็มมอดูล mมีสัญลักษณ์หลายแบบที่ใช้สำหรับวัตถุทางพีชคณิตเหล่านี้ ส่วนใหญ่ใช้หรือแต่ตำราพื้นฐานและสาขาการประยุกต์ใช้หลายแห่งใช้สัญลักษณ์ที่ง่ายกว่าเมื่อไม่น่าจะเกิดความสับสนกับวัตถุทางพีชคณิตอื่นๆ ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m}$${\displaystyle \mathbb {Z} _{m}}$

ชั้นความสอดคล้องของจำนวนเต็มมอดูลmเดิมเรียกว่าชั้นเศษเหลือมอดูล mซึ่งสะท้อนให้เห็นว่าองค์ประกอบทั้งหมดของชั้นความสอดคล้องจะมีเศษเหลือ (เช่น "เศษเหลือ") เหมือนกันเมื่อหารด้วยmเซตของ จำนวนเต็ม mตัวที่เลือกมาเพื่อให้แต่ละตัวมาจากชั้นความสอดคล้องมอดูล m ที่แตกต่างกันเรียกว่าระบบเศษเหลือมอดูล m ที่สมบูรณ์ [ 9 ^{]อัลก}อริทึมการหารแสดงให้เห็นว่าเซตของจำนวนเต็ม{0, 1, 2, ..., m − 1}ก่อให้เกิดระบบเศษเหลือมอดู ล m ที่สมบูรณ์ ซึ่งเรียกว่าระบบเศษเหลือมอดูลm ที่น้อยที่สุด ในการทำงานกับปัญหาทางคณิตศาสตร์ บางครั้งการทำงานกับระบบเศษเหลือที่สมบูรณ์และใช้ภาษาของความสอดคล้องจะสะดวกกว่า ในขณะที่บางครั้งมุมมองของชั้นความสอดคล้องของวงแหวนจะมีประโยชน์มากกว่า^{[ 10 ]}${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

ไม่ใช่ว่าทุกองค์ประกอบของระบบเศษเหลือสมบูรณ์มอดูลmจะมีตัวผกผันการคูณมอดูล ตัวอย่างเช่น ศูนย์จะไม่มีตัวผกผันการคูณมอดูลถ้าm > 1หลังจากลบองค์ประกอบของระบบเศษเหลือสมบูรณ์ที่ไม่เป็นจำนวนเฉพาะสัมพัทธ์กับmออกไปแล้ว สิ่งที่เหลืออยู่เรียกว่าระบบเศษเหลือลดรูปซึ่งองค์ประกอบทั้งหมดมีตัวผกผันการคูณมอดูล จำนวนองค์ประกอบในระบบเศษเหลือลดรูปคือโดยที่คือฟังก์ชันโทเทียนต์ของออยเลอร์ นั่น คือ จำนวนเต็มบวกที่น้อยกว่าmที่เป็นจำนวนเฉพาะสัมพัทธ์กับm${\displaystyle \phi (m)}$${\displaystyle \phi }$

ในริงทั่วไปที่มีเอกลักษณ์ไม่ใช่ทุกสมาชิกจะมีตัวผกผันการคูณและสมาชิกที่มีตัวผกผันการคูณเรียกว่าหน่วยเนื่องจากผลคูณของหน่วยสองหน่วยก็คือหน่วย หน่วยของริงจึงรวมกันเป็นกลุ่มซึ่ง เรียกว่า กลุ่มของหน่วยของริงและมักจะใช้สัญลักษณ์R ^{× m}ถ้าRคือชื่อของริง กลุ่มของหน่วยของริงจำนวนเต็มมอดูลmเรียกว่ากลุ่มการคูณของจำนวนเต็มมอดูลmและมันสมสัณฐานกับระบบเศษเหลือลดรูป โดยเฉพาะอย่างยิ่ง มันมีอันดับ (ขนาด) เท่ากับm ${\displaystyle \phi (m)}$

ในกรณีที่mเป็นจำนวนเฉพาะเช่นpแล้วและสมาชิกที่ไม่เป็นศูนย์ทั้งหมดของมีตัวผกผันการคูณ ดังนั้น จึงเป็นฟิลด์จำกัดในกรณีนี้ กลุ่มการคูณของจำนวนเต็มมอดูล pจะก่อให้เกิดกลุ่มวัฏจักรที่มีอันดับp − 1${\displaystyle \phi (p)=p-1}$${\displaystyle \mathbb {Z} /p\mathbb {Z} }$${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

สำหรับจำนวนเต็มใดๆจะเป็นจริงเสมอว่าคือตัวผกผันการคูณแบบมอดูลาร์ของเทียบกับมอดูลัสเนื่องจากตัวอย่างเช่น, และอื่นๆ ${\displaystyle n>1}$${\displaystyle n^{2}-n+1}$${\displaystyle n+1}$${\displaystyle n^{2}}$${\displaystyle (n+1)(n^{2}-n+1)=n^{3}+1}$${\displaystyle 3\times 3\equiv 1{\pmod {4}}}$${\displaystyle 4\times 7\equiv 1{\pmod {9}}}$${\displaystyle 5\times 13\equiv 1{\pmod {16}}}$

ตัวอย่างต่อไปนี้ใช้ค่าสัมบูรณ์ 10: จำนวนเต็มสองจำนวนจะสมมูลกันมอด 10 ก็ต่อเมื่อผลต่างของจำนวนทั้งสองหารด้วย 10 ลงตัว ตัวอย่างเช่น

${\displaystyle 32\equiv 2{\pmod {10}}}$เนื่องจาก 10 หาร 32 − 2 ได้ลงตัวเท่ากับ 30 และ

${\displaystyle 111\equiv 1{\pmod {10}}}$เนื่องจาก 10 หาร 111 − 1 ได้ลงตัวเท่ากับ 110

กลุ่มความสอดคล้องทั้งสิบกลุ่มที่เกี่ยวข้องกับโมดูลัสนี้ ได้แก่:

${\displaystyle {\overline {0}}=\{\cdots ,-20,-10,0,10,20,\cdots \}}$

${\displaystyle {\overline {1}}=\{\cdots ,-19,-9,1,11,21,\cdots \}}$

${\displaystyle {\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \}}$และ

${\displaystyle {\overline {9}}=\{\cdots ,-11,-1,9,19,29,\cdots \}.}$

สมการเชิงเส้น4x ≡ 5 (mod 10) ไม่มีคำตอบ เนื่องจากจำนวนเต็มที่สมมูลกับ 5 (กล่าวคือ จำนวนใน) เป็นจำนวนคี่ทั้งหมด ในขณะที่4xเป็นจำนวนคู่เสมอ อย่างไรก็ตาม สมการเชิงเส้น4x ≡ 6 (mod 10) มีสองคำตอบ คือx = 4และx = 9 ตัวหารร่วมมาก ของ4, 10 คือ 2และ 2 หาร 5 ไม่ลงตัว แต่หาร 6 ลงตัว ${\displaystyle {\overline {5}}}$

เนื่องจากgcd(3, 10) = 1ดังนั้นสมการเชิงเส้น3 x ≡ 1 (mod 10)จะมีคำตอบ นั่นคือ ตัวผกผันการคูณแบบมอดูลัสของ 3 มอดูลัส 10 จะมีอยู่จริง ในความเป็นจริง 7 สอดคล้องกับสมการนี้ (เช่น 21 − 1 = 20) อย่างไรก็ตาม จำนวนเต็มอื่นๆ ก็สอดคล้องกับสมการนี้เช่นกัน ตัวอย่างเช่น 17 และ −3 (เช่น 3(17) − 1 = 50 และ 3(−3) − 1 = −10) โดยเฉพาะอย่างยิ่ง จำนวนเต็มทุกตัวในจะสอดคล้องกับสมการนี้ เนื่องจากจำนวนเต็มเหล่านี้มีรูปแบบ7 + 10 rสำหรับจำนวนเต็มr บางตัว และ ${\displaystyle {\overline {7}}}$

${\displaystyle 3(7+10r)-1=21+30r-1=20+30r=10(2+3r),}$

หารด้วย 10 ลงตัว สมการนี้มีชุดคำตอบเพียงชุดเดียวเท่านั้น คำตอบในกรณีนี้อาจได้มาจากการตรวจสอบทุกกรณีที่เป็นไปได้ แต่จะต้องใช้อัลกอริทึมที่เป็นระบบสำหรับค่าสัมบูรณ์ที่ใหญ่กว่า และจะกล่าวถึงในส่วนถัดไป

ผลคูณของชั้นความสอดคล้องและสามารถหาได้โดยการเลือกสมาชิกของเช่น 25 และสมาชิกของเช่น −2 แล้วสังเกตว่าผลคูณของทั้งสอง (25)(−2) = −50 อยู่ในชั้นความสอดคล้องดังนั้นการบวกก็ถูกนิยามในทำนองเดียวกัน ชั้นความสอดคล้องทั้งสิบชั้นพร้อมกับการดำเนินการบวกและการคูณของชั้นความสอดคล้องเหล่านี้ก่อให้เกิดวงแหวนของจำนวนเต็มมอดูล 10 นั่นคือ ${\displaystyle {\overline {5}}}$${\displaystyle {\overline {8}}}$${\displaystyle {\overline {5}}}$${\displaystyle {\overline {8}}}$${\displaystyle {\overline {0}}}$${\displaystyle {\overline {5}}\cdot {\overline {8}}={\overline {0}}}$${\displaystyle \mathbb {Z} /10\mathbb {Z} }$

ระบบเศษเหลือที่สมบูรณ์มอดูล 10 คือเซต {10, −9, 2, 13, 24, −15, 26, 37, 8, 9} โดยที่จำนวนเต็มแต่ละตัวอยู่ในชั้นสมมูลมอดูล 10 ที่แตกต่างกัน ระบบเศษเหลือที่น้อยที่สุดที่ไม่ซ้ำกันมอดูล 10 คือ {0, 1, 2, ..., 9} ระบบเศษเหลือที่ลดรูปมอดูล 10 คือ {1, 3, 7, 9} ผลคูณของชั้นสมมูลสองชั้นใดๆ ที่แสดงด้วยจำนวนเหล่านี้ก็คือหนึ่งในสี่ชั้นสมมูลนี้เช่นกัน ซึ่งหมายความว่าสี่ชั้นสมมูลนี้ก่อตัวเป็นกลุ่ม ในกรณีนี้คือกลุ่มวัฏจักรอันดับสี่ โดยมี 3 หรือ 7 เป็นตัวสร้าง (ตัวคูณ) ชั้นสมมูลที่แสดงเหล่านี้ก่อตัวเป็นกลุ่มของหน่วยของริง ชั้นสมมูลเหล่านี้คือชั้นที่มีตัวผกผันการคูณมอดูลอย่างแม่นยำ ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$

ในวิกิบุ๊กเรื่องการนำอัลกอริทึมไปใช้ มีหน้าหนึ่งที่กล่าวถึงหัวข้อ: อัลกอริทึมยูคลิดแบบขยาย

สามารถหาตัวผกผัน การคูณแบบโมดูลัสของโมดูลัสm ได้โดยใช้อัลกอริทึมยุคลิดแบบขยาย

อัลกอริทึมของยุคลิดจะหาตัวหารร่วมมาก (gcd) ของจำนวนเต็มสองจำนวน เช่นaและmถ้าaมีตัวผกผันการคูณมอดูลm gcd นี้จะต้องเป็น 1 สมการสุดท้ายจากหลายสมการที่ได้จากอัลกอริทึมนี้สามารถแก้หา gcd ได้ จากนั้น โดยใช้วิธีที่เรียกว่า "การแทนค่าแบบย้อนกลับ" จะสามารถหาความสัมพันธ์ระหว่างพารามิเตอร์ดั้งเดิมกับ gcd ได้ กล่าวอีกนัยหนึ่งคือสามารถหา จำนวนเต็ม xและy ที่สอดคล้องกับ เอกลักษณ์ของเบซูต์ได้

${\displaystyle ax+my=\gcd(a,m)=1.}$

เขียนใหม่แล้ว นี่คือ

${\displaystyle ax-1=(-y)m,}$

นั่นคือ

${\displaystyle ax\equiv 1{\pmod {m}},}$

ดังนั้น จึงได้คำนวณ ตัวผกผันการคูณแบบโมดูลาร์ของ a แล้ว เวอร์ชันที่มีประสิทธิภาพมากกว่าของอัลกอริทึมนี้คืออัลกอริทึมยุคลิดแบบขยาย ซึ่งโดยการใช้สมการเสริม จะลดขั้นตอนการผ่านอัลกอริทึมสองรอบ (การแทนค่าย้อนกลับสามารถคิดได้ว่าเป็นการผ่านอัลกอริทึมในทางกลับกัน) เหลือเพียงรอบเดียว ใน สัญกรณ์ O ขนาดใหญ่อัลกอริทึมนี้ทำงานในเวลาO(log ² ( m ))โดยสมมติว่า| a | < mและถือว่าเร็วมากและโดยทั่วไปมีประสิทธิภาพมากกว่าทางเลือกอื่นคือการยกกำลัง

ตัวอย่างเช่น ตัวผกผันการคูณแบบโมดูลาร์ของเมื่อเทียบกับโมดูลัสคือแต่ยังรวมถึงกล่าวคือ ในวงแหวนชั้นเศษเหลือสามารถผกผันได้ด้วยตัวผกผัน ${\displaystyle a=15}$${\displaystyle m=34}$${\displaystyle -9}$${\displaystyle -9+34=25,}$${\displaystyle \mathbb {Z} /34\mathbb {Z} ,}$${\displaystyle {\overline {15}}}$

${\displaystyle {\overline {15}}^{\!\ -1}={\overline {-9}}={\overline {25}}.}$

เพราะ

${\displaystyle g=\mathrm {gcd} (m,a)=1=4m-9a,}$

ตามการคำนวณที่อยู่ติดกัน ในขั้นตอนแรก ซึ่งสอดคล้องกับการหารแบบยุคลิด " มีเศษเหลือ" สมการคูณจะถูกบวกเข้ากับสมการซึ่งนำไปสู่​​ทันทีที่มีเศษเหลือทางด้านซ้าย จะอยู่เหนือกว่า (หรือโดยทั่วไปหากอนุญาตให้มีเศษเหลือติดลบได้) ในตารางทางด้านขวาสุดที่สอดคล้องกันซึ่งมีการดำเนินการแถวที่คล้ายกัน เห็นได้ชัดว่าสามารถละเว้นคอลัมน์ ได้ สุดท้ายสามารถตรวจสอบได้โดยตรง: ${\displaystyle \;\!34\div 15}$${\displaystyle 2}$${\displaystyle 4\!\ }$${\displaystyle -2}$${\displaystyle 15=0m+1a}$${\displaystyle 34=1m+0a}$${\displaystyle 4=1m-2a.}$${\displaystyle 0,}$${\displaystyle g}$${\displaystyle \pm g}$${\displaystyle m}$${\displaystyle {\overline {15}}{}^{\!\ -1}={\overline {-9}}}$

${\displaystyle {\overline {15}}\cdot {\overline {-9}}={\overline {-135}}={\overline {-135+4\cdot 34}}={\overline {1}}}$

ใน${\displaystyle \mathbb {Z} /34\mathbb {Z} .}$

ทฤษฎีบทของออยเลอร์สามารถใช้แทนอัลกอริทึมยุคลิดแบบขยายเพื่อคำนวณอินเวอร์สโมดูลาร์ได้^{[ 11 ]}

ตามทฤษฎีบทของออยเลอร์ถ้าaเป็นจำนวนเฉพาะสัมพัทธ์กับmนั่นคือgcd( a , m ) = 1แล้ว

${\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}$

โดยที่คือฟังก์ชันโทเทียนต์ของออยเลอร์ซึ่งเป็นผลมาจากข้อเท็จจริงที่ว่าaเป็นสมาชิกของกลุ่มการคูณ^× ก็ต่อเมื่อaเป็น จำนวนเฉพาะ สัมพัทธ์กับm เท่านั้น ดังนั้น จึงสามารถหาตัวผกผันการคูณแบบมอดูลาร์ได้โดยตรง: ${\displaystyle \phi }$${\displaystyle (\mathbb {Z} /m\mathbb {Z} )}$

${\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}$

ในกรณีพิเศษที่mเป็นจำนวนเฉพาะและตัวผกผันมอดูลาร์กำหนดโดย ${\displaystyle \phi (m)=m-1}$

${\displaystyle a^{-1}\equiv a^{m-2}{\pmod {m}}.}$

โดยทั่วไปแล้ว วิธีนี้ช้ากว่าอัลกอริธึมยุคลิดแบบขยาย แต่บางครั้งก็ใช้เมื่อมีการใช้งานสำหรับการยกกำลังแบบโมดูลาร์อยู่แล้ว ข้อเสียบางประการของวิธีนี้ได้แก่:

• ต้องทราบค่า และวิธีการคำนวณที่มีประสิทธิภาพที่สุดที่ทราบกันนั้นต้องอาศัย การแยกตัวประกอบของmการแยกตัวประกอบนั้นเชื่อกันอย่างกว้างขวางว่าเป็นปัญหาที่ยากในเชิงการคำนวณ อย่างไรก็ตาม การคำนวณนั้นทำได้ง่ายเมื่อทราบ การแยกตัวประกอบเฉพาะของ m แล้ว${\displaystyle \phi (m)}$${\displaystyle \phi (m)}$
• ต้นทุนสัมพัทธ์ของการยกกำลัง แม้ว่าจะสามารถดำเนินการได้อย่างมีประสิทธิภาพมากขึ้นโดยใช้การยกกำลังแบบโมดูลาร์แต่เมื่อค่าmมีขนาดใหญ่ การคำนวณที่มีประสิทธิภาพที่สุดคือด้วย วิธี การลดทอนของมอนต์โก เมอรี ซึ่งวิธีการนั้นเองก็ต้องการตัวผกผันโมดูลาร์ mod mซึ่งเป็นสิ่งที่ต้องคำนวณตั้งแต่แรกอยู่แล้ว หากไม่มีวิธีการของมอนต์โกเมอรีการยกกำลังแบบไบนารี มาตรฐาน ซึ่งต้องใช้การหาร mod mในทุกขั้นตอน จะเป็นการดำเนินการที่ช้าเมื่อmมีขนาดใหญ่

ข้อดีที่โดดเด่นอย่างหนึ่งของเทคนิคนี้คือไม่มีเงื่อนไขใดๆ ที่ขึ้นอยู่กับค่าของaดังนั้นค่าของaซึ่งอาจเป็นความลับสำคัญในระบบการเข้ารหัสแบบกุญแจสาธารณะจึงสามารถได้รับการปกป้องจากการโจมตีแบบช่องทางด้านข้างได้ด้วยเหตุนี้ การใช้งานมาตรฐานของCurve25519จึงใช้เทคนิคนี้ในการคำนวณค่าผกผัน

เป็นไปได้ที่จะคำนวณค่าผกผันของจำนวนหลายจำนวนa _iมอดูลm ทั่วไป ด้วยการเรียกใช้อัลกอริทึมยุคลิดเพียงครั้งเดียวและการคูณสามครั้งต่ออินพุตเพิ่มเติม^{[ 12 ]} แนวคิดพื้นฐานคือการสร้างผลคูณของa _i ทั้งหมด ผกผันผลคูณนั้น แล้วคูณด้วยa _jสำหรับj ≠ i ทั้งหมด เพื่อให้เหลือเพียงa ที่ต้องการ⁻¹ _i.

กล่าวโดยละเอียดแล้ว อัลกอริทึมมีดังนี้ (การคำนวณทางคณิตศาสตร์ทั้งหมดดำเนินการแบบโมดูลัสm ):

1. คำนวณผลคูณพรีฟิก สำหรับทุกi ≤ n${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$
2. คำนวณb⁻¹ _นโดยใช้อัลกอริธึมใดก็ได้ที่มีอยู่
3. สำหรับiตั้งแต่nลงมาถึง 2 ให้คำนวณ
   • เอ⁻¹ _i= b⁻¹ _ib _{i −1}และ
   • ข⁻¹ _{i −1}= b⁻¹ _iเอ_ไอ .
4. สุดท้ายนี้⁻¹ ₁= b⁻¹ ₁.

สามารถทำการคูณในโครงสร้างแบบต้นไม้แทนที่จะเป็นแบบเชิงเส้น เพื่อใช้ประโยชน์จากการประมวลผลแบบขนานได้

ในกรณีที่โมดูลัสMอยู่ในรูปแบบสำหรับจำนวนเฉพาะp บางตัว และจำนวนเต็มบวกm บางตัว เป็น ไปได้ที่จะคำนวณตัวผกผันการคูณแบบโมดูลัสได้อย่างมีประสิทธิภาพโดยใช้การวนซ้ำของนิวตัน-ราฟสัน ซึ่งช่วยให้สามารถคำนวณตัวผกผันได้ด้วยการคูณ สามารถแสดงได้ว่าถ้า ${\displaystyle p^{m}}$${\displaystyle O(\log m)}$

${\displaystyle ax\equiv 1{\pmod {p^{k}}}}$

(นั่นคือxเป็นตัวผกผันการคูณแบบโมดูลาร์ของaโมดูลัสกำลังของจำนวนเฉพาะบางตัว ) แล้ว ${\displaystyle p^{k}}$

${\displaystyle ax\left(2-ax\right)\equiv 1{\pmod {p^{2k}}}}$

ซึ่งหมายความว่าสามารถทำการคำนวณผกผันโมดูลาร์ได้โดยการคำนวณผกผันการคูณโมดูลาร์ของโมดูลัสจำนวนเฉพาะ p หรือกำลังเล็กๆ ของจำนวนเฉพาะนั้นก่อน จากนั้นจึงทำการวนซ้ำแบบนิวตัน-ราฟสันหลายครั้งเพื่อคำนวณผกผันโมดูลัสกำลังของจำนวนเฉพาะที่ใหญ่ขึ้นเรื่อยๆ^{สำหรับ}ค่าn ที่ใหญ่ขึ้นเรื่อยๆ [ ^{13 ] [ 14 ]}${\displaystyle p^{2^{n}*k}}$

การประยุกต์ใช้วิธีนี้ในทางปฏิบัติคือการคำนวณตัวผกผันการคูณแบบโมดูลาร์โมดูลัสกำลังของ 2 อย่างมีประสิทธิภาพ สำหรับการคำนวณดังกล่าว เราอาจเริ่มต้นด้วยการสังเกตว่าจำนวนเต็มคี่ทั้งหมดเป็นตัวผกผันการคูณแบบโมดูลาร์โมดูลัสของตัวเองดังที่สามารถแสดงได้โดยการตรวจสอบ: ${\displaystyle 2^{3}}$

${\displaystyle 1*1=1\equiv 1{\pmod {8}}}$, , , , ${\displaystyle 3*3=9\equiv 1{\pmod {8}}}$${\displaystyle 5*5=25\equiv 1{\pmod {8}}}$${\displaystyle 7*7=49\equiv 1{\pmod {8}}}$

จากนั้นใช้การวนซ้ำแบบนิวตัน-ราฟสันเพื่อคำนวณค่าผกผันเชิงโมดูลัสโมดูลัส, , และอื่นๆ ต่อไป ${\displaystyle 2^{6}}$${\displaystyle 2^{12}}$${\displaystyle 2^{24}}$

ตัวอย่างเช่น ในภาษาโปรแกรม Cซึ่งการบวก การลบ และการคูณบนuint64_tชนิดข้อมูลจะทำในรูปแบบโมดูลัสทั้งหมดเราสามารถคำนวณตัวผกผันการคูณแบบโมดูลัสของจำนวนเต็มคี่aโมดูลัสโดยใช้ฟังก์ชันต่อไปนี้ซึ่งทำการวนซ้ำแบบนิวตัน-ราฟสันห้าครั้ง: ${\displaystyle 2^{64}}$${\displaystyle 2^{64}}$

#include <stdint.h> uint64_t modinv64 ( uint64_t a ) { uint64_t x = a ; for ( int i = 0 ; i < 5 ; i ++ ) x *= 2 - a * x ; return x ; }

ขึ้นอยู่กับแอปพลิเคชันและแพลตฟอร์ม อาจเหมาะสมที่จะปรับปรุงรูทีนนี้ให้ดียิ่งขึ้นไปอีก เช่น อาจข้ามการวนซ้ำสองสามครั้งแรกโดยใช้ตารางค้นหาเพื่อหาค่าผกผันโมดูลัสของกำลังสองที่ใหญ่กว่า นอกจากนี้ ในบางระบบ การคูณ 32 บิตอาจเร็วกว่าการคูณ 64 บิต ในกรณีนี้ สามารถเพิ่มความเร็วได้โดยใช้การคูณ 32 บิตจนกว่าจะได้ค่าผกผันโมดูลัส แล้วจึงเปลี่ยนไปใช้การคูณ 64 บิตหลังจากนั้น เมื่อใช้การปรับปรุงดังกล่าว รูทีนภาษา C ที่คำนวณค่าผกผันโมดูลัสของการคูณแบบโมดูลัสจะกลายเป็น: ${\displaystyle 2^{32}}$${\displaystyle 2^{64}}$

#include <stdint.h> uint64_t modinv64 ( uint64_t a ) { static const uint8_t tbl [ 256 ] = { 0 , 1 , 0 , 171 , 0 , 205 , 0 , 183 , 0 , 57 , 0 , 163 , 0 , 197 , 0 , 239 , 0 , 241 , 0 , 27 , 0 , 61 , 0 , 167 , 0 , 41 , 0 , 19 , 0 , 53 , 0 , 223 , 0 , 225 , 0 , 139 , 0 , 173 , 0 , 151 , 0 , 25 , 0 , 131 , 0 , 165 , 0 , 207 , 0 , 209 , 0 , 251 , 0 , 29 , 0 , 135 , 0 , 9 , 0 , 243 , 0 , 21 , 0 , 191 , 0 , 193 , 0 , 107 , 0 , 141 , 0 , 119 , 0 , 249 , 0 , 99 , 0 , 133 , 0 , 175 , 0 , 177 , 0 , 219 , 0 , 253 , 0 , 103 , 0 , 233 , 0 , 211 , 0 ,245 , 0 , 159 , 0 , 161 , 0 , 75 , 0 , 109 , 0 , 87 , 0 , 217 , 0 , 67 , 0 , 101 , 0 , 143 , 0 , 145 , 0 , 187 , 0 , 221 , 0 , 71 , 0 , 201 , 0 , 179 , 0 , 213 , 0 , 127 , 0 , 129 , 0 , 43 , 0 , 77 , 0 , 55 , 0 , 185 , 0 , 35 , 0 , 69 , 0 , 111 0 , 113 , 0 , 155 , 0 , 189 , 0 , 39 , 0 , 169 , 0 , 147 , 0 , 181 , 0 , 95 , 0 , 97 , 0 , 11 , 0 , 45 , 0 , 23 , 0 , 153 , 0 , 3 , 0 , 37 , 0 , 79 , 0 , 81 , 0 , 123 , 0 , 157 , 0 , 7 , 0 , 137 , 0 , 115 , 0 , 149 , 0 , 63 , 0 , 65 , 0 , 235​ , 0 ,13 , 0 , 247 , 0 , 121 , 0 , 227 , 0 , 5 , 0 , 47 , 0 , 49 , 0 , 91 , 0 , 125 , 0 , 231 , 0 , 105 , 0 , 83 , 0 , 117 , 0 , 31 , 0 , 33 , 0 , 203 , 0 , 237 , 0 , 215 , 0 , 89 , 0 , 195 , 0 , 229 , 0 , 15 , 0 , 17 , 0 , 59 , 0 , 93 , 0 , 199 , 0 , 73 , 0 , 51 , 0 , 85 , 0 , 255 }; uint32_t a32 = ( uint32_t ) a ; uint32_t x = tbl [ a & 0xFF ]; // ตัวผกผันโมดูลัส 2^8 x *= 2 - a32 * x ; // การคูณ 32 บิตx *= 2 - a32 * x ; // การคูณ 32 บิตreturn x * ( 2 - a * x ); // การคูณ 64 บิต}

การค้นหาตัวผกผันการคูณแบบโมดูลาร์มีแอปพลิเคชันมากมายในอัลกอริธึมที่อาศัยทฤษฎีเลขคณิตแบบโมดูลาร์ ตัวอย่างเช่น ในการเข้ารหัสลับ การใช้เลขคณิตแบบโมดูลาร์ช่วยให้การดำเนินการบางอย่างทำได้เร็วขึ้นและใช้พื้นที่จัดเก็บน้อยลง ในขณะที่การดำเนินการอื่นๆ ยากขึ้น^{[ 15 ]}คุณสมบัติทั้งสองนี้สามารถนำมาใช้ให้เกิดประโยชน์ได้ โดยเฉพาะอย่างยิ่งในอัลกอริธึม RSA การเข้ารหัสและถอดรหัสข้อความจะทำโดยใช้ตัวเลขสองตัวที่เป็นตัวผกผันการคูณเมื่อเทียบกับโมดูลัสที่เลือกอย่างระมัดระวัง ตัวเลขตัวหนึ่งจะถูกเปิดเผยและสามารถใช้ในขั้นตอนการเข้ารหัสอย่างรวดเร็ว ในขณะที่อีกตัวหนึ่งซึ่งใช้ในขั้นตอนการถอดรหัสจะถูกเก็บเป็นความลับ การหาตัวเลขที่ซ่อนไว้จากตัวเลขที่เปิดเผยนั้นถือว่าทำได้ยากในทางคอมพิวเตอร์ และนี่คือสิ่งที่ทำให้ระบบทำงานเพื่อรับประกันความเป็นส่วนตัว^{[ 16 ]}

ในอีกตัวอย่างหนึ่งในบริบทที่แตกต่างออกไป ลองพิจารณา ปัญหา การหารที่แม่นยำในวิทยาการคอมพิวเตอร์ ซึ่งคุณมีรายการตัวเลขขนาดคำคี่แต่ละตัวหารด้วยk ลงตัว และคุณต้องการหารตัวเลขเหล่านั้นทั้งหมดด้วยkวิธีแก้ปัญหาหนึ่งมีดังนี้:

1. ใช้ขั้นตอนวิธีแบบยุคลิดแบบขยายเพื่อคำนวณk ⁻¹ซึ่งเป็นตัวผกผันการคูณแบบมอดูลัสของk mod 2 ^wโดยที่wคือจำนวนบิตในคำ ตัวผกผันนี้จะมีอยู่เนื่องจากตัวเลขเป็นเลขคี่และมอดูลัสไม่มีตัวประกอบที่เป็นเลขคี่
2. สำหรับแต่ละตัวเลขในรายการ ให้คูณตัวเลขนั้นด้วยk ^{− 1}แล้วเลือกคำที่มีค่าน้อยที่สุดจากผลลัพธ์

ในเครื่องคอมพิวเตอร์หลายเครื่อง โดยเฉพาะเครื่องที่ไม่มีฮาร์ดแวร์รองรับการหาร การหารเป็นกระบวนการที่ช้ากว่าการคูณ ดังนั้นวิธีการนี้จึงช่วยเพิ่มความเร็วได้อย่างมาก ขั้นตอนแรกค่อนข้างช้า แต่จำเป็นต้องทำเพียงครั้งเดียวเท่านั้น

ตัวผกผันการคูณแบบโมดูลาร์ถูกนำมาใช้เพื่อหาคำตอบของระบบสมการเชิงเส้นที่รับประกันโดยทฤษฎีบทเศษเหลือของจีน

ตัวอย่างเช่น ระบบ

X ≡ 4 (mod 5)

X ≡ 4 (mod 7)

X ≡ 6 (mod 11)

มีคำตอบร่วมกัน เนื่องจาก 5, 7 และ 11 เป็นจำนวนเฉพาะสัมพัทธ์ กัน คำตอบหนึ่งคือ

X = t ₁ (7 × 11) × 4 + t ₂ (5 × 11) × 4 + t ₃ (5 × 7) × 6

ที่ไหน

t ₁ = 3 คือตัวผกผันการคูณแบบโมดูลาร์ของ 7 × 11 (mod 5)

t ₂ = 6 คือตัวผกผันการคูณแบบโมดูลาร์ของ 5 × 11 (mod 7) และ

t ₃ = 6 คือตัวผกผันการคูณแบบโมดูลาร์ของ 5 × 7 (mod 11)

ดังนั้น,

X = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504

และในรูปแบบย่อที่เป็นเอกลักษณ์

X ≡ 3504 ≡ 39 (mod 385)

เนื่องจาก 385 คือค.ร.ม.ของ 5, 7 และ 11

นอกจากนี้ ตัวผกผันการคูณแบบโมดูลาร์ยังมีบทบาทสำคัญในนิยามของผลรวมคลูสเตอร์แมนอีก ด้วย

• เครื่องกำเนิดเลขสุ่มแบบผกผันเชิงสอดคล้อง – เครื่องกำเนิดเลขสุ่มเทียมที่ใช้ตัวผกผันการคูณแบบโมดูลาร์
• การสร้างใหม่เชิงเหตุผล (คณิตศาสตร์)

• ไวส์สไตน์, เอริก ดับเบิลยู. "Modular Inverse" . แมทเวิลด์ .
• เกวารา วาสเกซ เฟอร์นันโดได้นำเสนอตัวอย่างการแก้ปัญหาตัวผกผันการคูณแบบโมดูลัสโดยใช้อัลกอริทึมของยูคลิด
• ตัวผกผันการคูณจำนวนเต็มโดยใช้วิธีของนิวตันให้ขั้นตอนวิธีที่รวดเร็วในการคำนวณตัวผกผันการคูณโมดูลัสกำลังของ 2