17 - The Bytelandian Cryptographer (Act I)
Given the result of applying a simple cryptographic function , where is the number of seconds from midnight 1970.01.01 GMT to a certain date, we need to find the original date.
An integer is called a quadratic residue modulo if it is congruent to a perfect square (mod ); i.e. if there exists an integer x such that:
When and are mutually prime, it is solvable if . It will always be or , because of Fermat's Little Theorem. When p is of the form (like 4000000007), the solutions will be and . Only one of these will fit in the given range.
- If you are using your programming language's date feature, make sure to take care of time-zones.
You can use the string "%a %b %d %T %Y" for the "strftime" function.
Sun Jun 13 16:20:39 2004