Sphere Online Judge

SPOJ Problem Set (classical)

17. The Bytelandian Cryptographer (Act I)

Problem code: CRYPTO1

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 questions.
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

Added by:Adrian Kosowski
Time limit:1s
Source limit:10000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: NODEJS PERL 6

hide comments
2014-08-25 02:57:56 Gonzalo Ciruelos
I submitted a solution in haskell and it fails to compile because the system lacks "Data.Time.Format", can somebody tell me how to proceed?

Last edit: 2014-08-25 02:58:18
2014-03-01 20:10:44 Dorijan Cirkveni
Do I have to write e.g. 00:02:05?
Or is 0:2:5 good?
2013-06-17 18:25:36 Tanmay Kulshrestha
for the given output, the input should be 1749870178.What is wrong????
2013-04-12 07:42:14 Rahul
there are two soln to above problem 1087143639 and 2912856368. First one gives the output as Sun Jun 13 21:50:39 2004

Last edit: 2013-04-12 09:01:44
2012-04-03 19:04:12 Ikhaduri
How is it even possible to solve this with TEXT??????
2011-05-27 15:22:47 simon
I guess the answer is expected to be integer
2011-05-26 06:52:49 Santiago Palacio
if there are multiple answers, how would we know which use? beacouse for the same number the answers could be, int theory, infinite.
2011-02-25 03:30:21 George Bezerra [UnB]
@Nagoorkani A: x would be 1087143639 and not 1087136439 as you stated. f(x) given by the example is correct.
2011-02-12 14:35:35 Nagoorkani A
encryption seems to be f(x) = x^2 mod p
the output of the example is Sun Jun 13 16:20:39 2004, which lets x be 1087136439, but then f(x) would be 2933335865 and not 1749870067 as indicated by the input!
2011-02-04 08:51:15 Scott Nicholas
4000000007 is prime, so i guess trying to factor out some trials isn't going to help. thus, i'm stuck at brute-force. i'll have to come back to this one when it's earlier in the day. :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.