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

AKS prime number test

Expand Messages
  • Kermit Rose
    I ve implemented the AKS prime number test. It is slower than any of the standard pseudo prime tests. I ve also extended the AKS test to a potential factoring
    Message 1 of 3 , Dec 9, 2010
    • 0 Attachment
      I've implemented the AKS prime number test.

      It is slower than any of the standard pseudo prime tests.

      I've also extended the AKS test to a potential factoring algorithm.

      For moderately sized numbers, it factors much much slower than other
      factoring algorithms.

      For example, it required 354 seconds to completely factor 549755813887.

      AKS factored z = 549755813887 by initial trial division by prime < 100.
      z = 7 is prime < 100.

      AKS factored z = 78536544841 by initial trial division by prime < 100.
      z = 79 is prime < 100.

      AKS: z = 994133479 r = 911

      AKS factored z = 994133479 by [ 14 +x]** 994133479 mod(x** 911 -1,
      994133479 )

      AKS: z = 8191 r = 179

      AKS determined that z = 8191 is prime by [ 1 +x]** 8191 equals x**
      8191 + 1 mod(x** 179 -1, 8191 ).

      AKS: z = 121369 r = 347

      AKS determined that z = 121369 is prime by [ 1 +x]** 121369 equals
      x** 121369 + 1 mod(x** 347 -1, 121369 ).


      [[7, 1], [79, 1], [8191L, 1], [121369L, 1], 353.68099999427795]


      Kermit
    • Chris Caldwell
      ... Nice. ... Indeed, that s the rub. It has a proven polynomial length, but the constants are so large it is easily beat in practice by ECPP (and all other
      Message 2 of 3 , Dec 10, 2010
      • 0 Attachment
        > I've implemented the AKS prime number test.

        Nice.

        > It is slower than any of the standard pseudo prime tests.

        Indeed, that's the rub. It has a proven polynomial length, but the
        constants are so large it is easily beat in practice by ECPP (and all
        other methods for very small numbers, say a couple hundred digits).
        That may always be so (for reasonable sized numbers), or may not. Some
        very sharp folks are working on it.

        But the key success of AKS was answering the P vs NP question. In
        theory the constants do not matter, in practice, they can be
        everything!!!

        CC
      • Walter Nissen
        Hi , all , ... Great , I m very glad to hear this . ... Another point is that AKS is actually a primality test . Many writers have a tendency to omit the
        Message 3 of 3 , Dec 10, 2010
        • 0 Attachment
          Hi , all ,

          At 2010-12-10 13:27, "Chris Caldwell" <caldwell@...> wrote :

          > Some very sharp folks are working on it.

          Great , I'm very glad to hear this .

          > But the key success of AKS was answering the P vs NP question.

          Another point is that AKS is actually a primality test .
          Many writers have a tendency to omit the "pseudo-" from
          "pseudo-primality test" when describing a compositeness test .

          > In theory the constants do not matter,
          > in practice, they can be everything!!!

          Indeed , so true .
          See my similar point in "Counting in Separate Realms" ,
          http://upforthecount.com/math/asymtotes.html

          Cheers ,

          Walter
        Your message has been successfully submitted and would be delivered to recipients shortly.