Carmichael numbers algorithm sanjoy das gupta

Question

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

Answer 1

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$.

Answer 2

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.