Three technical remarks about GMP functions

David T. Ashley dashley at abi-consulting.com
Mon Jun 6 09:03:49 CEST 2005


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

http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

However, I freely admit that I'm not a good number theorist--I believe that
2 and 3 are prime and
that is as far as my knowledge goes.



More information about the gmp-discuss mailing list