CRYPTO1 - The Bytelandian Cryptographer (Act I)
The infamous Bytelandian Bit-eating Fanatic Organisation (BBFO for short) plans to launch an all-out denial-of-service attack on the Bytelandian McDecimal's fast food network by blocking the entrance to every restaurant with a camel (the purpose being to rid the Organisation of unhealthy competition, obviously). In a sly and perfidious move, the head cryptographer of BBFO decided to disclose the date and time of the planned attack to the management of McDecimal's, but in encrypted form (ha ha). He calculated the number of seconds from midnight 1970.01.01 GMT to the moment of attack, squared it, divided it by 4000000007 and sent the remainder by e-mail to McDecimal's. This made the original date impossible to decode.
Or did it?
You work as the head algorthimist at McDecimal's HQ and know nothing of what is happening in Byteland. Things are not going well. You are playing a quiet game of hearts against your computer and wondering why on earth Management are considering making you redundant. Suddenly, the CEO bursts into your office, saying:
- Look here, young man[lady]! I have this number and those guys claim it is supposed to be some date. I am giving you one second to tell me what it all means!
I am afraid you have no choice. You can't ask any further
You just have to answer, now.
The encrypted timestamp.
The decrypted GMT time and date of attack, somewhere between 1970 and 2030, using standard 26 character formatting.
Sun Jun 13 16:20:39 2004
Please check your answer on submission, do not rely on the given example in this problem
this problem is specialized case of other well known problem for which there is no efficient deterministic algorithm exists. good luck.
Even if your answer is Sun Jun 13 21:50:39 2004, it gets AC. Turns out in this case there are two solutions.
Use Fermat's Little Theorem but with some manipulation . Try to relate quadratic residues with the theorem.
took me 5 hours to solve this.. But happy :)
elliptic curve cryptography, there you go!!
The total offset between 1970 and 2030 is 1893456000 seconds. Why in the world is he dividing the result by 4000000007? If x<y, x mod y = x. So I did time.asctime(time.localtime(<timestamp>)). WRONG!Last edit: 2016-06-05 16:37:34
four WA for changing code due to strftime displaying wrong output as Sun Jun 13 21:50:39 2004 instead of Sun Jun 13 16:20:39 2004 but got AC when submitted the code for 1st output without any changes in spoj. Its weird how there are differences in output of same code between my compiler and spoj.
Be aware of format of time and avoid spelling mistakes of (Thu, Sep ,..etc)..that costed me 2 WALast edit: 2016-01-13 18:12:51