Fermat Factorization Please review my implementation of Fermat's Factorization.

fermat :: Int -&gt; Maybe (Int, Int)
fermat n = odd' n &gt;&gt; (go $ ceiling $ sqrt (fromIntegral n)) 
   where go a = case (try n a) of j @ (Just _) -&gt; j
                                  Nothing      -&gt; go (a + 1) 

odd' :: Int -&gt; Maybe Int
odd' x = if (odd x) then Just x else Nothing

try :: Int -&gt; Int -&gt; Maybe (Int, Int)
try n a = fmap (\b -&gt; ((a + b), (a - b))) result
  where result = get_perfect_sq (a^2 - n)

get_perfect_sq :: Int -&gt; Maybe Int
get_perfect_sq x = if (sq * sq == x) then Just sq else Nothing
  where sq = floor $ sqrt (fromIntegral x :: Float)


examples

ghci&gt; fermat 5995
Just (109,55)

-- prime per http://www.bigprimes.net/cruncher/1300633/
ghci&gt; fermat 1300633
Just (1300633,1)
odd' seems like a useless function, you never use its result, only its monadic context. Use a guard on fermat instead.

fermat n | odd n     = Just $ -- ...
         | otherwise = Nothing


Don't use snake_case in Haskell (get_perfect_sq). We're a camelCase language.

Instead of writing your recursive functions explicitly, try to use higher order functions out of Prelude. They more clearly express intent to readers of your code by highlighting common patterns. In this case, having read Wikipedia's page on Fermat's factorization method, the pseudo-code given in the Basic Method section shows that the primary operation of the function iterates on changing values of \$a\$ and \$b2\$. In Haskell we can use iterate to produce an infinite lazy stream of values, and find to grab the first that meets a condition.

-- given odd n
let a  = ceiling . sqrt $ fromIntegral n
    b2 = a * a - n
in find squareb2 $ iterate step (a, b2)


I'd also be sure to strap a comment to the top with the pseudo-code or algorithm you're trying to implement. It aids understanding and error recognition far easier.

{-
From https://en.wikipedia.org/wiki/Fermat%27s_factorization_method

FermatFactor(N): // N should be odd
  a ← ceil(sqrt(N))
  b2 ← a*a - N
  while b2 isn't a square:
    a ← a + 1 // equivalently: b2 ← b2 + 2*a + 1
    b2 ← a*a - N // a ← a + 1
  endwhile
  return a - sqrt(b2) // or a + sqrt(b2)
-}
fermat :: Integer -&gt; Maybe (Integer, Integer)
fermat n | odd n     = Just . solutions $ find squareb2 (iterate step (a_0, b2_0))
         | otherwise = Nothing
  where
    a_0  = ceiling . sqrt $ fromIntegral n
    b2_0 = a_0 * a_0 - n

    step (a, b2) = (a + 1, b2 + 2 * a + 1)

    squareb2 = isSquare . snd

    solutions (a, b2) = let b = floor . sqrt $ fromIntegral b2 in (a - b, a + b)