## Re: Fast Primality GMP Function ?

Expand Messages
• ... Yeah thanks , I have been sloppy with my words , I m normally fairly careful , but it s getting late. ... FYI , I m doing a bit of work on a MPIR (a gmp
Message 1 of 5 , Aug 24, 2009
--- In primenumbers@yahoogroups.com, Mark Rodenkirch <mgrogue@...> wrote:
>
>
> 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.

Yeah thanks , I have been sloppy with my words , I'm normally fairly careful , but it's getting late.

>
> 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.
>
> --Mark
>
> [Non-text portions of this message have been removed]
>

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")
Your message has been successfully submitted and would be delivered to recipients shortly.