Browse Groups

• ... 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 1:25 PM
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.