- 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

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?

> - --- Kermit Rose <kermit@...> wrote:
> Currently, I test the number Z for primness by testing

How big is z?

> 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.

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 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]