In: Computer Science
Q4. Find the multiplicative inverse of 14 in GF(31) domain using Fermat’s little theorem. Show your work
Q5. Using Euler’s theorem to find the following exponential: 4200mod 27. Show how you have employed Euler’s theorem here
Fermat’s theorem :
Theorem
Let p be a prime. Then for all integers a not divisible by p, we have
ap-1 ≡ 1 mod p
Proof:
The group has p − 1 elements. Then by the Lagrange
theorem, for all a ∈ , ap-1 ≡ 1 mod p
p−1 ≡ 1 mod p.
// Java program to find modular inverse of a under modulo m
// using Fermat's little theorem.
// This program works only if m is prime.
class GFG
{
static int __gcd(int a, int b)
{
if(b == 0)
{
return a;
}
else
{
return __gcd(b, a % b);
}
}
// To compute x^y under modulo m
static int power(int x,int y,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;
}
// Function to find modular
// inverse of a under modulo m
// Assumption: m is prime
static void modInverse(int a, int m)
{
if (__gcd(a, m) != 1)
System.out.print("Inverse doesn't exist");
else {
// If a and m are relatively prime, then
// modulo inverse is a^(m-2) mode m
System.out.print("Modular multiplicative inverse is "
+power(a, m - 2, m));
}
}
// Driver code
public static void main (String[] args)
{
int a = 31, m = 14;
modInverse(a, m);
}
}
Euler’s theorem:
Let n be any positive integer. Then, for all integers a relatively prime to n, we have
≡ 1 mod n.
So, By the formula we get 4200 modulo 27 = 15.