Three technical remarks about GMP functions

[David T. Ashley]

>Nunes wrote:
>
>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:

No demo program is necessary.  Between the manual, the function prototypes,
and the source code, it is pretty obvious.

With any documentation, one has to make assumptions about the skill level of
the reader.  The assumption is that the reader is fluent in 'C'.  If this
assumption is invalid in your case, the solution is for you to close any
technical gaps you have.  The solution is NOT to enhance the documentation.

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

Quatsch! (Did I spell that right?).  Bologna!  Miller-Rabin is neither a
compositeness test nor a primality
test.  True, an individual application _might_ prove that a given number is
composite (but cannot prove
it is prime).  But using Miller-Rabin, one can always generate a large
composite that will not be identified
as a composite (assuming one knows in advance which bases will be used).
So, Miller-Rabin is not a
compositeness test--there are composites that will slip through and not be
identified as such.

It does not, in finite compute time, identify every composite as a
composite;
thus it is not a compositeness test.

It is, in fact, a probable primality test.  This nomenclature is just fine.

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

This argument is interesting.  It gets in to the precise interface between
the GMP and
the client (and what should be on each side of the interface).

Generally, a library like the GMP might want to just do arbitrary-size
integer operations
and let the client worry about higher-level things (like application of
Miller-Rabin).
The rationale for drawing the interface there is performance--the
high-frequency interactions
should occur within the GMP and everything else belongs to the client.  The
criterion
for whether to include something in the GMP might be "Can it be included in
a client
with little performance penalty?".

However, the function in question has already violated that line.  It has
included
something in the GMP that could just as well be in the client with no real
performance penalty.

There would seem to be two choices:

a)Remove the function in question from the GMP and force it into clients, or

b)Enhance the function per your suggestion.

I partially agree with you about this function.  In some sense it is
incompletely
implemented.

Dave.