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