Brian, I forgot to mention, there is a new test file tests/mpz/t-likely_prime_p.c which you might wish to add to the Windows build.
Bill. 2009/12/7 Bill Hart <[email protected]>: > 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.
