// Arup Guha
// 10/31/2023
// Solution to CIS 3362 Homework #6 Question #3

import java.util.*;
import java.math.BigInteger;

public class h6q3 {

	public static void main(String[] args) {
	
		// Get from homework...
		BigInteger aliceN = new BigInteger("5027378074612278683849377061501198168112765099092211588948671006054146262763926543857634165199504551");
		BigInteger aliceE = new BigInteger("57323338227899193769901534310113340374743309");
		
		BigInteger bobN = new BigInteger("4751614356616424867781976168280737158143706077825299390190036646711989408286996041120433429097816319");
		BigInteger bobE = new BigInteger("4685895394525945948602630590450251030824289205");
		
		// This is the value of q for both Alice and Bob.
		BigInteger q = aliceN.gcd(bobN);
		BigInteger qMinusOne = q.subtract(BigInteger.ONE);
		
		// We can use this to extract p for both Alice and Bob.
		BigInteger aliceP = aliceN.divide(q);
		BigInteger aPMinusOne = aliceP.subtract(BigInteger.ONE);
		BigInteger bobP = bobN.divide(q);
		BigInteger bPMinusOne = bobP.subtract(BigInteger.ONE);
		
		// Then we can get phi for both.
		BigInteger alicePhi = qMinusOne.multiply(aPMinusOne);
		BigInteger bobPhi = qMinusOne.multiply(bPMinusOne);
		
		// Now d.
		BigInteger aliceD = aliceE.modInverse(alicePhi);
		BigInteger bobD = bobE.modInverse(bobPhi);
		
		// Recover what was sent to Bob.
		BigInteger cipherToBob = new BigInteger("1046284573466962387739473944807380691612565121927521278523282411305437337626467565825335153065591711");
		BigInteger msgToBob = cipherToBob.modPow(bobD, bobN);
		System.out.println(recover(msgToBob));
		System.out.println();
		
		// Recover what was sent to Alice.
		BigInteger cipherToAlice = new BigInteger("3325523873963550704984437728904370519830678404172921362089587136490304638487650626956531260800780164");
		BigInteger msgToAlice = cipherToAlice.modPow(aliceD, aliceN);
		System.out.println(recover(msgToAlice));
	
	}
	
	public static String recover(BigInteger m) {
		
		// Calculate smallest power of 26 that is bigger than m.
		BigInteger base = new BigInteger("26");
		BigInteger pow = new BigInteger("1");
		int sz = 0;
		while (pow.compareTo(m) < 0) {
			sz++;
			pow = pow.multiply(base);
		}
		
		// Store answer here.
		char[] res = new char[sz];
		
		// Peel off each character one by one and store in string.
		for (int i=sz-1; i>=0; i--) {
			BigInteger tmp = m.mod(base);
			res[i] = (char)(tmp.intValue() + 'a');
			m = m.divide(base);
		}
		
		return new String(res);
	}
}