หารากที่สองภายใต้โมด्यูล로 p (อัลกอริทึม Shanks-Tonelli) ใน C++

ในปัญหานี้ เราได้รับค่า n และจำนวนเฉพาะ p งานของเราคือการหารากที่สองภายใต้โมดูลอ p (Square Root under Modulo p)

ตัวอย่างเพื่อความเข้าใจ

Input : n = 4, p = 11 
Output : 9

แนวทางแก้ปัญหา

เราจะใช้ อัลกอริทึม Tonelli-Shanks ซึ่งใช้ในคณิตศาสตร์โมดูลอ เพื่อแก้สมการสมมาตรในรูป x² ≡ n (mod p)

ขั้นตอนของอัลกอริทึม Tonelli-Shanks

1. ขั้นตอนที่ 1 − คำนวณ n^((p-1)/2) (mod p) หากผลลัพธ์เป็น p-1 แสดงว่าไม่มีรากที่สองภายใต้โมดูลอ
2. ขั้นตอนที่ 2 − แยก p-1 ให้อยู่ในรูป s × 2^e โดยที่ s เป็นเลขคี่บวก และ e เป็นจำนวนเต็มบวก
3. ขั้นตอนที่ 3 − หา q ที่ทำให้ q^((p-1)/2) ≡ -1 (mod p)
4. ขั้นตอนที่ 4 − ใช้ลูปเพื่ออัปเดตค่า x จนกว่าจะได้คำตอบ

ตัวอย่างโค้ด

#include <iostream>
#include <math.h>
using namespace std;

int powerMod(int base, int exponent, int modulus) {
    int result = 1;
    base = base % modulus;
    while (exponent > 0) {
        if (exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int orderValues(int p, int b) {
    if (gcd(p, b) != 1)
        return -1;
    int k = 3;
    while (1) {
        if (powerMod(b, k, p) == 1)
            return k;
        k++;
    }
}

int findx2e(int x, int& e) {
    e = 0;
    while (x % 2 == 0) {
        x /= 2;
        e++;
    }
    return x;
}

int calcSquareRoot(int n, int p) {
    if (gcd(n, p) != 1)
        return -1;
    
    if (powerMod(n, (p - 1) / 2, p) == (p - 1))
        return -1;
    
    int s, e;
    s = findx2e(p - 1, e);
    
    int q;
    for (q = 2; ; q++) {
        if (powerMod(q, (p - 1) / 2, p) == (p - 1))
            break;
    }
    
    int x = powerMod(n, (s + 1) / 2, p);
    int b = powerMod(n, s, p);
    int g = powerMod(q, s, p);
    int r = e;
    
    while (1) {
        int m;
        for (m = 0; m < r; m++) {
            if (orderValues(p, b) == -1)
                return -1;
            if (orderValues(p, b) == pow(2, m))
                break;
        }
        if (m == 0)
            return x;
        
        x = (x * powerMod(g, pow(2, r - m - 1), p)) % p;
        g = powerMod(g, pow(2, r - m), p);
        b = (b * g) % p;
        if (b == 1)
            return x;
        r = m;
    }
}

int main() {
    int n = 3;
    int p = 13;
    int sqrtVal = calcSquareRoot(n, p);
    if (sqrtVal == -1)
        cout << "Modular square root does not exist";
    else
        cout << "Modular square root of the number is " << sqrtVal;
    return 0;
}

ผลลัพธ์

Modular square root of the number is 9