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

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