What's the technique used by this teacher to solve ax+by=GCD(a,b) in RSA Algorithm-Cryptography?

[shivajikobardan]

It's the part where he's pointing his hand in this picture. I didn't get it although it's pretty mechanical, so I'd like to learn that technique as this is really useful in RSA algorithm(rather than having to memorize some values). I've been searching for a method like that since I saw this problem(been months) but could not find a technique like that. And it was always about just do it rather having any mechanical method like this one. So, I want to learn this.

Or, if you have any other simple methods to solve this equation, please tell me

 

[AvgStudent]

The equation [imath]ax+by=gcd(a,b)[/imath] is called a Diophantine equation. One method that I know solves them is the Reverse Euclidean Algorithm. (I think that's what he's doing in the picture).

 

[Otis]

I saw this problem(been months) but could not find a technique like that.

Hi. The name of the algorithm appears at the top of the white board. Did you try searching keywords rivest shamir adleman algorithm? There ought to be a number of sites lecturing on that topic. Wikipedia says the algorithm makes use of the Chinese Remainder Theorem.

?

[imath]\;[/imath]

 

[shivajikobardan]

Hi. The name of the algorithm appears at the top of the white board. Did you try searching keywords rivest shamir adleman algorithm? There ought to be a number of sites lecturing on that topic. Wikipedia says the algorithm makes use of the Chinese Remainder Theorem.

?

[imath]\;[/imath]

Hi, I tried finding the way to solve this, but could not find any thing that looks simpler than it. But I didn't find any one explaining this method.
I'm trying to solve,
d*e mod m=1
or, d.17 mod 480=1
So, we want to solve.
480x+17y=GCD(480,17)
480x+17y=1
So, I need to solve this linear diophantine equation. Can you help me with this one? I want something similar to that table, but I'm not getting it fluently.

 

[shivajikobardan]

The equation [imath]ax+by=gcd(a,b)[/imath] is called a Diophantine equation. One method that I know solves them is the Reverse Euclidean Algorithm. (I think that's what he's doing in the picture).

(Repost) Hi, I tried finding the way to solve this, but could not find any thing that looks simpler than it. But I didn't find any one explaining this method.
I'm trying to solve,
d*e mod m=1
or, d.17 mod 480=1
So, we want to solve.
480x+17y=GCD(480,17)
or,480x+17y=1
So, I need to solve this linear diophantine equation. Can you help me with this one? I want something similar to that table, but I'm not getting it fluently.

 

[AvgStudent]

(Repost) Hi, I tried finding the way to solve this, but could not find any thing that looks simpler than it. But I didn't find any one explaining this method.
I'm trying to solve,
d*e mod m=1
or, d.17 mod 480=1
So, we want to solve.
480x+17y=GCD(480,17)
or,480x+17y=1
So, I need to solve this linear diophantine equation. Can you help me with this one? I want something similar to that table, but I'm not getting it fluently.

Here's an online tool I found with steps.
Check it out.

 

[shivajikobardan]

Here's an online tool I found with steps.
Check it out.

Hmm thanks for the information! Is there an way to do it in fx-991 EX calculator? I've found one way but it takes little bit more time.
(d*e-1)/m=1
Now calculate d from this equation in calculator.
I'm seeking if I can do other faster methods for it? Like if there's an equation that solves it? Or any method to implement this in calculator?

 

[AvgStudent]

Hmm thanks for the information! Is there an way to do it in fx-991 EX calculator? I've found one way but it takes little bit more time.
(d*e-1)/m=1
Now calculate d from this equation in calculator.
I'm seeking if I can do other faster methods for it? Like if there's an equation that solves it? Or any method to implement this in calculator?

I'm not familiar with the fx-991 EX calculator.

Diophantine equations have 2 knowns and 1 equation. We can't solve it algebraically besides trial error (as I learned from another thread of mine), so we don't have "an equation that solves it". So we have to rely on an algorithm to solve it, namely the Extended Euclidean Algorithm. There may be a faster method, but I'm unaware of it.

 

[JeffM]

I'm not familiar with the fx-991 EX calculator.

Diophantine equations have 2 knowns and 1 equation. We can't solve it algebraically besides trial error (as I learned from another thread of mine), so we don't have "an equation that solves it". So we have to rely on an algorithm to solve it, namely the Extended Euclidean Algorithm. There may be a faster method, but I'm unaware of it.

That is not my understanding of Diophantine equations. It is correct that they have more than one unknown, but to compensate we have an additional piece of information, namely that the solutions must be positive integers. Whether that extra information is sufficient to generate solutions is the issue.

It is not correct that an algorithm can solve any Diophantine equation. First off, some do not have a solution: for example,

[math]a^3 + b^3 = 64[/math]
There are no positive integers a and b that satisfy that equation as you can easily prove.

Second, there may be solvable types of Diophantine equation for which no algorithm other than trial and error is yet known.

In any case, this question is about explaining an algorithm for a particular type of Diophantine equation.

 

[shivajikobardan]

That is not my understanding of Diophantine equations. It is correct that they have more than one unknown, but to compensate we have an additional piece of information, namely that the solutions must be positive integers. Whether that extra information is sufficient to generate solutions is the issue.

It is not correct that an algorithm can solve any Diophantine equation. First off, some do not have a solution: for example,

[math]a^3 + b^3 = 64[/math]
There are no positive integers a and b that satisfy that equation as you can easily prove.

Second, there may be solvable types of Diophantine equation for which no algorithm other than trial and error is yet known.

In any case, this question is about explaining an algorithm for a particular type of Diophantine equation.

It's extended euclid algorithm. I saw in bishop's security book.