This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes Extended Euclidean Algorithm Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Extended Euclidean Algorithm" Watch "Extended Euclidean Algorithm" New topic
Author

Extended Euclidean Algorithm

Cheryl Scodario
Ranch Hand

Joined: Nov 28, 2009
Posts: 69
Hi all, I am doing an encryption program, and need to find the x and y in this formula: gcd(a,b)=a*x+b*y;
I know the idea is to follow the steps of the actual Euclidean algorithm, and then just doing everything backwards, but I don't know how to put that in code.
One thing to note, gcd (a, b) will be 1 in my case, because a and b are coprime. so basically we are looking at 1=a*x+b*y and find x and y.
Please give me some hints!

Thanks.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Then first explain in words how to do it. The second step would be to change those words into code.
 
Don't get me started about those stupid light bulbs.
 
subject: Extended Euclidean Algorithm
 
Similar Threads
GCD calculation using Euclidean algorithm fails
if gcd(a,b)=1 , what happens?
GCD/LCM problems
Card Shuffle Problem
I got it, but is my code sloppy?