úÎÐÄX¥      !"#$%&'()*+,-./012 3 4 5 6 7 8 9 : ; < => ? @ A B C D E F G H I JKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œžŸ ¡ ¢ £¤"Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered ¥¦§¨©ª«¬­® ¥¦§¨©ª«¬­® ¥¦§¨©ª«¬­®portable Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered n gives (for n > 0) an 7 approximation of the number of primes not exceeding  n'. The approximation is fairly good for n large enough. 9 The number of primes should be slightly overestimated 8 (so it is suitable for allocation of storage) and is  never underestimated for n <= 10^12.  n gives (for n > 0) an 6 approximation to the n-th prime. The approximation  is fairly good for n large enough. Dual to  , this estimate should err ! on the low side (and does for n < 10^12). Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered k calculates the k-th Fibonacci number in  O( log (abs k))) steps. The index may be negative. This ? is efficient for calculating single Fibonacci numbers (with = large index), but for computing many Fibonacci numbers in < close proximity, it is better to use the simple addition ; formula starting from an appropriate pair of successive  Fibonacci numbers.  k returns the pair (F(k), F(k+1)) of the k-th H Fibonacci number and its successor, thus it can be used to calculate G the Fibonacci numbers from some index on without needing to compute 4 the previous. The pair is efficiently calculated  in O( log (abs k)$) steps. The index may be negative.  k computes the k-th Lucas number. Very similar  to .  k computes the pair (L(k), L(k+1)) of the k-th 3 Lucas number and its successor. Very similar to .  p q k calculates the quadruple (U(k), U(k+1), V(k), V(k+1))  where U(i)- is the Lucas sequence of the first kind and V(i) the Lucas 2 sequence of the second kind for the parameters p and q, where p^2-4q /= 0. 2 Both sequences satisfy the recurrence relation A(j+2) = p*A(j+1) - q*A(j),  the starting values are U(0) = 0, U(1) = 1 and V(0) = 2, V(1) = p. K The Fibonacci numbers form the Lucas sequence of the first kind for the  parameters  p = 1, q = -12 and the Lucas numbers form the Lucas sequence of ) the second kind for these parameters. M Here, the index must be non-negative, since the terms of the sequence for 1 negative indices are in general not integers. Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered@A list of primes. The sieve does not handle overflow, hence for & bounded types, garbage occurs near ¯. If primes that  large are requested, use    ° ± $ ² (<= ³ ¯)  Iinstead. Checking for overflow would be slower. The sieve is specialised  for ´, µ and ¶$, since these are the most commonly  used. For the fixed-width Int or Word types, sieving at one of the / specialised types and converting is faster. O To ensure sharing of the list of primes, bind it to a monomorphic variable, + to make sure that it is not shared, use  with different  arguments.  n generates the list of primes >= n. C The remarks about overflow and performance in the documentation  of  apply here too. Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered·Remove factors of 2 and count them. If   n = 2^k*m with m odd, the result is (k, m).  Precondition: argument not 0 (not checked). ¸Remove factors of 2. If  n = 2^k*m with m odd, the result is m.  Precondition: argument not 0 (not checked). ¹.Shift argument right until the result is odd.  Precondition: argument not 0, not checked. ºLike ¹/, but count the number of places to shift too. »Number of 1-bits in a ¼. ½Number of 1-bits in a µ. ¾Number of 1-bits in an ´. ¿·¸¹º»½¾À ¿·¸¹º»½¾À ¿·¸¹º»½¾ÀNon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered Greatest common divisor of two ´-s, calculated with the binary gcd algorithm. Test whether two ´:s are coprime, using an abbreviated binary gcd algorithm. Greatest common divisor of two µ-s, calculated with the binary gcd algorithm. Test whether two µ:s are coprime, using an abbreviated binary gcd algorithm. Greatest common divisor of two Á-s, calculated with the binary gcd algorithm. Test whether two Ás are coprime. Greatest common divisor of two ¼-s, calculated with the binary gcd algorithm. Test whether two ¼s are coprime.      Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-InferedFCalculate the greatest common divisor using the binary gcd algorithm. H Depending on type and hardware, that can be considerably faster than  Â* but it may also be significantly slower. $There are specialised functions for ´ and µ and rewrite rules  for those and IntN and WordN, N <= 32 , to use the R specialised variants. These types are worth benchmarking, others probably not. It is very slow for ¶6 (and probably every type except the abovementioned), ' I recommend not using it for those. PRelies on twos complement or sign and magnitude representaion for signed types. FCalculate the greatest common divisor of two numbers and coefficients  for the linear combination.  Satisfies:   case extendedGCD a b of  (d, u, v) -> u*a + v*b == d   d == gcd a b and, for signed types,    abs u < abs b || abs b <= 1   abs v < abs a || abs a <= 1 (except if one of a and b is à of a signed type). PTest whether two numbers are coprime using an abbreviated binary gcd algorithm. % A little bit faster than checking binaryGCD a b == 1 if one of the arguments * is even, much faster if both are even. !The remarks about performance at # apply here too, use this function ) only at the types with rewrite rules. PRelies on twos complement or sign and magnitude representaion for signed types. Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered'Invert a number relative to a modulus.  If number and modulus are coprime, the result is   Just inverse where  0 (number * inverse) `mod` (abs modulus) == 1  0 <= inverse < abs modulus unless  modulus == 0 and abs number == 1, in which case the  result is  Just number.  If gcd number modulus > 1, the result is Nothing. Jacobi symbol of two numbers.  The " denominator"6 must be odd and positive, this condition is checked. 7If both numbers have a common prime factor, the result  is 0, otherwise it is ±1. 7Jacobi symbol of two numbers without validity check of  the " denominator". Modular power.   powerMod base exponent modulus  calculates (base ^ exponent) `mod` modulus% by repeated squaring and reduction.  If  exponent < 0 and base is invertible modulo modulus, (inverse ^ |exponent|) `mod` modulus j is calculated. This function does some input checking and sanitation before calling the unsafe worker. -Modular power worker without input checking. G Assumes all arguments strictly positive and modulus greater than 1. Specialised version of  for ¶ exponents. ? Reduces the number of shifts of the exponent since shifting  large ¶,s is expensive. Call this function directly  if you don' t want or can't rely on rewrite rules. DSpecialised worker without input checks. Makes the same assumptions  as the general version . sqrtModP n prime% calculates a modular square root of n modulo prime ' if that exists. The second argument must" be a (positive) prime, otherwise O the computation may not terminate and if it does, may yield a wrong result.  The precondition is not checked. If prime is a prime and n a quadratic residue modulo prime , the result  is Just r where r^2 "a n (mod prime), if n is a quadratic nonresidue,  the result is Nothing. sqrtModPList n prime* computes the list of all square roots of n  modulo prime. prime must be a (positive) prime.  The precondition is not checked. sqrtModP' square prime finds a square root of square modulo  prime. prime must be a (positive) prime, and sqaure must be a  quadratic residue modulo prime, i.e. 'jacobi square prime == 1.  The precondition is not checked. tonelliShanks square prime calculates a square root of square  modulo prime, where prime is a prime of the form 4*k + 1 and  square is a quadratic residue modulo prime , using the  Tonelli-Shanks algorithm. ) No checks on the input are performed. sqrtModPP n (prime,expo) calculates a square root of n  modulo  prime^expo if one exists. prime must be a  (positive) prime. expo must be positive, n must be coprime  to prime sqrtModF n primePowers calculates a square root of n modulo  product [p^k | (p,k) < - primePowers] if one exists and all primes  are distinct. !sqrtModFList n primePowers calculates all square roots of n modulo  product [p^k | (p,k) < - primePowers] if all primes are distinct. "sqrtModPPList n (prime,expo) calculates the list of all  square roots of n modulo  prime^expo. The same restriction  as in  applies to the arguments. # Given a list [(r_1,m_1), ..., (r_n,m_n)] of (residue,modulus)  pairs, chineseRemainder- calculates the solution to the simultaneous  congruences    r "a r_k (mod m_k)  :if all moduli are pairwise coprime. If not all moduli are # pairwise coprime, the result is Nothing regardless of whether  a solution exists. $%chineseRemainder2 (r_1,m_1) (r_2,m_2) calculates the solution of    r "a r_k (mod m_k) if m_1 and m_2 are coprime.  !"#$ !"#$#" !$ !"#$Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-InferedÄÅNon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-InferedÆ Power of an ¶3 by the left-to-right repeated squaring algorithm. G This needs two multiplications in each step while the right-to-left D algorithm needs only one multiplication for 0-bits, but here the I two factors always have approximately the same size, which on average  gains a bit. ÆÆÆNon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-InferedÇTotient of a prime power. %8Calculate the totient from the canonical factorisation. &:Calculate the Carmichael function from the factorisation. B Requires that the list of prime factors is strictly ascending. 'NThe set of divisors, efficiently calculated from the canonical factorisation. (QThe number of divisors, efficiently calculated from the canonical factorisation. )RThe sum of all divisors, efficiently calculated from the canonical factorisation. *=The sum of the powers (with fixed exponent) of all divisors, < efficiently calculated from the canonical factorisation. Ç%&'()*Ç%&'()*Ç%&'()*Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered+:Calculate the integer square root of a nonnegative number n,  that is, the largest integer r with r*r <= n. & Throws an error on negative input. ,:Calculate the integer square root of a nonnegative number n,  that is, the largest integer r with r*r <= n.  The precondition n >= 0 is not checked. -Returns È" if the argument is not a square,  É r if r*r == n and r >= 0#. Avoids the expensive calculation  of the square root if n is recognized as a non-square < before, prevents repeated calculation of the square root 4 if only the roots of perfect squares are needed.  Checks for negativity and 0. .'Test whether the argument is a square. 1 After a number is found to be positive, first 0 @ is checked, if it is, the integer square root is calculated. /.Test whether the input (a nonnegative number) n is a square.  The same as .#, but without the negativity test. 5 Faster if many known positive numbers are tested. The precondition n >= 0! is not tested, passing negative * arguments may cause any kind of havoc. 04Test whether a non-negative number may be a square. A Non-negativity is not checked, passing negative arguments may  cause any kind of havoc. BFirst the remainder modulo 256 is checked (that can be calculated E easily without division and eliminates about 82% of all numbers). D After that, the remainders modulo 9, 25, 7, 11 and 13 are tested 9 to eliminate altogether about 99.436% of all numbers. This is the test used by -. For large numbers, + the slower but more discriminating test isPossibleSqure2 is  faster. 14Test whether a non-negative number may be a square. A Non-negativity is not checked, passing negative arguments may  cause any kind of havoc. BFirst the remainder modulo 256 is checked (that can be calculated E easily without division and eliminates about 82% of all numbers). E After that, the remainders modulo several small primes are tested ; to eliminate altogether about 99.98954% of all numbers. BFor smallish to medium sized numbers, this hardly performs better  than 0+, which uses smaller arrays, but for large F numbers, where calculating the square root becomes more expensive, A it is much faster (if the vast majority of tested numbers aren' t squares). +,-./01+,-./01+,-./01+,-./01 Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered2 totientSum n is, for n > 0 , the sum of [totient k | k < - [1 .. n]], / computed via generalised Moebius inversion. 6 Arguments less than 1 cause an error to be raised. 3generalInversion g n0 evaluates the generalised Moebius inversion of g  at the argument n. GThe generalised Moebius inversion implemented here allows an efficient 2 calculation of isolated values of the function  f : N -> Z if the function  g defined by   , g n = sum [f (n `quot` k) | k <- [1 .. n]]  Lcan be cheaply computed. By the generalised Moebius inversion formula, then   8 f n = sum [moebius k * g (n `quot` k) | k <- [1 .. n]]   which allows the computation in O (n) steps, if the values of the H Moebius function are known. A slightly different formula, used here, C does not need the values of the Moebius function and allows the  computation in O(n^0.75) steps, using O(n^0.5) memory. DAn example of a pair of such functions where the inversion allows a : more efficient computation than the direct approach is   @ f n = number of reduced proper fractions with denominator <= n  8 g n = number of proper fractions with denominator <= n  (a proper fraction is a fraction 0 < n/d < 1). Then f n is the . cardinality of the Farey sequence of order n (minus 1 or 2 if 0 and/or H 1 are included in the Farey sequence), or the sum of the totients of  the numbers 2 <= k <= n. f n$ is not easily directly computable,  but then  g n = n*(n-1)/22 is very easy to compute, and hence the inversion * gives an efficient method of computing f n. FSince the function arguments are used as array indices, the domain of  f is restricted to ´.  The value f n is then computed by generalInversion g n). Note that when  many values of f8 are needed, there are far more efficient methods, this < method is only appropriate to compute isolated values of f. 23233223 Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered4 totientSum n is, for n > 0 , the sum of [totient k | k < - [1 .. n]], / computed via generalised Moebius inversion. 6 Arguments less than 1 cause an error to be raised. 5generalInversion g n0 evaluates the generalised Moebius inversion of g  at the argument n. GThe generalised Moebius inversion implemented here allows an efficient 2 calculation of isolated values of the function  f : N -> Z if the function  g defined by   , g n = sum [f (n `quot` k) | k <- [1 .. n]]  Lcan be cheaply computed. By the generalised Moebius inversion formula, then   8 f n = sum [moebius k * g (n `quot` k) | k <- [1 .. n]]   which allows the computation in O (n) steps, if the values of the H Moebius function are known. A slightly different formula, used here, C does not need the values of the Moebius function and allows the  computation in O(n^0.75) steps, using O(n^0.5) memory. DAn example of a pair of such functions where the inversion allows a : more efficient computation than the direct approach is   @ f n = number of reduced proper fractions with denominator <= n 8 g n = number of proper fractions with denominator <= n  (a proper fraction is a fraction 0 < n/d < 1). Then f n is the . cardinality of the Farey sequence of order n (minus 1 or 2 if 0 and/or H 1 are included in the Farey sequence), or the sum of the totients of  the numbers 2 <= k <= n. f n$ is not easily directly computable,  but then  g n = n*(n-1)/22 is very easy to compute, and hence the inversion * gives an efficient method of computing f n. For ´F valued functions, unboxed arrays can be used for greater efficiency. N That bears the risk of overflow, however, so be sure to use it only when it's  safe.  The value f n is then computed by generalInversion g n). Note that when  many values of f8 are needed, there are far more efficient methods, this < method is only appropriate to compute isolated values of f. 45455445Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered6"Compact store of primality flags. 7,Sieve primes up to (and including) a bound. 8 For small enough bounds, this is more efficient than  using the segmented sieve. Since arrays are ´)-indexed, overflow occurs when the sieve  size comes near ¯ :: ´, that corresponds to an  upper bound near 15/8*¯. On 32-bit systems, that ( is often within memory limits, so don't give bounds larger than  8*10^9 there. 81Generate a list of primes for consumption from a  6. 9List of primes. G Since the sieve uses unboxed arrays, overflow occurs at some point. A On 64-bit systems, that point is beyond the memory limits, on " 32-bit systems, it is at about  1.7*10^18. :(List of primes in the form of a list of 6s, more compact than  9, thus it may be better to use : >>= 8 @ than keeping the list of primes alive during the entire run. ÊSieve up to bound in one go. ;; n* creates the list of primes not less than n. << n creates the list of 6s starting roughly  at n=. Due to the organisation of the sieve, the list may contain  a few primes less than n. # This form uses less memory than [¶], hence it may be preferable & to use this if it is to be reused. 6ËÌÍÎÏ789:ÊÐ;<ÑÒÓ6ËÌÍÎÏ789:ÊÐ;<ÑÒÓ6ËÌÍÎÏ789:ÊÐ;<ÑÒÓ Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered6789:;<9;67:<8Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-InferedÔ Factorise an ¶1 using a given list of numbers considered prime. K If the list is not a list of primes containing all relevant primes, the  result could be surprising. == 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. ÕDCheck whether a number is coprime to all of the numbers in the list D (assuming that list contains only numbers > 1 and is ascending). >> bound n tests whether n is coprime to all primes <= bound.  If n < = bound^2., this is a full prime test, but very slow if n has no small prime divisors. Ô=Õ>Ô=Õ>Ô=Õ>Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered?? n tests whether n$ is a prime (negative or positive). 1 First, trial division by the primes less than 1200 is performed.  If that hasn'7t determined primality or compositeness, a Baillie PSW  test is performed. CSince the Baillie PSW test may not be perfect, it is possible that J some large composites are wrongly deemed prime, however, no composites 3 passing the test are known and none exist below 2^64. @@A Miller-Rabin like probabilistic primality test with preceding < trial division. While the classic Miller-Rabin test uses  randomly chosen bases, @ k n uses the k > smallest primes as bases if trial division has not reached / a conclusive result. (Only the primes up to 1200 are 6 available in this module, so the maximal effective k is 196.) AA n b tests whether n is a strong Fermat  probable prime for base b, where n > 2 and 1 < b < n. 4 The conditions on the arguments are not checked. ?Apart from primes, also some composite numbers have the tested A property, but those are rare. Very rare are composite numbers @ having the property for many bases, so testing a large prime ? candidate with several bases can identify composite numbers ( with high probability. An odd number n > 3 is prime if and  only if A n b holds for all b with  2 <= b <= (n-1)/2), but of course checking all those bases @ would be less efficient than trial division, so one normally @ checks only a relatively small number of bases, depending on D the desired degree of certainty. The probability that a randomly  chosen base doesn't identify a composite number n is less than  1/4<, so five to ten tests give a reasonable level of certainty  in general. &Some notes about the choice of bases: b is a strong Fermat base  for n if and only if n-b is, hence one needs only test b <= (n-1)/2.  If b is a strong Fermat base for n , then so is b^k Ö n for  all k > 17, hence one needs not test perfect powers, since their 1 base yields a stronger condition. Finally, if a and b are strong  Fermat bases for n, then a*b" is in most cases a strong Fermat  base for n, it can only fail to be so if n Ö 4 == 1 and ? the strong Fermat condition is reached at the same step for a as for b, 2 so primes are the most powerful bases to test. BB n b tests whether n is a Fermat probable prime  for the base b, that is, whether b^(n-1) Ö n == 1. A This is a weaker but simpler condition. However, more is lost G in strength than is gained in simplicity, so for primality testing, 6 the strong check should be used. The remarks about $ the choice of bases to test from A apply ! with the modification that if a and b are Fermat bases  for n, then a*b always is a Fermat base for n too.  A Charmichael number is a composite number n which is a ' Fermat probable prime for all bases b coprime to n . By the  above, only primes p <= n/2 not dividing n need to be tested > to identify Carmichael numbers (however, testing all those B primes would be less efficient than determining Carmichaelness C from the prime factorisation; but testing an appropriate number 6 of prime bases is reasonable to find out whether it' s worth the 1 effort to undertake the prime factorisation). CAPrimality test after Baillie, Pomerance, Selfridge and Wagstaff. G The Baillie PSW test consists of a strong Fermat probable primality I test followed by a (strong) Lucas primality test. This implementation  assumes that the number n to test is odd and larger than 3. B Even and small numbers have to be handled before. Also, before J applying this test, trial division by small primes should be performed I to identify many composites cheaply (although the Baillie PSW test is I rather fast, about the same speed as a strong Fermat test for four or G five bases usually, it is, for large numbers, much more costly than 8 trial division by small primes, the primes less than 1000 , say, so O eliminating numbers with small prime factors beforehand is more efficient). CThe Baillie PSW test is very reliable, so far no composite numbers B passing it are known, and it is known (Gilchrist 2010) that no ( Baillie PSW pseudoprimes exist below 2^64 . However, a heuristic argument L by Pomerance indicates that there are likely infinitely many Baillie PSW 1 pseudoprimes. On the other hand, according to   :http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html there is @ reason to believe that there are none with less than several ? thousand digits, so that for most use cases the test can be  considered definitive. ×>The Lucas-Selfridge test, including square-check, but without 3 the Fermat test. For package-internal use only. ?@ABC×?@ABC×?@ABC× Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-InferedD.Calculate the integer cube root of an integer n,  that is the largest integer r such that r^3 <= n. ) Note that this is not symmetric about 0, for example  integerCubeRoot (-2) = (-2) while integerCubeRoot 2 = 1. E9Calculate the integer cube root of a nonnegative integer n,  that is, the largest integer r such that r^3 <= n.  The precondition n >= 0 is not checked. FReturns Nothing if the argument is not a cube,  Just r if n == r^3. G#Test whether an integer is a cube. H.Test whether a nonnegative integer is a cube.  Before D is calculated, a few tests > of remainders modulo small primes weed out most non-cubes. / For testing many numbers, most of which aren' t cubes,  this is much faster than  let r = cubeRoot n in r*r*r == n.  The condition n >= 0 is not checked. I6Test whether a nonnegative number is possibly a cube. 3 Only about 0.08% of all numbers pass this test.  The precondition n >= 0 is not checked. DEFGHIDEFGHIDEFGHIDEFGHINon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-InferedJ;Calculate the integer fourth root of a nonnegative number,  that is, the largest integer r with r^4 <= n. & Throws an error on negaitve input. K;Calculate the integer fourth root of a nonnegative number,  that is, the largest integer r with r^4 <= n.  The condition is not checked. LReturns Nothing if n is not a fourth power,  Just r if n == r^4 and r >= 0. M+Test whether an integer is a fourth power. 6 First nonnegativity is checked, then the unchecked  test is called. N5Test whether a nonnegative number is a fourth power.  The condition is not! checked. If a number passes the  O test, its integer fourth root  is calculated. O>Test whether a nonnegative number is a possible fourth power.  The condition is not checked. - This eliminates about 99.958% of numbers. JKLMNOJKLMNOJKLMNOJKLMNONon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-InferedPCalculate an integer root, P k n computes the (floor of) the k-th  root of n, where k must be positive.  r = P k n means r^k <= n < (r+1)^k if that is possible at all.  It is impossible if k is even and n < 0 , since then r^k >= 0 for all r,  then, and if k <= 0, P raises an error. For k < 5, a specialised P version is called which should be more efficient than the general algorithm. N However, it is not guaranteed that the rewrite rules for those fire, so if k is L known in advance, it is safer to directly call the specialised versions. QQ k n returns È if n is not a k -th power,  É r if n == r^k. If k is divisible by 4, 3 or 2, a F residue test is performed to avoid the expensive calculation if it  can thus be determined that n is not a k -th power. RR k n checks whether n is a k -th power. SS n checks whether n == r^k for some k > 1. TT n produces the pair (b,k) with the largest  exponent k such that n == b^k , except for Ø n <= 1, > in which case arbitrarily large exponents exist, and by an  arbitrary decision (n,3) is returned. BFirst, by trial division with small primes, the range of possible  exponents is reduced (if p^e exactly divides n, then k must  be a divisor of e!, if several small primes divide n, k must G divide the greatest common divisor of their exponents, which mostly  will be 17, generally small; if none of the small primes divides  n?, the range of possible exponents is reduced since the base is F necessarily large), if that has not yet determined the result, the > remaining factor is examined by trying the divisors of the gcd G of the prime exponents if some have been found, otherwise by trying  prime exponents recursively. PQRSTPQRSTPQRSTPQRSTNon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered+-.DFGJLMPQRST+.-DGFJMLPRQSTNon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-InferedU7Calculate the integer logarithm for an arbitrary base. D The base must be greater than 1, the second argument, the number N whose logarithm is sought, must be positive, otherwise an error is thrown.  If  base == 23, the specialised version is called, which is more ) efficient than the general algorithm.  Satisfies:  H base ^ integerLogBase base m <= m < base ^ (integerLogBase base m + 1) for base > 1 and m > 0. V&Calculate the integer logarithm of an ¶ to base 2. @ The argument must be positive, otherwise an error is thrown. W&Calculate the integer logarithm of an ´ to base 2. @ The argument must be positive, otherwise an error is thrown. X%Calculate the integer logarithm of a µ to base 2. @ The argument must be positive, otherwise an error is thrown. YSame as V/, but without checks, saves a little time when & called often for known good input. ZSame as W/, but without checks, saves a little time when & called often for known good input. [Same as X/, but without checks, saves a little time when & called often for known good input. \Same as U/, but without checks, saves a little time when & called often for known good input. UVWXYZ[\UVWXYZ[\UVWX\YZ[UVWXYZ[\Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered ]] n% produces the prime factorisation of n , including  a factor of (-1) if n < 0. ] 0 is an error and the  factorisation of 1 is empty. Uses a Ù produced in an arbitrary " manner from the bit-pattern of n. ^Like ]$, but without input checking, hence n > 1 is required. __ is like ^, except that it doesn't use a B pseudo random generator but steps through the curves in order. G This strategy turns out to be surprisingly fast, on average it doesn't  seem to be slower than the Ù based variant. ``4 first strips off all small prime factors and then, J 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 04 has no prime factorisation, a zero argument causes  an error. aLike `!, but without input checking, so  n must be larger than 1. bA wrapper around c$ providing a few default arguments.  The primality test is C, the prng function - naturally -  Ú?. This function also requires small prime factors to have been  stripped before. ccD is the driver for the factorisation. Its performance (and success) H 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 X first argument allows skipping the comparatively expensive primality test for those.  If nT is such that all prime divisors must have a specific easy to test for structure, a Y custom primality test can improve the performance (normally, it will make very little  difference, since nG 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 b and an initial state for the PRNG) used to generate the curves to try. A lucky choice here can g make a huge difference. So, if the default takes too long, try another one; or you can improve your H chances for a quick result by running several instances in parallel. cJ requires that small prime factors have been stripped before. Also, it is  unlikely to succeed if n0 has more than one (really) large prime factor. dd 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 5 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 S 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. R If they are too small, none of the orders will probably divide the multiplier, M 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. ee bound n finds all prime divisors of n > 1 up to bound# by trial division and returns the m list of these together with their multiplicities, and a possible remaining factor which may be composite. ]^_`ab#Lower bound for composite divisors Standard PRNG 4Estimated number of digits of smallest prime factor The number to factorise $List of prime factors and exponents c#Lower bound for composite divisors A primality test A PRNG Initial PRNG state 8Estimated number of digits of the smallest prime factor The number to factorise $List of prime factors and exponents deÛ ]^_`abcdeÛ ]^_`abcdeÛNon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered f6A compact store of values of the Carmichael function. gA compact store of totients. h+A compact store of smallest prime factors. ii nH creates a store of smallest prime factors of the numbers not exceeding n. _ If you need to factorise many smallish numbers, this can give a big speedup since it avoids c many superfluous divisions. However, a too large sieve leads to a slowdown due to cache misses. # The prime factors are stored as Ü for compactness, so n must be  smaller than 2^32. ÝÝ sieveG tells the limit to which the sieve stores the smallest prime factors. ÞÞ sieve n checks in the sieve whether n is prime. If n is larger 2 than the sieve can handle, an error is raised. jj fs n" finds the prime factorisation of n using the h fs.  For negative n, a factor of -1 is included with multiplicity 1. ' After stripping any present factors 2, the remaining cofactor c (if larger  than 1) is factorised with fs&. This is most efficient of course if c does not  exceed the bound with which fs: was constructed. If it does, trial division is performed \ until either the cofactor falls below the bound or the sieve is exhausted. In the latter H case, the elliptic curve method is used to finish the factorisation. kk n> creates a store of the totients of the numbers not exceeding n.  A g+ only stores values for numbers coprime to 30 to reduce space usage. $ The maximal admissible value for n is ³ (¯ :: µ). ll ts n finds the totient À(n), i.e. the number of integers k with  1 <= k <= n and  n k == 12, in other words, the order of the group of units  in !$/(n) , using the g ts.  First, factors of 2, 3 and 5, are handled individually, if the remaining  cofactor of n@ is within the sieve range, its totient is looked up, otherwise L the calculation falls back on factorisation, first by trial division and " if necessary, elliptic curves. mm n6 creates a store of values of the Carmichael function  for numbers not exceeding n.  Like a g, a f+ only stores values for numbers coprime to 30 ; to reduce space usage. The maximal admissible value for n is ³ (¯ :: µ). nn cs n finds the value of »(n) (or È(n)), the smallest positive  integer e such that for all a with  gcd a n == 1 the congruence a^e "a 1 (mod n) holds, D in other words, the (smallest) exponent of the group of units in !$/(n).  The strategy is analogous to l. fghiÝÞjklmn fghiÝÞjklmn fghiÝÞjklmnNon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered o,Calculates the totient of a positive number n, i.e.  the number of k with 1 <= k <= n and  n k == 1, 6 in other words, the order of the group of units in !$/(n). p Alias of o& for people who prefer Greek letters. qDCalculates the Carmichael function for a positive integer, that is, 4 the (smallest) exponent of the group of units in &8484;/(n). r Alias of q& for people who prefer Greek letters. ss n* is the set of all (positive) divisors of n.  s 0 is an error because we can't create the set of all ¶s. tt n) is the number of (positive) divisors of n.  t 0 is an error because 0 has infinitely many divisors. u Alias for t. v8The sum of all (positive) divisors of a positive number n, , calculated from its prime factorisation. w Alias for x. xx k n is the sum of the k-th powers of the  (positive) divisors of n. k must be non-negative and n positive.  For k == 0, it is the divisor count (d^0 = 1). y Alias for x& for people preferring Greek letters. z Alias for t& for people preferring Greek letters. opqrstuvwxyz%%&'()*=]^_`abcdefghijklmnopqrstuvwxyz%]`_^ahij=ebcdopgkl%qrfmn&stzuvxyw'()* opqrstuvwxyzNon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered{5An argument for primality of a number (which must be > 1).  …s translate directly to PrimalityArguments, J correct arguments can be transformed into proofs. This type allows the ? manipulation of proofs while maintaining their correctness. * The only way to access components of a … except # the prime is through this type. |Primality assumed }aprime6 is said to be obviously prime, that holds for primes < 30 ~2Primality should be provable by trial division to alimit €$A suggested Pocklington certificate …7A proof of primality of a positive number. The type is . abstract to ensure the validity of proofs. †&The number whose primality is proved. &The number whose primality is proved. &The number whose primality is proved. ‡9An argument for compositeness of a number (which must be > 1).  s translate directly to CompositenessArguments, J correct arguments can be transformed into proofs. This type allows the ? manipulation of proofs while maintaining their correctness. * The only way to access components of a  except ' the composite is through this type. ˆNo particular reason given ‰compo fails the Lucas-Selfridge test Šcompo" fails the strong Fermat test for  fermatBase Œcompo == firstDiv*secondDiv, where all are > 1 ;A proof of compositeness of a positive number. The type is . abstract to ensure the validity of proofs. ‘*The number whose compositeness is proved. *The number whose compositeness is proved. *The number whose compositeness is proved. ’9A certificate of either compositeness or primality of an  ¶. Only numbers > 1 can be certified, trying to ; create a certificate for other numbers raises an error. ––A transforms a proof of primality into an argument for primality. ——7 checks the given argument and constructs a proof from V it, if it is valid. For the explicit arguments, this is simple and resonably fast,  for an |, the verification uses ! and hence may take a long time. ˜˜6 transforms a proof of compositeness into an argument  for compositeness. ™™7 checks the given argument and constructs a proof from V it, if it is valid. For the explicit arguments, this is simple and resonably fast,  for a ˆ, the verification uses ! and hence may take a long time. šCheck the validity of a ’ . Since it should be impossible J to construct invalid certificates by the public interface, this should  never return ß. ›Check the validity of a . Since it should be E impossible to create invalid proofs by the public interface, this  should never return ß. œCheck the validity of a …. Since it should be E impossible to create invalid proofs by the public interface, this  should never return ß. àà" records a trivially known prime. ; If the argument is not one of them, an error is raised. á<Certify a small number. This is not exposed and should only B be used where correct. It is always checked after use, though,  so it shouldn't be able to lie.  n constructs, for n > 1, a proof of either ! primality or compositeness of n. This may take a very long 7 time if the number has no small(ish) prime divisors âVCertify a number known to be not too small, having no small prime divisors and having / passed the Baillie PSW test. So we assume it's prime, erroring if not.  Since it'#s presumably a large number, we don'!t bother with trial division and ( construct a Pocklington certificate. 3{|}~€‚ƒ„…ãäåæ†çè釈‰Š‹ŒŽêëìí‘îï’“”•–—˜™š›œàáâ3{|}~€‚ƒ„…ãäåæ†çè釈‰Š‹ŒŽêëìí‘îï’“”•–—˜™š›œàáâ{ €~}|‚ƒ„… æäã†çèé†å†‡ ŒŠ‰ˆŽ‹ íëê‘îï‘ì‘’”“•–—˜™š›œàáâNon-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Inferedžž n" produces the prime factorisation  of n1, proving the primality of the factors, but doesn't report the proofs. ŸŸ n produces a    with a default bound of 100000.    bound n) constructs a the prime factorisation of n 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 N 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 9 will usually be slow (but should be faster than using ] and 7 proving the primality of the factors from scratch). žŸ žŸ žŸ žŸ Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered#{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œ/’”“•‘‘‘‘…††††‡ŒŠ‰ˆŽ‹{€~}|‚ƒ„–˜—™š›œ Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered¡¡ n tests primality of n, first trial division G by small primes is performed, then a Baillie PSW test and finally a J prime certificate is constructed and verified, provided no step before  found n; to be composite. Constructing prime certificates can take  a very# long time, so use this with care. ¡¡¡ Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered¢Test primality using a h. If n is out of bounds  of the sieve, fall back to ?. ¢ >?@ABCh¡¢ ?¡C@ABh¢>¢! non-portable Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered££ n == À(n)2 is the number of (positive) primes not exceeding n. OFor efficiency, the calculations are done on 64-bit signed integers, therefore n must  not exceed  8 * 10^18.  Requires O(n^0.5)' space, the time complexity is roughly O(n^0.7).  For small bounds, £ n( simply counts the primes not exceeding n,  for bounds from 30000 on, Meissel'0s algorithm is used in the improved form due to  D.H. Lehmer, cf.   \http://en.wikipedia.org/wiki/Prime_counting_function#Algorithms_for_evaluating_.CF.80.28x.29. ¤¤ n calculates the n"-th prime. Numbering of primes is  1 -based, so ¤ 1 == 2.  Requires O((n*log n)^0.5)' space, the time complexity is roughly O((n*log n)^0.7. ? The argument must be strictly positive, and must not exceed  1.5 * 10^17. £¤£¤£¤ non-portable Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered£¤£¤"Non-portable (GHC extensions) Provisional1Daniel Fischer <daniel.is.fischer@googlemail.com> Safe-Infered8%&'()*6789:;<=>?@ABC]^_`abcdefghijklmnopqrstuvwxyz¡¢£¤ð#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRST U V U VWXY*Z+[\]^_`ab c d e f g hijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œžŸ ¡¢£¤¥¦§¨©ª«¬­®¯°±²³´µ¶·¸¹º»¼½¾¿ À Á!Â!ÃÄÅÆÇÈ“ÉÊËÌÍÎÏÍÐÑÍÒÓÍÔÕÍÖ×ØÙÚÍÛÜÝÞßàáâãäØåæçèéêØåëÍÖìÍÎíÝîïÝîðñòÍóôÍóõö÷øùúûüýþÿÍÖÍÒ ÍÛ   ØÙ arithmoi-0.4.0.3!Math.NumberTheory.Primes.CountingMath.NumberTheory.LucasMath.NumberTheory.Primes.HeapMath.NumberTheory.GCD.LowLevelMath.NumberTheory.GCDMath.NumberTheory.Moduli&Math.NumberTheory.Primes.Factorisation Math.NumberTheory.Powers.Squares"Math.NumberTheory.MoebiusInversion&Math.NumberTheory.MoebiusInversion.IntMath.NumberTheory.Primes.Sieve Math.NumberTheory.Primes.TestingMath.NumberTheory.Powers.CubesMath.NumberTheory.Powers.Fourth Math.NumberTheory.Powers.GeneralMath.NumberTheory.Logarithms-Math.NumberTheory.Primes.Testing.Certificates0Math.NumberTheory.Primes.Factorisation.Certified'Math.NumberTheory.Primes.Sieve.Indexing-Math.NumberTheory.Primes.Counting.ApproximateMath.NumberTheory.Utils%Math.NumberTheory.Logarithms.Internal Math.NumberTheory.Powers.Integer,Math.NumberTheory.Primes.Factorisation.Utils+Math.NumberTheory.Primes.Sieve.Eratosthenes4Math.NumberTheory.Primes.Factorisation.TrialDivision.Math.NumberTheory.Primes.Testing.ProbabilisticMath.NumberTheory.Powers1Math.NumberTheory.Primes.Factorisation.Montgomery#Math.NumberTheory.Primes.Sieve.Misc6Math.NumberTheory.Primes.Testing.Certificates.Internal*Math.NumberTheory.Primes.Testing.Certified&Math.NumberTheory.Primes.Counting.ImplMath.NumberTheory.PrimesapproxPrimeCountnthPrimeApprox fibonacci fibonacciPairlucas lucasPair generalLucasprimes sieveFromgcdInt coprimeIntgcdWord coprimeWordgcdInt# coprimeInt#gcdWord# coprimeWord# binaryGCD extendedGCDcoprime invertModjacobijacobi'powerMod powerMod'powerModIntegerpowerModInteger'sqrtModP sqrtModPList sqrtModP' tonelliShanks sqrtModPPsqrtModF sqrtModFList sqrtModPPListchineseRemainderchineseRemainder2totientFromCanonicalcarmichaelFromCanonicaldivisorsFromCanonicaltauFromCanonicaldivisorSumFromCanonicalsigmaFromCanonicalintegerSquareRootintegerSquareRoot'exactSquareRootisSquare isSquare'isPossibleSquareisPossibleSquare2 totientSumgeneralInversion PrimeSieve primeSieve primeList psieveList psieveFromtrialDivisionTotrialDivisionPrimeToisPrime millerRabinVisStrongFermatPP isFermatPP bailliePSWintegerCubeRootintegerCubeRoot' exactCubeRootisCubeisCube'isPossibleCubeintegerFourthRootintegerFourthRoot'exactFourthRoot isFourthPowerisFourthPower'isPossibleFourthPower integerRoot exactRoot isKthPowerisPerfectPower highestPowerintegerLogBase integerLog2intLog2wordLog2 integerLog2'intLog2' wordLog2'integerLogBase' factorise factorise'stepFactorisationdefaultStdGenFactorisationdefaultStdGenFactorisation'stdGenFactorisationcurveFactorisationmontgomeryFactorisation smallFactorsCarmichaelSieve TotientSieve FactorSieve factorSieve sieveFactor totientSieve sieveTotientcarmichaelSievesieveCarmichaeltotientφ carmichaelλdivisorstau divisorCount divisorSumdivisorPowerSumsigmaσÏ„PrimalityArgument AssumptionObviousDivisionalimitPockaprime largeFactor smallFactor factorListPrimalityProofcprimeCompositenessArgumentBeliefLucasFermat fermatBaseDivisorscompo firstDivisor secondDivisorCompositenessProof composite CertificatePrime CompositeargueCertificatearguePrimalityverifyPrimalityArgumentargueCompositenessverifyCompositenessArgumentcheckCertificatecheckCompositenessProofcheckPrimalityProofcertifycertifiedFactorisationcertificateFactorisationprovenFactorisationisCertifiedPrime fsIsPrime primeCountnthPrimeidxPrtoPrimtoIdxrhodeltabyteidxmunubaseGHC.EnummaxBoundGHC.BasemapGHC.Num fromIntegerGHC.List takeWhileGHC.Real fromIntegralghc-prim GHC.TypesIntGHC.WordWord integer-gmpGHC.Integer.TypeIntegershiftToOddCount shiftToOdd shiftToOdd#shiftToOddCount# bitCountWord#GHC.PrimWord# bitCountWord bitCountIntuncheckedShiftRsplitOffInt#gcdminBoundGHC.Integer.Logarithms wordLog2# integerLog2# integerPower ppTotient Data.MaybeNothingJustsieveToPS sieveBytes sieveBits sieveRange sieveWords countFromTo nthPrimeCt countToNthcountAlltrialDivisionWithtrialDivisionPrimeWithmod lucasTestabsrandom-1.0.1.1 System.RandomStdGenrandomR findParmsWord16fsBound fsPrimeTestFalsetrivial smallCert certifyBPSWTrivial TrialDivisiontdLimit PocklingtonfactorisedPartcofactor knownFactorsLucasSelfridge StrongFermatwitnessFactors firstFactor secondFactor