using System;

using System.Numerics;

public class Program

{

    public static void Main()

    {

        /*

        公钥与私钥的产生：

        (1)进行加密之前，首先找出2个不同的大质数p和q

​

        (2)计算n=p*q

​

        (3)根据欧拉函数，求得φ(n)=φ(p)φ(q)=(p−1)(q−1)

​

        (4)找出一个公钥e，e要满足: 1<e<φ(n) 的整数，且使e和φ(N)互质。

​

        (5)根据e*d除以φ(n)余数为1，找到私钥d。

​

        (6)所以,公钥就是(n,e) 私钥就是(n,d)

​

*/

        var p =  BigInteger.Parse("3487583947589437589237958723892346254777");

        var q =  BigInteger.Parse("8767867843568934765983476584376578389");

        var e = 65537   ;

        var phi = (p-1)*(q-1) ;

        Console.WriteLine("phi(n) = "+phi);

        //(5)根据e*d除以φ(n)余数为1，找到私钥d。

        //var d = gmpy2.invert(e,phi);

        BigInteger d;

        int i = 1;

        while(true){

            var sum = (phi*i-1);

        var mod = (sum)%e;

            if(mod ==0){

            d = sum/e;

                break;

            }

            i++;

        }

        Console.WriteLine(" i = "+i);

        Console.WriteLine(" d = "+d);

        /*

        2. 消息加密:

​

m^e除以n求余数即为c(密文)

        */

        /*

        3. 消息解密:

​

c^d除以n求余数即为m(明文)

        */

    }

}