## Jaeschke's bounds

Expand Messages
• 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, 2006
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.