Skip to content

Bibliography

Sources for the mathematics Numerisect implements, and for the engines it uses. Where a documentation page states a bound, a constant or a named theorem, it cites from this list.

General references

  • R. Crandall and C. Pomerance. Prime Numbers: A Computational Perspective, 2nd edition. Springer. The standard reference for computational prime number theory, covering pseudoprimes, primality proving and every factoring method here.
  • H. Cohen. A Course in Computational Algebraic Number Theory. Springer. Algorithms for number fields, quadratic forms, class groups and modular arithmetic.
  • H. Riesel. Prime Numbers and Computer Methods for Factorization. Birkhäuser.
  • D. E. Knuth. The Art of Computer Programming, volume 2, Seminumerical Algorithms. Addison-Wesley.
  • G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. Oxford.
  • H. L. Montgomery and R. C. Vaughan. Multiplicative Number Theory I: Classical Theory. Cambridge.
  • H. Iwaniec and E. Kowalski. Analytic Number Theory. American Mathematical Society.
  • K. Ireland and M. Rosen. A Classical Introduction to Modern Number Theory. Springer. Gaussian and Eisenstein integers, reciprocity, finite fields and cyclotomic structure.
  • P. Ribenboim. The New Book of Prime Number Records. Springer. Special prime forms, primitive roots, recurring decimals and prime constellations.
  • L. E. Dickson. History of the Theory of Numbers, volume I. Carnegie Institution. Classical sources for perfect numbers and special prime families.

Primality

  • R. Baillie and S. S. Wagstaff, Jr. "Lucas pseudoprimes". Mathematics of Computation.
  • C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr. "The pseudoprimes to \(25 \cdot 10^9\)". Mathematics of Computation.
  • G. Miller. "Riemann's hypothesis and tests for primality". Journal of Computer and System Sciences.
  • M. Rabin. "Probabilistic algorithm for testing primality". Journal of Number Theory.
  • G. Jaeschke. "On strong pseudoprimes to several bases". Mathematics of Computation.
  • J. Sorenson and J. Webster. "Strong pseudoprimes to twelve prime bases". Mathematics of Computation.
  • H. C. Pocklington. "The determination of the prime or composite nature of large numbers by Fermat's theorem". Proceedings of the Cambridge Philosophical Society.
  • V. Pratt. "Every prime has a succinct certificate". SIAM Journal on Computing.
  • L. M. Adleman, C. Pomerance and R. S. Rumely. "On distinguishing prime numbers from composite numbers". Annals of Mathematics. The basis of APR-CL.
  • A. O. L. Atkin and F. Morain. "Elliptic curves and primality proving". Mathematics of Computation. The basis of ECPP.

Factorization

  • J. M. Pollard. "A Monte Carlo method for factorization". BIT.
  • J. M. Pollard. "Theorems on factorization and primality testing". Proceedings of the Cambridge Philosophical Society. The p−1 method.
  • R. P. Brent. "An improved Monte Carlo factorization algorithm". BIT.
  • H. C. Williams. "A \(p+1\) method of factoring". Mathematics of Computation.
  • H. W. Lenstra, Jr. "Factoring integers with elliptic curves". Annals of Mathematics.
  • C. Pomerance. "The quadratic sieve factoring algorithm". Advances in Cryptology, EUROCRYPT '84.
  • A. K. Lenstra and H. W. Lenstra, Jr., editors. The Development of the Number Field Sieve. Springer Lecture Notes in Mathematics 1554.
  • J. E. Gower and S. S. Wagstaff, Jr. "Square form factorization". Mathematics of Computation. The reference implementation notes for SQUFOF.
  • D. Shanks. "Analysis and improvement of the continued fraction method of factorization". Unpublished manuscript, described in the Gower–Wagstaff paper above.
  • M. A. Morrison and J. Brillhart. "A method of factoring and the factorization of \(F_7\)". Mathematics of Computation 29 (1975). CFRAC, the first subexponential method.
  • R. S. Lehman. "Factoring large integers". Mathematics of Computation 28 (1974). The deterministic \(O(N^{1/3})\) method.
  • W. B. Hart. "A one line factoring algorithm". Journal of the Australian Mathematical Society 92 (2012).
  • D. Coppersmith. "Small solutions to polynomial equations, and low exponent RSA vulnerabilities". Journal of Cryptology 10 (1997). The lattice method behind recovering a factor from its leading bits.
  • A. May. "Using LLL-reduction for solving RSA and factorization problems". The LLL Algorithm, Springer (2010). A survey of what partial knowledge of a factor buys.
  • D. G. Cantor and H. Zassenhaus. "A new algorithm for factoring polynomials over finite fields". Mathematics of Computation 36 (1981). The equal-degree stage.
  • V. Shoup. A Computational Introduction to Number Theory and Algebra, 2nd edition, Cambridge (2009). Chapter 20 for the square-free, distinct-degree and equal-degree stages in the order they must run.

