Design a Modulo-13 Using a 163

Introduction

Mod-arithmetic is the central mathematical concept in cryptography. Almost any cipher from the Caesar Cipher to the RSA Cipher use it. Thus, I will show you here how to perform Mod addition, Mod subtraction, Mod multiplication, Mod Division and Mod Exponentiation. It is a very easy concept to understand as you will see. Use this page as a reference page and open it whenever you encounter any mod-calculations or mod-terminology that leave questions behind. So let's start:

What is meant by Mod, Modulus and Modular Arithmetic?

�Modulus� (abbreviated as "mod") is the Latin word for �remainder, residue� or more in �what is left after parts of the whole are taken�. Thus, "modular" or "mod arithmetic" is really "remainder arithmetic". More precise: We are looking for the integer that occurs as a remainder (or the "left-over") when one integers is divided by another integer. Let's do three examples:

Example 1:
When 7 is divided by 3 it leaves a remainder of 1. Think of $1 as a left over after $7 are equally split among 3 people. Surely, there is a mathematical notation for mod arithmetic: Instead of writing 7 = 3*2 + 1 where 1 is the integer remainder we will write:

                                  7 mod 3 = 1

which reads as: "7 modulo 3 is 1" and 3 is called the "modulus".
Sure, this notation does not reveal the $2 that every person gets as his share. True, however, we are solely interested in the left over part, the remainder of $1 in our example.

Example 2:
When 8 is divided by 3 it leaves a remainder of 2. Thus, we write:
8 mod 3 = 2.

Example 3:
When 9 is divided by 3 it leaves no remainder. Thus, we write:
9 mod 3 = 0.

Figure 1: Arithmetic MOD 3 can be performed on a clock with 3 different times: 0, 1 and 2.

Computations involving the modulus to determine remainders are called �Modular Arithmetic�. It was first studied by the German Mathematician Karl Friedrich Gauss (1777-1855) in 1801. You may have heard this anecdote about Gauss when he went to school: His Mathematics teacher tried to keep the bored genius busy, so he asked him to add up the first 100 integers hoping that he would keep him quiet for a little while. However, young Karl promptly responded �5050 and the formula for the sum of the first n integers is n*(n+1) / 2�. Do you know why?

Great, we have the principle of Mod Arithmetic straight: To find the remainder simply divide the larger integer by the smaller integer. This surely works for large numbers as well: I.e.  365 MOD 7 = 1 (since 365 = 52*7 +1) .

What is the usage of Mod arithmetic?
365 MOD 7 = 1 tells us that if Christmas will fall on Thursday and we don't have a leap year it will fall on a Friday next year. The same for your birthday and any other day as well: every week day will fall on the following weekday the next year. Notice again that we only care about the remainder 1 and not the completed 52 weeks in a year. In fact if a year would consist of only 358 or 351 or 15 or 8 days, we would still have the same "shift by 1" effect. Apparently, solely the length of each week (called the modulus) determines the "shift by 1". What does 366 MOD 7 = 2 explain for leap years?

Shift by 2 days.

---

Congruent numbers

Integers that leave the same remainder when divided by the modulus m are somehow similar, however, not identical. Such numbers are called "congruent" .  For instance, 1 and 13 and 25 and 37 are congruent mod 12 since they all leave the same remainder when divided by 12. We write this as 1 = 13 = 25 = 37 mod 12. However, they are not congruent mod 13. Why not? Yield a different remainder when  divided by 13.

Find 5 numbers that are congruent to
1) 7 mod 5    2,12,17,-3,-10
2) 7 mod 25    32,57,82,-18,-43
3) 17 mod 25. 42,67,92,-8,-33

Modular Arithmetic is also called Clock Arithmetic

