The basis for the deterministic polynomial-time algorithm for primality of Agrawal, Kayal and Saxena is (the degree one version of) the following generalization of Fermat's theorem.
Theorem
Suppose that P is a polynomial with integer coefficients, and that p is a prime number. Then
$(P(X))^pequiv P(X^p) (mod p)$.
Surely this result was known previously, but I have not been able to find a reference in the literature on the AKS algorithm (which means that the authors also did not know of a reference). Does anyone here know of one?
Furthermore, there is a converse to the lemma in the AKS paper:
Lemma
If n is a composite number, then $(X+a)^nnot equiv X^n+a (mod n)$ whenever a is coprime to n.
Again, it is easy to generalize this statement. For example, if P is a polynomial which has at least two nonzero coefficients and such that all nonzero coefficients are coprime to n, then $P(X)^nnotequiv P(X^n) (mod n)$ for composite n.
On the other hand, clearly some conditions are necessary; for example $(3X+4)^6equiv 3X^6+4 (mod 6)$.
Is there a best possible statement? And, again, is there a reference?
No comments:
Post a Comment