import java.util.*;
import java.math.BigInteger;
public class rsa {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		BigInteger p,q,phi,p1,q1,e,m,m2,N,t,d = new BigInteger("0"),i = new BigInteger("1");
		
		System.out.println("Enter values for p and q");
		p = in.nextBigInteger();
		q = in.nextBigInteger();
		
		//Calculating N and phi of N
		N = p.multiply(q);
		p1 = p.subtract(BigInteger.ONE);
		q1 = q.subtract(BigInteger.ONE);
		phi = p1.multiply(q1);
		
		//Calculating cipher text
		System.out.println("At sender's end");
		System.out.println("Enter public key of recipient");
		e = in.nextBigInteger();	//Public key
		System.out.println("Enter Message");
		m = in.nextBigInteger();
		t = m.modPow(e,N);
	
		//Receiver side
		System.out.println("At Receiver's end");
		System.out.println("The received message is: " + t);
		d = e.modInverse(phi);		//Calculate private key
		m2 = t.modPow(d,N);
		System.out.println("The decrypted message is: " + m2);
	}
}

/* Output

Enter values for p and q
13
17
At sender's end
Enter public key of recipient
5
Enter Message
10
At Receiver's end
The received message is: 108
The decrypted message is: 10

*/