Extended Euclidean Algorithm Explanation Help and Modular Multiplicative Inverse

[Peter_APIIT]

Hello to all, i have a hard time understand this these two topics.

I hope someone can clear my myth.

I do check the EEA page and did quite amount of research regarding this topic.

This is what i understand.

51x + 36y = gcd(a, b)
Rewrite them in quotient remainder theorem

Euclid Algorithm
51 = 1 x 36 + 15 52 / 36 = 3 r 6
36 = 2 x 15 + 6 36 / 15 = 2 r 6
15 = 2 x 6 + 3 15 / 6 = 2 r 3
6 = 2 x 3 + 0 6 / 2 = 3 r 0

Extended Euclidean Algorithm
=Take the last second solution

15 = 2 x 6 + 3
Rewrite the remainder at LHS

3 = 15 - 2 x 6
= 15 - 2 x (36 - 2 * 15)
= 5 * 15 - 2 * 36 (simplifying)(*)
= 5 * (51 - 36) - 2 * 36
= 5 * 51 - 7 * 36 (simplifying)(*)

Question
1. How modular multiplicative inverse related to EEA ?
Please show example.
2. How to simplify the equation(*) ?
3. How human hand calculation differ to code implementation ?

Thanks for your help.

[glennzo]

Sorry Peter, I don't have time to answer your question as I'm currently busy building a large particle accelerator single handedly. :)

Seriously though, what? :eek:

What's an Extended Euclidean Algorithm and a Modular Multiplicative Inverse :confused:

[ibbo]

What's an Extended Euclidean Algorithm and a Modular Multiplicative Inverse

Yea thats what I was thinking.

Need a hand with that particle accelerator?

Ibbo

[notageek]

Let me pretend a little :D

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

[ibbo]

If only I could GCD my bills and use the Quotient & Remainder as the sums owed instead.

Perhaps then I would know what this is all about.

Thank god I can do maths via the keyboard. I had strange not so nostalgic memories of my 3hr real time systems exam that was all bloody scheduling maths.

I must of cheated I got 67% :)

Ibbo

[Peter_APIIT]

I really bother this for few weeks.

Yes, i do read the wikipedia article and research for few days.

Question
1. How modular multiplicative inverse related to EEA ?
Please show example.
2. How to simplify the equation(*) ?
3. How human hand calculation differ to code implementation ?

This is my question.

For instance, ax +by = gcd(a, b);

I know that the algorithm will implement in iteration mode and during the iteration gcd(a, b) and xy will be computed.

Another question is at least there are two variant of this algorithm in computing implementation which are pure EEA and EEA with Euclid algorithm ?


I want to understand them in paper then i can code it. Example is greatly appreciated by me and others.

Thanks.

Thanks for your help.

[creeping death]

I really bother this for few weeks.

Yes, i do read the wikipedia article and research for few days.

Question
1. How modular multiplicative inverse related to EEA ?


in the equation ax + by = gcd(a,b)
x is the multiplicative inverse value of a % b .
so you know a, b (note that they HAVE TO BE co-prime). you can find x by the statement above you then find y by solving the equation by substituting the values of a,b,x.


Please show example.
2. How to simplify the equation(*) ?
3. How human hand calculation differ to code implementation ?

in eulers theorem...suppose you need to find 33 power 77 mod 87
33^77 mod 87 will be done by hand in a tedious way. ask your instructor, i cannot demonstrate.

33 power 77 mod 87 will be done in C as


unsigned long int expocal(unsigned long int c,unsigned long int d,unsigned long int n)
{
unsigned long int i=0,ans=1;
for(i=1;i<=d;i++)
{
ans=ans*c;
ans=ans%n;
}
ans=ans%n;
return ans;
}


where ans=c power d mod n
[/quote]

This is my question.

For instance, ax +by = gcd(a, b);

I know that the algorithm will implement in iteration mode and during the iteration gcd(a, b) and xy will be computed.

Another question is at least there are two variant of this algorithm in computing implementation which are pure EEA and EEA with Euclid algorithm ?


I want to understand them in paper then i can code it. Example is greatly appreciated by me and others.

Thanks.

Thanks for your help.

how do you expect someone to explain something on paper online?

[Peter_APIIT]

in the equation ax + by = gcd(a,b)
x is the multiplicative inverse value of a % b .
so you know a, b (note that they HAVE TO BE co-prime). you can find x by the statement above you then find y by solving the equation by substituting the values of a,b,x.


