CODEWITHSUNDEEP
haskell
ntb457
ntb457

Reputation: 31

Modular Inverse in Haskell

So far I've solved euclid, lCM,extGCD, and coprime. How would I solve for the modular Inverse(minv)? I think that "assumes a n are coprime" is confusing me. 

euclid :: Integer -> Integer -> Integer
euclid 0 0 = error "GCD(0,0) is undefined"
euclid a 0 = a
euclid a b =  euclid b (a `emod` b)

-- Returns the least common multiple of a and b, using the definition of lcm
-- given in class (in terms of the gcd). DO NOT use the built-in `lcm` function.
lCM :: Integer -> Integer -> Integer
lCM 0 0 = error "LCM(0,0) is undefined"
lCM a b = a*b `ediv` (euclid a b)

-- extGCD a b
-- Returns the GCD of a and b, along with x and y such that
--   GCD(a,b) = ax + by
-- calculated via the recursive extended Euclidean algorithm presented in
-- class.
extGCD :: Integer -> Integer -> (Integer,Integer,Integer)
extGCD 0 0 = error "extGCD(0,0) is undefined"
extGCD a 0 = (1,0,a)     -- Base case
extGCD a b = let (q,r) = a `eDivMod` b           -- q and r of a/b
               (c,x,y) = extGCD b r          -- Recursive call
         in  (x,c-q*x, y) -- Recursive results

-- coprime a b 
-- Returns True if a and b are coprime (have no common factors)
coprime :: Integer -> Integer -> Bool
coprime 0 0 = error "coprime(0,0) is undefined"
coprime a b = (euclid a b) == 1

-- minv a n
-- Returns the modular inverse of a mod n. Assumes that a and n are coprime.
minv :: Integer -> Integer -> Integer
minv a n =

Upvotes: 2

Views: 1965

Answers (3)

Howard
Howard

Reputation: 1

Bézout's identity states that for any integers a and b, there exist integers x and y such that ax + by = gcd(a, b) (see Bézout's identity). Specifically, when a and b are co-prime, this simplifies to ax + by = ax = gcd(a, b) = 1 mod b. Utilizing the extended Euclidean algorithm, we iterate through expressions of the form (b mod a)x + ay = gcd(a, b), where we redefine a as a' = b mod a and b as b' = a. Eventually, we arrive at the final state where (a, b, x, y) = (0, gcd(a, b), 0, 1).

To implement this in Haskell, we define a function extgcd that takes a and b as inputs and returns a tuple (x, y). To understand the relationship between each iteration, we compare the equations ax + by = gcd(a, b) and (b mod a)x + ay = gcd(a, b). From this comparison, we derive x = y' - floor(b/a) * x' and y = x'. This leads us to the following Haskell implementation:

modInverse :: Int -> Int -> Maybe Int
modInverse a n = case gcd a n of
  1 -> Just $ makePositive $ fst $ extgcd a n
  _ -> Nothing
  where
    extgcd 0 b = (0, 1)
    extgcd a b =
      let (x', y') = extgcd (b `mod` a) a
          x = y' - (b `div` a) * x'
          y = x'
      in (x, y)
    makePositive x = if x >= 0 then x else x + n

Upvotes: 0

Bakuriu
Bakuriu

Reputation: 101909

First of all a and n must be coprime because otherwise the inverse doesn't exist. This comes from the fact that finding the inverse of a modulo n is the same as solving the congruence: ax = 1 mod n.

A linear congruence ax = b mod n has a solution only if gcd(a, n) | b. But in this case gcd(a, n) | 1 implies that gcd(a, n) = 1.

So now, to find the inverse you use Bezout identity, i.e. there exist x and y such that: gcd(a, n) = a*x + n*y. You have already found such values in your extGCD function so you can implement minv as:

minv a n =  a*x + n*y
    (x, y, _) = extGCD a n

It may be better to write a function with type Integer -> Integer -> Maybe Integer and return Nothing if the extGCD is different from 1:

minv a n =
  | g == 1    = Just $ a*x + n*y
  | otherwise = Nothing
  where
    (x, y, g) = extGCD a n

As an aside: the subgroup of invertible elements in Zn is precisely the set of as < n coprime with n. When n is prime this subgroup coincides with Zn without 0 and in this case Zn is a field.

Upvotes: 3

ErikR
ErikR

Reputation: 52029

You can do it with your extGCD function.

If a and m are co-prime, then use your extGCD function to solve:

a*x + m*y = gcd a m = 1

That means a * x = 1 mod m, i.e. a and x are multiplicative inverses mod m.

Upvotes: 4

Related Questions