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.