I do understand this but not coding part.

Please help.

[creeping death]

1.find the multiplicative inverse of a mod b
for this there is a simple way

ax=1(mod) b

this can also be expressed as
ax (mod) b =1
or (ax-1) (mod) b = 0
to find x run a loop which goes on till you get ax-1 mod b as 0 and try out all values of x . when you get ax-1 mod b as 0 break from the loop and that is the correct value of x

2. find gcd(a,b)

3.now you know x , gcd(a,b) , a, b so find y.

[Peter_APIIT]

Your approach is using brute force to try out all possible value of X which contradiction to EEA which using substitute/assignment to compute X.

Thanks for your suggestion.

[creeping death]

that has nothing to do with EEA...it is to find multiplicative inverse of a finite field

it is the easiest approch to finding multiplicative inverse of a finite field...

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Computing_a_multiplic ative_inverse_in_a_finite_field

[citojaso]

no matter what route you take....the answer is and will always be "42" ! :-)

[creeping death]

I think this algorithm is the best for hand computation. For implementation on a computer, it has a drawback: You need to store all the Euclidean algorithm quotients and remainders, because you need to work your way backward up the table.
by,
Bruce Ikenaga , Department of Mathematics, Millersville University.

good luck doing it in the note-book way...its possible though...

[mtl2002]

How is modular multiplicative inverse related to the EEA?
================================================== =======

Well, what does it mean to say that A has a multiplicative inverse modulo B?
---------------------------------------------------------------------------
By definition, this means that for some integer X, AX = 1 (mod B).
By definition, this means that B divides (AX-1).
By definition, this means that for some integer Y, B*(-Y) = AX-1, or AX+BY=1.

In other words, "A has a multiplicative inverse modulo B" if and only if
there are X and Y such that AX+BY=1, which occurs if and only if the greatest
common divisor of A and B is 1.

If gcd(A,B)=1,the extended Euclidean algorithm will find a pair of X and Y that
satisfies AX+BY=1.

As an example take 51 = 3*17 and 36 = 4*9. Obviously gcd(51,36)=3. Since 3 != 1, the above discussion allows us to conclude that 36 does not have an inverse under multiplication mod 51.

We can also see this directly. For suppose 36 *DID* have an inverse under
multiplication mod 51.
Then for some integer X, 36X = 1 (mod 51)
Then 51 divides (36X-1)
Then for some integer Y, 51(-Y) = 36X-1, or 36X + 51Y = 1.
But the last equation is impossible, because 3 divides the left side, but not the right side.


How to simplify the calculation of the EEA? And how do hand and computer calculations differ?
================================================== ============================================
I don't think you can really simplify the calculation. I would organize the calculation by hand exactly the same way to do it by computer.

I have attached a C program with comments. Perhaps if look through it you may understand better how to arrange the calculation. The key realization is that in the following sequence:

a = b*q0 + r0
b = r0*q1 + r1
r0= r1*q2 + r2
r1= r2+q3 + r3
etc.

ALL the remainders r(i) can be expressed in the form r(i) = a*x(i) + b*y(i).
Set r(-2)=a, r(-1)=b, and for k>=0, note that r(k)=r(k-2)-r(k-1)*q(k), so
a*x(k) + b*y(k) = a*x(k-2)+b*y(k-2) - a*x(k-1)*q(k) - b*y(k-1)*q(k), so
x(k) = x(k-2)-x(k-1)*q(k) and y(k) = y(k-2)-y(k-1)*q(k). Please see the attached program for details.



/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Given integers a and b, suppose d=gcd(a,b). Then there exist integers x and y
such that d=ax+by. How do we find d, x, and y?

Assume without loss of generality that a >= 0, b > 0.

Use the Euclidean algorithm:
r_{-2} = a r_{-2} = ax_{-2} + by_{-2} = a(1) + b(0)
r_{-1} = b r_{-1} = ax_{-1} + by_{-1} = a(0) + b(1)

r_{-2} = r_{-1}q_0 + r_0 r_0 = ax_0 + by_0
r_{-1} = r_0q_1 + r_1 r_1 = ax_1 + by_1
r_0 = r_1q_2 + r_2 r_2 = ax_2 + by_2
.
.
r_{n-2} = r_{n-1}q_n + r_n r_n = ax_n + by_n
r_{n-1} = r_nq_{n+1} + r_{n+1}

