primality test

[Sisyphus]

----- Original Message ----- 
From: "Jens Hillenbach" <jhillenbach at yahoo.com>
To: <gmp-discuss at swox.com>
Sent: Thursday, May 19, 2005 2:20 AM
Subject: primality test


> Hi everybody,
>
> I need a deterministic test which decides wether a number is prime or
> not. Unlike the Miller-Rabin-Version which is used by GMP's
> mpz_probab_prime_p (mpz_t n, int reps), I need it really to be
> deterministic. Do you know examples, where Miller-Rabin fails? Which
> test do you use?
> I read somewhere there is one test which has polynomical complexity.
> Has someone implemented this Agarwal-Kayal-Saxena Primality Test with
> GMP and is willing to share it?
> Or is it better to use Elliptic Curve Primality Proving? Where do I
> obtain the algorithm or even source?
>
> Any help is appreciated! Thanks in advance, bye, Jens
>

The following composite will be reported "prime" by many individual
Miller-Rabin tests, especially for small bases:

8038374574536394912570796143419421081388376882875581458374889175222974273765
3336521865023361639600454579150420236032087665699667609872840439654082329287
3879185086916685732826776177102938969773947016708230428687109997439976544144
8453411558724506334092790222752962294149842306881685404326457534018329786111
298960644845216191652872597534901

This number has been carefully engineered by someone - it wasn't discovered
by chance.

I set x to that value and ran 1000 iterations of mpz_probab_prime_p(x, 5).
All tests returned "composite". (But then I'm a little suspicious about the
usuefulness of running multiple iterations of mpz_probab_prime_p() tests -
see the footnote below).

Put simply - if you have an application that needs prime numbers, check for
primality by performing an adequate number of Miller-Rabin tests (using
bases chosen at random). If you want to be certain that they are prime, then
go way overboard on the number of tests done - it is still much faster than
any primality-proving algorithm. Imho, the only time you need a
primality-proving algorithm is when you want to prove primality as an
academic exercise.

For that, if you're on Win32, there's a nice little app available from
http://www.ellipsa.net/ .

For some primality discussion/algorithms (both provable and probable) see
Chapter 4 of "Handbook of Applied Cryptography" - which you can download
from  http://www.cacr.math.uwaterloo.ca/hac/ .

The Sci.Crypt usenet newsgroup is a good place for questions/discussion
involving prime numbers.

And there's what has already been suggested by others.

*footnote - As I understand it, the second arg supplied to
mpz_probab_prime_p() determines the number of Miller-Rabin tests that are
performed, and the base for each of those Miller-Rabin tests is randomly
chosen. Yet, I find that mpz_probab_prime_p(x, 1) *always* returns 1,
mpz_probab_prime_p(x, 2) *always* returns 1, and mpz_probab_prime_p(x, 3)
*always* returns 0.
What's happening there - how can 2 repetitions *always* return "prime" and 3
repetitions *always* return "composite" ? Are the same bases being chosen
each time the mpz_probab_prime_p() tests are run ? A properly designed
probable prime test should be selecting random bases for the miller-rabin
tests.
The actual program is included below my signature, for anyone who wants to
run it. For me, it prints 600 1's followed by 300 0's.

Cheers,
Rob

#include <stdio.h>
#include <gmp.h>

int main(void) {
    mpz_t c;
    int i;

    mpz_init_set_str(c,
"803837457453639491257079614341942108138837688287558145837488917522297427376
5333652186502336163960045457915042023603208766569966760987284043965408232928
7387918508691668573282677617710293896977394701670823042868710999743997654414
4845341155872450633409279022275296229414984230688168540432645753401832978611
1298960644845216191652872597534901", 10);

    for(i = 0; i < 300; ++i)
       printf("%d", mpz_probab_prime_p(c, 1));

    for(i = 0; i < 300; ++i)
       printf("%d", mpz_probab_prime_p(c, 2));

    for(i = 0; i < 300; ++i)
       printf("%d", mpz_probab_prime_p(c, 3));

    return 0;

}