In secure authentication, one does not necessarily need to provide their password; they just need to prove that they know their own password. The subtle difference allows one to store just an encoded hash of a password. That way, the actual (plaintext) password is never stored, making the system more secure, as the real password is never written down and can’t be stolen, should the system be compromised...
The input file DATA5.txt will contain 5 lines, integers 0 ≤ N ≤ 1,000,000 being the hashes stored in place of the passwords.
The output file OUT5.txt will contain 5 lines, each a 4-character-long password that generates the corresponding input hash.
Assume that all passwords are four characters long and are made up of capital letters only.
A hash is calculated as follows: Given a password P, made up of four letters (a1, a2, a3, a4), each letter is turned into its ASCII value where A = 65 and Z = 90, resulting in (n1, n2, n3, n4). Let k = n1×106 + n2×104 + n3×102 + n4. Let m = n1×11 + n2×101 + n3×1009 + n4×10007. Then hash(P) = k mod m.
For example: Given a password P = “TONY”, there are four letters a1 = T, a2 = O, a3 = N, a4 = Y. Mapped to ASCII, they become n1 = 84, n2 = 79, n3 = 78, n4 = 89. Then k = 84797889. And m = 84×11 + 79×101 + 78×1009 + 89×10007 = 978228. So hash(TONY) = 84797889 % 978228 = 670281.
Note: Be aware of time constraints. Also, there are cases where multiple passwords result in the same hash. Those hashes are not a part of the test cases.
670281
603131
464132
TONY
DWTE
PASS