FermatsFactorizationMethod.hs

module FermatsFactorizationMethod where

import Control.Monad
import Data.List (sort)
import Math.NumberTheory.Roots -- https://hackage.haskell.org/package/integer-roots

factor :: Integer -> [Integer]
factor = sort . g
  where
    g 1 = []
    g n =
      case findFactor n of
        Nothing -> [n]
        Just (a,b) -> g a ++ g b

findFactor :: Integer -> Maybe (Integer, Integer)
findFactor 2 = Nothing
findFactor n
  | n `mod` 2 == 0 = Just (2, n `div` 2)
  | otherwise = msum [exactSquareRoot (x^(2::Int) - n) >>= \y -> pure (x - y, x + y) | x <- [k .. (n+1) `div` 2 - 1]]
  where
    k = if tmp*tmp < n then tmp+1 else tmp
      where
        tmp = integerSquareRoot n


-- 素因数分解のフェルマー法とは何か
-- https://math-fun.net/20210227/11418/
test1 = factor 2021 == [43,47]
test2 = factor 11418 == [2,3,11,173]