Three technical remarks about GMP functions
Décio Luiz Gazzoni Filho
decio at decpp.net
Mon Jun 6 04:04:09 CEST 2005
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
More information about the gmp-discuss
mailing list