Primes and number theory

OverviewPrimality testing for word-size integersHow n_is_prime proves primality of any 64-bit integer with at most two strong probable prime tests, using table lookups, vectorised trial division and a hashed table of witnesses.

OverviewFactoring word-size integersHow n_factor combines trial division, primality testing, perfect power detection, Pollard–Brent rho, Hart's one-line method and SQUFOF to factor any 64-bit integer.

AlgorithmPrimality proving: APRCL and ECPPHow FLINT proves the primality of large integers, by n \pm 1 tests when the factorisations allow it, by the APRCL test with Jacobi sums, and by elliptic curve primality proving with verifiable certificates.

OverviewFactoring integersThe factoring methods available in FLINT (trial division, Pollard rho, p \pm 1, ECM, SQUFOF and the quadratic sieve), their running times, and how fmpz_factor combines them.

AlgorithmSquare roots modulo a primeHow nmod_sqrt finds a square root modulo a word-size prime n. It uses one exponentiation when n \equiv 3 \pmod 4 or n \equiv 5 \pmod 8, and otherwise Tonelli–Shanks in two forms or Müller's variant of Cipolla–Lehmer, depending on the power of 2 dividing n - 1. Every candidate root is checked by squaring.

AlgorithmThe elliptic curve methodLenstra's elliptic curve method for finding a prime factor p of N, with Montgomery curves, Suyama's parametrisation, the Montgomery ladder in stage 1 and the standard continuation in stage 2.

AlgorithmThe quadratic sieveFactoring N by finding a congruence of squares from many smooth values of quadratic polynomials, with self-initialising polynomials, a block and bucket sieve, the large prime variation and block Lanczos linear algebra.

AlgorithmDiscrete logarithms modulo a prime (Pohlig–Hellman)Computes x with g^x = y modulo a prime p by solving the problem in each subgroup of prime-power order of (\mathbb{Z}/p\mathbb{Z})^\times, one base-q digit at a time, and combining the results by the Chinese remainder theorem. Fast when p - 1 has only small prime factors.

AlgorithmDiscrete logarithm tablesPrecomputations for many discrete logarithms in a fixed cyclic group modulo a word-size prime power, combining baby-step giant-step tables sized for the number of queries, the Pohlig–Hellman decomposition and p-adic logarithms, and a sieve for the logarithms of all small integers.

AlgorithmStrong probable prime testThe Miller–Rabin test for a single base. Every odd prime passes it, at most a quarter of the bases let a composite pass, and with tabulated pseudoprimes it becomes a proof of primality for word-size integers.

AlgorithmComputing the partition functionComputes p(n) exactly by the Hardy–Ramanujan–Rademacher series, truncated with Rademacher's error bound, with the exponential sums factored into products of cosines and each term evaluated in ball arithmetic at the precision it needs; small values come from Euler's pentagonal recurrence.

AlgorithmGaussian integersDivision with remainder, the canonical associate, and the four GCD algorithms of fmpzi (Euclidean in exact and floating-point arithmetic, the (1+i)-ary binary algorithm, and a lattice algorithm), together with primality testing and the removal of factors 1+i.

AlgorithmBernoulli numbersComputes exact Bernoulli numbers from the zeta function (numerically, with the denominator from von Staudt–Clausen), from Harvey's multimodular algorithm, by a reverse zeta iterator with a table of powers for ranges, and by Ramanujan's recursion or power series modulo primes for short vectors.

AlgorithmArithmetic in number fieldsHow nf_elem represents elements of Q[x]/(f) with special cases for degrees 1 and 2 and for Q(i), multiplies with reduction by precomputed powers of the generator, inverts by the extended Euclidean algorithm, and computes norms as resultants and traces from power sums of the roots.

AlgorithmRational reconstructionRecovers a fraction n/d with |n| \le N and 0 < d \le D from its residue modulo m > 2ND by stopping the extended Euclidean algorithm at the first remainder below N. Used to return rational results from multimodular and p-adic algorithms.

AlgorithmContinued fractions of rational numbersComputes the continued fraction of a rational number with a half-GCD algorithm that finds the terms from leading bits, evaluates continued fractions by balanced matrix products, and uses the same machinery for the simplest fraction in an interval, Farey neighbours and Dedekind sums.

AlgorithmDirichlet charactersRepresents the Dirichlet characters modulo q through the decomposition of the unit group into cyclic components with Conrey's generators, so that characters, values, conductors, parities and orders are computed from discrete logarithms in each component or directly from the Conrey number.

AlgorithmStirling and Bell numbersIsolated Stirling numbers by binary splitting of rising factorials, power sums or power series, chosen by k/n; rows by convolution; Bell numbers by Dobiński's formula, a multimodular sum, the Bell triangle or generating functions modulo primes.

AlgorithmBinary quadratic forms and class groupsReduction of positive definite binary quadratic forms, enumeration of the reduced forms of a discriminant (the class number), composition by Shanks' NUCOMP, and the computation of orders and of the exponent of the form class group by a two-stage method in the style of Pollard and Sutherland.

In this section#