language-agnostic - c、e、nがわかっている場合、c = m^e（mod n）でmを見つける方法

Question

Java BigInteger c、e、および n を知っているとします。BigInteger m をすばやく計算する方法はありますか。

c = m^e (mod n)

Answer 1

そうですね... 数 "d" を次のように決定したとします。

d*e=1  (mod phi(n))

ここで、phi(n) は、n に対して互いに素な数のセットのサイズです。たとえば、p と q が素数である n=pq の場合、phi(n)=(p-1)*(q-1) となります。

それで

m=c^d (mod n)

「d」をまだ知らない場合、一般的にその関数を逆にするのはかなり難しいと思います。幸運を。