RSA：爲什麼phi（phi（n））有效？

Question

顯然，獲得解密指數的另一種方法（僅使用擴展歐幾里德算法）是做d = e **（phi（phi（n）） - 1）mod（phi（n））。爲什麼這個工作？

Answer 1

RSA操作正常工作的一般要求是e*d = 1 mod X，其中X通常是(p-1)*(q-1)。

在這種情況下，X是phi(n)，e是e，和d是e^[phi(phi(n))-1] = e^[phi(X)-1]。

請注意，e*d mod X是e*e^[phi(X)-1] mod X = e^phi(X) mod X。

Euler's Theorem指出a^phi(X) = 1 mod X，對於任何a這是相對於X的質數，因此該要求成立。