This looks like a sensible interface. I think I would like to implement something like this.
For now I have simply turned on my BPSW test for single limbs in mpz_likely_prime_p and added some test code. This means at least for single limbs, mpz_nextprime probably won't return any composites. Most people who want an actual prime who are using this function probably want a single limb prime. Others are probably going to realise that multiple limb primes are not necessarily going to be prime. Anyhow the test code passes, not that it does a whole lot. It merely uses the test code for mpz_probab_prime_p which just trial divides to see if a given number is prime or not, so it doesn't do anything with multiple limb primes anyway. Bill. 2009/12/5 Case Vanhorsen <[email protected]>: > On Sat, Dec 5, 2009 at 6:49 AM, Bill Hart <[email protected]> wrote: >> I guess the important question is, is there a better way for us to do >> mpz_nextprime and mpz_likely_prime_p. >> >> I strongly suspect people who are after primes for RSA or DH >> applications will use the latter, whereas someone after a convenient >> function which for all intents and purposes returns a prime, will use >> the former. >> >> Thus my feeling is that mpz_nextprime should be more like the GMP >> mpz_nextprime function, i.e. with "few" exceptions. However, this is >> certainly something we should discuss. Technically the function is >> obsoleted anyway because it doesn't, and wont ever, do what it says. >> But even so, it will be replaced by mpz_next_likely_prime. This is >> going to be a problem if mpz_likely_prime_p does something completely >> different to mpz_next_likely_prime. >> >> So I see a potential conflict here, and no obvious solution. Any ideas? > I'm sure I missed something in the prior discussions so feel free to > correct me. > > These are conflicting use cases so I think the default behavior should > be the most conservative. In gmpy, I'd like to assume > gmpy.next_prime(n) has the same results as "while not > gmpy.is_prime(n): n+=1". If it's faster, that's great. > > Would it make sense to provide the following functions? > > mpz_trial_factor(mpz_t z, n): > Perform trial factoring of z to at least limit n. > > mpz_miller_rabin(mpz_t z, n): > Perform a Miller-Rabin test to base-n (possibly some trial factoring). > > mpz_bpsw_psp_p(mpz_t z): > Perform the BPSW test. > > mpz_mr_psp_p(mpz_t z, gmprandstate, prob, div): > Perform trial factoring to div, then prob iterations of Miller-Rabin test. > > mpz_next_mr_p(mpz_t z): > Returns the next mpz that passes mpz_miller_rabin(z, 2). > > mpz_next_mr_psp_p(...) > Returns the next mpz that passes mr_psp_p(). > > mpz_next_bpsw_p(...) > Returns the next mpz that passes mpz_bpsw_psp_p(). > > Then leave the old GMP functions as is. I think the old > mpz_probab_prime_p would map to mpz_mr_psp_p with a fixed random > state. > > And then provide convenience functions: > mpz_pseudo_prime_p and mpz_next_pseudo_prime (or mpz_psp_p and > mpz_next_p) that call the appropriate functions listed above with > reasonable defauls. Faster, but theoretically more likely to be wrong, > versions could be called mpz_fast_psp_p and mpz_fast_next_psp_p. > > If an application wants to guarantee behavior (algorithm vs. speed vs. > reliability), it would call functions in the first set. If an > application just wants an answer, it would call the convenience > functions. > > casevh > >> >> Bill. >> >> 2009/12/5 Bill Hart <[email protected]>: >>> I realise the statement was not precise. What I meant to suggest is >>> that given a number in the range I was working with, chosen through >>> some randomised process, which has already been trial factored, but >>> which has non-trivial factors, what is the chance that a single >>> Miller-Rabin test to a random base will not detect that the number is >>> composite. >>> >>> Of course I should have said that the chances approach 1/4 in some >>> cases. This is kind of like gutter journalism. I could have said that >>> your chances of dying of swine flu approached 1 in 200. For some >>> particularly poorly chosen outlier sample, it's true. >>> >>> Of course my application just happened to be a particularly pooly chosen >>> sample. >>> >>> Sorry for being inaccurate. >>> >>> By the way, on T.R. Nicely's page he has a paper on instances where >>> the GMP primality test function returns composites. It does happen, it >>> is just exceptionally rare. In our case it does happen, it's just not >>> rare. (For some suitably vague definition of rare.) >>> >>> Bill. >>> >>> 2009/12/5 Xilman <[email protected]>: >>>> >>>> >>>> On Dec 4, 5:29 pm, Bill Hart <[email protected]> wrote: >>>>> Whoah, it just does trial division up to 1000 then uses a *single* >>>>> *random* base for a strong pseudoprime test! >>>>> >>>>> I have a definite problem with this. What is the probability of >>>>> returning a composite? Assuming the factors are bigger than 1000, it >>>>> is like 1/4. >>>> >>>> Your question is ill-defined and your answer is, arguably, very rarely >>>> correct. >>>> >>>> If you meant to ask: "what is the probability of a composite integer c >>>> picked uniformly at random from the range 1000<c<N being reported as >>>> pseudoprime by a single Miller-Rabin test?", the answer is "very >>>> small, much much smaller than 1/4". The precise value of "very small" >>>> depends on N, and becomes smaller as N increases. >>>> >>>> If you meant to ask: "given that composite c < N is reported as >>>> pseudoprime by a Miller-Rabin test to a particular base b, what >>>> fraction of bases 2 <= b < N-1 give such a report?" the answer is " >>>> less than 1/4, but a small fraction of such c give a fraction which >>>> approaches arbitrarily close to 1/4 as N grows arbitrarily large". >>>> >>>> For numbers of interest to, say, RSA or DH implementations a single M- >>>> R test is sufficient as this corresponds to the first re-phrasing of >>>> your question. >>>> >>>> Paul >>>> >>>> -- >>>> >>>> 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. >>>> >>>> >>>> >>> >> >> -- >> >> 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. >> >> >> > > -- > > 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. > > > -- 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.