Since r_{-1} > r_0 > r_1 > r_2 >...>= 0, eventually r_{n+1}=0 for some n >= -1.
In fact, since the r_i are strictly decreasing, n <= |r_{-1}|.

Then gcd(a,b)=gcd(b,r_0)=gcd(r_0,r_1)= ... =gcd(r_{n-1},r_n)=gcd(r_n,0)=r_n.

Also, for i >= 0
r_i = ax_i + by_i
= r_{i-2} - r_{i-1}q_i
= (ax_{i-2}+by_{i-2}) - (ax_{i-1}+by_{i-1})q_i
= a(x_{i-2}-x_{i-1}q_i) + b(y_{i-2}-y_{i-1}q_i)

Thus, gcd(a,b) = r_n = x_n*a + y_n*b, where
1) n is the index of the last positive remainder in the sequence
r_{-2} >= r_{-1} > r_0 > ... > r_n > r_{n+1} = 0

2) The r_i, x_i, y_i are determined by the initial conditions:
r_{-2} = a x_{-2} = 1 y_{-2} = 0
r_{-1} = b x_{-1} = 0 y_{-1} = 1
and the following relations for i >= 0:
q_i = r_{i-2} / r_{i-1}
r_i = r_{i-2} - r_{i-1}*q_i
x_i = x_{i-2} - x_{i-1}*q_i
y_i = y_{i-2} - y_{i-1}*q_i

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~

What is the relationship to modular multiplicative inverses?

Suppose gcd(a,b)=1
===================
By the extended Euclidean algorithm, we can find x and y such that ax + by = 1.
This means that (ax-1) = -by, which means b | (ax-1), which means ax = 1 (mod b).
This means that a has an inverse (namely x) under multiplication mod b.

Suppose a has an inverse (say x) under multiplication mod b
================================================== =========
This means that ax = 1 (mod b), which means b | (ax-1), which means ax+by=1
for some integer y. In turn, this means gcd(a,b)=1.

We can see that the following three statements are equivalent:
1) gcd(a,b)=1
2) a has an inverse under multiplication mod b
3) ax + by = 1 for some integers x, y

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~

We now present a C implementation of the extended Euclidean algorithm.
The function int gcd(int a, int b, int *x, int *y)
1) takes integers a, b as arguments
2) returns their greatest common divisor d
3) takes pointers to integers x and y, and will fill x and y with values such
that a*x + b*y = d
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

int absval(int a) { return (a<0) ? (-a) : a; }

int gcd(int a, int b, int *x, int *y) /* gcd(a,b) = a*x + b*y */
{
int aa, bb, q, rr[3], xx[3], yy[3];
/* we set things up so that rr[i] = aa*xx[i] + bb*yy[i] for i=0,1,2 */

aa = absval(a);
bb = absval(b);

if (aa==0 && bb==0) { *x = 0; *y = 0; return 0; }
if (aa==0 && bb!=0) { *x = 0; *y = bb/b; return bb; }
if (aa!=0 && bb==0) { *x = aa/a; *y = 0; return aa; }

/* at this point, aa>0 and bb>0 */

/* now set up initial conditions */
rr[0] = aa; xx[0] = 1; yy[0] = 0;
rr[1] = bb; xx[1] = 0; yy[1] = 1;

while (rr[1]!=0) {
/* calculate next values of r,x,y in rr[2],xx[2],yy[2] */
q = rr[0] / rr[1]; /* q_n = r_{n-2} / r_{n-1} */
rr[2] = rr[0] - rr[1]*q; /* r_n = r_{n-2} - r_{n-1}*q_n */
xx[2] = xx[0] - xx[1]*q; /* x_n = x_{n-2} - x_{n-1}*q_n */
yy[2] = yy[0] - yy[1]*q; /* y_n = y_{n-2} - y_{n-1}*q_n */

/* update values of rr,xx,yy */
rr[0] = rr[1]; rr[1] = rr[2];
xx[0] = xx[1]; xx[1] = xx[2];
yy[0] = yy[1]; yy[1] = yy[2];
}

/* when we stop, rr[1]==0, which represents r_{n+1}
then d = r_n = rr[0], x_n = xx[0], y_n = yy[0] */
*x = xx[0] * (aa/a); /* a*x = aa*xx[0] */
*y = yy[0] * (bb/b); /* b*y = bb*yy[0] */

return rr[0];
}