Date: 09/01/2023
Lab no. 7
Title: Write a program to find the value of s and t in as + bt = 1 in Extended Euclidean
algorithm with user input a and b.
Extended Euclidean Algorithm:
The Euclidean algorithm is a way to find the greatest common divisor of two positive integers.
GCD of two numbers is the largest number that divides both of them. A simple way to find GCD
is to factorize both numbers and multiply common prime factors.
Algorithm:
1. Input the integer a and b.
2. Initialize the variables: s0=1, s1=0, t0=0, t1=1
3. Loop while r1 is not equal to 0:
a. Calculate 'q' as the integer division of r0 by r1: q = r0 // r1.
b. Update (r0, r1) as (r1, r0 - q * r1).
c. Update (s0, s1) as (s1, s0 - q * s1).
d. Update (t0, t1) as (t1, t0 - q * t1).
4. When the loop terminates, r0 contains the GCD of 'a' and 'b', and (s0, t0) contains
the coefficients 's' and 't' such that 'as + bt = gcd(a, b)'.
5. Return r0 as the GCD, and (s0, t0) as the coefficients.
IDE: DEV C++
Language: C
Source code:
#include <stdio.h>
int extended_gcd(int a, int b, int *s, int *t) {
if (b == 0) {
// Base case: When b is 0, GCD is a, and s and t are 1 and 0 respectively.
*s = 1;
*t = 0;
return a;
}
int s1, t1;
int gcd = extended_gcd(b, a % b, &s1, &t1);
*s = t1;
*t = s1 - (a / b) * t1;
return gcd;
}
int main() {
int a, b;
printf("Enter two integers a and b: ");
scanf("%d %d", &a, &b);
int s, t;
int gcd = extended_gcd(a, b, &s, &t);
// Print the calculated GCD, s, and t values.
printf("GCD(%d, %d) = %d\n", a, b, gcd);
printf("s = %d, t = %d\n", s, t);
return 0;
}
Output:
Date: 09/01/2023
Lab no. 8
Title: Write a program to test the prime number using Little Fermat’s Theorem Extended
Little Fermat's Theorem:
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. ap ≡ a (mod p). Special Case: If a is not divisible by p, Fermat's little
theorem is equivalent to the statement that a p-1-1 is an integer multiple of p. Here a is not
divisible by p.
Algorithm:
1. Input p to test for primality
2. If 'p' is less than or equal to 1, return "Not Prime."
3. Else repeat the following steps 'k' times:
a. Choose a random integer 'a' in the range [2, 'p' - 2].
b. Calculate 'result' as 'a^(p-1) % p' using modular exponentiation.
c. If 'result' is not equal to 1, return "Not Prime."
4. If, after 'k' iterations, 'p' has not been declared "Not Prime," return "Prime."
IDE: DEV C++
Language: C
Source Code:
#include <stdio.h>
#include <stdlib.h>
#define ll long long
// Function to perform modular exponentiation (base^exponent % mod)
ll modulo(ll base, ll exponent, ll mod) {
ll x = 1; // Initialize result
ll y = base; // Initialize base value
while (exponent > 0) {
if (exponent % 2 == 1)
x = (x * y) % mod; // Multiply x with y if exponent is odd
y = (y * y) % mod; // Square y
exponent = exponent / 2; // Divide the exponent by 2 (right shift)
}
return x % mod; // Ensure the result is within mod
}
int Fermat(ll p, int iterations) {
int i;
if (p == 1) {
return 0; // 1 is not prime
}
for (i = 0; i < iterations; i++) {
ll a = rand() % (p - 1) + 1;
if (modulo(a, p - 1, p) != 1) {
return 0; // If a^(p-1) % p is not 1, p is definitely not prime
}
}
return 1;
}
int main() {
int iteration = 50; // Number of iterations for the Fermat primality test
ll num; // The integer to be tested for primality
printf("Enter integer to test primality: ");
scanf("%lld", &num);
// If Fermat's test suggests it's prime, print as prime
if (Fermat(num, iteration) == 1)
printf("%lld is prime\n", num);
// If Fermat's test suggests it's not prime, print as not prime
else
printf("%lld is not prime\n", num);
return 0;
}
Output:
Date: 09/01/2023
Lab no. 9
Title: Write a program to test the prime no. using Miller-Rabin Algorithm
Miller-Rabin Algorithm:
Miller Rabin is a fast approach to test primality of the large numbers. This algorithm is called a
Rabin-miller primality test and this algorithm decides whether number is prime which is same to
other tests including Fermat primality Test and Solovay- Strassen primality test.
Algorithm:
1. Input the integer to check for prime.
2. Write n as (2^r) * d, where r is the largest non-negative integer such that 2^r divides n,
and d is an odd number.
3. Repeat the following steps k times:
a. Choose a random integer a from the range [2, n-2].
b. Compute x = (a^d) % n using modular exponentiation.
c. If x is congruent to 1 (mod n) or x is congruent to n-1 (mod n), continue to the next
iteration.
d. For i from 1 to r-1:
i. Compute x = (x^2) % n using modular exponentiation.
ii. If x is congruent to n-1 (mod n), break from the loop.
e. If x is not congruent to n-1 (mod n) after all iterations, return "Not Prime."
4. If, after k iterations, the number has not been declared "Not Prime," return "Prime."
IDE: DEV C++
Language: C
Source Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// Function to perform modular multiplication (a * b) % mod
long long mulmod(long long a, long long b, long long mod)
{
long long x = 0, y = a % mod;
while (b > 0)
{
if (b % 2 == 1)
{
x = (x + y) % mod;
}
y = (y * 2) % mod;
b /= 2;
}
return x % mod;
}
// Function to perform modular exponentiation (base^exponent % mod)
long long modulo(long long base, long long exponent, long long mod)
{
long long x = 1;
long long y = base;
while (exponent > 0)
{
if (exponent % 2 == 1)
x = (x * y) % mod;
y = (y * y) % mod;
exponent = exponent / 2;
}
return x % mod;
}
// Miller-Rabin primality test
int Miller(long long p, int iteration)
{
int i;
if (p < 2)
return 0;
if (p != 2 && p % 2 == 0)
return 0;
s = p - 1;
while (s % 2 == 0)
s /= 2;
for (i = 0; i < iteration; i++)
{
// Generate a random integer between 1 and p-1
long long a = rand() % (p - 1) + 1;
long long temp = s;
long long mod = modulo(a, temp, p);
while (temp != p - 1 && mod != 1 && mod != p - 1)
{
mod = mulmod(mod, mod, p);
temp *= 2;
}
if (mod != p - 1 && temp % 2 == 0)
return 0;
}
return 1;
}
int main()
{
int iteration = 5;
long long num;
printf("Enter integer to test primality: ");
scanf("%lld", &num);
if (Miller(num, iteration))
printf("\n%lld is prime\n", num);
else
printf("\n%lld is not prime\n", num);
return 0;
}
Output:
Date: 09/01/2023
Lab no. 10
Title: Write a program to test whether the input α is primitive root of p
Primitive Root:
Primitive roots are fundamental in number theory and have practical applications, particularly in
cryptography. They play a crucial role in generating secure keys and ensuring the security of data
transmission.
Algorithm:
1. Initialize a set 'powers_set' to store the powers of 'g'.
2. Loop through potential values of 'g' from 2 to 'p - 1':
a. For each 'g' value, initialize an empty set 'visited' to keep track of visited
residues.
b. Loop through 'i' from 1 to 'p - 2':
i. Calculate 'power' as 'g^i % p'.
ii. If 'power' is already in the 'visited' set, break from the loop.
iii. Otherwise, add 'power' to the 'visited' set.
c. If the size of the 'visited' set is equal to 'p - 2', it means 'g' generates all
residues modulo 'p' except 0, so 'g' is a primitive root.
d. Add 'g' to the 'powers_set'.
3. If 'powers_set' is empty, no primitive root was found, and it is not possible to find a
primitive root for 'p'.
4. If 'powers_set' is not empty, return any element 'g' from the 'powers_set' as a
primitive root.
5. If a primitive root 'g' is found, return 'g'.
6. If no primitive root is found, indicate that it's not possible for the given 'p'.
IDE: DEV C++
Language: C
Source Code:
#include <stdio.h>
#include <stdbool.h>
// Function to calculate the greatest common divisor (GCD) of two numbers
int gcd(int a, int b) {
if (b == 0) {
return a; // If b is 0, the GCD is a
}
return gcd(b, a % b); // Otherwise, recursively compute GCD
}
// Function to calculate f(p), Euler's totient function for a prime number p
int eulerTotient(int p) {
int result = 1; // Initialize the result to 1
for (int i = 2; i < p; i++) {
if (gcd(i, p) == 1) {
result++; // If i and p are coprime, increment the result
}
}
return result; // Return the Euler's totient value
}
// Function to test if a is a primitive root of p
bool isPrimitiveRoot(int a, int p) {
if (gcd(a, p) != 1) {
return false; // If GCD is not 1, a is not relatively prime to p
}
int phi = eulerTotient(p); // Calculate Euler's totient function for p
int powers[phi]; // Create an array to store powers of a
int x = 1;
// Calculate a^1, a^2, ..., a^(f(p)) modulo p
for (int i = 0; i < phi; i++) {
x = (x * a) % p; // Calculate the next power of a
powers[i] = x; // Store it in the powers array
}
// Check if all the powers are distinct
for (int i = 0; i < phi; i++) {
for (int j = i + 1; j < phi; j++) {
if (powers[i] == powers[j]) {
return false; // If any powers are not distinct, a is not primitive
}}}
return true; // a is a primitive root of p if all conditions pass
int main() {
int alpha, p;
printf("Enter alpha: ");
scanf("%d", &alpha);
printf("Enter p (a prime number): ");
scanf("%d", &p);
// Output if alpha is primitive
if (isPrimitiveRoot(alpha, p)) {
printf("%d is a primitive root of %d.\n", alpha, p);
}
// Output if alpha is not primitive
else {
printf("%d is not a primitive root of %d.\n", alpha, p);
}
return 0;
}
Output:
Date: 09/01/2023
Lab no. 6
Title: Write a program to find the GD of two integer using Euclidean Algorithm
Euclidean Algorithm:
The Euclidean algorithm is a way to find the greatest common divisor of two positive integers, a
and b. The GCD of two numbers is the largest positive integer that divides both numbers without
leaving a remainder. The Euclidean Algorithm is named after the ancient Greek mathematician
Euclid.
Algorithm:
1. Input two integer say m and n.
2. If n==0, return the value of m as the output and stop
3. If m==0, return the value of n as output and stop
4. Divide m by n and assign the value of the remainder to r.
5. Assign the value of n to m and the value or r to n and go to step 3
6. Stop
IDE: DEV C++
Language: C
Source Code:
#include <stdio.h>
// Function to calculate the GCD using the Euclidean Algorithm
int euclideanGCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2;
// Input two integers
printf("Enter the first integer: ");
scanf("%d", &num1);
printf("Enter the second integer: ");
scanf("%d", &num2);
// Find and print the GCD using the Euclidean Algorithm
int gcd = euclideanGCD(num1, num2);
printf("The GCD of %d and %d is %d\n", num1, num2, gcd);
return 0;
}
Output:
