Re: Extended Euclidean Algorithm and Modular Multiplicative InvesInverse

On Apr 4, 3:49�am, Peter_APIIT <PeterAP...@xxxxxxxxx> wrote:
On Apr 4, 8:57�am, CBFalconer <cbfalco...@xxxxxxxxx> wrote:

Peter_APIIT wrote:

Please help �me.

OK. �Grasp banister with hand, pull. �Attempt to stand up.

[quote]

The Extended Euclidean Algorithm
--------------------------------

There are two prevailing versions of expositions of the extended
Euclidean algorithm. �All students I have talked to find both
confusing. �Certainly I felt that there ought to be a better way
after I managed to understand them. Here is my take.

Given two numbers a and b, the algorithm should end with this
equation:

� a*m + b*n = d

where d = gcd(a,b).

The algorithm accomplishes this by working with a pair of equations
instead. �At the beginning, they are:

� a*1 + b*0 = a
� a*0 + b*1 = b

Then we go through iterations of modifying these two equations.

In each iteration, the pair is modified to keep this form:

� a*u(1) + b*v(0) = w(a) � �(1)
� a*x(0) + b*y(1) = z(b) � �(2)

u = 1, v = 0, w = a;
x = 0, y = 1, z = b;

with w and z satisfying:

� gcd(w,z) = gcd(a,b) � �(*)

(Note that the initial pair satisfies (*) already.)

In other words, u,v,w,x,y,z are initially 1,0,a,0,1,b.

Then we keep updating the equations, changing the values of
u,v,w,x,y,z accordingly, but we have to ensure that gcd(w,z) always
happens to be gcd(a,b).

(This despite the fact that we do not yet know the value of gcd(a,b)
until the end.)

How to do this? �This is where we extend the Euclidean algorithm.

Initially, w,z is a,b, so gcd(w,z) = gcd(a,b) at the beginning for
free.

Now in each iteration, if gcd(w,z) is gcd(a,b), then certainly gcd(w
mod z, z) is still gcd(a,b).

Thus we can indeed maintain the
condition (*) without even knowing the value of gcd(a,b).

So we replace w by w mod z. �Assuming w>=z, this is not a waste of
time. And u,v,x,y need to be updated in sync.

The new pair of equations is:

u,v,w,x,y,z

� a*u(1) + b*v(0) = w(a) � �(1)
� a*x(0) + b*y(1) = z(b) � �(2)

� a*(u-qx) + b*(v-qy) = w-qz
� a*x + b*y = z

where q = w div z (and so w-qz = w mod z, as promised).
I.e., compute q, then replace (1) by (1)-q*(2).

(In the case that w<z, you can do the symmetric thing, or just
swap the two equations and do the above.)

What's good of doing this? �Because this process is just the plain old
Euclidean algorithm when you just look at the values of w,z,
eventually one of them, say w, will become 0, and z will become gcd
(a,b):

� a*u + b*v = 0
� a*x + b*y = gcd(a,b)

Then you take the second equation and you are done!

[/quote]

Can anyone explain the algorithm from this approach ?

No, it's too much work. I just use a library function.

Python 2.6rc1
IDLE 2.6

import gmpy
help(gmpy.gcdext)
Help on built-in function gcdext in module gmpy:

gcdext(...)
gcdext(a,b): returns a 3-element tuple (g,s,t) such that
g==gcd(a,b) and g == a*s + b*t
(a and b must be mpz objects, or else get coerced to mpz)

gmpy.gcd(8,9)
mpz(1)
gmpy.gcdext(8,9)
(mpz(1), mpz(-1), mpz(1))

If your goal is to solve a problem that requires this, then
mucking about inside the algorithm is a waste of time that
distracts from the problem at hand.

For example, from the extended Euclidean algorithm, we can
solve a linear congruence (if it's solvable). I'm only
interesetded in the answer, not how it was derived.

Take the equation g = (8a-5)/9. To find an integer 'a'
such that 'g' is also an integer, recast as a linear
congruence:

8a == 5 (mod 9)

It's solvable if gcd(8,9) divides 5, which it does.
From the extended Euclidean algorithm, you can find
the modular inverse (if gcd(8,9)=1, which it does).

But why muck about trying to figure out how to do this
when there's a library function to do it for you.

gmpy.divm(5,8,9)
mpz(4)

So, a=4 is the first integer (we'll call it a0) that
results in an integer g.

(8*4-5)/9 = (32-5)/9
= 27/9
= 3

Now, for further solutions (ai), we simply take i*9+a0.
So, the solution list is

4,13,22,31,40,49,58,67,76,85,...

Which result in the g list (i*8+g0)

3,11,19,27,35,43,51,59,67,75,...

Note that 67 is on both lists. The 'a' list are what's
called 1st generation solutions. Every 9th first generation
solution is a second generation solution, every 9th 2nd
generation is a 3rd generation solution, etc.

So, 76 is a second generation solution whose 'g' is also
a solution. But it can get tricky for different equations.
Sometimes every generation+1 solution is the 27th solution
starting from the 17th, whereas the generation+2 is every
27th solution starting from the 11th, every generation+3
is the 27th starting from the 23rd, etc.

Trying to cast a process to determine the ith member of the
kth generation is a real challenge, and you certainly don't
want to waste time with the eEa:

def gen0_recursive(k,xyz):
"""Find first member of generation k of Hailstone Function.

gen0(k,xyz)
k: generation
xyz: HailstoneFunctionParameters
Locates the first _a_ for the requested generation k of
the Hailstone Function.
Needs to know _d_ and _c_ from previous generation,
so it calls itself recursively until generation 1.
At generation 1, results are simple linear congruence of x,y,z.
a: the first solution to the Hailstone Function
g: seed that genertes _a_
d: difference between _a_ and _g_
j: index of _a_ where d == 0 (mod y**k)
c: a[j] the
returns [0,0,0,0] if k invalid
returns GenerationParameters [a,g,d,c]
"""
if k<1: return [0,0,0,0]
if k==1:
a = gmpy.divm(xyz[2],xyz[0],xyz[1])
g = seed(a,xyz)
d = a - g
c = a
return [a,g,d,c]
else:
prev_gen = gen0(k-1,xyz)
j = gmpy.divm(xyz[1]**(k-1)-prev_gen[2],xyz[1]-xyz[0],xyz[1]**
(k-1))/xyz[1]**(k-2)
a = j*xyz[1]**(k-1) + prev_gen[3]
g = seed(a,xyz)
c = a
d = a - g
return [a,g,d,c]


Thanks.

.

Relevant Pages