The classical example for mod arithmetic is clock arithmetic:
Look at the 12-hour clock in your room. You see 12 numbers on the clock. Here, the modulus is 12 with the twelve remainders 0,1,2,..11. So, when you give the time you actually give a remainder between 0 and 11. Again, the modulus m=12 is in charge of these reminders. What time is it 50 hours after midnight? It is 2 (a.m.) since 50 hours equal 2 full days and 2 hours.

Reduce the following:

1) 40 mod 12 4
2) 50 mod 12      2
3) 50 mod 24 2
4) 40 mod 24 16
5) 100 mod 33 1
6) 1000 mod 33 10

---

In Modular Arithmetic, we add, subtract, multiply, divide and exponentiate as follows:

A) Mod Addition

Let's start simple: What time is it 10 hours after 11:00? It is 11+10 = 21 o'clock, and 21 minus the modulus 12 leaves a remainder of 9, thus 9 o'clock.  What time is it 22 hours after 11:00? It is 11+22 = 33 and subtracting the modulus 12 repeatedly (which is also called "dividing") yields again 9. Ignoring a.m. and p.m., we are performing mod arithmetic on the clock. Let's write the two examples in mod notation: 11+10 = 21 mod 12 = 9  and 11 +  22 = 33 mod 12 = 9.

How to perform Mod Addition:
First add the two numbers,
Secondly, divide the sum by the modulus to compute the remainder.

In "8-hour-land" where a day lasts only 8 hours, we would add 12 and 9 as follows:
First, 12+9 = 21,
secondly 21 divided by the modulus 8 leaves a remainder of 5 since 21=2*8+5.
How many different remainders does  "8-hour-land" have?
Click here for a modular clock.

---

B) Mod Subtraction

Subtraction is performed in a similar fashion:
First subtract,
secondly compute the remainder.

Example 1: 25 - 8  = 17 MOD 12 = 5
Example 2: 50 - 11 = 39 MOD 12 = 3

What if we obtain a negative answer? Say it is 2 o'clock in New York, what time is it in L.A.? Turning the hand on a clock 3 hours backwards shows that it is 11 o'clock:  2 - 3  = -1 MOD 12 = 11
Thus, if the answer is negative, add the modulus you get a positive number. That number must be between 0 and the modulus.
Example 3: 3 - 50 = -47 MOD 12 = 1 since - 1 + 12 =11.
Example 4: 14 - 77  = -63 MOD 12 = 9  since -63 + 12 + 12 + 12 + 12 + 12 + 12 = 9.
Example 5: 50 - 11 = -39 MOD 15 = 6 since -39 + 15 + 15 + 15 = 6

---

C) Mod Multiplication

Since multiplication of positive numbers is repeated addition it can be reduced to the above mod addition.
How do we compute 5 * 8 MOD 12?
First we multiply:  5 * 8 = 40
secondly we find the remainder: 40 MOD 12 = 4.

A useful shortcut:
A mod expert would find the answer to 123 * 62 mod 12 immediately. It is 6. How does she know? Without being a Gauss genius, she computes 123 mod 12 = 3 and 62 mod 12 = 2 and multiplies those two answers. To verify this: 123*62 mod 12 = 7626 mod 12 = 6. This computation aid is true for addition and subtraction as well. Therefore, we may write them as:

3 Computation Rules for Mod Arithmetic

1) a + b mod m = (a mod m) + (b mod m)

2) a - b mod m = (a mod m) - (b mod m)

3) a * b mod m = (a mod m) * (b mod m)

Compute the following:

1) 73 + 58 = x mod 12 11
2) 1411 - 285 = x mod 141 139
3) 74 * 93 = x mod 13 5
4) 33 * 266 = x mod 26 16
5) 2590 * 5253= x mod 26 16
6) 133 * 5202 = x mod 26 6

---

D) Mod Division

Division is the inverse operation of multiplication. This means that every division question can be answered by answering a "find the missing number" multiplication question.

I.e. Since 5*8 = 4 MOD 12 dividing by 5 yields

              8 = 4/5 MOD 12.

