Three technical remarks about GMP functions
NUNES
raulnunes at yahoo.com
Sun Jun 5 19:04:57 CEST 2005
To GMP Discussions Group (gmp-discuss at swox.com)
Permit me to make three technical remarks about the following GMP functions:
A) I'll appreciate so much (and I suppose that many other GMP users too) to have a little "demo" program showing how one can use the procedure mpz_array_init (Dest: mpz_array_ptr; ArraySize, FixedNumBits: mp_size_t); asmname '__gmpz_array_init'; in GNU Pascal (my main doubt is in relation to mpz_array_ptr).
B) Moreover, how to use mpz_inp_raw and mpz_out_raw, also in GNU Pascal since they use C file pointers:
{$if False} { @@ commented out because they use C file pointers } function mpz_inp_str (var Dest: mpz_t; Src: CFilePtr; Base: Integer): SizeType; asmname '__gmpz_inp_str'; function mpz_inp_raw (var Dest: mpz_t; Src: CFilePtr): SizeType ; asmname '__gmpz_inp_raw'; function mpz_out_str (Dest: CFilePtr; Base: Integer; protected var Src: mpz_t): SizeType; asmname '__gmpz_out_str'; function mpz_out_raw (Dest: CFilePtr; protected var Src: mpz_t): SizeType ; asmname '__gmpz_out_raw'; { @@ mpf_out_str has a bug in GMP 2.0.2: it writes a spurious #0 before the exponent for negative numbers } function mpf_out_str (Dest: CFilePtr; Base: Integer; NumberOfDigits: SizeType; protected var Src: mpf_t): SizeType; asmname '__gmpf_out_str'; function mpf_inp_str (var Dest: mpf_t; Src: CFilePtr; Base: Integer): SizeType; asmname '__gmpf_inp_str'; {$endif}
C) At last, I would like to make a comment about the [Function] int mpz_probab_prime_p (mpz t n, int reps) which determines whether n is prime. It returns 2 if n is definitely prime, returns 1 if n is probably prime (without being certain), or returns 0 if n is definitely composite.
This function does some trial divisions (for primes <=???), then some Miller-Rabin probabilistic primality tests. reps controls how many such tests are done, 5 to 10 is a reasonable number, more will reduce the chances of a composite being returned as "probably prime".
Miller-Rabin and similar tests can be more properly called compositeness tests. Numbers which fail are known to be composite but those which pass might be prime or might be composite. Only a few composites pass, hence those which pass are considered probably prime.
But, from the Elementary Number Theory, it is so known that the Rabin-Miller test can assert WITH CERTAINTY the compositeness or primality of any natural number less than 341,550,071,728,321 (by testing ONLY the seven prime bases 2,3,5,7,11,13,and 17). So, why this function does not apply these simple criteria? For example, for the prime 2^32-5=4,294,967,291, it returns 1 when it could return 2.
Thanks in advance for your kind consideration about.
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 http://geocities.yahoo.com.br/raulnunes/
---------------------------------
Yahoo! Mail Mobile
Take Yahoo! Mail with you! Check email on your mobile phone.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://gmplib.org/list-archives/gmp-discuss/attachments/20050605/95ddd295/attachment.html
More information about the gmp-discuss
mailing list