21 Mar
2001
21 Mar
'01
6:33 p.m.
In article <99b89r$lgd$1@abraham.cs.berkeley.edu>, Ian Goldberg <iang@cs.berkeley.edu> wrote:
If p is wrong, the result S' will be correct mod q but incorrect mod p. so S' ^ e mod q = M mod q, but S' ^ e mod p != M mod p.
Therefore GCD(S' ^ e mod n, M) = q, and we're done.
I think you meant GCD((S'^e mod n)-M, n) = q. I don't think what you said is true, since q does not necessarily divide M. - Nikita