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

คำนวณเลขชี้กำลังมอดุลาร์ a^b mod n อย่างมีประสิทธิภาพโดยใช้อัลกอริทึมการยกกำลังแบบไบนารี (fast power) ป้อนฐาน เลขชี้กำลัง และมอดุลัส เพื่อรับผลลัพธ์ทันทีพร้อมการแสดงขั้นตอนวิธี squaring-and-multiply การแจกแจงเลขฐานสอง และบริบททางด้านวิทยาการรหัสลับ

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

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

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

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

🔐

การเข้ารหัส RSA

เข้ารหัสและถอดรหัสข้อความโดยใช้การยกกำลังมอดุลาร์กับผลคูณของจำนวนเฉพาะขนาดใหญ่

🤝

Diffie-Hellman

โปรโตคอลการแลกเปลี่ยนคีย์ที่คำนวณ g^a mod p เพื่อความปลอดภัยของความลับที่แชร์ร่วมกัน

✍

ลายเซ็นดิจิทัล

DSA, ECDSA และ EdDSA ล้วนอาศัยการยกกำลังมอดุลาร์

🧪

การทดสอบความเป็นจำนวนเฉพาะ

การทดสอบ Fermat และ Miller-Rabin ใช้ a^(n-1) mod n เพื่อตรวจสอบความเป็นจำนวนเฉพาะ

🏆

การเขียนโปรแกรมเชิงแข่งขัน

เลขคณิตมอดุลาร์พร้อมการยกกำลังที่รวดเร็วเป็นสิ่งจำเป็นสำหรับโจทย์การแข่งขัน

🔗

บล็อกเชน

Proof-of-work และการแฮชทางรหัสลับอาศัยเลขคณิตมอดุลาร์

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

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

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

ขั้นตอนที่ 1: แปลงเลขชี้กำลัง \(b\) เป็นเลขฐานสอง

ขั้นตอนที่ 2: กำหนดค่าเริ่มต้น result = 1 (หรือเท่ากับฐานหากบิตแรกเป็น 1)

ขั้นตอนที่ 3: สำหรับแต่ละบิตถัดไป: ยกกำลังสอง ผลลัพธ์ (mod n) หากบิตเป็น 1 ให้ คูณ ด้วยฐาน (mod n) เพิ่มเติม

ขั้นตอนที่ 4: หลังจากประมวลผลบิตทั้งหมดแล้ว ผลลัพธ์ที่ได้คือ \(a^b \bmod n\)

