SPOJ CRYPTO1

From Algorithmist
Jump to navigation Jump to search

17 - The Bytelandian Cryptographer (Act I)[edit]

Summary[edit]

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.

Explanation[edit]

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.

Gotchas[edit]

  • If you are using your programming language's date feature, make sure to take care of time-zones.

Implementation[edit]

You can use the string "%a %b %d %T %Y" for the "strftime" function.

Input[edit]

1749870067

Output[edit]

Sun Jun 13 16:20:39 2004

References[edit]

  1. http://mathworld.wolfram.com/QuadraticResidue.html
  2. http://www.spoj.pl/forum/viewtopic.php?f=3&t=3081#p3351
  3. http://vikhyat.net/articles/remainder_when_dividing_large_numbers/