-------------------- Modular arithmetic --------------------

p :: Int
p = 7     -- change this appropriately

----------- Datatypes --------------------

data Residue = Res Int

----------- Instance declarations ---------

instance Eq Residue where
  (Res x) == (Res y) = (x-y) `mod` p == 0

instance Mult Residue where
  unit = Res 1

instance LeftMul Residue Residue where
  (Res x) * (Res y) = Res ((x*y) `mod` p)

instance LeftMul Int Residue where
    n * (Res x) = (Res n) * (Res x)

instance Add Residue where
   (Res x) + (Res y) = Res ((x+y) `mod` p)
   (Res x) - (Res y) = Res ((x-y) `mod` p)
   zero = Res 0

instance Div Residue Residue where
   (Res x) / (Res y) = Res ((x*u) `mod` p) where
         (1,u,_) = gcdplus y p

instance Div Residue Int where
    x / n  =  x / (Res (n `mod` p))


--------- Definitions --------------------

--- gcdplus x y == (d,u,v) where u*x+v*y == d ( == hcf x y )
gcdplus :: Int -> Int -> (Int,Int,Int)
gcdplus x y | y == 0     = (x, 1, 0)
            | otherwise  = (d, v, u-v*(x/y))
              where (d, u, v) = gcdplus y (x `mod` y)

--- x^(order x) == 1 modulo p
order :: Residue -> Int
order x = 1 + length (takeWhile (/= unit) [ x^n | n <- [1..]])

--- every x == primGen^n modulo p for some n, if x /= 0 modulo p
primGen :: Residue
primGen = Res g
     where g = while (\x -> (order (Res x) /= (p-1))) (+1) 2

length x = sum [ 1 | _ <- x ]

while          :: (a -> Bool) -> (a -> a) -> a -> a
while p f x | p x       = while p f (f x)
            | otherwise = x

------ End Modular
          