On Friday 04 September 2009 03:38:58 Jason Moxham wrote: > 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) > Or getting rid of the mpz_next_prime_thing all-together , cant say I like it much. What do people use it for ?
The old function was mpz_nextprime_p . We obsoleted this function because it was badly named (it was not necessarily prime) and even if we admit that , the random state used to generate the probable primes was not random , but reset on each call. > 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 -~----------~----~----~----~------~----~------~--~---
