primality test

Sisyphus sisyphus1 at
Thu May 19 03:31:32 CEST 2005

----- Original Message ----- 
From: "Jens Hillenbach" <jhillenbach at>
To: <gmp-discuss at>
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:


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 .

For some primality discussion/algorithms (both provable and probable) see
Chapter 4 of "Handbook of Applied Cryptography" - which you can download
from .

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


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

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

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;


More information about the gmp-discuss mailing list