## Re: Equivalent to BPSW

Expand Messages
• ... 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.
Message 1 of 2 , Dec 14, 2010
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
Your message has been successfully submitted and would be delivered to recipients shortly.