Carmichael numbers

A Carmichael number is a pseudoprime for every possible base b: that is, for every b coprime to N. It was recently shown that there infinitely many of these numbers too. We have computed all Carmichael numbers up to 1021 and various other lists: see tables and statistics. Details of the computation are in a number of papers.

Carmichael numbers up to various limits

Carmichael numbers up to 1015

Math. Comp. 61:203 (Jul 1993) 381--391

There are 105212 Carmichael numbers up to 1015: we describe the calculations. The numbers were generated by a back-tracking search for possible prime factorisations, and the computations checked by searching selected ranges of integers directly using a sieving technique, together with a ``large prime variation''.

See the full paper in PS format.

Zbl. 780.11069

Math Review 93m:11137

Carmichael numbers up to 1016

We extend our previous computations to show that there are 246683 Carmichael numbers up to 1016. As before, the numbers were generated by a back-tracking search for possible prime factorisations together with a ``large prime variation''. We present further statistics on the distribution of Carmichael numbers..

Arxiv:math.NT/9803082 or here.

See the full paper in PS format.

Carmichael numbers up to 1017

We further extend our computations to show that there are 585355 Carmichael numbers up to 1017.

See the full paper in DVI or PS format.

Carmichael numbers up to 1018

We further extend our computations to show that there are 1401644 Carmichael numbers up to 1018.

See the full paper in PS format.

Carmichael numbers up to 1019

We further extend our computations to show that there are 3381806 Carmichael numbers up to 1019.

See a poster for the ANTS VII meeting in PS format.

Carmichael numbers up to 1021

Proceedings Conference on Algorithmic Number Theory, Turku, May 2007. Turku Centre for Computer Science General Publications 46, edited by Anne-Maria Ernvall-Hytönen, Matti Jutila, Juhani Karhumäki and Arto Lepistö.

We further extend our computations to show that there are 20138200 Carmichael numbers up to 1021.

See a poster for the ANTS VIII meeting in PDF format.

See the the full paper in PDF format.

Carmichael number data files

On using Carmichael numbers for public key encryption systems

Proceedings 6th IMA Conference on Coding and Cryptography, Cirencester 1997, (ed. M. Darnell) Springer Lecture Notes in Computer Science 1355 (1997) 265--269

We show that the inadvertent use of a Carmichael number instead of a prime factor in the modulus of an RSA cryptosystem is likely to make the system fatally vulnerable, but that such numbers may be detected.

See the paper in DVI or PS format.

Pseudoprimes

A Fermat pseudoprime base b is a composite number N which satisfies the Fermat condition bN-1 congruent to 1 modulo N. In the common case b = 2 we often talk simply of a pseudoprime. The first few examples are 341 = 11.31, 561 = 3.11.17, ... . It is not too hard to show that there are infinitely many: if n is a pseudoprime, so is 2n-1.

Pseudoprimes up to 1013

4th International Algorithmic Number Theory Symposium, ANTS-IV, Leiden, The Netherlands, 2--7 July 2000; Springer Lecture Notes in Computer Science 1838 (2000), 459-474

There are 38975 Fermat pseudoprimes (base 2) up to 1011, 101629 up to 1012 and 264239 up to 1013: we describe the calculations and give some statistics. The numbers were generated by a variety of strategies, the most important being a back-tracking search for possible prime factorisations, and the computations checked by a sieving technique..

See the full paper in PDF format. (Copyright © Springer-Verlag 2000)


Some preprints are available in the Number Theory section of the eprint Arxiv: try here or use the UK mirror site at Southampton


Back to Richard Pinch's personal or mathematical home page.


Updated 24/03/2008 by Richard Pinch