C++ প্রোগ্রাম: রবিন-মিলার মৌলিকতা পরীক্ষা বাস্তবায়ন

রবিন-মিলার মৌলিকতা পরীক্ষা একটি দত্তক সংখ্যা মৌলিক কিনা তা যাচাই করতে ব্যবহৃত হয়। এটি ফার্মাট মৌলিকতা পরীক্ষা এবং সোলোভে-স্ট্রেসেন পরীক্ষার সাথে মিলিত। এই পরীক্ষা প্রথমে রুশ গণিতজ্ঞ এম. এম. আর্তুজভ আবিষ্কার করেছিলেন।

অ্যালগরিদম

শুরু
    ll mulmod(ll a, ll b, ll m)
    ll x = 0, y = a mod m
    যতক্ষণ (b > 0)
        যদি (b mod 2 == 1)
            x = (x + y) mod m
        y = (y * 2) mod m
        b = b / 2
    x mod m ফেরত দাও
শেষ

শুরু
    ll modulo(ll base, ll e, ll m)
    ইনিশিয়ালাইজ:
    ll x = 1
    ll y = base
    যতক্ষণ (e > 0)
        যদি (e mod 2 == 1)
            x = (x * y) mod m
        y = (y * y) mod m
        e = e / 2
    x mod m ফেরত দাও
শেষ

শুরু
    bool Miller(ll p, int iteration)
    যদি (p < 2)
        false ফেরত দাও
    যদি (p != 2 এবং p mod 2 == 0)
        false ফেরত দাও
    কম্পিউট: ll s = p - 1
    যতক্ষণ (s mod 2 == 0)
        s = s / 2
    for i = 0 to iteration - 1
        ll a = rand() mod (p - 1) + 1, temp = s
        ll mod = modulo(a, temp, p)
        যতক্ষণ (temp != p - 1 এবং mod != 1 এবং mod != p - 1)
            mod = mulmod(mod, mod, p)
            temp *= 2
        যদি (mod != p - 1 && temp % 2 == 0)
            false ফেরত দাও
        অন্যথায়
            true ফেরত দাও
শেষ

উদাহরণ কোড

#include <iostream>
#include <stdlib.h>
#define ll long long
using namespace std;

ll mulmod(ll a, ll b, ll m) {
    ll x = 0, y = a % m;
    while (b > 0) {
        if (b % 2 == 1) {
            x = (x + y) % m;
        }
        y = (y * 2) % m;
        b /= 2;
    }
    return x % m;
}

ll modulo(ll base, ll e, ll m) {
    ll x = 1;
    ll y = base;
    while (e > 0) {
        if (e % 2 == 1)
            x = (x * y) % m;
        y = (y * y) % m;
        e = e / 2;
    }
    return x % m;
}

bool Miller(ll p, int iteration) {
    if (p < 2) {
        return false;
    }
    if (p != 2 && p % 2 == 0) {
        return false;
    }
    ll s = p - 1;
    while (s % 2 == 0) {
        s /= 2;
    }
    for (int i = 0; i < iteration; i++) {
        ll a = rand() % (p - 1) + 1, temp = s;
        ll mod = modulo(a, temp, p);
        while (temp != p - 1 && mod != 1 && mod != p - 1) {
            mod = mulmod(mod, mod, p);
            temp *= 2;
        }
        if (mod != p - 1 && temp % 2 == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int iteration = 10;
    ll num;
    cout << "মৌলিকতা পরীক্ষার জন্য পূর্ণসংখ্যা দিন: ";
    cin >> num;
    if (Miller(num, iteration))
        cout << num << " মৌলিক" << endl;
    else
        cout << num << " মৌলিক নয়" << endl;
    return 0;
}

আউটপুট

মৌলিকতা পরীক্ষার জন্য পূর্ণসংখ্যা দিন: 26
26 মৌলিক নয়