[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: MODP groups draft concern
> Tero:
>
> A probability like 1/4^200 always impresses people but misses the point.
> There is a class of composite integers for which Miller-Rabin always gives
> the wrong answer, for any and all bases we try. To be acceptable for our
> application, I think we would want to verify that the candidate does not
> belong to this class before accepting the probability as reliably indicating
> that it has the security properties we desire.
Actually, that is factually wrong: there is *no* composite integer for which
Miller-Rabin will give the wrong answer for more than 1/4 of the possible
bases (or, in other words, with more than 1/4 probability if we choose the
base randomly). Reference: Handbook of Applied Cryptography, Menezes et al,
section 4.2.3 (in particular, fact 4.23)
Oh, by the way, Tero, have you tested both p and (p-1)/2 for primality
200 times using Miller-Rabin?
--
scott
Follow-Ups: