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