Scribd
Upload
13 views3 pages

Cryptography

The document outlines a laboratory exercise for implementing the Extended Euclidean Algorithm in Java to find the modular inverse. It includes a step-by-step algorithm, sample code, and instructions for user input. The program checks if two integers are coprime and calculates the modular inverse, displaying the result upon execution.

Uploaded by

kirthanavambiga
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views3 pages

Cryptography

The document outlines a laboratory exercise for implementing the Extended Euclidean Algorithm in Java to find the modular inverse. It includes a step-by-step algorithm, sample code, and instructions for user input. The program checks if two integers are coprime and calculates the modular inverse, displaying the result upon execution.

Uploaded by

kirthanavambiga
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CS22611 – CRYPTOGRAPHY AND NETWORK SECURITY LABORATORY

[Link](b) ​ ​ ​ NUMBER THEORY


​ ​ ​ ​ ​ ​
DATE:​ ​ EXTENDED EUCLIDEAN ALGORITHM

AIM:
​ To write a java program to implement the Extended Euclid Algorithm to find the Inverse Modulo.

ALGORITHM:

1.​ Start the program and declare two integer variables A and M to store user input.
2.​ Take input from the user for two integers A and M using the Scanner class.
3.​ Check if A and M are coprime using the GCD function:
○​ If gcd(A, M) > 1, return -1 (modular inverse does not exist).
4.​ Find the modular inverse by iterating X from 1 to M-1:
○​ If ((A % M) * (X % M)) % M == 1, return X as the modular inverse.
5.​ Display the modular inverse result as output.
6.​ End the program.

PROGRAM:

import [Link].*;

import [Link];

class inversemod {

static int gcd(int a, int b) {

if (b == 0) {

return a;

}
[Link] ​ [Link]:
return gcd(b, a % b);

static int modInverse(int A, int M) {

if (gcd(A, M) > 1){

return -1;

for (int X = 1; X < M; X++)

if (((A % M) * (X % M)) % M == 1)

return X;

return 1;

public static void main(String args[])

int A,M;

Scanner c = new Scanner([Link]);

[Link]("Enter the first Number:");

A=[Link]();

[Link]("Enter the second Number:");

M=[Link]();

int result = modInverse(A, M);

[Link]("Inverse Modulo of"+A+"and"+M+":"+result);

[Link] ​ [Link]:
SAMPLE INPUT AND OUTPUT:

RESULT:

Thus the java program "to implement Extended Euclid algorithm to find the Inverse Modulo" is
executed and the output is verified successfully

[Link] ​ [Link]:

You might also like