Extending Babbage's (non-)primality tests

DOI10.1007/978-3-319-68032-3_19MaRDI QIDQ5230187zbMATH OpenOpenAlexFDO

Authors Jonathan Sondow

Publication date 21 August 2019

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.07650

zbMATH Keywords

binomial coefficientCharles BabbagecongruenceLucas's theoremprimality testWolstenholme prime

Mathematics Subject Classification ID

Factorization; primality (11A51) Primality (11Y11)

Abstract: We recall Charles Babbage's 1819 criterion for primality, based on simultaneous congruences for binomial coefficients, and extend it to a least-prime-factor test. We also prove a partial converse of his non-primality test, based on a single congruence. Two problems are posed. Along the way we encounter Bachet, Bernoulli, Bezout, Euler, Fermat, Kummer, Lagrange, Lucas, Vandermonde, Waring, Wilson, Wolstenholme, and several contemporary mathematicians.

Recommendations

• An extension of Babbage's criterion for primality
• Fast Primality Tests for Numbers Less Than 50 ⋅10 9
• Primality tests
• Recent developments in primality testing
• scientific article; zbMATH DE number 17386

Cited in

(2)

• Correcting noisy exponentiation black-boxes modulo a prime
• An extension of Babbage's criterion for primality

This page was built for publication: Extending Babbage's (non-)primality tests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230187)