What Did The Ancient Chinese Teach Us About Hacking?

And so a large army met. The general asks the collected troops to arrange themselves into groups of 50. He counts that there are four troops left without a group. He then asks for groups of 60, and there are 14 left, and finally, he asks for groups of 70, and there are 24 left. The general stands up and tells the army that they are 201,554 strong. So how did the general do it?

>>> army%50
4
>>> army%60
14
>>> army%70
24
>>> print (army)
201554

The Chinese remainder theorem was first published by Chinese mathematician Sun Tzu. It determines a number x so that, when divided by some given divisors, leaves given remainders. As public key encryption typically involves this type of operation, CRT is well setup to help to crack encrypted messages. So what value will x equal in the following [Soln]:

x mod 3 = 2
x mod 5 = 3
x mod 7 = 2

The answer is 23, as 23 divided by 3 gives 21 remainder 2, 23 divided by 5 gives 4 remainder 3, and 23 divided by 7 gives 3 remainder 2.