Factorisation functions

factorise n produces the prime factorisation of n. factorise 0 is an error and the factorisation of 1 is empty. Uses a StdGen produced in an arbitrary manner from the bit-pattern of n.

Warning: there are no guarantees of any particular order of prime factors, do not expect them to be ascending. E. g.,

>>> factorise 10251562501
[(101701,1),(100801,1)]

defaultStdGenFactorisation first strips off all small prime factors and then, if the factorisation is not complete, proceeds to curve factorisation. For negative numbers, a factor of -1 is included, the factorisation of 1 is empty. Since 0 has no prime factorisation, a zero argument causes an error.

stepFactorisation is like factorise', except that it doesn't use a pseudo random generator but steps through the curves in order. This strategy turns out to be surprisingly fast, on average it doesn't seem to be slower than the StdGen based variant.

Like factorise, but without input checking, hence n > 1 is required.

Like defaultStdGenFactorisation, but without input checking, so n must be larger than 1.

trialDivisionTo bound n produces a factorisation of n using the primes <= bound. If n has prime divisors > bound, the last entry in the list is the product of all these. If n <= bound^2, this is a full factorisation, but very slow if n has large prime divisors.

smallFactors bound n finds all prime divisors of n > 1 up to bound by trial division and returns the list of these together with their multiplicities, and a possible remaining factor which may be composite.

A wrapper around curveFactorisation providing a few default arguments. The primality test is bailliePSW, the prng function - naturally - randomR. This function also requires small prime factors to have been stripped before.

curveFactorisation is the driver for the factorisation. Its performance (and success) can be influenced by passing appropriate arguments. If you know that n has no prime divisors below b, any divisor found less than b*b must be prime, thus giving Just (b*b) as the first argument allows skipping the comparatively expensive primality test for those. If n is such that all prime divisors must have a specific easy to test for structure, a custom primality test can improve the performance (normally, it will make very little difference, since n has not many divisors, and many curves have to be tried to find one). More influence has the pseudo random generator (a function prng with 6 <= fst (prng k s) <= k-2 and an initial state for the PRNG) used to generate the curves to try. A lucky choice here can make a huge difference. So, if the default takes too long, try another one; or you can improve your chances for a quick result by running several instances in parallel.

curveFactorisation n requires that small (< 100000) prime factors of n have been stripped before. Otherwise it is likely to cycle forever. When in doubt, use defaultStdGenFactorisation.

curveFactorisation is unlikely to succeed if n has more than one (really) large prime factor.

montgomeryFactorisation n b1 b2 s tries to find a factor of n using the curve and point determined by the seed s (6 <= s < n-1), multiplying the point by the least common multiple of all numbers <= b1 and all primes between b1 and b2. The idea is that there's a good chance that the order of the point in the curve over one prime factor divides the multiplier, but the order over another factor doesn't, if b1 and b2 are appropriately chosen. If they are too small, none of the orders will probably divide the multiplier, if they are too large, all probably will, so they should be chosen to fit the expected size of the smallest factor.

It is assumed that n has no small prime factors.

The result is maybe a nontrivial divisor of n.