[Next] [Up/Previous] [Index]

Some Modulus Arithmetic

Modular arithmetic is something you may remember from your schooldays, if you were taught using what was once called the 'New Math'. However, it may be worthwhile to review it a little here.

Here are addition, multiplication, and exponentiation tables modulo 7:

 + | 0 1 2 3 4 5 6   * | 0 1 2 3 4 5 6
------------------- -------------------  ^ | 0 1 2 3 4 5 6
 0 | 0 1 2 3 4 5 6   0 | 0 0 0 0 0 0 0  -------------------
 1 | 1 2 3 4 5 6 0   1 | 0 1 2 3 4 5 6   1 | 1 1 1 1 1 1 1
 2 | 2 3 4 5 6 0 1   2 | 0 2 4 6 1 3 5   2 | 1 2 4 1 2 4 1
 3 | 3 4 5 6 0 1 2   3 | 0 3 6 2 5 1 4   3 | 1 3 2 6 4 5 1
 4 | 4 5 6 0 1 2 3   4 | 0 4 1 5 2 6 3   4 | 1 4 2 1 4 2 1
 5 | 5 6 0 1 2 3 4   5 | 0 5 3 1 6 4 2   5 | 1 5 4 6 2 3 1
 6 | 6 0 1 2 3 4 5   6 | 0 6 5 4 3 2 1   6 | 1 6 1 6 1 6 1

If you remove the row and column from the multiplication table that are filled with zeroes, the six numbers in each row and column are all different. And, because of that, for every number from 1 to 6, some number from 1 to 6 will, when multiplied by that number, give 1. This is not always true in modular arithmetic: it is true here because 7, the modulus, is a prime number.

The exponentiation table repeats when you get to 6 as an exponent. For exponentiation, if the base is a number modulo 7, the exponent has to be thought of as being modulo 6!

This is true, in general, for all prime bases. What about a base that isn't prime?

If you know the remainder after a number is divided both by 5 and by 7, you can determine (because 5 and 7 are relatively prime, having no common factors) the remainder after that same number is divided by 35. So the properties of arithmetic modulo 35 are in a way a combination of those of arithmetic modulo 5 and modulo 7. Therefore, instead of the exponent being modulo 34, it is modulo 24: exponents for modulo 5 arithmetic are modulo 4, and exponents for modulo 7 arithmetic are modulo 6, and so exponents for modulo 35 arithmetic are modulo 4 times 6, or 24.

This explains (well, okay, only a little bit) the role of the number (p-1)(q-1) in the RSA public-key method.

Now, here's what an exponentiation table modulo 55 looks like:

  ^ |  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21
