题目描述

RSA是最著名的公钥加密算法。在这种算法中,每个参与者都有一个私钥,该私钥与其他人共享,并且一个公钥被发布,以便每个人都知道它。要向该参与者发送安全消息,您可以使用广为人知的公钥加密消息;然后参与者使用他或她的私钥解密消息。以下是RSA的流程:

首先,选择两个不同的大素数$P$和$Q$,并乘以它们来获得$N(=P * Q)。$

其次,选择正整数$E(0<E<N)$作为加密密钥,使E和$T=(P-1)*(Q-1)$相对为素数。

第三,计算解密密钥$D$,使$0 <= D < T和(E * D)mod T = 1$。这里$D$是$E$,模量$T$的乘法逆。

现在公钥由对${E,N}$构建,私钥是${D,N}$。$P$和$Q$可以丢弃。

加密由$C = (M ^ E)mod N$定义,解密由$M = (C ^ D)mod N$定义,这里$M,$这是一个非负整数,小于$N$,是明文消息,$C$是生成的密文。

为了说明这个想法,让我们看看下面的例子:

我们选择$P = 37,Q = 23$,所以$N = P * Q = 851,T = 792。$如果我们选择$E = 5,D$将是$317((5 * 317)mod 792 = 1)。$公钥是${5,851}$,私钥是${317,851}$。对于给定的明文$M = 7$,我们可以得到密文$C = (7 ^ 5) mod 851 = 638。$

众所周知,要正确选择非常大的P和Q,需要数千年才能打破一把钥匙,但对于小公司来说,这是另一回事。

现在,您获得了密文$C$和公钥${E,N}$,您能找到明文M吗?

输入

输入将包含几个测试用例。每个测试用例包含三个正整数$C,E,N(0<C<N,0<E<N,0<N<2^{62})。$

输出

以单行输出明文 M。 输入数 1

638 5 851

输出数位 1

7

来源

POJ 月度,静态