lowest_primitive_root.hs

-- Lowest primitive root
primitivelowest :: Int -> Int
primitivelowest 2 = 1
primitivelowest 3 = 2
primitivelowest n = let phin    = phi n
                        pws     = map (\x -> phin `div` x) (map fst (factor phin))
                    in primitivelowest' n phin [2..(n - 1)] pws pws
                        where
                            primitivelowest' :: Int -> Int -> [Int] -> [Int] -> [Int] -> Int
                            primitivelowest' n phin [] aps ps = 0
                            primitivelowest' n phin (a:as) [] ps
                                | powmod a phin n == 1      = a
                                | otherwise                 = primitivelowest' n phin as ps ps
                            primitivelowest' n phin (a:as) (ap:aps) ps
                                | powmod a ap n <= 1        = primitivelowest' n phin as ps ps
                                | otherwise                 = primitivelowest' n phin (a:as) aps ps