C++ प्रोग्राम सोलोवे-स्ट्रासेन प्राइमैलिटी टेस्ट लागू करने के लिए

सोलोवे-स्ट्रासेन प्राइमैलिटी टेस्ट का उपयोग यह जांचने के लिए किया जाता है कि कोई संख्या कम्पोजिट है या संभावित रूप से प्राइम।

एल्गोरिदम

1. मोड्यूलो फंक्शन: बाइनरी एक्सपोनेंशिएशन के लिए।
2. जैकोबियन फंक्शन: दी गई संख्या का जैकोबियन सिंबल कैलकुलेट करने के लिए।
3. सोलोवेस्ट्रासेन फंक्शन: प्राइमैलिटी टेस्ट करने के लिए।

C++ कार्यान्वयन

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

long modulo(long base, long exp, long mod) {
    long a = 1;
    long b = base;
    while (exp > 0) {
        if (exp % 2 == 1)
            a = (a * b) % mod;
        b = (b * b) % mod;
        exp = exp / 2;
    }
    return a % mod;
}

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

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

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

आउटपुट

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