2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Look up Fermat's Little Theorem and Erdos' method. $\endgroup$ – ultrainstinct Apr 3 '16 at 15:09
  • $\begingroup$ That will be a probabilistic method. Isn't there a way to say for sure if a number is carmichael? $\endgroup$ – Mayank Apr 3 '16 at 15:12
  • $\begingroup$ Yes it has to be probabilistic because there is no feasible way to factorize a big number such as that. $\endgroup$ – ultrainstinct Apr 3 '16 at 15:17
  • $\begingroup$ 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). $\endgroup$ – DanaJ Apr 5 '16 at 1:25
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mayank Apr 3 '16 at 21:06
  • $\begingroup$ 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}$ $\endgroup$ – Peter Apr 3 '16 at 21:14
  • 1
    $\begingroup$ I corrected my implementation. its running now.. Thanks a lot for all the help. $\endgroup$ – Mayank Apr 4 '16 at 11:21
  • 1
    $\begingroup$ actually integer overflow was happening. $\endgroup$ – Mayank Apr 4 '16 at 11:24
  • 1
    $\begingroup$ @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. $\endgroup$ – Peter Apr 5 '16 at 14:35
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – DanaJ Apr 5 '16 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.