Thus, if I had asked you: Compute 4/5 MOD 12,
the answer is apparently 8.

Example 1:
To compute     5 / 7 mod 12, we introduce an x

                x = 5 / 7 mod 12  to multiply both sides by 7.

7x = 5 mod 12.

We find x by testing the 12 different remainders 0, 1, ...11.

Trial and error yields x=11 since
7 * 11 mod 12 = 77 mod 12 = 5.

Do these problems:

1) 7 / 5 = x mod 12

11
2) 7 / 11 = x mod 12 5
3) 29 / 7 = x mod 12 11
4) x * 7 = 8 mod 12 8
5) 7 * x = 9 mod 12 3
6) x * 7 = 5 mod 12 11

A Better Division Method

If the modulus is small as above, trial and error will find the answer. But what if the modulus is large, i.e.

x * 8 = 19 mod 131 ?

Testing each remainder would take a long time. Surely, we could have a computer do the testing for us, and we would confirm the found answer by performing the Mod multiplication. Luckily, all this is not necessary as there exists a straightforward method to perform Mod Division:

To divide i.e. 5 by 7 mod 12, we first rewrite it as we did above by  multiplying both sides by 7:  x * 7 = 5 mod 12
To isolate x, we simply multiply both sides by the inverse of 7 mod 12, which is by chance 7 itself since 7 * 7 mod 12 = 49 mod 12 = 1. Now, we multiply both sides by 7 which yields x on the left and 7 * 5 mod 12 = 35 mod 12 = 11 on the right. Therefore,
x = 11 mod 12 or 5/7 = 11 mod 12. Done we are.

Looking back at this method, the only tricky part is how to find the inverse. If we had to do trial and error, we would not gain anything in comparison to our previous method. It is the extended version of the Euclidean Algorithm that allows us to find the inverse mod m in an efficient manner. Click here for an explanation of the Extended Euclidean Algorithm.

I also created a Javascript-demonstration of the Extended Euclidean Algorithm here which allows you to understand the mechanics involved quickly.

Of course, you don't have to practice this Algorithm, a computer will do this for us. You do the trial and error method to find multiplicative inverses. Afterwards, check your answers here:

1)  5 mod 12 5
2)  5 mod 11 9
3)  5 mod 13 8
4)  7 mod 26 15
5)  11 mod 26 19
6)  15 mod 26 7

Try to solve the following 4 challenging problems. Hint: Let a be 2, 3, 4, etc., compute the inverse a^-1 in each case and find a pattern.

7)  Find a^-1 mod 2a-1. 2
8)  Find a^-1 mod 2a+1. 2a -1
9)  Find a^-1 mod a²-1.  a
10) Find a^-1 mod a²+1. a²+1-a

Using the found inverses, now perform the following Mod divisions yourself. First rewrite the equations as we did in example 1, then compute.

11) 7 / 5 = x mod 12 11
12) 7 / 5 = x mod 11 8
13) 7 / 5 = x mod 13 4
14) 3 / 7 = x mod 26 19
15) 9 / 11 = x mod 26 15
16) 11 / 15 = x mod 26 25

Some Mod Divisions have no Solution

Unlike the division of real numbers, mod division does not always yield an answer. The reason for that is that the mod-multiplication does not always yield all possible remainders less than the modulus. Let's investigate this fact. For example:

Using a modulus of m=6, we set up a multiplication table that displays the multiplications of the remainders 0,1,2,3,4 and 5.

* mod 6	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	1	2	3	4	5
2	0	2	4	0	2	4
3	0	3	0	3	0	3
4	0	4	2	0	4	2
5	0	5	4	3	2	1

Two Observations:

