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

Jaeschke's bounds

Expand Messages
  • Kermit Rose
    1c. Re: number of witnesses needed to verify a number of given size is p Posted by: Phil Carmody thefatphil@yahoo.co.uk thefatphil Date: Mon Jun 26, 2006
    Message 1 of 1 , Jun 27 11:11 PM
    • 0 Attachment
      1c. Re: number of witnesses needed to verify a number of given size is p
      Posted by: "Phil Carmody" thefatphil@... thefatphil
      Date: Mon Jun 26, 2006 6:58 am (PDT)


      How big is z?

      If it's small, then use Jaeschke's or Moxham's bounds


      **************************



      For Jaeschke's

      I found the references

      http://primes.utm.edu/prove/prove2_3.html


      # If n < 1,373,653 is a both 2 and 3-SPRP,
      then n is prime.


      # If n < 25,326,001 is a 2, 3 and 5-SPRP,
      then n is prime.

      # If n < 25,000,000,000 is a 2, 3, 5 and 7-SPRP,
      then either n = 3,215,031,751 or n is prime. (This is actually true for n <
      118,670,087,467.)

      # If n < 2,152,302,898,747 is a 2, 3, 5, 7 and 11-SPRP,
      then n is prime.

      # If n < 3,474,749,660,383 is a 2, 3, 5, 7, 11 and
      13-SPRP, then n is prime.

      # If n < 341,550,071,728,321 is a 2, 3, 5, 7, 11, 13 and 17-SPRP,
      then n is prime.



      I incorporated these numbers in my prime number testing routine. Actually,
      I incorporated only their integer log base 2
      in my routine.

      For Z > 2^48, i decided to use

      int( sqrt ( log2 ( Z ) ) ) + 1, as the upper bound on the number of
      witnesses.

      I expect that their could be some counterexamples, but they would be very
      scarce.

      After I figure out the Lucas prime number tests, I can combine them, and
      then will fee
      more assured that my test will be valid for integers of any size that I'm
      remotely likely to be dealing with.


      and



      http://en.wikipedia.org/wiki/Miller-Rabin_primality_test


      When the number n we want to test is small, trying all a < 2(ln n)^2
      is not necessary, as much smaller sets of potential witnesses are known to
      suffice.


      Here is the answer I sought to my original question.

      The simple function is 2 * ( ln(z) )^2

      It's larger than the ln(z) that I'm currently using.
    Your message has been successfully submitted and would be delivered to recipients shortly.