I don't personally like the name mpz_practical_prime_p(). The reason is that it doesn't mean anything particular to anyone but us. Here's some random ideas. We could change the prototypes to:
mpz_is_probab_prime_p(mpz_t p, prime_alg_t alg, unsigned long iterations) mpz_is_prime_p(mpz_t p) where p is the number being checked for primality, alg specifies a algorithm (the prime_alg_t would be an enum enumerating possible algorithms) and the iterations thing is self explanatory. The mpz_is_prime wouldn't need an algorithm specified as it should just do whatever is fastest to certify the prime. mpz_next_probab_prime(mpz_t p, mpz_t old_p, prime_alg_t alg, unsigned long iterations) mpz_next_prime(mpz_t p) Again the flags and rationale would be the same. The only thing which doesn't fit very well is the trial factoring thing. If the number has already been trial factored up to some bound then how would you specify that. But not all algorithms care about that. Perhaps all the extra data about algorithm, iterations, trial factoring limit should be passed in in a single struct, a gmp_prime_t struct or something like that, which could be null if you really don't care and just want something quick and dirty with no special properties (like we currently have). So you'd have: mpz_is_probab_prime_p(mpz_t p, mpz_prime_t inf) mpz_is_prime_p(mpz_t p, mpz_prime_t inf) mpz_next_probab_prime(mpz_t p, mpz_prime_t inf) mpz_next_prime(mpz_t p, mpz_prime_t inf) I don't know, this whole primality testing thing just opens a huge can of worms. I mean, the most efficient way of finding the nextprime is to first sieve which means you want to be setting up a persistent sieve. But that is not something you want to do with a type like that as every time the function is called you have to check if p is actually the last prime that was found in the associated sieve. Instead you want specific functions which initialise a sieve and find the next prime in the sieve given an offset in the sieve: mpz_prime_sieve_init(mpz_sieve_t sieve, mpz_t start) - where start specifies the first number in the sieve (must be even and not 2) mpz_next_prime(mpz_t p, mpz_t old_p, mpz_sieve_t sieve) - where old_p must specify a number which lies in the sieve, p will be the next prime after it Of course to do *that* efficiently you need the an atkins sieve or the other algorithm whose name I forgot - the one miller used in his primepi implementation. Bill. 2009/9/4 Jason Moxham <[email protected]> > > 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 -~----------~----~----~----~------~----~------~--~---
