C++ প্রোগ্রাম: ফার্মেটস লিটল থিওরেম বাস্তবায়ন

ফার্মেটস লিটল থিওরেম এলিমেন্টারি নাম্বার থিওরির মৌলিক ফলাফলগুলোর একটি এবং এটি ফার্মেট প্রাইম্যালিটি টেস্টের ভিত্তি। এই থিওরেমটি পিয়ের ডি ফার্মেটের নামের সাথে জড়িত, যিনি ১৬৪০ সালে এটি স্টেট করেছেন। থিওরেমটি বলে যে যদি p একটি প্রাইম নম্বর হয়, তবে যেকোনো ইন্টিজার a-এর জন্য, a^p−a নম্বরটি p-এর একটি ইন্টিজার মাল্টিপল।

অ্যালগরিদম

শুরু
  power() ফাংশন ব্যবহার করা হয় a-এর b পাওয়ার মডুলো M-এ কম্পিউট করতে
  modInverse() ফাংশন ব্যবহার করা হয় a-এর মডুলার ইনভার্স m মডুলোতে বের করতে:
  m হলো প্রাইম
  If a এবং m রিলেটিভলি প্রাইম, তবে
    মডুলো ইনভার্স হলো a^(m - 2) mod m
শেষ

উদাহরণ কোড

#include <iostream>
using namespace std;

int pow(int a, int b, int M) {
    int x = 1, y = a;
    while (b > 0) {
        if (b % 2 == 1) {
            x = (x * y);
            if (x > M)
                x %= M;
        }
        y = (y * y);
        if (y > M)
            y %= M;
        b /= 2;
    }
    return x;
}

int modInverse(int a, int m) {
    return pow(a, m - 2, m);
}

int main() {
    int a, m;
    cout << "Enter number to find modular multiplicative inverse: ";
    cin >> a;
    cout << "Enter Modular Value: ";
    cin >> m;
    cout << modInverse(a, m) << endl;
}

আউটপুট

Enter number to find modular multiplicative inverse: 26
Enter Modular Value: 7
3