---------------------------------------------------------------------
  1 |  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
  2 |  2  4  8 16 32  9 18 36 17 34 13 26 52 49 43 31  7 14 28  1  2
  3 |  3  9 27 26 23 14 42 16 48 34 47 31 38  4 12 36 53 49 37  1  3
  4 |  4 16  9 36 34 26 49 31 14  1  4 16  9 36 34 26 49 31 14  1  4
  5 |  5 25 15 20 45  5 25 15 20 45  5 25 15 20 45  5 25 15 20 45  5
  6 |  6 36 51 31 21 16 41 26 46  1  6 36 51 31 21 16 41 26 46  1  6
  7 |  7 49 13 36 32  4 28 31 52 34 18 16  2 14 43 26 17  9  8  1  7
  8 |  8  9 17 26 43 14  2 16 18 34 52 31 28  4 32 36 13 49  7  1  8
  9 |  9 26 14 16 34 31  4 36 49  1  9 26 14 16 34 31  4 36 49  1  9
 10 | 10 45 10 45 10 45 10 45 10 45 10 45 10 45 10 45 10 45 10 45 10
 11 | 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
 12 | 12 34 23  1 12 34 23  1 12 34 23  1 12 34 23  1 12 34 23  1 12
 13 | 13  4 52 16 43  9  7 36 28 34  2 26  8 49 32 31 18 14 17  1 13
 14 | 14 31 49 26 34 36  9 16  4  1 14 31 49 26 34 36  9 16  4  1 14
 15 | 15  5 20 25 45 15  5 20 25 45 15  5 20 25 45 15  5 20 25 45 15
 16 | 16 36 26 31  1 16 36 26 31  1 16 36 26 31  1 16 36 26 31  1 16
 17 | 17 14 18 31 32 49  8 26  2 34 28 36  7  9 43 16 52  4 13  1 17
 18 | 18 49  2 36 43  4 17 31  8 34  7 16 13 14 32 26 28  9 52  1 18
 19 | 19 31 39 26 54 36 24 16 29  1 19 31 39 26 54 36 24 16 29  1 19
 20 | 20 15 25  5 45 20 15 25  5 45 20 15 25  5 45 20 15 25  5 45 20
 21 | 21  1 21  1 21  1 21  1 21  1 21  1 21  1 21  1 21  1 21  1 21
 22 | 22 44 33 11 22 44 33 11 22 44 33 11 22 44 33 11 22 44 33 11 22
 23 | 23 34 12  1 23 34 12  1 23 34 12  1 23 34 12  1 23 34 12  1 23
 24 | 24 26 19 16 54 31 29 36 39  1 24 26 19 16 54 31 29 36 39  1 24
 25 | 25 20  5 15 45 25 20  5 15 45 25 20  5 15 45 25 20  5 15 45 25
 26 | 26 16 31 36  1 26 16 31 36  1 26 16 31 36  1 26 16 31 36  1 26
 27 | 27 14 48 31 12 49  3 26 42 34 38 36 37  9 23 16 47  4 53  1 27
 28 | 28 14  7 31 43 49 52 26 13 34 17 36 18  9 32 16  8  4  2  1 28
 29 | 29 16 24 36 54 26 39 31 19  1 29 16 24 36 54 26 39 31 19  1 29
 30 | 30 20 50 15 10 25 35  5 40 45 30 20 50 15 10 25 35  5 40 45 30
 31 | 31 26 36 16  1 31 26 36 16  1 31 26 36 16  1 31 26 36 16  1 31
 32 | 32 34 43  1 32 34 43  1 32 34 43  1 32 34 43  1 32 34 43  1 32
 33 | 33 44 22 11 33 44 22 11 33 44 22 11 33 44 22 11 33 44 22 11 33
 34 | 34  1 34  1 34  1 34  1 34  1 34  1 34  1 34  1 34  1 34  1 34
 35 | 35 15 30  5 10 20 40 25 50 45 35 15 30  5 10 20 40 25 50 45 35
 36 | 36 31 16 26  1 36 31 16 26  1 36 31 16 26  1 36 31 16 26  1 36
 37 | 37 49 53 36 12  4 38 31 47 34 48 16 42 14 23 26 27  9  3  1 37
 38 | 38 14 37 31 23 49 47 26 53 34 27 36 48  9 12 16  3  4 42  1 38
 39 | 39 36 29 31 54 16 19 26 24  1 39 36 29 31 54 16 19 26 24  1 39
 40 | 40  5 35 25 10 15 50 20 30 45 40  5 35 25 10 15 50 20 30 45 40
 41 | 41 31  6 26 21 36 46 16 51  1 41 31  6 26 21 36 46 16 51  1 41
 42 | 42  4  3 16 12  9 48 36 27 34 53 26 47 49 23 31 37 14 38  1 42
 43 | 43 34 32  1 43 34 32  1 43 34 32  1 43 34 32  1 43 34 32  1 43
 44 | 44 11 44 11 44 11 44 11 44 11 44 11 44 11 44 11 44 11 44 11 44
 45 | 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45
 46 | 46 26 41 16 21 31 51 36  6  1 46 26 41 16 21 31 51 36  6  1 46
 47 | 47  9 38 26 12 14 53 16 37 34  3 31 27  4 23 36 42 49 48  1 47
 48 | 48 49 42 36 23  4 27 31  3 34 37 16 53 14 12 26 38  9 47  1 48
 49 | 49 36  4 31 34 16 14 26  9  1 49 36  4 31 34 16 14 26  9  1 49
 50 | 50 25 40 20 10  5 30 15 35 45 50 25 40 20 10  5 30 15 35 45 50
 51 | 51 16 46 36 21 26  6 31 41  1 51 16 46 36 21 26  6 31 41  1 51
 52 | 52  9 28 26 32 14 13 16  7 34  8 31 17  4 43 36  2 49 18  1 52
 53 | 53  4 47 16 23  9 37 36 38 34 42 26  3 49 12 31 48 14 27  1 53
 54 | 54  1 54  1 54  1 54  1 54  1 54  1 54  1 54  1 54  1 54  1 54

Two things stand out when looking at this table.

Although the column headed 20 isn't entirely filled with ones, the column headed 21 is the same as the column headed 1; it contains the numbers from 1 to 54 in order. This means that the table repeats with a period of 20, rather than a period of (5-1)(11-1) or 40. This will always happen when p-1 and q-1 share 2 as a common factor.

Since 55 isn't a prime number, it makes sense that the numbers divisible by 5 and by 11 cannot, by repeated multiplication, yield anything not divisible by them, such as 1.

Only numbers relatively prime to (p-1)(q-1) can be used as enciphering and deciphering exponents in RSA. This excludes, in this case, everything divisible by 2 or by 5.

And here we do have valid choices for e and d. 3 and 7 are inverses. So are 13 and 17.

9, 11 and 19 are their own inverses.

Of course, the situation will improve as we move up to larger moduli. And RSA requires the use of very large moduli to be secure in any case.


[Next] [Up/Previous] [Index]

Next
Chapter Start
Table of Contents
Home Page