primality test

[Jonathan A. Zylstra]

Sisyphus wrote:

>----- 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).
>
>  
>
There is nothing in the documentation that suggests that the bases 
chosen are random. It's much more useful to preform

mpz_probab_prime_p(c, 3000)

than 3000 iterations of mpz_probab_prime_p(c, 1)


>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.
>
>  
>
Be very careful here ... even if you run a 'large number' of tests, 
there is still a chance [small, yes] of that number being composite.
Now, from "Prime Numbers, A Computation Perspective" by R. Crandall, C. 
Pomerance, they have detailed explanations of the Miller Rabin Test, 
plus descritions of algorithms of many primality proving tests.
The following info is from the above book:

To use the Miller-Rabin test to prove that a number is conclusively prime,
you need to test using all bases up to sqrt(n)
If you want to assume a conjecture [namely the Extended Riemann hypothesis]
you need to test using all bases up to 2 * (ln^2  n)
Otherwise, there is still a chance for a number to pass dozens of 
iterations of the test, and still be composite.

Try these numbers on for size: (use the algorithm in the footnote 
provided by Rob ... starting with 1 iteration, and working your way up)

1502401849747176241 (passes bases 2 -11, recognized composite by base 
12) ( ?? requires 8+ iterations to pass -my guess, haven't tried it 
using gmp)
341550071728321 (passes bases 2-22, recognized composite by base 23) ( 
?? requires 13+ iterations to pass -my guess, haven't tried it using gmp)

Jonathan A. Zylstra

>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;
>
>}
>
>_______________________________________________
>gmp-discuss mailing list
>gmp-discuss at swox.com
>https://gmplib.org/mailman/listinfo/gmp-discuss
>
>  
>