Infinitely many Carmichael numbers for a modified Miller-Rabin prime test

DOI10.1145/2930889.2930911MaRDI QIDQ2985807zbMATH OpenOpenAlexWikidataFDO

Authors Eric Bach, Rex Fernando

Publication date 10 May 2017

Published in Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

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

zbMATH Keywords

Carmichael numberscomputational number theoryprimality testing

Mathematics Subject Classification ID

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

Abstract: We define a variant of the Miller-Rabin primality test, which is in between Miller-Rabin and Fermat in terms of strength. We show that this test has infinitely many "Carmichael" numbers. We show that the test can also be thought of as a variant of the Solovay-Strassen test. We explore the growth of the test's "Carmichael" numbers, giving some empirical results and a discussion of one particularly strong pattern which appears in the results.

Recommendations

• The Miller–Rabin test with randomized exponents
• Constructing Carmichael numbers which are strong pseudoprimes to several bases
• scientific article; zbMATH DE number 691479
• scientific article; zbMATH DE number 493094
• scientific article; zbMATH DE number 2081060

This page was built for publication: Infinitely many Carmichael numbers for a modified Miller-Rabin prime test

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