模运算很像我们看手表的思路。比如晚上22点再过3小时是几点呢?结果不是25点,而是1点,所以钟表就是一个模等于24的体系。我们可以任意规定模的大小,比如在模是7的体系里,2+3=5 (mod7),2+6=1 (mod7)。
乘法也一样可以用模运算,比如在模为13的体系中,11×9等于多少呢?加入不考虑模,我们知道结果等于99。可是在模等于13的表盘里没有99,所以数字的增加只能等同于不断的转圈,99相当于转了7圈后又走了8格。所以在模13的体系中,11×9=8 (mod13)。
模运算怎么就是单向函数了呢?
我们可以看看刚才的例子:11×9=8 (mod13) 这个算式,从左往右推可以推出来,而且结果是唯一的。但是从右往左呢,就相当于问你“在模等于13的体系中,什么数×9以后余数为8”。这个问题能不能逆运算呢?答案是不能。
当然,不一定模运算就一定没有乘法逆。当模比较小的时候,可以逆运算的数字比较多;但是当模大到一定程度时,就完全没有逆运算了。这是由数学决定的。
