Check if a number is Carmichael

Question

I am trying to implement Modified Miller-Rabin Algorithm by Shyam Narayanan (https://math.mit.edu/research/highschool/primes/materials/2014/Narayanan.pdf). The algorithm demands to check if a number is carmichael number. Is there any possible algorithm to check if a number of the order $10^{100}$ is a carmichael number or not in reasonable time on a standard PC?(Other than by efficient factorization)

The Paper also describes that there is a $O(\log(n)^4)$ algo for checking if a number is carmichael or not. Do any such algorithm exists?

Answer 1

First check, whether the given number $n$ is prime. (This can be done efficiently and $100$% correct very fast for numbers with about $100$ digits).

If the number is prime, it is not a carmichael number.

Go through the numbers $a$ coprime to $n$ and check whether $a^{n-1}\equiv 1\ (\ mod\ n\ )$ holds.

If you find such an $a$, for which this is not the case, the number is not carmichael.

It will not take too long to find a base $a$, such that $n$ is pseudoprime to base $a$, but not strong pseudoprime (or you find a base $a$, such that $n$ is not even pseudoprime to base $a$, in which case you are done).

In this case, you can efficiently find a non-trivial factor because you get a non-trivial congruence $s^2\equiv 1\ (\ mod\ n\ )$.

It is not known, whether you find a base $a$ "quickly", but in practise you will probably always succeed.

Answer 2

There are different ways to find out. For such a big number we need a method without having to factorize it.

One way to start, is to prove that N is composite. Therefore we choose a strong primality-test like the one of Miller–Rabin,Solovay–Strassen or the newer APRCL-test. If this test returns false, the compositeness of N is proven.

Next choose a test based on Fermat's little theorem:

$a^{p}\equiv a \ (mod\ p)$ for all integer $a$ with $0<a<p$ and $p \in primes$.

Proceed as follows:

pick a random $a$ with $1<a<N-1$ .

case 1: $a^{N-1}\equiv 1 \ (mod\ N)$ then pick another $a$ and repeat the test.

case 2: $a^{N-1}\not\equiv 1 \ (mod\ N)$ and $gcd(a,N)= 1$ then $N$ is composite but not a Carmichael number. We are finished.

case 3: $a^{N-1}\not\equiv 1 \ (mod\ N)$ and $gcd(a,N)\neq 1$ then $N$ is composite and $gcd(a,N)$ is a non-trivial Divisor of $N$. Pick another $a$ and repeat the test.

for case 1 and 3 repeat the test $k$-times. When finished $N$ is a Carmichael number with probability $1-2^{-k}$.

Here is my implementation for Pari-gp:

iscarmichael(n)={ \\input: positive integer n > 1
my(a=0,k=100); \\returns 1, if n is a Carmichael number with probability 1-2^-k
if(n%2==0||ispseudoprime(n)==1,return(0));
for(t=1,k,a=random(n-3)+2;if(lift(Mod(a,n)^(n-1))<>1&&gcd(a,n)==1,return(0)));
return(1)
};

The function iscarmichael(n) returns 1, if n is a Carmichael number with probability $1-2^{-k}$, otherwise it returns 0. Parameter k is set to 100. You can increase k for higher probability or decrease for lower probability.