CRYPTO技能修正

关于前篇求模运算的修正

今天突然对模运算开窍了,这是上篇RSA总结中我对同余式的理解:

x = y (mod n) 可以看成是 x % n = y
x $\equiv$ y (mod n) 可以看成是 x % n = y % n

是错误的!!!

其实三等还是两等,都是一样的,比如,对于 $A\ \%\ N = B$,
我们可以很容易得到
$$x_1N + B = A$$
也可以是
$$x_2N + A = B$$
然后这两个式子就会给我们一个错觉推出,
$$x_1N + B = A \Longrightarrow A\ \%\ N = B\ (B = A\ (mod\ N))$$
$$x_2N + A = B \Longrightarrow B\ \%\ N = A\ (A = B\ (mod\ N))$$

看着好像没错的样子,其实错了一半!

如果我们已知 $A\ \%\ N = B$, 我们可以推出$xN + B = A$没错,但是我们不能从而得到 B % N = A,可是上面推的貌似没问题?不,有问题!

$$xN + A = B\ \ \nRightarrow \ \ B\ \%\ N = A$$
这个推导是错误的!正确的应该是
$$xN + A = B \Longrightarrow B\ \%\ N = A\ \%\ N$$

这不就是同余式么: $A \equiv B(mod\ N)$

这里暗藏了一个等式,当我们已知$A\ \%\ N = B$ 时,我们可以确定$B = B\ \%\ N$, 所以这个时候就可以从 $xN + B = A$ 推导出 $A\ \%\ N = B$, 但是A却不一定等于$A\ \%\ N$, 所以并不能得到$B\ \%\ N = A$

文章目录