mcd :: Integer -> Integer -> Integer
mcd a 0 = abs a
mcd a b = mcd b (a `mod` b)

pot :: Integer -> Integer -> Integer -> Integer
pot x 0 n = 1 `mod` n
pot x e n
  | even e    = (y * y) `mod` n
  | otherwise = (x * ((y * y) `mod` n)) `mod` n
  where
    y = pot x (e `quot` 2) n

rho :: Integer -> Integer
rho f = rho' t l
  where
    e = 2 ^ (f + 2)
    n = 1 + 2 ^ (2 ^ f)
    g x = 1 + (pot x e n) `mod` n
    s = 3
    t = g s
    l = g (g s)
    rho' t' l'
      | d == 1    = rho' (g t') (g (g l'))
      | otherwise = d
      where
        d = mcd (t' - l') n

main = rho 15