On Friday 04 September 2009 04:58:53 Bill Hart wrote: > 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.
I think this is an advantage. I dont want people to confuse this function with any particular probable prime test , and get upset when they find out it is no particular one ,and they wont find it in the mathematical literature (why ? , because we have not shown any particular mathematical property is true, eg like true for all n<10^15 , or true with an error rate of <1 in 2^10 etc). It's purpose is for factoring , where we want speed and reasonable accuracy , and this function is ment to be it. As it is common in factoring to do trial division , it is pointless to do it again , so that is why I added the bound.I did think of adding a structure to pass other information , but that is overkill for the purpose of this function(if we do a real prime test , then we should pass this sort of info). I don't want to get into real prime tests yet , that is a whole new can of worms. We have obsoleted mpz_probab_prime_p because of reasons stated before, so we have to replace the functionality of it with some new functions. mpz_probab_prime_p was used in factoring and the new mpz_practical_prime_p is my attempt at replacing it for that purpose. The other use of mpz_probab_prime_p was to perform strong psuedoprime tests so the user could say this number passed 10 reps of sprp tests. The new mpz_probable_prime_p is my attempt at replacing this part , here we have dropped any specification of a particular probable prime algorithm , this gives us freedom to use faster variants , and the user still gets what they wanted , a declaration of probable primeality with a given maximum error rate.I put a trial div bound in here , as again it is a common thing to of allready have done. The other use of the old mpz_probab_prime_p was when the user specifically wants a strong psuedoprime test performed and not something similar. I haven't provided for this. We could certainly add specific functions for this , for the moment the user can just call our new mpz_probable_prime_p because that is the only test it uses at the moment. Users should not care about the algorithms used , the functions should be black boxes. My main motivation was to replace the clearly poor functions we had with something better. The new functions do solve the poor random state of the old functions , and in principle , if you replace the old mpz_probab_prime_p in your programs with the appropriate new function you should see a speed up. I haven't actually written the new code yet for that.I do plan to add some of these "missing" functions later , but I see how well this first lot go down > 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 -~----------~----~----~----~------~----~------~--~---
