五二小说网

手机浏览器扫描二维码访问

04 密码学 素数的秘密生活 Cryptography the Secret Life of Primes（第7页）

在依次相减的过程中，同样的数重复出现了好几次，我们可以把它们表达在一个方程里。

这样我们就得到以下几个等式：

558=396+162；

396=2×162+72；

162=2×72+18；

72=4×18.

从第二行开始到最后一行，我们可以用各个等式逐个消去中间余数。

在这个例子中，先利用倒数

第二个等式，然后是它上面的那个，我们得到：

18=162-2×72=162-2×（396-2×162）

=5×162-2×396.

最后再用第一个等式，我们可以把第一个中间余数162也消去：

5×162-2×396=5×（558-396）-2×396=

=5×558-7×396=18.

无论是对于实践还是理论，可以倒过来执行这一程序都是很重要的。

特别是在解密里，为了找出爱丽丝的解密数d，我们想要d满足de除以φ（n）余1的条件。

为了简洁，我们用一个单独的符号k来代表φ（n）。

现在就可以看出我们坚持要e和k互素的原因了。

因为如果它们的最大公因数是1，当我们对e和k执行欧几里得算法时，最终出现的余数自然是1。

倒过来执行这一算法，我们就能最终把1表示成e和k的组合。

特别地，我们会找到整数c和d，它们满足ck+de=1，或者换句话说de=1-ck。

因此de除以k会余1。

这个相对简单的过程将给出爱丽丝的解密数d：直接从方程里得出的d的值可能不在1到k的范围内；倘若不在，通过加上或减去合适的k的倍数，我们最终可以找到那个d，在给定范围内，它是唯一具有de除以k余1这个神奇性质的数。

（我们可以轻松证明d的唯一性，不过这里还是不要离题太远了。

）这便是如何计算解密数d的方法。

我们可以回到前面的例子来说明，这里p=5，q=13，于是n=pg=5×13=65。

我们有φ（n）=（p-1）（q-1）=4×12=48。

爱丽丝设定e=11，由于11与48互素，这在游戏规则所允许的范围内。

应用欧几里得算法于φ（n）=k=48和11，可得：

48=4×11+4；

11=2×4+3；

4=1×3+1.

这显示k和e的最大公因数确实是1。

将算法反转，我们得到：

1=4-3=4-（11-2×4）=3×4-11

=3（48-4×11）-11=3×48-13×11.