Deterministic Primality Test?

[Paulo J. Matos]

On 22/04/06, David T. Ashley <dta at e3ft.com> wrote:
> > > Is there any deterministic primality test available in GMP?
> > >
> >
> > A primality proving test ?
> > No - though if mpz_probab_prime_p() returns 2, the number in question is
> > definitely prime.
>
> How about the GMP equivalent of:
>
> is_prime(arg)
>    {
>    for (i=2; i<=sqrt(arg); i++)
>       if ((arg % i) == 0)
>          return(FALSE);
>
>    return(TRUE);
>    }
>
> ?????
>
> Well, that ought to get me banned from this list!!
>
> In all seriousness, you'd have to roll your own using your own code atop the
> GMP.  Since primes get sparser as the numbers get larger, the best approach
> is probably probabilistic primality tests followed up with other steps if
> the number is looking possibly prime ...
>

OK, thanks for the insight on this.

Paulo Matos

> Dave.
>
>
>


--
Paulo Jorge Matos - pocm at sat inesc-id pt
Web: http://sat.inesc-id.pt/~pocm
Computer and Software Engineering
INESC-ID - SAT Group