เครื่องคำนวณเลขชี้กำลังมอดุลาร์

เกี่ยวกับ เครื่องคำนวณเลขชี้กำลังมอดุลาร์

เครื่องคำนวณเลขชี้กำลังมอดุลาร์ ใช้สำหรับคำนวณ \(a^b \bmod n\) — คือการยกกำลังเลขฐาน \(a\) ด้วยเลขชี้กำลัง \(b\) แล้วหาเศษที่เหลือจากการหารด้วยมอดุลัส \(n\) โดยใช้ อัลกอริทึมการยกกำลังแบบไบนารี (หรือเรียกว่า Fast Power หรือ Exponentiation by Squaring) ซึ่งช่วยลดจำนวนการดำเนินการจากการคูณระดับ \(O(b)\) เหลือเพียง \(O(\log b)\) นี่คืออัลกอริทึมเดียวกันกับที่ใช้ในการปรับใช้ทางวิทยาการรหัสลับในโลกแห่งความเป็นจริง เช่น RSA, Diffie-Hellman และ ElGamal

การประยุกต์ใช้งานการยกกำลังมอดุลาร์

อัลกอริทึมการยกกำลังแบบไบนารีทำงานอย่างไร

แนวคิดหลักคือเราสามารถแยกเลขชี้กำลังใดๆ ให้เป็นผลรวมของเลขยกกำลังของ 2 โดยใช้การแทนค่าด้วยเลขฐานสอง ตัวอย่างเช่น \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\) ดังนั้น \(a^{13} = a^{8} \times a^{4} \times a^{1}\)

อัลกอริทึมจะประมวลผลตัวเลขฐานสองของเลขชี้กำลังจากซ้ายไปขวา:

รหัสจำลอง (Pseudocode)

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // บิตเป็น 1
            result = (result × base) mod mod
        exp = exp >> 1        // เลื่อนบิตไปทางขวา (หารด้วย 2)
        base = (base × base) mod mod
    return result

สูตรสำคัญ

วิธีใช้งานเครื่องคำนวณเลขชี้กำลังมอดุลาร์

1. ป้อนฐาน (a): นี่คือตัวเลขที่คุณต้องการยกกำลัง สามารถเป็นค่าบวกหรือลบก็ได้ ตัวอย่างเช่น ป้อน 7 สำหรับการคำนวณ 7^256 mod 13
2. ป้อนเลขชี้กำลัง (b): ต้องเป็นจำนวนเต็มที่ไม่เป็นลบ แทนค่าพลังงานสำหรับการยกกำลัง สำหรับการประยุกต์ใช้ทางรหัสลับ ค่านี้อาจมีขนาดใหญ่มาก (เครื่องคำนวณรองรับสูงสุด 10^18)
3. ป้อนมอดุลัส (n): ต้องเป็นจำนวนเต็มบวก คือตัวเลขที่คุณนำไปหารเพื่อหาเศษ ใน RSA มักจะเป็นผลคูณของจำนวนเฉพาะขนาดใหญ่สองจำนวน
4. คลิกคำนวณ: เครื่องคำนวณจะหาค่า a^b mod n โดยใช้การยกกำลังแบบไบนารีและแสดงผลลัพธ์ทันที
5. ดูแอนิเมชัน: กดปุ่ม "เล่น" เพื่อดูอัลกอริทึมการยกกำลังแบบไบนารีทำงานทีละขั้นตอน แต่ละบิตของเลขชี้กำลังจะถูกประมวลผลตามลำดับ โดยแสดงว่าอัลกอริทึมทำการยกกำลังสอง หรือยกกำลังสองและคูณ
6. ตรวจสอบการทำงาน: ตารางแสดงขั้นตอนจะแสดงการคำนวณระดับกลางทุกขั้นตอน และการเปรียบเทียบประสิทธิภาพจะแสดงให้เห็นว่าการยกกำลังแบบไบนารีเร็วกว่าการคูณซ้ำแบบปกติเพียงใด

ทำไมการยกกำลังแบบไบนารีถึงรวดเร็ว

พิจารณาการคำนวณ \(2^{1000} \bmod 13\) วิธีปกติจะต้องใช้การคูณถึง 999 ครั้ง แต่การยกกำลังแบบไบนารีจะแปลง 1000 เป็นเลขฐานสอง (1111101000) ซึ่งมี 10 บิต โดยต้องการการยกกำลังสองเพียง 9 ครั้ง บวกกับการคูณเพิ่มอีกเล็กน้อยสำหรับแต่ละบิตที่เป็น '1' — รวมแล้วใช้การดำเนินการประมาณ 15 ครั้งเท่านั้น นั่นหมายถึง ลดการดำเนินการลงประมาณ 98.5% สำหรับเลขชี้กำลังในระดับรหัสลับที่มีหลายร้อยหลัก ความแตกต่างจะมหาศาลมาก: วิธีไบนารีใช้การดำเนินการเพียงหลักพันครั้ง ในขณะที่วิธีปกติอาจต้องใช้การดำเนินการมากกว่าจำนวนอะตอมในจักรวายเสียอีก

คำถามที่พบบ่อย (FAQ)