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