AKS vs. Fermat Primality Tests

[aikismos]

I'm trying to wrap my mind around the notion of the difference of forms. Since the AKS primality test is logically equivalent to Fermat's $2^{p-1} - 1 ≡ 0\ (mod\ p)$, is it fair to say that the main advantage of the form of the former is that it essentially splits up a single division problem into a polynomial with integer coefficients that can be handled by a distributed algorithm?

 

[Dragonfall]

AKS is not logically equivalent to Fermat's little theorem. For example, the existence of absolute pseudoprimes.

 

[aikismos]

AKS is not logically equivalent to Fermat's little theorem. For example, the existence of absolute pseudoprimes.

As far as I understand it, $2^{p-1}−1≡0\ (mod\ p)$ is a corollary to Fermat's Little Theorem, and is a subset in the case only where $p$ doesn't divide $a$. As such, I believe the question still stands?

 

[Yomi]

It is not equivalent to $2^{p-1} - 1 ≡ 0\ (mod\ p)$. That is just Fermat's Little Theorem with a=2. It is true for primes and base-2 pseudoprimes, of which there are almost 119 million below $2^{64}$. AKS is a deterministic test for all input sizes, meaning there are no pseudoprimes to the full test.

Let's first just give it a "could this possibly be true" look. If AKS was equivalent to that, then we would have had a deterministic polynomial time algorithm, one that runs unbelievably faster than AKS, hundreds of years ago. There would have been no fuss over AKS.

There's a bit of truth here though. In the late 1600s it was seen that $n$ is prime if and only if $(X + a)^n ≡ X^n + a\ (mod\ n)$. Basically saying that if all the binomial coefficients are divisible by n, then n is prime. This is deterministic and easily stated. There's a problem ... it's exponential time. This is a very roundabout way of testing divisibility by all numbers 2 to n-1. Ouch. Even naive trial division is more efficient than this (though still exponential time). This is Lemma 2.1 in the AKS paper, and as mentioned, everyone knew this for a very long time, but there wasn't any obvious way to make it efficient.

The AKS paper shows (1) that we can choose an r such that we can test modulo $X^r-1$ for a subset of 'a' values where only primes and prime powers pass the test, (2) that in fact we can choose them small enough with respect to n that the result grows by a polynomial factor of n, and (3) a surprisingly simple and relatively easy to follow algorithm to obtain the parameters.

Since we do a number of tests with different 'a' values, it is indeed trivially easy to parallelize or distribute. However other proof methods are also able to be parallelized (though not as trivially). Primo, for example, does ECPP proofs using up to 48 threads, obtaining excellent efficiency.

AKS was a landmark theoretical result for many reasons. However it is still not a practical algorithm, as it is vastly slower than other proof methods. To my knowledge AKS is not used for practical results for any size input. We have extremely fast methods below 2^81, and above that we generally use APR-CL or ECPP. Many people just use a probable prime test such as BPSW or Miller-Rabin.

 

[aikismos]

@Yomi,

Thanks for responding to my post in such an articulate manner to clarify the relationship between some of these ideas. And your first post to boot!

Okay, so I knew most of that (in a somewhat disjoint fashion) mostly from poking around haphazardly. I do have a reason for my misconception, and it is from a series of back of the envelope calculations after I heard a brief explanation of AKS by Andrew Grimes. I get that the general genius of AKS is that it shows determining primality is in the polynomial time, but the finer points of the paper are above my head currently. Maybe you could give me some feedback on the following.

(1) Starting with the congruence you gave that was discovered in the 17th century:
$prime(a, x) := (x-a)^n \buildrel (n) \over\equiv (x^n - a) \forall a,x \in \mathbb{Z} n \in \mathbb{P}$

(2) And in the special case:
$prime(-1, x) := (x+1)^n \buildrel (n) \over\equiv (x^n+1)$

(3) Which implies by the definition of congruence:
$(x+1)^n = nP(x)+ (x^n+1)$

(4) Subtractive property of equations:
$nP(x) = (x+1)^n - (x^n+1)$

(5) And given the expansion of the binomial:
$nP(x) = (c_1x^n + c_2x^{n-1} + ... + c_{n-1}x + c_n) + (-x^n-1) : c_n := C(n,0), c_1 := C(n,n), c_n = c_1 = 1$

(6) Combining additive inverses with first and last terms:
$nP(x) = c_2x^{n-1} + ... + c_{n-1}x\ \forall n > 2$

(7) Implicating the polynomial as a multiple of $n$ such that:
$n | (c_2x^{n-1} + ... + c_{n-1}x)$

(8) In sigma as:
$n | \sum\limits_{b=2}^{n-1} c_b: c_1 + \sum\limits_{b=2}^{n-1} c_b + c_n = 2^n$

(9) Where the remaining coefficients are given their cardinality:
$n | 2^n - 2 \rightarrow n|2(2^{n-1} - 1)$

(10) And so by virtue of restriction on $n > 2$:
$n | 2^{n-1} - 1\ \forall n \in \mathbb{P}$

$\blacksquare$

I get your refutation that the special case of FLiT is bound to have binary pseudoprimes (starting at n=341), but what I don't get is how in the above derivation, I'm supposed to be able to see that pseudoprimes necessarily exist. Any hints would be greatly appreciated so I can go on instead of staring at this.