arithmoi-0.7.0.0: Efficient basic number-theoretic functions.

Copyright(c) 2011 Daniel Fischer
LicenseMIT
MaintainerDaniel Fischer <daniel.is.fischer@googlemail.com>
StabilityProvisional
PortabilityNon-portable (GHC extensions)
Safe HaskellNone
LanguageHaskell2010

Math.NumberTheory.Primes.Factorisation.Certified

Description

Factorisation proving the primality of the found factors.

For large numbers, this will be very slow in general. Use only if you're paranoid or must be really sure.

Synopsis

Documentation

certifiedFactorisation :: Integer -> [(Integer, Int)] Source #

certifiedFactorisation n produces the prime factorisation of n, proving the primality of the factors, but doesn't report the proofs.

provenFactorisation :: Integer -> Integer -> [((Integer, Int), PrimalityProof)] Source #

provenFactorisation bound n constructs a the prime factorisation of n (which must be positive) together with proofs of primality of the factors, using trial division up to bound (which is arbitrarily replaced by 2000 if the supplied value is smaller) and elliptic curve factorisation for the remaining factors if necessary.

Construction of primality proofs can take a very long time, so this will usually be slow (but should be faster than using factorise and proving the primality of the factors from scratch).