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? 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.
