หาค่ายกกำลังซ้อนภายใต้ modulo ของจำนวนเฉพาะใน C++

ในปัญหานี้ เราได้รับค่าสี่ค่า A, B, C, M (จำนวนเฉพาะ) งานของเราคือ หาค่ายกกำลังซ้อนภายใต้ modulo ของจำนวนเฉพาะ

เราต้องการหาค่าของ (A ^ (B ^ C)) (mod M)

มาดูตัวอย่างเพื่อเข้าใจปัญหา

Input

A = 3, B = 6, C = 2, M = 11

Output

3

อธิบาย

(A ^ (B ^ C)) = (3 ^ (6 ^ 2)) = (3 ^ (36)) (mod 11) = 3

วิธีแก้ปัญหา

วิธีแก้ที่ง่ายคือคำนวณค่า (A ^ (B ^ C)) โดยตรง ซึ่งทำโดยคำนวณค่า (B^C) ก่อน แล้วค่อย (A ^ (B ^ C)) แล้วหา modulo แต่ (B^C) จะให้ค่ามากมาย การเก็บอาจเป็นปัญหา และการคำนวณอาจเกิด overflow

ดังนั้น วิธีที่มีประสิทธิภาพมากกว่าคือใช้ทฤษฎีบทเล็กของ Fermat (Fermat's Little Theorem) เพื่อหาค่า

ทฤษฎย์บทคือ

a^(m-1) = 1 (mod M) โดยที่ m เป็นจำนวนเฉพาะ

ใช้ทฤษฎีนี้ เราจะแปลง bc ของปัญหาเราให้อยู่ในรูป

x*(M-1) + y สำหรับค่า M ที่กำหนด

โดยใช้ทฤษฎีของ Fermat ส่วน A^(x*(M-1)) จะกลายเป็น 1

สิ่งนี้ลดการคำนวณเหลือ การหาค่า A^y

ค่าของ y สามารถคำนวณได้จาก

B^c = x*(M-1) + y

ทำให้ y เป็นเศษที่เหลือเมื่อเราหาร B^c ด้วย (M-1)

ดังนั้น y = B^c % (M-1)

นี่ทำให้ผลลัพธ์ง่ายขึ้นมาก เราต้องหาแค่

(A ^ ((B^C) % (M-1)) % M

โปรแกรมแสดงการทำงานของวิธีแก้

ตัวอย่าง

#include<iostream> 
using namespace std; 

int calcPowerMod(int x, int y, int p) { 
    int powMod = 1; 
    x = x % p; 
    while (y > 0) { 
        if (y & 1) 
            powMod = (powMod*x) % p; 
        y /= 2; 
        x = (x*x) % p; 
    } 
    return powMod; 
} 

int findPowerOfPowerMod(int A, int B, int C, int M) { 
    return calcPowerMod(A, calcPowerMod(B, C, M-1), M); 
} 

int main() { 
    int A = 3, B = 6, C = 2, M = 11; 
    cout<<"The power of power under modulo is "<<findPowerOfPowerMod(A, B, C, M); 
    return 0; 
}

ผลลัพธ์

The power of power under modulo is 3