The RSA Algorithm is an algorithm for public-key cryptography that is based on the presumed difficulty of factoring large integers. Assuming that the Public and Private Keys have already been generated, the RSA algorithm basically consists of the following two operations:
- Encryption: C = PE (mod N)
- Decryption: P = CD (mod N)
where P is a plaintext unit, C is the corresponding ciphertext unit, [E,N] is the Public Key (used for encryption above) and [D,N] is the Private Key (used for decryption).
You will be provided with a ciphertext and the public key used to generate it. Your task is to break the encryption and obtain the private key and the original message.
In case the values of the public and private keys are sufficiently large, it becomes computationally infeasable to perform the operations that you are required to do here. This is the basis for the security provided by this encryption scheme.
- The 1st line of the input consists of a single integer T, which is the number of testcases that follow.
- Each testcase consists of one line, such that the total number of lines in the input file is T+1.
- Each testcase consists of 3 integers on a single line, separated by spaces: E, N and C, as specified above.
- Corresponding to each testcase, output two integers on one line, separated by a space: D and P, as specified above.
- T <= 50, N < 105.
17 3233 2790
53 667 511
Problem Setter: Kaustubh Karkare