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

number of witnesses needed to verify a number of given size is prime.

Expand Messages
  • Kermit Rose
    Currently, I test the number Z for primness by testing whether or not Z is a pseudo prime base w for one more than log base 2 of Z primes. I m sure I m testing
    Message 1 of 4 , Jun 25, 2006
    • 0 Attachment
      Currently, I test the number Z for primness by testing

      whether or not Z is a pseudo prime base w for one more than

      log base 2 of Z

      primes.

      I'm sure I'm testing for too many witnesses to ensure that z is prime.

      I hope for suggestions for a function that would give a tighter bound, and

      ensure that I have at least enough different witnesses to know for sure

      whether or not Z is prime.

      For example, to test if

      401 is prime,

      log base 2 of 401 is 8,

      so I'm testing for strongly probably prime with

      the first 9 primes, 2,3,5, 7,11,13, 17,19,23.


      But the smallest base 2 pseudo prime for strong probable prime test is 2047.

      So for 401, I needed to test only one witness, not nine.

      Is there a simple function that will for sure give me a close to optimum
      number
      of witnesses that I need to test to ensure primeness,

      given that my witnesses are the primes in sequential order?
    • Alan McFarlane
      Check out Thomas R Nicely s pages at http://www.trnicely.net/ Specifically GNU GMP mpz_probab_prime_p pseudoprimes http://www.trnicely.net/misc/mpzspsp.html
      Message 2 of 4 , Jun 25, 2006
      • 0 Attachment
        Check out Thomas R Nicely's pages at

        http://www.trnicely.net/

        Specifically "GNU GMP mpz_probab_prime_p pseudoprimes"

        http://www.trnicely.net/misc/mpzspsp.html

        and " The Baillie-PSW primality test"

        http://www.trnicely.net/misc/bpsw.html

        --

        Kermit Rose wrote:
        >
        >
        > Currently, I test the number Z for primness by testing
        >
        > whether or not Z is a pseudo prime base w for one more than
        >
        > log base 2 of Z
        >
        > primes.
        >
        > I'm sure I'm testing for too many witnesses to ensure that z is prime.
        >
        > I hope for suggestions for a function that would give a tighter bound, and
        >
        > ensure that I have at least enough different witnesses to know for sure
        >
        > whether or not Z is prime.
        >
        > For example, to test if
        >
        > 401 is prime,
        >
        > log base 2 of 401 is 8,
        >
        > so I'm testing for strongly probably prime with
        >
        > the first 9 primes, 2,3,5, 7,11,13, 17,19,23.
        >
        >
        > But the smallest base 2 pseudo prime for strong probable prime test is 2047.
        >
        > So for 401, I needed to test only one witness, not nine.
        >
        > Is there a simple function that will for sure give me a close to optimum
        > number
        > of witnesses that I need to test to ensure primeness,
        >
        > given that my witnesses are the primes in sequential order?
        >
      • Phil Carmody
        ... How big is z? If it s small, then use Jaeschke s or Moxham s bounds. Anyone remember a reference to the chinese result which used agreement among higher
        Message 3 of 4 , Jun 26, 2006
        • 0 Attachment
          --- Kermit Rose <kermit@...> wrote:
          > Currently, I test the number Z for primness by testing
          > whether or not Z is a pseudo prime base w for one more than
          > log base 2 of Z primes.
          >
          > I'm sure I'm testing for too many witnesses to ensure that z is prime.

          How big is z?

          If it's small, then use Jaeschke's or Moxham's bounds.
          Anyone remember a reference to the 'chinese' result which used agreement among
          higher roots of unity apart from square (Jaeschke) or 4th (Moxham)?

          It's probably in the groups archives, as it's come up a few times.

          For anything in the real world, just aim for the $620 counter-example to the
          PSW test. If you find a composite after using this test to suggest primality,
          fame and fortune are guaranteed!

          Phil

          () ASCII ribbon campaign () Hopeless ribbon campaign
          /\ against HTML mail /\ against gratuitous bloodshed

          [stolen with permission from Daniel B. Cristofani]

          __________________________________________________
          Do You Yahoo!?
          Tired of spam? Yahoo! Mail has the best spam protection around
          http://mail.yahoo.com
        • Ed Pegg Jr
          I m not sure if it s been mentioned here. The latest Al Zimmermann Programming contest shattered all existing records in the field of Prime Generating
          Message 4 of 4 , Jun 26, 2006
          • 0 Attachment
            I'm not sure if it's been mentioned here.

            The latest Al Zimmermann Programming contest shattered all existing records in the field of Prime Generating Polynomials.
            For example, one polynomial that generates 49 primes is x^4 - 97*x^3 + 3294*x^2 - 45458*x + 213589, first found by Mark
            Beyleveld and later by 5 other participants. More results:

            CUBIC:
            -66 x^3 + 3845 x^2 - 60897 x + 251831. Prime for x=0 to 45. Ivan Kazmenko and Vadim Trofimov.
            42 x^3 + 270 x^2 - 26436 x + 250703. Prime for x=0 to 39. Jaroslaw Wroblewski and Jean-Charles Meyrignac.

            QUARTIC:
            x^4 - 97x^3 + 3294x^2 - 45458x + 213589. Prime for x=0 to 49. Mark Beyleveld.

            QUINTIC:
            (x^5 - 133 x^4 + 6729 x^3 - 158379 x^2 + 1720294 x - 6823316)/4. x=0 to 56. Shyam Sunder Gupta.
            x^5 - 99x^4 + 3588x^3 - 56822x^2 + 348272x - 286397. x=0 to 46. Jaroslaw Wroblewski & Jean-Charles Meyrignac.

            SEXTIC:
            (x^6 - 126 x^5 + 6217 x^4 - 153066 x^3 + 1987786 x^2 - 13055316 x + 34747236)/36. Prime for x=0 to 54. Jaroslaw Wroblewski & Jean-Charles Meyrignac.

            Full details and findings will eventually be published at recmath.org

            Ed Pegg Jr


            [Non-text portions of this message have been removed]
          Your message has been successfully submitted and would be delivered to recipients shortly.