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

Re: [PrimeNumbers] number of witnesses needed to verify a number of given size is prime.

Expand Messages
  • 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 1 of 4 , Jun 25, 2006
      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 2 of 4 , Jun 26, 2006
        --- 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 3 of 4 , Jun 26, 2006
          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.