รหัสจำลอง (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

สูตรสำคัญ

คุณสมบัติ	สูตร	คำอธิบาย
การยกกำลังมอดุลาร์	\(a^b \bmod n\)	เศษที่เหลือจากการหาร a^b ด้วย n
ทฤษฎีบทน้อยของแฟร์มาต์	\(a^{p-1} \equiv 1 \pmod{p}\)	สำหรับจำนวนเฉพาะ p และ ห.ร.ม.(a,p)=1
ทฤษฎีบทของออยเลอร์	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	สำหรับ ห.ร.ม.(a,n)=1 โดยที่ φ คือฟังก์ชันโทเชียนต์ของออยเลอร์
ความซับซ้อนของวิธีไบนารี	\(O(\log b)\) การคูณ	ใช้การคูณมอดุลาร์ไม่เกิน 2·log₂(b) ครั้ง
การเข้ารหัส RSA	\(c = m^e \bmod n\)	เข้ารหัสข้อความ m ด้วยคีย์สาธารณะ (e, n)
การถอดรหัส RSA	\(m = c^d \bmod n\)	ถอดรหัสข้อความลับ c ด้วยคีย์ส่วนตัว d

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

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

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

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

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

การยกกำลังมอดุลาร์คืออะไร?

การยกกำลังมอดุลาร์คือการคำนวณ (a^b) mod n — เป็นการยกกำลังตัวเลขฐานแล้วหาเศษที่เหลือจากการหารด้วยมอดุลัส เป็นการดำเนินการหลักในวิทยาการรหัสลับแบบคีย์สาธารณะ (RSA, Diffie-Hellman, ElGamal) และใช้กันอย่างแพร่หลายในทฤษฎีจำนวน การเขียนโปรแกรมเชิงแข่งขัน และวิทยาการคอมพิวเตอร์ วิธีการยกกำลังแบบไบนารีช่วยให้คำนวณได้อย่างมีประสิทธิภาพในการคูณระดับ O(log b)

การยกกำลังแบบไบนารี (Exponentiation by Squaring) ทำงานอย่างไร?

การยกกำลังแบบไบนารีจะแปลงเลขชี้กำลังเป็นเลขฐานสอง จากนั้นประมวลผลแต่ละบิตจากซ้ายไปขวา (หรือขวาไปซ้าย) สำหรับแต่ละบิต จะทำการยกกำลังสองผลลัพธ์ปัจจุบันมอดุลัส n หากบิตนั้นเป็น 1 จะทำการคูณผลลัพธ์ด้วยฐานมอดุลัส n เพิ่มเติม วิธีนี้จะลดจำนวนการคูณจาก b−1 (วิธีปกติ) เหลือเพียงไม่เกิน 2×log₂(b) ทำให้สามารถคำนวณด้วยเลขชี้กำลังที่มีขนาดใหญ่มากได้

ทำไมการยกกำลังมอดุลาร์ถึงสำคัญในวิทยาการรหัสลับ?

การเข้ารหัส RSA คำนวณ c = m^e mod n สำหรับการเข้ารหัส และ m = c^d mod n สำหรับการถอดรหัส โดยที่ n คือผลคูณของจำนวนเฉพาะขนาดใหญ่สองจำนวน และเลขชี้กำลังอาจมีความยาวหลายร้อยหลัก หากไม่มีการยกกำลังมอดุลาร์ที่รวดเร็ว การดำเนินการเหล่านี้จะเป็นไปไม่ได้ในทางคอมพิวเตอร์ ความปลอดภัยขึ้นอยู่กับความจริงที่ว่าการดำเนินการย้อนกลับ (การคำนวณลอการิทึมแบบไม่ต่อเนื่อง) นั้นเชื่อกันว่าไม่สามารถทำได้ในทางคอมพิวเตอร์

ฐานสามารถเป็นค่าลบได้หรือไม่?

ได้ รองรับฐานที่เป็นค่าลบอย่างสมบูรณ์ เครื่องคำนวณจะลดทอนฐานด้วยมอดุลัส n ก่อน (โดยใช้เลขคณิตมอดุลาร์ของ Python ซึ่งให้ผลลัพธ์ที่ไม่เป็นลบเสมอสำหรับ n ที่เป็นบวก) ตัวอย่างเช่น (−3)^2 mod 7 = 9 mod 7 = 2 โดยผลลัพธ์ที่เป็นลบจะไม่เกิดขึ้นเนื่องจากการลดทอนมอดุลาร์จะให้ค่าในช่วง [0, n−1] เสมอ

จะเกิดอะไรขึ้นเมื่อมอดุลัสเป็น 1?

จำนวนเต็มใดๆ มอดุลัส 1 จะเท่ากับ 0 เสมอ เนื่องจากการหารจำนวนเต็มใดๆ ด้วย 1 จะได้ตัวมันเองโดยเหลือเศษ 0 ดังนั้น a^b mod 1 = 0 สำหรับทุกค่าของ a และ b เครื่องคำนวณจะจัดการกรณีนี้เป็นกรณีพิเศษ

อ้างอิงเนื้อหา หน้าหรือเครื่องมือนี้ว่า:

"เครื่องคำนวณเลขชี้กำลังมอดุลาร์" ที่ https://MiniWebtool.com/th/เครื่องคำนวณเลขชี้กำลังมอดุลาร์/ จาก MiniWebtool, https://MiniWebtool.com/

โดยทีมงาน miniwebtool. อัปเดตเมื่อ: 2026-04-16

คุณสามารถลองใช้ AI แก้ปัญหาคณิตศาสตร์ GPT ของเรา เพื่อแก้ไขปัญหาทางคณิตศาสตร์ของคุณผ่านคำถามและคำตอบด้วยภาษาธรรมชาติ.