import java.util.LinkedList;
import java.util.List;

public class Main {
    private static long powMod(long a, long n, long m) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                res = a * res % m;
            }
            a = a * a % m;
            n >>= 1;
        }
        return res;
    }

    private static long modInverse(long a, long m) {
        a = a % m;
        for (long x = 1;
             x < m;
             x++) {
            if ((a * x) % m == 1) {
                return x;
            }
        }
        return 1;
    }

    private static long randomPrimeInRange(long upperLimit) {
        for (long result = (int) (Math.random() * upperLimit); result != 0; result--) {
            if (isPrime(result)) {
                return result;
            }
        }
        return randomPrimeInRange(upperLimit);
    }

    private static boolean isPrime(long n) {
        if (n < 2) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        for (long i = 2; i < Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    private static List<Long> encryptRSA(String s, long e, long n) {
        List<Long> encrypted = new LinkedList<>();
        for (int i = 0;
             i < s.length();
             ++i) {
            encrypted.add(powMod(s.charAt(i), e, n));
        }
        return encrypted;
    }

    private static String decryptRSA(List<Long> encrypted, long d, long n) {
        StringBuilder stringBuilder = new StringBuilder();
        encrypted.forEach(c -> stringBuilder.append((char) powMod(c, d, n)));
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        long p = randomPrimeInRange(5000L);
        System.out.println("p=" + p);
        long q = randomPrimeInRange(5000L);
        System.out.println("q=" + q);
        long phi = (p - 1) * (q - 1);
        System.out.println("phi=" + phi);
        long e = randomPrimeInRange(phi);
        System.out.println("e=" + e);
        long d = modInverse(e, phi);
        System.out.println("d=" + d);
        long n = p * q;
        System.out.println("n=" + n);
        System.out.println();
        System.out.println(decryptRSA(encryptRSA("test message", e, n), d, n));

    }
}