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:

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.

**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.

- 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 * */

Java Program to Implement Extended Euclidean Algorithm based on Number Theory
Reviewed by Huzaif Sayyed
on
October 18, 2017
Rating:

Great Article

ReplyDeleteInformation Security Projects for CSE Students

Project Centers in Chennai

JavaScript Training in Chennai

JavaScript Training in Chennai