Bare Bones Cryptography Part I: Modular Arithmetic

Welcome to my blog!

This is the first of a beginner-friendly multipart series teaching the both mathematical and programmatic fundamentals behind the vast field that is cryptography. In this first lecture, we will go over the basic mathematics needed for cryptography, namely modular arithmetic and the notion of groups and residue classes.

Modular Arithmetic

Think about the way that we normally perform addition over the integers (those are your basic numbers that you think of when you count 1,2,3, plus the negatives of those numbers, including 0). When we add two integers together, we get... another integer. If we add 1 and 2, then we get 3, which is also a member in the set of integers. Similarly if we add 1 and -5, we get -4, which is also an integer. Because of this property of the integers when considering addition, we state that the integers are closed under addition. Visually, you can kind of think about this as going around along a "path" of integers: think about starting at one of the integers and each step as adding an integer to that one:. For example, if we start at 3 and take 4 steps, we end up at 7. Adding a negative element in this case will be like going backwards, in which case going backwards 4 steps from 3 lands us at -1.

However, no matter how many steps we add, we will never go past this straight path of integers, since taking steps always keeps us in line of integers. Thus, we can consider this something of a "closed path" we are treading on, which is why we refer to this set as "closed". Now, what if instead of a path, we consider a circle, or a ring? In this case, let's say that we have the integers from 1 up to 12, and we arrange them all in a circle such that after we reach 12, we cycle back over to 1. The end result should look like something very familiar...

time for you to study math again! >:)

We have a set of integers in a similar fashion to that in a clock! But this seems even more closed. When we add two numbers here together, we end up with another element in the clock, because the integers tend to "wrap back around" once a multiple of 12 is reached. So we end up going around a cycle of 12 integers. The set of these 12 integers are known as the cyclic group of order 12. In LaTeX, we represent this as a sort of stylized "Z" (representing the integers) with a subscript of "12" attached to it, saying that these first 12 integers cycle back everytime the value of 12 is reached:

In code throughout this mini-course, we will represent this as ZZ_12. Let's take a look at one of these elements, say [5]. This is achieved by starting at 12 and going clockwise by 5 steps. What happens though if we instead consider [17]? In this case, we take 17 steps from that start at 12. If we do so, then after 12 steps, then we will end up back where we started. However, because there are 17-12 = 5 steps left to take, we simply take 5 steps again clockwise and end up at the right spot. So therefore, [17] and [5] are equivalent elements-- they describe the same thing. Thus, we normally count 17 as part of the residue class [5]. This works for anything of the form 12n+5 where n is an integer. By convention, the residue class [l] of the set ZZ_k represents the collection/partition of all the integers that can be represented as the form kn + l for any integer n. In other words, this is the collection of all the integers that have a remainder of l when divided by k, and the notion of this is so important to both Cryptography and Number Theory, that we give this an entirely different name: we say that any number in the residue class [l] is equivalent to

or "l modulo k". For now, you can consider the residue class [l]∈ZZ_k and the above notation equivalent statements.

The residue class [12] that is a part of this set represents all of the integer multiples of 12; that is, numbers like 12,24,48, and so on. However, one number that technically fits this description would be 0, because any number could divide 0. Thus, we normally have the convention of representing the residue class [12] as the class [0] instead. So ZZ_12 represents the set of residue classes {[0], [1], [2], ..., [11]}

There are many properties of the modulo operator that we have below, that we will use throughout the course:

• If a == b (mod n) and b == c (mod n) then a == c (mod n)
• a == a (mod n)
• a == b (mod n) implies that b == a (mod n)
• if a == b (mod n) then a**k == b**k (mod n) for any natural number k (a**k represents a to the power of k)
• if a == b (mod n) then a*k == b*k (mod n) for any integer k while the converse is not necessarily true
• if a == b (mod n) and c == d (mod n) then:
  • a + c == b + d (mod n)
  • ac == bd (mod n)

We will be using these properties quite extensively in the future, so it's good to read up on these. I highly suggest the following textbook for further reading:

• Number Theory Through Inquiry (David Marshall, Edward Odell, and Michael Starbird)
• Elementary Number Theory (College notes; start from chapter 12 onwards)

Next lecture, we will be going over more rigorous applications of modular arithmetic to primality tests and algebraic properties of residue classes in order to begin studying the very basics of cryptography. Stay tuned!