Loading ...
Sorry, an error occurred while loading the content.

Re: Equivalent to BPSW

Expand Messages
  • djbroadhurst
    ... 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
    • 0 Attachment
      --- 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
    Your message has been successfully submitted and would be delivered to recipients shortly.