RSA算法是现在使用最广泛的非对称加密算法，比如 HTTPS 加密连接、苹果的APP签名就使用了RSA。非对称加密算法的主要优势就是使用两个而不是一个密钥值：一个密钥值用来加密消息，另一个密钥值用来解密消息。这两个密钥值在同一个过程中生成，称为密钥对。用来加密消息的密钥称为公钥，用来解密消息的密钥称为私钥。用公钥加密的消息只能用与之对应的私钥来解密，私钥除了持有者外无人知道，而公钥却可通过非安全管道来发送或在目录中发布。比如区块链加密虚拟货币比如比特币就是基于非对称加密算法，公钥为钱包地址，私钥为钱包密码。

RSA算法主要有以下几个步骤：

1. 随机选择两个质数 p,q

2. 令 n = p * q，由欧拉公式 计算与 n 互质的整数的个数

3. 取 且 e 与 互质 。( n , e ) 作为公钥对，工业环境中 e 取65537

4. 令 ，计算 d 。( n , d ) 作为私钥对。 计算 d 可以利用扩展欧几里得算法进行计算，注意 d 为正整数才有效

公钥用来加密，私钥用来解密

加密：

解密：

现在给出一对 p,q 的值， 你需要根据这一对质数计算出公钥和私钥，e 取 65537，并对给出的数字加密。

为了题目简单合理，这里的 p 和 q 都是大于1000小于10000的正质数，在实际运用中这两个数至少有1024位。

前两行分别给出 p 和 q
下一行给出需要加密的数字m，m为小于50000000的正整数

第一行为计算出来的 d 的值
第二行为对m加密后的结果

7477
7481
20200202

46071233
30986104

n = 55935437，，d = 46071233，

d 实际情况有多个可能值，这里求的 d 为满足条件的最小正整数