dbfin

#!/bin/bash --
# requires bash 4.0+

### FUNCTIONS

# usage: error_exit message
function error_exit() {
  echo -e "\e[31m$1\e[0m"
  exit 1
}

dbfin

-- Sorted lists' `minus`
minus :: [Int] -> [Int] -> [Int]
minus xs ys = minus' xs ys []
    where
        minus' :: [Int] -> [Int] -> [Int] -> [Int]
        minus' [] _ res             = res
        minus' (x:xs) [] res        = res ++ (x:xs)
        minus' (x:xs) (y:ys) res    | x < y        = minus' xs (y:ys) (res ++ [x])
                                    | x > y        = minus' (x:xs) ys res
                                    | otherwise    = minus' xs ys res

dbfin

-- Factor a number
factor :: Int -> [(Int, Int)]
factor n    | n < 2        = []
            | otherwise    = factor' n (eratosthenes.floor.sqrt.fromIntegral $ n) 0 []
    where
        factor' :: Int -> [Int] -> Int -> [(Int, Int)] -> [(Int, Int)]
        factor' n [] _ res          = res ++ [(n,1)]
        factor' 1 (p:ps) pw res     | pw > 0         = res ++ [(p,pw)]
                                    | otherwise      = res
        factor' n (p:ps) pw res     | n `mod` p == 0 = factor' (n `div` p) (p:ps) (pw + 1) res

dbfin

-- Euler's totient function
phi :: Int -> Int
phi n = product $ map (\(p,pw) -> (p - 1) * p^(pw - 1)) $ factor n

dbfin

-- Power modulo a number
powmod :: Int -> Int -> Int -> Int
powmod a pw n   | pw <= 0        = 1
                | pw == 1        = a `mod` n
                | even pw        = powmod' (sqmod a n) (pw `div` 2) n 1
                | otherwise      = powmod' (sqmod a n) (pw `div` 2) n (a `mod` n)
    where
        sqmod :: Int -> Int -> Int
        sqmod a n = (a*a) `mod` n
        powmod' :: Int -> Int -> Int -> Int -> Int

dbfin

-- 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