Java Program to Implement Extended Euclidean Algorithm based on Number Theory

Extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y (one of which is typically negative) that satisfy Bézout’s identity 

ax + by = gcd(a, b).

This Program is based on Pune University BE IT Syllabus: Develop and program in C++ or Java based on number theory such as Chinese remainder or Extended Euclidean algorithm. ( Or any other to illustrate number theory for security)

Here is the source code of the Java Program to Implement Extended Euclidean Algorithm. The Java program is successfully compiled and run on a Eclipse IDE. The program output is also shown below.

Points to be remember

1. Create the Java Class with the name of ExtendedEuclied 

import java.util.Scanner;

/*
 * @author Professional Cipher [www.professionalcipher.com]
 */
public class ExtendedEuclied 
{
    
    public void solve(long a, long b)
{
   long x=0,y=1,last_x=1,last_y=0,temp;
   while(b!=0)
{
    long q=a/b;
    long r=a%b;
    a=b;
    b=r;
    temp=x;
    x=last_x-q*x;
    last_x=temp;
    temp=y;
    y=last_y-q*y;
    last_y=temp;
 }
 
    System.out.println("Roots x:"+ last_x +"y:"+last_y+"\nGCD : "+a);
}

/** main function **/

public static void main (String[] args)
{
   Scanner scan=new Scanner(System.in);
System.out.println("Extended Eucliead Algorithm Test \n");
/** more an object of Extended Eucliead class **/
 ExtendedEuclied ee=new ExtendedEuclied();
/** Accept two integers **/

System.out.println("Enter ab of an + by=gcd(a,b) \n");
long a=scan.nextLong();
long b=scan.nextLong();
/** call function solve of class extended euclied **/
ee.solve(a,b);
}
}

/*
 * 
 * 
 *OUTPUT:
 *Extended Eucliead Algorithm Test 
 *Enter ab of an + by=gcd(a,b) 
 *105
 *80
 *Roots x:-3y:4
 *GCD : 5
 *
 */

CLICK HERE FOR ALL BE PROGRAMS

CLICK HERE FOR ALL BE BOOKS

CLICK HERE FOR ALL BE NOTES