Summatory functions and Brun-type constants

  • V. Brun. "La série \(1/5+1/7+1/11+\cdots\) où les dénominateurs sont nombres premiers jumeaux est convergente ou finie". Bulletin des Sciences Mathématiques (1919). The convergence that makes the constant exist.
  • D. Klyve. Explicit bounds on twin primes and Brun's constant. Dartmouth College thesis (2007). The extrapolated estimate quoted for comparison.
  • A. M. Odlyzko and H. J. J. te Riele. "Disproof of the Mertens conjecture". Journal für die reine und angewandte Mathematik 357 (1985).
  • M. Deléglise and J. Rivat. "Computing the summation of the Möbius function". Experimental Mathematics 5 (1996). The sublinear approach to \(M(x)\).

Exceptional primes and Fermat quotients

  • A. Wieferich. "Zum letzten Fermat'schen Theorem". Journal für die reine und angewandte Mathematik 136 (1909).
  • D. D. Wall. "Fibonacci series modulo \(m\)". American Mathematical Monthly 67 (1960). The question behind Wall–Sun–Sun primes.
  • Z. H. Sun and Z. W. Sun. "Fibonacci numbers and Fermat's last theorem". Acta Arithmetica 60 (1992).
  • R. Crandall, K. Dilcher and C. Pomerance. "A search for Wieferich and Wilson primes". Mathematics of Computation 66 (1997).
  • R. J. McIntosh and E. L. Roettger. "A search for Fibonacci–Wieferich and Wolstenholme primes". Mathematics of Computation 76 (2007).

Distribution of primes

  • J. B. Rosser and L. Schoenfeld. "Approximate formulas for some functions of prime numbers". Illinois Journal of Mathematics.
  • P. Dusart. "Estimates of some functions over primes without R.H." and "The \(k\)th prime is greater than \(k(\ln k + \ln\ln k - 1)\) for \(k \ge 2\)". Mathematics of Computation.
  • J. E. Littlewood. "Sur la distribution des nombres premiers". Comptes Rendus. The sign of \(\pi(x) - \mathrm{li}(x)\) changes infinitely often.
  • G. H. Hardy and J. E. Littlewood. "Some problems of 'Partitio numerorum' III: On the expression of a number as a sum of primes". Acta Mathematica.
  • P. T. Bateman and R. A. Horn. "A heuristic asymptotic formula concerning the distribution of prime numbers". Mathematics of Computation.
  • M. Rubinstein and P. Sarnak. "Chebyshev's bias". Experimental Mathematics.
  • A. Granville. "Harald Cramér and the distribution of prime numbers". Scandinavian Actuarial Journal.
  • T. R. Nicely. Computational work on prime gaps and maximal gaps.
  • A. Odlyzko. Tables and papers on zeros of the zeta function.

Prime counting

  • J. C. Lagarias, V. S. Miller and A. M. Odlyzko. "Computing \(\pi(x)\): the Meissel–Lehmer method". Mathematics of Computation.
  • M. Deléglise and J. Rivat. "Computing \(\pi(x)\): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method". Mathematics of Computation.
  • X. Gourdon. "Computation of \(\pi(x)\): improvements to the Meissel, Lehmer, Lagarias, Miller, Odlyzko, Deléglise and Rivat method". Available from the primecount project.

Analytic number theory and zeta

  • B. Riemann. "Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse".
  • H. M. Edwards. Riemann's Zeta Function. Dover.
  • E. C. Titchmarsh, revised by D. R. Heath-Brown. The Theory of the Riemann Zeta Function. Oxford.
  • A. M. Turing. "Some calculations of the Riemann zeta-function". Proceedings of the London Mathematical Society. The zero-counting method.
  • H. L. Montgomery. "The pair correlation of zeros of the zeta function". Analytic Number Theory, Proceedings of Symposia in Pure Mathematics.

Quadratic forms

  • D. A. Buell. Binary Quadratic Forms: Classical Theory and Modern Computations. Springer.
  • J. H. Conway. The Sensual (Quadratic) Form. Mathematical Association of America.
  • D. A. Cox. Primes of the Form \(x^2 + ny^2\). Wiley.

Software

Reference data

  • The On-Line Encyclopedia of Integer Sequences. https://oeis.org/ Sequences cited in the documentation include A002386 and A005250 (maximal prime gaps) and A005180.
  • RSA Laboratories. The RSA Factoring Challenge. The challenge-number definitions and historical status catalogue; Numerisect treats the transcribed values as data and independently verifies every mathematical claim before displaying it.
  • The Great Internet Mersenne Prime Search. https://www.mersenne.org/ Operational background for Mersenne trial factoring and Lucas–Lehmer testing. Numerisect verifies its own examples with PARI/GP rather than treating a web catalogue as proof.

On citation practice

Where a documentation page states a numerical bound or a named result, it cites the source so you can check the claim rather than take Numerisect's word for it. Where an attribution is uncertain, the page describes the result without inventing a date.