0
$\begingroup$

I am reading Carmichael numbers in Algorithms book by Sanjoy das gupta at followinglink page 38

http://www.cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf

Carmichael numbers The smallest Carmichael number is 561. It is not a prime: 561 = 3*11* 17; yet it fools the Fermat test, There is a way around Carmichael numbers, using a slightly more refined primality test due to Rabin and Miller. Write N - 1 in the form 2^t * u. As before we'll choose a random base a and check the value of a ^N-1 mod N. Perform this computation by first determining a^u mod N and then repeatedly squaring, to get the sequence:

a^u mod N; a^2u mod N; : : : ; a^2tu = a^N-1 mod N:

If a^N-1 not equal to 1 mod N, then N is composite by Fermat's little theorem, and we're done.

But if a^N-1 is equal to 1 mod N, we conduct a little follow-up test: somewhere in the preceding sequence, we ran into a 1 for the first time. If this happened after the first position (that is, if a^u mod N is not equal to 1), and if the preceding value in the list is not -1 mod N, then we declare N composite.

In the latter case, we have found a nontrivial square root of 1 modulo N: a number that is not 1 mod N but that when squared is equal to 1 mod N. Such a number can only exist if N is composite. It turns out that if we combine this square-root check with our earlier Fermat test, then at least three-fourths of the possible values of a between 1 and N - 1 will reveal a composite N, even if it is a Carmichael number.

Following questions on above text.

Question 1:

I am not able to follow below text

But if a^N-1 is equal to 1 mod N, we conduct a little follow-up test: somewhere in the preceding sequence, we ran into a 1 for the first time. If this happened after the first position (that is, if a^u mod N is not equal to 1), and if the preceding value in the list is not -1 mod N, then we declare N composite.

What does above statement mean? Any example will help.

Question 2:

What does author talking about square root here in last paragraph first two lines?

Thanks

$\endgroup$
1
$\begingroup$

What the text describes is the procedure of the strong-fermat-pseudoprime-test. If a number fails this test, it must be composite. If it passes, the chance that the number is prime is good. It is well known that at most $25$% of the bases coprime to $n$ give a wrong result, if the number is composite. So, if we repeat the test with $N$ random bases, the probability that a number passing this test is composite is at most $$\left(\frac{1}{4}\right)^N$$ This gives a very powerful primality test, but still does not guarantee that the number is prime. To do this, you can apply the APR-test (Aldeman-Pomerance-Rumely), for example.

$\endgroup$
0
$\begingroup$

Let's do an example: $n=561$ and $a=2$. Then $n-1=560=2^4\times 35$. We compute $2^{35}\equiv 263\pmod{561}$, $2^{70}=(2^{35})^2\equiv166\pmod{561}$, $2^{140}=(2^{70})^2\equiv67\pmod{561}$, $2^{280}=(2^{140})^2\equiv1\pmod{561}$.

At this stage, we know $b^2\equiv1\pmod{561}$ where $b=67$. As $b\not\equiv\pm1\pmod{561}$ then $561$ cannot be prime. Indeed $\gcd(67-1,561)$ must be a proper factor of $561$, and $\gcd(67-1,561)=33$ and $33\mid 561$.

$\endgroup$

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.