Modular Arithmetic is fundamentally the same as normal arithmetic except that the numbers of numbers is limited. Instead of counting:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18...
we chop the sequence off at a chosen point, and loop it back. So, for modulo-7 arithmetic, we chop off at 7, and loop 7 round to 0 (so that 7=0). Therefore we count:
0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2...
This is similar to counting hours on a clock, where we count 1 to twelve, and then 13=1, 14=2 etc, up to 24=12, then 25=1, 26=2 and so on. We never get to 13 o'clock since this would equal 1 o'clock, just as in the sequence above we never reach 7 since this would equal 0.
The use of modular arithmetic in cryptography stems from the unintuitive answers that are generated by working with it. For example, using modulo-7 (mod 7) again:
3 + 6 = 2 (mod 7) (3 + 6 = 9, but 9=2 in modulo-7).
So if you were asked to find out which two consecutive numbers were multiplied to give an answer of 5 (mod 7), what would you try?
Maybe you try 2 × 3. This is 6. Too high. So go down and try 1 × 2? This is 2. Too low. In fact, you need to go up to 3 × 4. This is 12, which is 5 (mod 7). Counter-intuitive. 1 × 2 = 2 = 2 (mod 7) 2 × 3 = 6 = 6 (mod 7) 3 × 4 = 12 = 5 (mod 7) 4 × 5 = 20 = 6 (mod 7) 5 × 6 = 30 = 2 (mod 7)
So if you are given a number and asked to find the two numbers that were multiplied to make it, this becomes very hard to do if modular arithmetic is used. A similar complexity is encountered with factoring prime numbers.