RSA是一种不可逆的加密方法，不可逆的原因是公钥特别大，对它分解质因子时间上会很长，普通计算机大概是

10年左右，量子计算机一星期就可以了，基本不可能在常数时间分解出来；

1.首先我们要对n进行分解质因数

``````#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define mmset(a,b) memset(a,b,sizeof(a))
#define UI64d unsigned __int64
UI64d FastPower(UI64d a , UI64d k);
UI64d MOD = 1001733993063167141;

int main()
{
UI64d res = 1001733993063167141;
for(int i= 2; i * i < res; i++)
{
while(res % i == 0 && res != 1)
{
printf("%I64d %I64d\n",i,res / i);
res /= i;
}
}

return 0;
}``````

2.求解e

``````
def computeD(fn, d):
(x, y, r) = exGCD(fn, d)

if y < 0:
return fn + y
return y

def exGCD(a, b):

if b == 0:
return (1, 0, a)

x1 = 1
y1 = 0

x2 = 0
y2 = 1
while b != 0:
q = a / b

r = a % b
a = b
b = r

x = x1 - q*x2
x1 = x2
x2 = x

y = y1 - q*y2
y1 = y2
y2 = y
return(x1, y1, a)

p = 891234941
q = 1123984201
d = 212353

sum = (p - 1) * (q - 1)

e = computeD(sum, d)
print e
``````

e = 823816093931522017;

3.已知C,e,n,求解X = C^e mod n

X是原文。

``````MOD = 1001733993063167141
def FastPower(a,k):
res = a
ans = 1
while k != 0:
if (k % 2) != 0:
ans = (ans % MOD) * (res % MOD) % MOD
res = (res % MOD) * (res % MOD) % MOD
k = k / 2
return ans
a = 20190324
k = 823816093931522017
res = FastPower(a1,k1)
print(res)
``````