Question

Find the multiplicative inverse of 14 in GF(31) domain using Fermat’s little theorem. Show your work.

Answer 1

Fermat’s little theorem states that if p is a prime number,

then for any integer a, the number a^p–a is an integer multiple of p.

Answer: Multiplicative inverse of 14 in GF(31) is 20

C++ code that generated the answer is as mentioned below:

#include <iostream>
using namespace std;

int power(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 MulInverse(int a, int m)

{
return power(a, m - 2, m);
}

int main()

{
int a = 14, m = 31;
cout<<"Multiplicative inverse is "<<MulInverse(a, m)<<endl;
}