HaskellForMaths-0.4.2: Math/NumberTheory/Factor.hs
-- Copyright (c) 2006-2011, David Amos. All rights reserved.
-- |A module for finding prime factors.
module Math.NumberTheory.Factor (pfactors) where
import Math.NumberTheory.Prime
import Data.Either (lefts)
import Data.List (zip4)
-- Cohen, A Course in Computational Algebraic Number Theory, p488
-- return (u,v,d) s.t ua+vb = d, with d = gcd a b
extendedEuclid a b
| b == 0 = (1,0,a)
| otherwise = let (q,r) = a `quotRem` b -- a == qb + r
(s,t,d) = extendedEuclid b r -- s*b+t*r == d
in (t,s-q*t,d) -- s*b+t*(a-q*b) == d
-- ELLIPTIC CURVE ARITHMETIC
data EllipticCurve = EC Integer Integer Integer deriving (Eq, Show)
-- EC p a b represents the curve y^2 == x^3+ax+b over Fp
data EllipticCurvePt = Inf | P Integer Integer deriving (Eq, Show)
-- P x y
isEltEC _ Inf = True
isEltEC (EC n a b) (P x y) = (y*y - x*x*x - a*x - b) `mod` n == 0
-- Koblitz p34
-- Addition in an elliptic curve, with bailout if the arithmetic fails (giving a potential factor of n)
ecAdd _ Inf pt = Right pt
ecAdd _ pt Inf = Right pt
ecAdd (EC n a b) (P x1 y1) (P x2 y2)
| x1 /= x2 = let (_,v,d) = extendedEuclid n ((x1-x2) `mod` n) -- we're expecting d == 1, v == 1/(x1-x2) (mod n)
m = (y1-y2) * v `mod` n
x3 = (m*m - x1 - x2) `mod` n
y3 = (-y1 + m*(x1 - x3)) `mod` n
in if d == 1 then Right (P x3 y3) else Left d
| x1 == x2 = if (y1 + y2) `mod` n == 0 -- includes the case y1 == y2 == 0
then Right Inf
else let (_,v,d) = extendedEuclid n ((2*y1) `mod` n) -- we're expecting d == 1, v == 1/(2*y1) (mod n)
m = (3*x1*x1 + a) * v `mod` n
x3 = (m*m - 2*x1) `mod` n
y3 = (-y1 + m*(x1 - x3)) `mod` n
in if d == 1 then Right (P x3 y3) else Left d
-- Note that b isn't actually used anywhere
-- Note, only the final `mod` n calls when calculating x3, y3 are necessary
-- and the code is faster if the others are removed
-- Scalar multiplication in an elliptic curve
ecSmult _ 0 _ = Right Inf
ecSmult ec k pt | k > 0 = ecSmult' k pt Inf
where -- ecSmult' k q p = k * q + p
ecSmult' 0 _ p = Right p
ecSmult' i q p = let p' = if odd i then ecAdd ec p q else Right p
q' = ecAdd ec q q
in case (p',q') of
(Right p'', Right q'') -> ecSmult' (i `div` 2) q'' p''
(Left _, _) -> p'
(_, Left _) -> q'
-- ELLIPTIC CURVE FACTORISATION
-- We choose an elliptic curve E over Zn, and a point P on the curve
-- We then try to calculate kP, for suitably chosen k
-- What we are hoping is that at some stage we will fail because we can't invert an element in Zn
-- This will lead to finding a non-trivial factor of n
discriminantEC a b = 4 * a * a * a + 27 * b * b
-- perform a sequence of scalar multiplications in the elliptic curve, hoping for a bailout
ecTrial ec@(EC n a b) ms pt
| d == 1 = ecTrial' ms pt
| otherwise = Left d
where d = gcd n (discriminantEC a b)
ecTrial' [] pt = Right pt
ecTrial' (m:ms) pt = case ecSmult ec m pt of
Right pt' -> ecTrial' ms pt'
Left d -> Left d
-- In effect, we're calculating ecSmult ec (product ms) pt, but an m at a time
l n = exp (sqrt (log n * log (log n)))
-- L(n) is some sort of measure of the average smoothness of numbers up to n
-- # [x <= n | x is L(n)^a-smooth] = n L(n)^(-1/2a+o(1)) -- Cohen p 482
-- q is the largest prime we're looking for - normally sqrt n
-- the b figure here is from Cohen p488
multipliers q = [p' | p <- takeWhile (<= b) primes, let p' = last (takeWhile (<= b) (powers p))]
where b = round ((l q) ** (1/sqrt 2))
powers x = iterate (*x) x
findFactorECM n | gcd n 6 == 1 =
let ms = multipliers (sqrt $ fromInteger n)
in head $ filter ( (/= 0) . (`mod` n) ) $
lefts [ecTrial (EC n a 1) ms (P 0 1) | a <- [1..] ]
-- the filter is because d might be a multiple of n,
-- for example if the problem was that the discriminant was divisible by n
-- |List the prime factors of n (with multiplicity).
-- The algorithm uses trial division to find small factors,
-- followed if necessary by the elliptic curve method to find larger factors.
-- The running time increases with the size of the second largest prime factor of n.
-- It can find 10-digit prime factors in seconds, but can struggle with 20-digit prime factors.
pfactors :: Integer -> [Integer]
pfactors n | n > 0 = pfactors' n $ takeWhile (< 10000) primes
| n < 0 = -1 : pfactors' (-n) (takeWhile (< 10000) primes)
where pfactors' n (d:ds) | n == 1 = []
| n < d*d = [n]
| r == 0 = d : pfactors' q (d:ds)
| otherwise = pfactors' n ds
where (q,r) = quotRem n d
pfactors' n [] = pfactors'' n
pfactors'' n = if isMillerRabinPrime n then [n]
else let d = findFactorParallelECM n -- findFactorECM n
in merge (pfactors'' d) (pfactors'' (n `div` d))
merge (x:xs) (y:ys) =
case compare x y of
LT -> x : merge xs (y:ys)
EQ -> x : y : merge xs ys
GT -> y : merge (x:xs) ys
merge xs ys = xs ++ ys
-- Cohen p489
-- find inverse of as mod n in parallel, or a non-trivial factor of n
parallelInverse n as = if d == 1 then Right bs else Left $ head [d' | a <- as, let d' = gcd a n, d' /= 1]
where c:cs = reverse $ scanl (\x y -> x*y `mod` n) 1 as
ds = scanl (\x y -> x*y `mod` n) 1 (reverse as)
(u,_,d) = extendedEuclid c n
bs = reverse [ u*nota `mod` n | nota <- zipWith (*) cs ds]
-- let m = length as
-- then the above code requires O(m) mod calls - in fact 3m-3 calls (?)
parallelEcAdd n ecs ps1 ps2 =
case parallelInverse n (zipWith f ps1 ps2) of
Right invs -> Right [g ec p1 p2 inv | (ec,p1,p2,inv) <- zip4 ecs ps1 ps2 invs]
Left d -> Left d
where f Inf pt = 1
f pt Inf = 1
f (P x1 y1) (P x2 y2) | x1 /= x2 = x1-x2 -- slightly faster not to `mod` n here
| x1 == x2 = 2*y1 -- slightly faster not to `mod` n here
-- inverses = parallelInverse n $ zipWith f ps1 ps2
g _ Inf pt _ = pt
g _ pt Inf _ = pt
g (EC n a b) (P x1 y1) (P x2 y2) inv
| x1 /= x2 = let m = (y1-y2) * inv -- slightly faster not to `mod` n here
x3 = (m*m - x1 - x2) `mod` n
y3 = (-y1 + m*(x1 - x3)) `mod` n
in P x3 y3
| x1 == x2 = if (y1 + y2) `elem` [0,n] -- `mod` n == 0 -- includes the case y1 == y2 == 0
then Inf
else let m = (3*x1*x1 + a) * inv -- slightly faster not to `mod` n here
x3 = (m*m - 2*x1) `mod` n
y3 = (-y1 + m*(x1 - x3)) `mod` n
in P x3 y3
parallelEcSmult _ _ 0 pts = Right $ map (const Inf) pts
parallelEcSmult n ecs k pts | k > 0 = ecSmult' k pts (map (const Inf) pts)
where -- ecSmult' k qs ps = k * qs + ps
ecSmult' 0 _ ps = Right ps
ecSmult' k qs ps = let ps' = if odd k then parallelEcAdd n ecs ps qs else Right ps
qs' = parallelEcAdd n ecs qs qs
in case (ps',qs') of
(Right ps'', Right qs'') -> ecSmult' (k `div` 2) qs'' ps''
(Left _, _) -> ps'
(_, Left _) -> qs'
parallelEcTrial n ecs ms pts
| all (==1) ds = ecTrial' ms pts
| otherwise = Left $ head $ filter (/=1) ds
where ds = [gcd n (discriminantEC a b) | EC n a b <- ecs]
ecTrial' [] pts = Right pts
ecTrial' (m:ms) pts = case parallelEcSmult n ecs m pts of
Right pts' -> ecTrial' ms pts'
Left d -> Left d
findFactorParallelECM n | gcd n 6 == 1 =
let ms = multipliers (sqrt $ fromInteger n)
in head $ filter ( (/= 0) . (`mod` n) ) $
lefts [parallelEcTrial n [EC n (a+i) 1 | i <- [1..100]] ms (replicate 100 (P 0 1)) | a <- [0,100..] ]
-- 100 at a time is chosen heuristically.