Check if a number is Carmichael 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?
 A: 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.
A: 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.
