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

Equivalent to BPSW

Expand Messages
  • Kermit Rose
    Hello David. ... 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
    Message 1 of 2 , Dec 14, 2010
    • 0 Attachment
      Hello David.

      > 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.

      > We have not yet found a BPSW pseudoprime.

      > David

      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.
    • 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 2 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.