Re: Fast Primality GMP Function ?
- --- In email@example.com, Mark Rodenkirch <mgrogue@...> wrote:
>Yeah thanks , I have been sloppy with my words , I'm normally fairly careful , but it's getting late.
> On Aug 24, 2009, at 6:29 PM, jasonmoxham@... wrote:
> > If you mean the gmp function mpz_probab_prime_p ,then there is a
> > problem in that it resets it's random state on each call , therefore
> > two calls to mpz_probab_prime_p will not give independent
> > probability's(for the same number N) and so you cannot "accumulate"
> > calls. In other words for each N and reps there exist (fixed)
> > numbers X such that N is composite but mpz_probab_prime_p will
> > return prime
> I believe you mean that it will return PRP, not prime under these
> conditions. This function only returns prime for small n (< 1e6) that
> are indeed prime.
>FYI , I'm doing a bit of work on a MPIR (a gmp fork) and we have just depreciated the existing mpz_probab_prime_p , and I/we will be replacing it with something better/faster. This is all for the SAGE project (a free/open source "mathematica")
> I suggested (offline) that he run a weak PRP test (wiki is your
> friend). If he wants a strong PRP test, then he could use
> mpz_probab_prime_p or code his own test. I suspect that a weak PRP
> test is sufficient for his needs. If he truly wants primality then he
> will have to go a different route.
> BTW, I also suggested that he does his own trial division. This would
> be easy to do if the numbers follow a pattern that allows a sieve to
> be used against them.
> [Non-text portions of this message have been removed]