Roughly programmed search of elements with given order in multiplicative group of ring of integers modulo prime p. First semester algebra exercise.

orders.hs

type Order = Integer
type Element = Integer

order :: Order -> Element -> Order
order p elem = order' p elem elem 1
  where
    order' _ 1 _ ord = ord
    order' p power elem ord = order' p (power*elem `mod` p) elem (ord+1)

-- Searching any generator of cyclic subgroup of order d.
minimalOfOrder :: Order -> Order -> Element
minimalOfOrder p d = minimalOfOrder' p d 1
  where
    minimalOfOrder' p d current = if order p current == d
      then current
      else minimalOfOrder' p d (current + 1)

coprime :: Integer -> Integer -> Bool
coprime a b = gcd a b == 1

search :: Order -> Order -> [Element]
-- Completeness of a list follows from a theorem that multiplicative group of a field is cyclic.
search p ord = map (\pow -> minimal^pow `mod` p) coprimes
  where
    minimal = minimalOfOrder p ord
    coprimes = filter (coprime ord) [0..ord-1]

main :: IO ()
main = do
  putStr "Insert modulus: "
  p <- read <$> getLine
  putStr "Insert order of element: "
  ord <- read <$> getLine
  print $ search p ord