{- |
Description: Modular multiplicative inverse
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P42" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P42 (multiplicativeInverse) where

{- |
Compute the multiplicative inverse \(x\) of a given integer \(a\) and modulus \(n\)
lying in the range \(0 \leq x < n\).

Uses the [extended Euclidean algorithm](https://brilliant.org/wiki/extended-euclidean-algorithm/)
and the fact that \(ax \equiv 1 \pmod{n}\) if \(ax+ny=1\).
-}
multiplicativeInverse :: Integral a => a -> a -> Maybe a
multiplicativeInverse :: forall a. Integral a => a -> a -> Maybe a
multiplicativeInverse a
a a
n
  | a
a a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
n    = a -> a -> Maybe a
forall a. Integral a => a -> a -> Maybe a
multiplicativeInverse (a
a a -> a -> a
forall a. Integral a => a -> a -> a
`mod` a
n) a
n
  | a
r a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
1    = a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ a
x a -> a -> a
forall a. Integral a => a -> a -> a
`mod` a
n
  | Bool
otherwise = Maybe a
forall a. Maybe a
Nothing
  where (a
r,a
x,a
_) = (a, a) -> (a, a) -> (a, a) -> (a, a, a)
forall a. Integral a => (a, a) -> (a, a) -> (a, a) -> (a, a, a)
reduce (a
n,a
a) (a
0,a
1) (a
1,a
0)

reduce :: Integral a => (a,a) -> (a,a) -> (a,a) -> (a,a,a)
reduce :: forall a. Integral a => (a, a) -> (a, a) -> (a, a) -> (a, a, a)
reduce (a
0,a
r') (a
_,a
x') (a
_,a
y')   = (a
r',a
x',a
y')
reduce (a
r,a
r') (a
x,a
x') (a
y,a
y') = (a, a) -> (a, a) -> (a, a) -> (a, a, a)
forall a. Integral a => (a, a) -> (a, a) -> (a, a) -> (a, a, a)
reduce (a
r'a -> a -> a
forall a. Num a => a -> a -> a
-a
qa -> a -> a
forall a. Num a => a -> a -> a
*a
r, a
r) (a
x'a -> a -> a
forall a. Num a => a -> a -> a
-a
qa -> a -> a
forall a. Num a => a -> a -> a
*a
x, a
x) (a
y'a -> a -> a
forall a. Num a => a -> a -> a
-a
qa -> a -> a
forall a. Num a => a -> a -> a
*a
y, a
y)
  where q :: a
q = a
r' a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
r