1
$\begingroup$

Hello world!

Now I'm implementing a stochastic (k-rounded) Fermat primality test for my annual scientific work. I know it is inefficient, but I do it for illustration only.

Well eventually I came up to a question: how inefficient it really is. So it does okay for a large amount of composites, but completely screws up for Carmichael numbers, except for the case when the randomly chosen witness occured to be a Carmichael number's factor.

And then the question was: how many factors do Carmichael numbers have? I mean, how does the number of factors grow with the length of the number? I haven't found any information on the topic, but it seems to be a curious question.

I'm not really a mathematician, so I kindly ask you to provide the answers as if they were addressed to a complete idiot.

3 Answers 3

1

There is a widely-believed (though not proved) hypothesis which implies that there are infinitely many Carmichael numbers with exactly $3$ prime factors (there are no Carmichael numbers with fewer than $3$ prime factors). In the other direction, as the answer from lhf suggests, undoubtedly there are Carmichaels with as many prime factors as you'd like.

1

As a first estimate, Carmichael numbers have as many factors as random numbers of similar size. You can use the Erdos-Kac theorem to estimate the number of prime factors, or simply use the mean: a number near $x$ has around $\log\log x$ prime factors on average.

Of course Carmichael numbers have at least three prime factors, so for small numbers you'll need to take that into account.

  • 0
    @Gerry Myerson: It would have to be, considering that AFAIK it's not even known that there are infinitely many Carmichael numbers with k prime factors for any given k.2011-07-05
0

Wikipedia says: Löh and Niebuhr in 1992 found some huge Carmichael numbers, including one with 1,101,518 factors and over 16 million digits. doi:10.1090/S0025-5718-96-00692-8