Three technical remarks about GMP functions (Corrective Message)

NUNES raulnunes at
Tue Jun 7 09:09:16 CEST 2005

Please, this message replace the preceeding one just sent.  Excuse me!

Thanks all for your prompt answers. But, I think I must to complement my questions. 

At on can read that 

"The strong k-pseudoprime test for k = 2, 3, 5 CORRECTLY IDENTIFIES ALL PRIMES below 2.5*10^10 with only 13 exceptions, and if 7 is added, then the only exception less than 2.5*10^10 is 3215031751. Jaeschke (1993) showed that there are only 101 strong pseudoprimes for the bases 2, 3, and 5 less than 10^12, nine if 7 is added, and NONE IF 11 is added." (capitalization added). 

Besides, from Riesel's "Prime Numbers and Computer Methods for Factorization" (2nd edition -1994-p.91), one can also read:

"As a matter of fact, the smallest strong pseudoprime to all the bases 2,3,5,7, and 11 simultaneously is the number 2152302898747, and THUS 5 STRONG PRIMALITY TESTS TO THESE BASES WILL PROVE A NUMBER BELOW THIS LIMIT PRIME (if it is). If we instead use the seven bases 2,3,5,7,11,13,and 17, EVERY NUMBER BELOW 341550071728321 CAN BE IDENTIFIED AS A PRIME OR COMPOSITE BY THIS TECHNIQUE. In practice we of course do not perform all seven tests first, and then decide on the characterof number. In most of the cases the test for base 2 already reveals the number as composed, and we are finished. If not, we pass on the next test and so on." (capitalization added).

Summing up: Although the Strong Pseudoprimes Test should be used only to test the compositeness of numbers, within the above limits, it may serve to assure the PRIMENESS of a lot of numbers < 3.41*10^14 very quicly. So, my suggestion is the insertion of these criteria in the subroutine mpz_probab_prime_p (perhaps replacing the trial division already embedded in it), in order to improve its performance. 

I hope to have shown my viewpoint about this point so clearly. Apropos, I believe I know enough of Number Theory, in particular about the subject in question. By the way, when a manual (about hardware or software) has not sufficiently clear descriptions, I use to make several tests to discovery the ommitted information (e.g., my test of the prime 2^32-5 cited). Despite my long-life experience and expertise in computer programming, I thought somebody could help me with a few lines of a demo of the use of mpz_array_init in GNU PASCAL. On the other hand, I insist that DEMOS programs for GNU PASCAL USERS showing how to use GMP subroutines can be very instructive. 

At last, HOW ONE CAN USE the GMP subroutines mpz_array_init , mpz_inp_raw, and mpz_out_raw, also in GNU Pascal?  This is the point!!!


Eng. Raul Nunes 
NEST Newsy Echoes on Science and Technology 

NEST presents the latest headlines on more than 300 different subjects,  harvested from near 2500 news sources and, above all, updated nearly  every 15 minutes.  Standard Headlines emphasize the sci-tech matters, while Personal Headlines permits customized specifications according to user's preferences.  Enjoy it!  CLICK HERE
Yahoo! Mail Mobile
 Take Yahoo! Mail with you! Check email on your mobile phone.
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the gmp-discuss mailing list