1) Some divisions have no answer
The rows created by the remainders 0,2,3,4 do not contain all six remainders. Consequently, some divisions have no answer. I.e. consider division by 2:
4 / 2 = 2 mod 6   since 2 * 2 = 4 mod 6.
2 / 2 = 1 mod 6   since 1 * 2 = 2 mod 6.
However, 3 / 2 = x mod 6 has no answer x since there exists no remainder x such that 2 * x yields 3 mod 6.
Also, 5 / 2 mod 6 has no answer. Why not? In fact no odd integer could possibly be divided by 2 mod. If, however, we use a modulus of 7 any odd (and any even) integer less than 7 can be divided by 2. Explain why by using the multiplication for mod 7 below.

2) Some divisions have many answers
I.e. 4 / 2 = 2 mod 6
since 2 * 2 = 4 mod 6,

also 4 / 2 = 5 mod 6
since 2 * 5 = 4 mod 6.

Even seemingly odd divisions like 0/3 or even worse 0/0 are legal mod 6. Both have the answer 2. Explain this.
If we don't limit us to the six remainders as answers, we actually find an infinite number of answers. Notice that also 2*8, 2*11, 2*14, 2*17, ... yield 4 mod 6. Consequently, when dividing 4 by 2 mod 6   8,11,14,17,...are correct answers as well. Thus, don't be surprised if your partner finds a different answer than you. It might be just as correct as yours.
Exercise: Give five answers to 3 / 3 mod 6. Is the obvious answer "1" correct?

Exercise 1:
Create mod multiplication table using modulus 6,7,8 on paper. Afterwards, verify their correctness by creating these tables at the right.

Exercise 2:
For encryption purposes, we prefer to have unique answers. By choosing the modulus in a certain way, can we assure unique answers? How shall we choose the modulus? Come up with a guess why division by 1 and 5 yields unique answers mod 6 (when restricting us to the six remainders 0,1,2,3,4 and 5). Observe from your tables created in exercise 1 the following facts:
a) Division by 1,3,5 and 7 yields unique answers mod 8, b) division by 1,2,4,5,7 and 8 yields unique answers mod 9,
c) division by 1,2,3,4,5 and 6 yields unique answers mod 7.
Before you continue reading write down your guess when mod division yields unique answers and when not.

Answer: If the number we are dividing by is relative prime to the modulus (that means their only common divisor is 1) the divisions yield unique answers. Consequently, if the modulus is a prime number (hence all integers less than the prime number are relative prime) all divisions yield unique answers.

Example:
If the modulus is m=7, the divisions yield unique solutions.

* mod 7	0	1	2	3	4	5	6
0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6
2	0	2	4	6	1	3	5
3	0	3	6	2	5	1	4
4	0	4	1	5	2	6	3
5	0	5	3	1	6	4	2
6	0	6	5	4	3	2	1

Perform the following divisions. Which one has multiple answers between 0 and the modulus? Find them if they exist. Which division has a unique answer? Which division has no answer?

1) 7 / 4 = x mod 12       (or 7 = 4*x mod 12) No answer.
2) 6 / 9 = x mod 12       (or 6 = 9*x mod 12) x=2.
3) 7 / 5 = x mod 13       (or 7 = 5*x mod 13) x=4.
4) 3 / 13 = x mod 26     (or 3 = 13*x mod 26) No answer.
5) 4 / 10 = x mod 26     (or 4 = 10*x mod 26) x=3.
6) 12 / 10 = x mod 29   (or 12 = 10*x mod 29) x=7.

---

E)  Mod Exponentiation

In the encryption process of the RSA Cipher the plain message is raised to the power of e mod m, where e and m (commonly a 200 digit number) make up the public key. To account for huge numbers, one of our goals in this section is to learn some shortcuts when performing mod exponentiation.
Since mod exponentiation is repeated multiplication,  it can be reduced to the above mod multiplication.
How do we compute 3⁴ MOD 12?
First we multiply:  3 * 3 * 3 * 3 = 81,
secondly we find the remainder: 81 mod 12 = 9.

Compute the following:

1) 4³ mod 12 4
2) 4⁴ mod 12 4
3) 5³ mod 12 5
4) 2⁷ mod 20 8
5) 11⁵ mod 10 1

