lab12
Fermats Theorem – Program
#include <iostream>
#include <cmath>
using namespace std;
// Function to perform modular exponentiation (a^exp % mod)
long long modExp(long long base, long long exp, long long mod) {
long long result = 1;
base = base % mod; // Reduce base if it is larger than mod
while (exp > 0) {
if (exp % 2 == 1) // If exponent is odd
result = (result * base) % mod;
base = (base * base) % mod; // Square base
exp /= 2; // Divide exponent by 2
}
return result;
}
// Function to demonstrate Fermat's Little Theorem
void fermatTheoremDemo() {
long long a, p;
// Input prime number p
cout << "Enter a prime number (p): ";
cin >> p;
// Input integer a (not divisible by p)
cout << "Enter an integer a (a should not be divisible by p): ";
cin >> a;
if (a % p == 0) {
cout << "Error: 'a' should not be divisible by 'p'." << endl;
return;
}
// Compute a^(p-1) % p
long long result = modExp(a, p - 1, p);
// Display the result
cout << a << "^(" << p - 1 << ") mod " << p << " = " << result << endl;
// Verify the theorem
if (result == 1) {
cout << "Fermat's Little Theorem is verified!" << endl;
} else {
cout << "Fermat's theorem does not hold. Check input values." << endl;
}
}
int main() {
// Run Fermat's Theorem Demonstration
fermatTheoremDemo();
return 0;
}
Euler’s Program
#include <iostream>
#include <cmath>
using namespace std;
// Function to calculate gcd (Greatest Common Divisor)
long long gcd(long long a, long long b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to calculate Euler's Totient Function phi(n)
long long eulerTotient(long long n) {
long long result = n;
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
}
if (n > 1)
result -= result / n;
return result;
}
// Function to perform modular exponentiation (a^exp % mod)
long long modExp(long long base, long long exp, long long mod) {
long long result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 == 1) // If exponent is odd
result = (result * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return result;
}
// Function to demonstrate Euler's Theorem
void eulerTheoremDemo() {
long long a, n;
// Input modulus n
cout << "Enter a positive integer (n): ";
cin >> n;
// Input integer a
cout << "Enter an integer (a) such that gcd(a, n) = 1: ";
cin >> a;
if (gcd(a, n) != 1) {
cout << "Error: 'a' must be coprime to 'n'." << endl;
return;
}
// Compute Euler's Totient Function phi(n)
long long phi_n = eulerTotient(n);
cout << "Euler's Totient Function φ(" << n << ") = " << phi_n << endl;
// Compute a^φ(n) % n using modular exponentiation
long long result = modExp(a, phi_n, n);
// Display the result
cout << a << "^" << phi_n << " mod " << n << " = " << result << endl;
// Verify Euler's theorem
if (result == 1) {
cout << "Euler's Theorem is verified!" << endl;
} else {
cout << "Euler's Theorem failed. Check input values." << endl;
}
}
int main() {
// Run Euler's Theorem Demonstration
eulerTheoremDemo();
return 0;
}
Comments
Post a Comment