--- In

primenumbers@yahoogroups.com,

Kermit Rose <kermit@...> wrote:

> Thank you David.

> I've added the BPSW parameter to my AKS routine, so that if

> the number to be tested is 2 or 3 mod 5,

> and the BPSW parameter is specified,

> it does

> (x+a)^n = x^n + a mod(n,x^r-1)

> with a = 1, r = 5.

I was careful to write "suggests" here:

> Problem 16 of

> http://www.ma.utexas.edu/users/voloch/Homework/problems2.pdf

> suggests that an AKS test

> (x+a)^n = x^n + a mod(n,x^r-1)

> with a = 1, r = 5, and n^2 = -1 mod 5, is equivalent to BPSW.

For myself, I cannot see why they should be equivalent.

Working modulo x^5-1, we include x = 1, which (with a = 1) gives

the base-2 Fermat test of BPSW. However the irreducible quartic

polcyclo(5) = x^4 + x^3 + x^2 + 1 of AKS

seems to me to demand more than working modulo

the Fibonacci quadratic x^2 + x - 1 of BPSW,

for n^2 = - 1 mod 5.

I am prepared to believe that an AKS pseudoprime of this ilk

would be a BPSW pseudoprime, but I cannot see why the converse

need be true. Of course, we have no example of either type

of pseudoprime. So the question is academic, but still

mathematically interesting, to me, at least.

Might someone clarify this (in?)equivalence, please?

David