On Monday 17 August 2009 14:02:13 Jason Moxham wrote: > Hi > > I've obsoleted then MPIR function > > int mpz_probab_prime_p (mpz_t N, int REPS) > > The reasons for this are mainly that the random state used in the above > algorithm is reset on every function call. So two consecutive calls to this > function are NOT independent. The other reason is that the parameter REPS > is dependant on the algorithm used(which is Miller-Rabin). > > We will maintain the old function interface for some time to come to > maintain compatibility. > > The question remains as what to offer as a replacement. We could of course > offer no replacement? or at the bare minimum > > int mpz_probable_prime_p (mpz_t N, int REPS, gmp_randstate_t STATE) > > However I would like to suggest something like this. > > Note: Some of these may not be functions but macros.
Here are the new functions: int mpz_practical_prime_p(mpz_t N, gmp_randstate_t STATE,unsigned long div) return true if N is probably a prime and return false if N is certainly a composite or (0,1,-1) . NOTE: I say N is probably a prime , NOT N is a probable prime , which can mean something specific. This would be the function that you would use in a integer prime factorization program , optimized for speed , implemented as a bit of trial division , and one iteration of small base random strong pseudoprime test , with corners cut to make run faster(on average).div is a trial division bound of which you have allready searched up to. And the mathematically better defined int mpz_probable_prime_p(mpz_t N, int PROB, gmp_randstate_t STATE,unsigned long div) return true iff N is a probable prime with less than 1/2^PROB error. This allows us to use different algorithms to achieve the same maximum probability of error. This would implemented robustly using the random strong pseudoprime test , RQFT test and others. div is a trial division bound of which you have allready searched up to. I have said that the new function interfaces are preliminary , in case we want to change anything. This brings into question what the new mpz_next_probable_prime should do , ie should it be practical or probable (with a defined probability) , at the moment it is just the old mpz_probab_prime with 5 reps which would be equivalent to a probability of 1 in 4^5 . Note: this is a maximum error and is WAY over the top of most reasonable applications. What do people think? What should we do ? , I am leaning towards having both next_practical and next_probable(with a stated probability) Jason Note: The trial division I have used in the above fn's is just for correctness , I will put faster code in a few days , so dont laugh at to much :) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en -~----------~----~----~----~------~----~------~--~---
