หารากที่สองภายใต้โมดูลอ p (เมื่อ p อยู่ในรูป 4i+3) ใน C++

ในปัญหานี้ เราได้รับค่า n และจำนวนเฉพาะ p งานของเราคือการหารากที่สองภายใต้โมดูลอ p เมื่อ p อยู่ในรูป (4i + 3) หมายถึง p % 4 = 3 สำหรับ i > 1 และ p เป็นจำนวนเฉพาะ

ตัวอย่างจำนวนที่อยู่ในรูปนี้: 7, 11, 19, 23, 31...

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

Input : n = 3, p = 7 
Output : (รากที่สองภายใต้โมดูลอ)

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

วิธีที่ 1: ใช้ลูปตรวจสอบทุกค่า (Brute Force)

วนลูปจาก 2 ถึง (p-1) ตรวจสอบว่ายกกำลังสองแล้ว mod p เท่ากับ n หรือไม่

ตัวอย่างโค้ด (วิธี Brute Force)

#include <iostream>
using namespace std;

void findSquareRootMod(int n, int p) {
    n = n % p;
    for (int i = 2; i < p; i++) {
        if ((i * i) % p == n) {
            cout << "Square root under modulo is " << i;
            return;
        }
    }
    cout << "Square root doesn't exist";
}

int main() {
    int p = 11;
    int n = 3;
    findSquareRootMod(n, p);
    return 0;
}

ผลลัพธ์

Square root under modulo is 5

วิธีที่ 2: ใช้สูตรโดยตรง (มีประสิทธิภาพมากกว่า)

หาก p อยู่ในรูป (4i + 3) และมีรากที่สองภายใต้โมดูลออยู่ รากจะอยู่ในรูป ±n^((p+1)/4) (mod p)

ตัวอย่างโค้ด (วิธีสูตรโดยตรง)

#include <iostream>
using namespace std;

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

void squareRoot(int n, int p) {
    if (p % 4 != 3) {
        cout << "Invalid Input";
        return;
    }
    
    n = n % p;
    int sr = calcPowerVal(n, (p + 1) / 4, p);
    
    if ((sr * sr) % p == n) {
        cout << "Square root under modulo is " << sr;
        return;
    }
    
    sr = p - sr;
    if ((sr * sr) % p == n) {
        cout << "Square root is " << sr;
        return;
    }
    
    cout << "Square root doesn't exist ";
}

int main() {
    int p = 11;
    int n = 4;
    squareRoot(n, p);
    return 0;
}

ผลลัพธ์

Square root under modulo is 9