Loading ...
Sorry, an error occurred while loading the content.
 

Re: Fast Primality GMP Function ?

Expand Messages
  • jasonmoxham@ymail.com
    ... 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.