As in title, why do people usually choose random bases for the Fermat primality test as opposed to just using bases $2, 3, 4, …$ in succession? Say we want to know if $N$ is prime/Carmichael or composite (with no preference for prime or Carmichael). We try a bunch of bases $a$ and calculate $a^{N – 1} \mod N$. Is there some structural thing that makes small bases not work as well?
Why do we choose random bases for the Fermat primality test
elementary-number-theorynumber theoryprimality-testprime numbers
Related Solutions
You are doing the computation in inexact arithmetic. $11^{16}$ cannot possibly be an even number. In fact, every power of eleven obviously ends in a one.
You're probably doing the computation in doubles. Doubles are only accurate to about fifteen decimal places; after that they round off.
Moreover, you do not need to calculate the whole big number. Use this identity:
$(a \times b) \bmod c$ is congruent modulo $c$ to $(a \bmod c) \times (b \bmod c)$
Make sure that makes sense to you. Take, say, $15$ and $18$, and you want to work out $(15\times 18) \bmod 4$. You could multiply $15$ by $18$ and then divide by $4$ and take the remainder. But think about it like this.
$(15 \times 18) =$
$( (3 \times 4 + 3) \times (4 \times 4 + 2 ) ) =$
$(3 \times 4) \times (4 \times 4) + 3 \times (4 \times 4) + 2 \times (3 \times 4) + 3 \times 2$.
Obviously the first three summands are all divisible by 4, so they go away modulo 4. So
$(15 \times 18) \bmod 4$ is congruent mod 4 to $(15 \bmod 4) \times (18 \bmod 4)$.
Which is equal to $3 \times 2$, so $(15 \times 18) \bmod 4$ is congruent modulo 4 to $(3 \times 2) \bmod 4$, which is a much easier problem to solve.
Do the same thing for powers.
$11^{16} \bmod 17$ is congruent mod 17 to $(11^{8} \bmod 17) \times (11^{8} \bmod 17)$
and the problem is now much easier to solve. Keep going:
$11^{8} \bmod 17$ is congruent $\bmod 17$ to $(11^{4} \bmod 17) \times (11^{4} \bmod 17)$
and now the problem is yet easier. Keep going!
$11^{4} \bmod 17$ is congruent $\bmod 17$ to $(11^{2} \bmod 17) \times (11^{2} \bmod 17)$
And now we have an easy problem to solve. $121 \bmod 17$ is 2, so $11^{4} \bmod 17$ is congruent to $2 \times 2 \bmod 17$. Therefore $11^{4} \bmod 17$ is 4.
$11^{8} \bmod 17$ is congruent $\bmod 17$ to $11^{4} \bmod 17 \times 11^{4} \bmod 17$, so $11^{8} \bmod 17$ is congruent mod 17 to $4 \times 4$, which is 16. Therefore $11^{8} \bmod 17$ is 16.
Similarly, $11^{16} \bmod 17$ is congruent $\bmod 17$ to $16 \times 16$, which is easily determined to be congruent to $1 \bmod 17$.
Therefore $11^{16}$ gives a remainder of 1 when divided by 17. That's a lot easier than doing the big multiplication and the big division, particularly when the numbers get large.
And sure enough, we got one, so that is evidence that 17 is prime.
I begin by trying also to answer your question:
Why would we exclude $a$ such that $\gcd(a, n) = 1$ when the test works well without such condition? If we know that $\gcd(a, n) \not= 1$, we already that $n$ is not prime, thus the test is pointless.
The answer is that we are not excluding those $a$, but the chances of randomly getting a Fermat witness $a$ such that $\gcd(a,n)>1$ may be extremely low. At least it can easily be too low to help us in the task of primality testing.
On with my more verbose rant.
I am not an expert on primality testing, but I think $561$ is too small to truly bring to light the risks of primality testing by crude Little Fermat. After all, $3$ is a small number, and you are likely to hit a multiple of three sooner rather than later. But what if you stumble upon a Carmichael number with only relatively large prime factors (for the purposes of crypto we are talking 100+ digit prime number candidates after all).
For example, by Chernik's result if $6k+1,12k+1$ and $18k+1$ are all primes, then their product $n$ is a Carmichael number. If here all those three primes have about 40 digits, then the probability that any given Fermat witness says "Possible prime" is $1-10^{-40}$ or thereabouts - not good when the number to be tested is actually composite!
But, if you use a slightly more sophisticated witness based primality testing, such as Rabin-Miller, then you never have this problem. Each (R-M) witness yelling "Possible prime!" lowers the odds of your candidate still being a composite by a known minimum factor (IIRC the factor is four - but do check your sources on Rabin-Miller).
So the point is that due to the existence of Carmichael numbers we need to use something other than basic Little Fermat to get something like 99.99% certainty of the candidate being a prime with a reasonable amount of testing (when 8 R-M witnesses, each cutting the chance of a false positive by a factor of four, will do it).
If the number to be tested would be a Carmichael number, then I'm not aware of any number $\epsilon>0$ such that each witness would lower the probability of a false positive by $(1-\epsilon)$. Furthermore (see the Wikipedia page I linked to earlier), there are quite a few Carmichael numbers in a given range. True, they form a tiny fraction, but when Rabin-Miller gives us the kind of a guarantee that Fermat cannot with the same computational complexity, why use Little Fermat?
Best Answer
When $a$ is chosen randomly (and $N$ is odd), instead of working in $\Bbb{Z}/N\Bbb{Z}^\times$ we can do our reasonning in the product of cyclic groups $\prod_{p^k\| N}\Bbb{Z/p^{k-1}(p-1) Z}$, choosing some $a$ randomly in this group,
whereas when $a$ is constrained to be in a small interval $[2,A]$, we have no idea of what kind of elements it gives in $\prod_{p^k\| N}\Bbb{Z/p^{k-1}(p-1) Z}$ thus we have no clue of what is the probability that it is a false Fermat witness.