Three technical remarks about GMP functions

[Décio Luiz Gazzoni Filho]

On Jun 6, 2005, at 4:03 AM, David T. Ashley wrote:

>>> 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.
>>
>
> "Finite" wasn't what I wanted to say.  What I meant is unless you are
> willing to expend the
> same amount of compute time that it would take to factor the number  
> (should
> it prove to be a
> composite), you have to settle for some small probability that it  
> is not
> prime, i.e.

If the Riemann Hypothesis is true, then Miller-Rabin may be made into  
a polynomial time primality (testing something like the first 2 log^2  
n bases reveals definitely whether n is prime or composite). Whether  
there exists a better result than that not conditional on the Riemann  
Hypothesis, I couldn't tell.

But the real source of the name `compositeness test' is that, if  
Miller-Rabin asserts that a given integer is composite, then it is a  
proven composite and the base used is a certificate of compositeness  
for the integer in question. In this sense it is a compositeness  
test, even if testing a lot of bases is required to uncover this. I  
believe the elliptic curve primality proving algorithm faces a  
similar problem -- you might be `unlucky' and be unable to advance to  
the next step in the certification chain for a long time. But that  
doesn't make it any less of a primality test, since when it is  
finished, it produces a certificate that can be independently checked  
and is proof of the primality of a given integer.

Of course, all this discussion is academic, since Miller-Rabin  
testing by a handful of bases very very rarely produces a wrong  
answer. As stated on the MathWorld page in question, the probability  
of failure is smaller than the probability of hardware error.

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/758f08b4/PGP.bin