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.
