Three technical remarks about GMP functions

David T. Ashley dashley at
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.

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