Forum Home
PC World Chat
 
Thread ID: 84334 2007-11-01 22:52:00 Maths question? Ninjabear (2948) PC World Chat
Post ID Timestamp Content User
607458 2007-11-01 22:52:00 Does anyone know how to use Euclidean algorithm to solve

4743^-1 MOD 1660

The answer is 7

How would you solve it?

I dont understand 		Ninjabear (2948)
607459 2007-11-01 23:04:00 Funny, I keep getting the answer = 42

That is the same answer I get for all problems.

Ken 		kenj (9738)
607460 2007-11-02 02:27:00 Mod means divide, but you want the remainder, not the actual answer. pcuser42 (130)
607461 2007-11-02 04:52:00 4743^-1 means "4743 to the power of -1"; that is, 1/4743. The MOD operation means "(integer) divide by 1660 and give the remainder as the answer ". I'd expect the remainder of 1/(4743 x 1660) to be 0. Graham L (2)
607462 2007-11-02 04:56:00 I was thinking the exact same thing. roddy_boy (4115)
607463 2007-11-02 18:53:00 To me it seems that it is (1/4743) divided by 1660, because there are no brackets in the original question. The answer my calculator gives to that one is 1.270102548 x 10^-7. pcuser42 (130)
607464 2007-11-03 02:25:00 You want to use the extended Euclidean algorithm. The quality of articles on this is appalling - it took me longer a few weeks ago to implement this algorithm than it took me to implement RSA encryption, which is just slightly more mathematically advanced! Here's the Haskell code I came up with ("--" begins a comment line):



-- Calculates the inverse of n modulo m.
-- Expects:
-- - Number to invert
-- - The order of the modular field
-- Returns:
-- n^-1 mod m
-- Satisfies:
-- for all m, (n in [1,m))
-- modularInverse n m == i implies (i * n) `mod` m == 1
modularInverse :: Integer -> Integer -> Integer
modularInverse n m = (snd (ee m (n `mod` m))) `mod` m

-- Extended Euclidean algorithm for use in modularInverse
ee :: Integer -> Integer -> (Integer, Integer)
ee a b = if r == 0 then (0,1) else (y, x-y*q)
where
(q,r) = divMod a b
(x,y) = ee b r


This code is slower than it could be but performance isn't critical for this library. The code does not yet check that the inverse exists - this will be added soon. We are basically solving in a field modulo b:

1 = a * x + b * y

Since we are working in a field modulo b then this means:

1 = a * x (mod b)

Assuming a > 0 and gcd(a,b) = 1:

x = a^-1 (mod b)

The code above finds the x value by working forwards until we finish the euclidean algorithm (i.e. we have the first equation above) then working backwards to produce our value of x. The Wikipedia page on the extended Euclidean algorithm has this written in pseudocode.

EDIT: divMod divides one number by another and returns (quotient, remainder). The quotient is labelled q and the remainder r in this code. The code is recursive and x and y are the values returned by the next call to ee.

EDIT 2: Haskell is lazy so it will only calculate values if they are required. Otherwise this code would go on forever! 		TGoddard (7263)
607465 2007-11-03 02:34:00 You want to use the extended Euclidean algorithm. The quality of articles on this is appalling - it took me longer a few weeks ago to implement this algorithm than it took me to implement RSA encryption, which is just slightly more mathematically advanced! Here's the Haskell code I came up with ("--" begins a comment line):



-- Calculates the inverse of n modulo m.
-- Expects:
-- - Number to invert
-- - The order of the modular field
-- Returns:
-- n^-1 mod m
-- Satisfies:
-- for all m, (n in [1,m))
-- modularInverse n m == i implies (i * n) `mod` m == 1
modularInverse :: Integer -> Integer -> Integer
modularInverse n m = (snd (ee m (n `mod` m))) `mod` m

-- Extended Euclidean algorithm for use in modularInverse
ee :: Integer -> Integer -> (Integer, Integer)
ee a b = if r == 0 then (0,1) else (y, x-y*q)
where
(q,r) = divMod a b
(x,y) = ee b r


This code is slower than it could be but performance isn't critical for this library. The code does not yet check that the inverse exists - this will be added soon. We are basically solving in a field modulo b:

1 = a * x + b * y

Since we are working in a field modulo b then this means:

1 = a * x (mod b)

Assuming a > 0 and gcd(a,b) = 1:

x = a^-1 (mod b)

The code above finds the x value by working forwards until we finish the euclidean algorithm (i.e. we have the first equation above) then working backwards to produce our value of x. The Wikipedia page on the extended Euclidean algorithm has this written in pseudocode.

EDIT: divMod divides one number by another and returns (quotient, remainder). The quotient is labelled q and the remainder r in this code. The code is recursive and x and y are the values returned by the next call to ee.

EDIT 2: Haskell is lazy so it will only calculate values if they are required. Otherwise this code would go on forever!

Damn! You beat me to it. :D 		allblack (6574)
1