# 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?

• Look up Fermat's Little Theorem and Erdos' method. – ultrainstinct Apr 3 '16 at 15:09
• That will be a probabilistic method. Isn't there a way to say for sure if a number is carmichael? – Mayank Apr 3 '16 at 15:12
• Yes it has to be probabilistic because there is no feasible way to factorize a big number such as that. – ultrainstinct Apr 3 '16 at 15:17
• On page 11-12 of the paper it states "there is no known polynomial time algorithm that determines whether n is a Carmichael number of the form pqr, where p,q,r = 3 mod 4." They conjecture on page 17 without any comment that it could be done in O(log^4(n)) time, but it isn't clear why they believe this is true. Regardless, adding a strong Lucas test to a base 2 Miller-Rabin test has been shown to be very effective and seemingly of more practical use than this (but it's nice to see). – DanaJ Apr 5 '16 at 1:25

## 2 Answers

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.

• what is s here? Is it this s : n-1 = d.2^s. I dont properly understand how will I be able to find a factor if I find a base for which n is pseudoprime but not strong pseudoprime. – Mayank Apr 3 '16 at 21:06
• No, not this $s$. If $n-1=2^sd$ with $d$ odd, we must have a $t<s$ with $a^{2^td}\ne \pm 1$ , but $a^{2^{t+1}d}=1$ modulo $n$. This gives a non-trivial congruence $u^2=1$ modulo $n$, where $u:=2^{2^td}$ – Peter Apr 3 '16 at 21:14
• I corrected my implementation. its running now.. Thanks a lot for all the help. – Mayank Apr 4 '16 at 11:21
• actually integer overflow was happening. – Mayank Apr 4 '16 at 11:24
• @DanaJ In the case the number is Carmichael, but not prime, we probably (there is no proof for that) find a "small" base $a$ coprime to $n$ (otherwise we already found a non-trivial factor), such that $n$ is NOT STRONG-probable prime to base $a$. A carmichael number is pseudoprime to every base $a$ coprime to $n$, but not necessarily strong-pseudoprime. In practice, the algorithm will be relatively efficient. $n-2$ steps will not be needed. – Peter Apr 5 '16 at 14:35

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.

• This shares the same property of including a primality test as an early step, making it recursive for the paper's purpose of a pretest for Miller-Rabin. Regardless, I'd recommend first doing a quick divisibility check with 4,9,25,49,121,169 which immediately cuts out many non-square free numbers. Other than that, leaving out the primality test this is a great iscarmichael pre-test or probable iscarmichael function. – DanaJ Apr 5 '16 at 17:47