โปรแกรม C++ ทดสอบจำนวนเฉพาะด้วยอัลกอริทึม Solovay-Strassen

การทดสอบจำนวนเฉพาะแบบ Solovay-Strassen

การทดสอบ Solovay-Strassen ใช้เพื่อตรวจสอบว่าจำนวนใดจำนวนหนึ่งเป็นจำนวนประกอบ (composite) หรือเป็นจำนวนเฉพาะได้ (probably prime)

อัลกอริทึม

Begin
    ฟังก์ชัน modulo สำหรับการคำนวณแบบทวิภาค
    รับพารามิเตอร์ m_base, m_exp, m_mod แบบ long
    ตัวแปร a = 1, b = m_base
    while (m_exp > 0)
        if (m_exp % 2 == 1) a = (a * b) % m_mod
        b = (b * b) % m_mod
        m_exp = m_exp / 2
    Return a % m_mod
End

Begin
    ฟังก์ชัน Jacobian คำนวณสัญลักษณ์ Jacobian
    รับพารามิเตอร์ CJ_a, CJ_n แบบ long
    if (!CJ_a) return 0
    answer = 1
    if (CJ_a < 0) CJ_a = -CJ_a, if (CJ_n % 4 == 3) answer = -answer
    if (CJ_a == 1) return answer
    while (CJ_a)
        if (CJ_a < 0) CJ_a = -CJ_a, if (CJ_n % 4 == 3) answer = -answer
        while (CJ_a % 2 == 0) CJ_a /= 2, if (CJ_n % 8 == 3 || CJ_n % 8 == 5) answer = -answer
        swap(CJ_a, CJ_n)
        if (CJ_a % 4 == 3 && CJ_n % 4 == 3) answer = -answer
        CJ_a = CJ_a % CJ_n
        if (CJ_a > CJ_n / 2) CJ_a = CJ_a - CJ_n
    if (CJ_n == 1) return answer
End

Begin
    ฟังก์ชัน SolovayStrassen ทดสอบจำนวนเฉพาะ
    รับพารามิเตอร์ SS_p (long), itr (int)
    if (SS_p < 2) return false
    if (SS_p != 2 && SS_p % 2 == 0) return false
    for i = 0 to itr-1
        a = rand() % (SS_p - 1) + 1
        jacob = (SS_p + Jacobian(a, SS_p)) % SS_p
        mod = modulo(a, (SS_p - 1) / 2, SS_p)
        if (!jacob || mod != jacob) return false
    return true
End

Begin
    โปรแกรมหลัก
    iter = 50
    รับ num1, num2
    เรียก SolovayStrassen แสดงผลเป็นจำนวนเฉพาะหรือประกอบ
End

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

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

long modulo(long m_base, long m_exp, long m_mod) {
    long a = 1, b = m_base;
    while (m_exp > 0) {
        if (m_exp % 2 == 1) a = (a * b) % m_mod;
        b = (b * b) % m_mod;
        m_exp = m_exp / 2;
    }
    return a % m_mod;
}

int Jacobian(long CJ_a, long CJ_n) {
    if (!CJ_a) return 0;
    int answer = 1;
    if (CJ_a < 0) {
        CJ_a = -CJ_a;
        if (CJ_n % 4 == 3) answer = -answer;
    }
    if (CJ_a == 1) return answer;
    while (CJ_a) {
        if (CJ_a < 0) {
            CJ_a = -CJ_a;
            if (CJ_n % 4 == 3) answer = -answer;
        }
        while (CJ_a % 2 == 0) {
            CJ_a = CJ_a / 2;
            if (CJ_n % 8 == 3 || CJ_n % 8 == 5) answer = -answer;
        }
        swap(CJ_a, CJ_n);
        if (CJ_a % 4 == 3 && CJ_n % 4 == 3) answer = -answer;
        CJ_a = CJ_a % CJ_n;
        if (CJ_a > CJ_n / 2) CJ_a = CJ_a - CJ_n;
    }
    if (CJ_n == 1) return answer;
    return 0;
}

bool SolovayStrassen(long SS_p, int itr) {
    if (SS_p < 2) return false;
    if (SS_p != 2 && SS_p % 2 == 0) return false;
    for (int i = 0; i < itr; i++) {
        long a = rand() % (SS_p - 1) + 1;
        long jacob = (SS_p + Jacobian(a, SS_p)) % SS_p;
        long mod = modulo(a, (SS_p - 1) / 2, SS_p);
        if (!jacob || mod != jacob) return false;
    }
    return true;
}

int main() {
    int iter = 50;
    long num1, num2;
    cout << "Enter the first number: ";
    cin >> num1;
    cout << endl;
    if (SolovayStrassen(num1, iter))
        cout << num1 << " is a prime number\n" << endl;
    else
        cout << num1 << " is a composite number\n" << endl;
    cout << "Enter another number: ";
    cin >> num2;
    cout << endl;
    if (SolovayStrassen(num2, iter))
        cout << num2 << " is a prime number\n" << endl;
    else
        cout << num2 << " is a composite number\n" << endl;
    return 0;
}

ผลลัพธ์

Enter the first number: 24
24 is a composite number
Enter another number: 23
23 is a prime number