Three technical remarks about GMP functions

[Décio Luiz Gazzoni Filho]

On Jun 5, 2005, at 9:03 PM, David T. Ashley wrote:

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

Not if you do enough tests. You may be thinking of Fermat's test,  
where a Carmichael number will never be identified by a Fermat test,  
unless the base happens to share a factor with the Carmichael number  
in question (so it might still be identified, although the  
probability is very small.)


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

That's not true. Even trial division finishes in a finite amount of a  
time for a given integer, and produces a factor (if the integer is  
composite) to boot.


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

Henri Cohen would disagree with you. In his book `A Course in  
Computation Algebraic Number Theory', the section housing an  
explanation to the Rabin-Miller test is called `Compositeness Tests'.

Not that I'm advocating a name change, but `compositeness tests' is  
correct, and so is `probable prime test'.


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

I have a different opinion here. It's a very handy function and  
widely used in number-theoretic software -- why should programmers be  
required to reimplement it each time (reinvent the wheel, if you will)?

I mean, look at the square rooting function -- one could write a  
Newton-Raphson routine that runs as fast as the library code, but do  
you really want to throw that away?

Décio

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20050606/ef1863ff/PGP.bin