## JDCC '15 Contest 5 P4 - RSA

View as PDF

Points: 12
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Reyno has invented his own encryption algorithm (called Reyno's Super Algorithm), which he uses to encrypt messages he sends to his friends. His algorithm works as follows:

1. He writes down his message. If it has an odd length, he adds a space to the end.
2. He breaks his message into pairs of characters, forming pairs in total.
3. He converts each pair into a number by multiplying the ASCII value of the first character by and adding the value of the second character.
4. He generates pseudo-random numbers .
5. He multiplies the value of the first pair by and outputs the result modulo (which is prime).
6. He repeats step for the second, third, fourth, etc. pair until he encrypts the entire message.

To generate the random numbers, he uses a linear congruential generator (which you have seen before). His generator uses the function:

Which means that to generate the random number (), he multiplies the number () by modulo . For the first number (), also known as the seed value, he picks a random number that he really likes. Reyno thinks his algorithm is unbreakable. Can you prove him wrong?

#### Input Specification

The first line of the input provides the number of test cases, . test cases follow. Each test case begins with the integer . The next line contains integers, the encrypted values of the message.

For of the cases, Reyno picks a seed value less than or equal to and only uses uppercase letters and spaces.

#### Output Specification

For each test case, output the original message. If there are multiple solutions, output the one with the smallest seed value.

#### Sample Input

3
6
9285 14187 23117 13153 39535 12859
19
11055 2553 29781 23952 11741 3298 15519 1333 12875 23540 747 19405 34018 37512 25977 36696 20201 2481 20533
9
35534 39644 22348 34428 2726 25535 33105 3555 6320

#### Sample Output

HELLO WORLD
THIS IS REYNO'S UNBREAKABLE ALGORITHM
FOUR MILK NO SUGAR

#### Explanation for Sample

In the first test case, Reyno uses a seed value of , which means the encryption works as follows:

Value Original Pair (Value) Encrypted Value
1 HE (9285) 9285
1997 LL (9804) 14187
27118 O (10144) 23117
22469 WO (11215) 13153
20504 RL (10572) 39535
17281 D (8736) 12859