Don't worry if you did not get the last one. However, if you did get 1, congratulations. You figured out already the shortcut that can be used to compute large powers. To compute 115 mod 10, we compute (11 mod 10) = 1 and multiply that answer 5 times by itself which yields the answer 1. Using this shortcut, the answer to 125 mod 10 is 2 since 12 mod 10 = 2 and 25 mod 10 = 32 mod 10 = 2.

Shortcut 1: Instead of first computing the (large) power and secondly finding the remainder, it is easier to find the remainders of smaller powers and mod multiply them to get the final answer.

Compute the following:

1) 14³ mod 12 8
2) 24⁴ mod 12 0
3) 37¹⁶ mod 12 1
4) 82⁷ mod 20 8
5) 163⁵ mod 10 3

There is a fast way to compute 2377 mod 24 . Since 23 = -1 mod 24, we may write (-1)77 mod 24 which simplifies to -1 mod 24. To get a positive answer, we add 24 to get 23 as the final answer.

Shortcut 2: If the base is a little less than the modulus, then rewrite the base as a small negative number which when exponentiated yields a smaller answer then the original power.

Compute the following:

1) 11³ mod 12 11
2) 15⁴ mod 17 16
3) 54¹⁶ mod 55 1
4) 82⁷ mod 84 40
5) 16⁵ mod 19 4
6) Powers such as 1234567⁶ would yield an overflow on your calculator. However, performing modular arithmetic using the modulus m=1234569 we are able to compute the answer 64. Why?
Answer: 1234567 = -2 mod 1234569. Thus, (-2)⁶ = 64 MOD 1234569

We conclude the Mod Exponentiation with one last shortcut. There is a fast way to compute 2¹¹ mod 15. Since 2¹¹ = ((2²)²)² * 2³ , we compute 2¹¹ mod 15 as  (2⁴)² * 2³ mod 15 =((2⁴)² mod 15 ) * (2³ mod 15 ) = 1 * 8 mod 15 = 8. Check: Dividing 2048 by 15 leaves a remainder of 8. Correct.

Shortcut 3: (Repeated Squaring) To compute aⁿ, divide the exponent n by the greatest power of 2 that is less than n. This yields an exponent e and a remainder r. Finally, compute a^e * a^r. To compute a^e, use shortcuts if necessary. a^r is a fairly small number.

Compute the following:

1) 3¹¹ mod 12   3. Since 3² = 9, 3⁴=(9)² = 81 = 9 mod 12. Also: 3⁸=(3⁴)²=(9)² = 81 = 9 mod 12. Since, 3³ = 27 = 3 mod 12, 3¹¹ = 3⁸ * 3³ = 9 * 3 = 27 = 3 mod 12.
2) 4¹¹ mod 12  4. Since 4² =4, 4⁴=4⁸=4. 4⁸ * 4³ = 4.
3) 4¹⁷ mod 17

4) 5¹³ mod 17 3. Since 5²=8, 5⁴ = 13 = -4, 5⁸ = 16 =-1, 5¹³ = -1 * -4 * 5 =20
5) 3³³ mod 17 3. Since 3² = 9, 3⁴ = -4, 3⁸ = -1, 3¹⁶ =1, 3³² = 1
6) 16⁵ mod 19 4. Since 16 = -3, 16² = 9, 16⁴ = 81 = 5.

A computation challenge:

7) 2¹³⁰ mod 17 4. Since 2⁴ =-1, 2⁸=2¹⁶=...=2¹²⁸ =1.
8) 2²⁶⁹ mod 19 10. Since 2⁴ = -3, 2⁸ =9, 2¹⁶ = 5,...
9) 3³³³ mod 15 3. Since 3⁵ = 3, ...

Design a Modulo-13 Using a 163

Source: https://www.ti89.com/cryptotut/mod_arithmetic.htm

Share this post