-
Notifications
You must be signed in to change notification settings - Fork 67
/
Copy pathfermats_little_theorem.cpp
43 lines (36 loc) · 1.01 KB
/
fermats_little_theorem.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// C++ program to find modular inverse of a
// under modulo m using Fermat's little theorem.
// This program works only if m is prime.
#include <bits/stdc++.h>
using namespace std;
// To compute x raised to power y under modulo m
int power(int x, unsigned int y, unsigned int m);
// Function to find modular inverse of a under modulo m
// Assumption: m is prime
void modInverse(int a, int m)
{
if (__gcd(a, m) != 1)
cout << "Inverse doesn't exist";
else {
// If a and m are relatively prime, then
// modulo inverse is a^(m-2) mode m
cout << "Modular multiplicative inverse is "
<< power(a, m - 2, m);
}
}
// To compute x^y under modulo m
int power(int x, unsigned int y, unsigned int m)
{
if (y == 0)
return 1;
int p = power(x, y / 2, m) % m;
p = (p * p) % m;
return (y % 2 == 0) ? p : (x * p) % m;
}
// Driver Program
int main()
{
int a = 3, m = 11;
modInverse(a, m);
return 0;
}