[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: MODP groups draft concern
At 11:07 19.12.2000 -0800, Scott Fluhrer wrote:
>> 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)
Scott is absolutely right, and the proof of this fact can be found in,
e.g., Knuth, The Art of Computer Programming, vol.2.
Carmichael numbers "fool" only the very basic Fermat's test (when one just
checks that a^(n-1) = 1 mod n)
Alexey
References: