資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 程式實現費馬小定理
費馬小定理是初等數論的一個基本結果，是費馬素數檢驗的基礎。該定理以皮埃爾·德·費馬命名，他於 1640 年提出了該定理。該定理指出，如果 p 是素數，則對於任何整數 a，數 ap–a 是 p 的整數倍。
演算法
Begin Function power() is used to compute a raised to power b under modulo M function modInverse() to find modular inverse of a under modulo m : Let m is prime If a and m are relatively prime, then modulo inverse is a^(m - 2) mod m End
示例程式碼
#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
已更新於： 30-7 月-2019
699 次瀏覽
廣告