Properties of Modulus

Description of Modulus


Modulus is a mathematical operation like addition, subtraction, multiplication and division. It is closely related to division. Suppose you have two numbers, A and B. A modulus B is the remainder when you take A divided by B. Here are a few examples:

>> 9 modulus 4 = 1 (9 divided by 4 = 2 with a remainder of 1)

>> 50 modulus 10 = 0 (50 divided by 10 = 5 with a remainder of 0)

>> 13 modulus 4 = 1 (13 divided by 4 = 3 with a remainder of 1)

Programming Languages and Modulus


The modulus operator is usually represented by the "%" sign. For example:

Python:

if my_variable%2 == 0:
   print my_variable, "is even."

Java:

if (myVariable%2 == 0) {
    System.out.println(myVariable + " is even.");
}

In most programming languages, the modulus operator can start to perform slowly (or not at all) when dealing with large numbers. Since cryptography often requires the use of modulus operations with very, very large numbers, it is not sufficient to rely on the built-in programming language operator for modulus. Instead, you will need to write a method that can handle the modulus operation more efficiently for large numbers.

The Funny Looking Equals Sign, \equiv


When looking at documentation about modulus, you often see what appears to be an equals sign with 3 horizontal bars instead of 2. So, instead of this:

1 = 9 (\mbox{mod } 4)

You see this:

9 \equiv 1 (\mbox{mod }4)

The \equiv sign represents the "congruence relationship". There's actually quite a bit that is represented by this relationship, but for our cryptography course, it is safe to say that when you see a \equiv sign, simply swap the number to the left of the congruence sign with the number directly to the right of the congruence sign, and then change the sign to an equals sign*. For example:

17 \equiv 5 (\mbox{mod }6)

can be reorganized to be thought of as the following:

5 \equiv 17 \mbox{ mod } 6

Warning!

In online documentation and videos, "=" and "\equiv" are used inconsistently. The "=" is often used when congruence is actually meant. When working through documentation or explanations of algorithms that use modulus, be patient and use context to understand the author's intent.

*If you are a mathematics god, you will notice that there is much more to the congruence relationship than represented here. The part of the relationship that is important for the problems in our class is what is represented in this description.

-1, A Negative Modulus Result?


Sometimes when reading about theorems and algorithms that use modulus, the documentation describes a modulus operation that results in a "-1". This seems counterintuitive. If the modulus of two numbers is the remainder after division, how could it be negative? There are a number of different ways that we can have negative numbers with modulus, but there is one important way that we should interpret this in cryptography. Take this example:

a \equiv -1 (\mbox{mod } n)

or, said another way:

-1 \equiv a \mbox{ mod } n

What we are looking for as a result of the modulus operation is n-1. So, for example:

n-1 \equiv a \mbox{ mod } n

To give an example with negative numbers:

-1 \equiv 13 \mbox{ mod }7

In this case, the result that a computer would give from 13 mod 7 is 6. And, 6 is equal to 7 - 1.