Cryptography, particularly modern cryptography, is heavily grounded in mathematics. The math involved is pretty much all integer based and falls within the number theory umbrellas of discrete mathematics and abstract algebra. There are many reasons for math emphasis, including the fact that our understanding of number theory has become quite advanced, though it is by no means complete. But perhaps the single most important reason, is that in most forms of cryptography, operations must be precise and exact. There can't be any such thing as round off error. Beyond that however, our understanding also gives us several well known and studied problems that at the present time we believe are very hard. To the point of being impossible in any practical sense for someone to solve without specific information. That specific information can then serve as a cryptographic key. In this lesson, we're going to really stick to some basics. Most will be stuff that you already know and have known since grade school. But these concepts are extremely important to us, and we will soon be using them in ways that you likely have not seen. If nothing else, this will be a good review, not only of the concepts, but also the terms that we'll be using and using in very precise ways. Plus, we need to address a few, often overlooked fine print details. We're going to look briefly at integers and their subsets. The notion of divisibility, prime and composite numbers, the fundamental theorem of arithmetic and also the notion of a greatest common divisor and what it means for numbers to be relatively prime.

The first thing we need to do is clearly define what a number is, or more precisely, what types of numbers we are going to be working with at any given time. For the most part, we're only going to be using integers and subsets of integers. So when we use the term number, let it be understood that we're talking about an integer of some sort. We may need to talk about rational numbers or even real numbers from time to time and if so, we'll make that pretty clear, either explicitly or by context.

The set of integers is traditionally given the label Z. When practical, this is usually written using what is known as a double-struck capital font. That's true for most of the labels used for sets of numbers. While a set of integers is infinite in size, it does not include a value known as infinity, either positive or negative. This is because infinity is a concept that is beyond the definition of an integer. If for no other reason, then its properties are not the same as those of just a really, really big integer. A very common subset of integers are the natural numbers, sometimes called the counting numbers. The usual symbol for this is a double struck capital N but is also often referred to as Z+, which is the more common notation in cryptography and referred to as the positive integers. This is as good a point as any to say that there's no international governing body that regulates what various number sets are, let alone the label used for them. So, while there are some pretty widespread conventions that are used, there are also some quite a few common alternatives. For instance, does the set of natural numbers include zero or not? Depends on who you're talking to. Usually it does not. And while that's how we will use it, we need to be aware that some authors do include it. What's important are not the specific definitions, but rather that they are used consistently, and the results and claims are likewise consistent with them. Other sets that we will see and use from time to time include negative integers, non-negative integers and non-positive integers. For the most part, the meanings are obvious, but this apparent obviousness itself causes miscommunication. The fine print deals with whether or not zero is included in the set and unfortunately, authors not to mention people in general, can get a bit sloppy. In particular, many people will assume that zero is included in the set of positive integers since we almost never write it with a minus sign. Others will assume it is in both the positive and negative integers, since we can write it with or without a minus sign. But these are purely notational distinctions and hardly form a sound basis for defining number sets. But humans are only human. We are often not good at distinguishing the difference between how we choose to represent a concept and the concept it represents. This is actually a very powerful survival trait, but it can get in our way from time to time. So you will need to always be on the lookout to determine what is meant in a particular context.

For our purposes, the value zero is neither positive nor negative. Which then implies that it is both non positive and nonnegative. The easiest way to keep these straight, is to dispense with the notion that positive and negative are opposites. Rather, the opposite of positive is non positive. These two sets partition the set of integers into two disjoint subsets, in which all integers are in exactly one of these two sets. Thought of this way, it becomes fairly evident which set zero has to fall within. The same is true for negative and nonnegative sets. We will usually need to be very careful about whether we should include zero or not. And should simply get in the habit of always asking ourselves explicitly, how our claims hold up when zero is considered? The next concept we need to be sure we have a handle on is the visibility. The definition is very simple, but there's a bit of fine print involved in understanding it. As you might guess, it involves zero.

Given two integers, a and b, if a divides b we write this using a vertical bar. And it means that there exists a third integer, c, such that b is the product of a and c. We can therefore say that a is a divisor of b. A divisibility sign is a predicate statement, or a claim that is either true or false, similar to a less than sign or an is equal sign. Depending on context, it can either be a question, does a divide b? Or a constraint, only if a divides b. It is not an arithmetic operator, like division or multiplication, and no operation is actually performed. Note that the sign of either number doesn't matter, since we only required that some integer exist that satisfies the defining relationship. The value of C can be positive, negative, or zero as needed. However, in most cases when we talk about the visibility, it is understood that we are only talking about strictly positive divisors.

Remember that I said we should always take a moment to ask how zero fits into things. And the answer will sometimes be not very well. First if b is zero then our definition holds for every value of a, since only needs to be zero. Thus, we conclude that zero is divisible by every integer, including zero. If we go to the other way and said a to be zero, then the only allowed value of b is zero. Although, c can be anything. Thus, we conclude that the only integer that zero divides is zero. But wait, you might say, that means zero is divisible by zero. But we all know that division by zero is undefined.

Remember, divisibility is merely a statement about whether a certain defining condition holds, the notion of division is different. And division of one integer by another is defined only if it results in a unique value. A fixed finite value for c in this case. And that's not the case here. So the operation of actually dividing any integer, including zero by zero, is undefined. This is a pretty pathological case and many mathematicians choose to side step it, by simply saying that the definition of divisibility only applies to non zero divisors. But this actually causes certain properties in what are known as communitive rings, to fail. To avoid this other authors add some additional terms, such as zero divisor, to deal with it. We'll skirt this issue by just keeping in mind that regardless of what the notion of divisibility says, we can't actually divide anything by zero.

This brings us pretty naturally to the definition of a prime number.

A first cut would be to claim that a prime number is any integer that is divisible only by 1 and itself. That probably sounds familiar from your early math education. But this definition has problems, two big ones, in fact.

First, in almost all instances in which it will be useful to invoke prime numbers, we need them to be positive. When we need to make a claim involving primes and negative numbers, we can almost always do so easily with the simple extension to the claim. The second problem is that, by this definition, 1 would be a prime number and possibly even 0, depending on if we've tweaked our definition of divisibility. But this would cause a large fraction of claims to have to say things like for any prime number except 1. Thus it is far more useful and practical to explicitly exclude 1 from being a prime number. And then, on the handful occasions when we need to include it we can say something like for 1 or any prime number. So the nearly universally accepted definition of a prime number, is that it is an integer strictly greater than 1, whose only positive divisors are 1 and itself. Notice that this definition removes any and all ambiguities surrounding whether divisors can be negative or zero. They are expressly excluded from consideration. Any number greater than 1 that is not prime has by definition other factors, and is called a composite number. Here is one of the most basic fine print areas that people get tripped up on. They were likely taught that any integer is either a prime number or a composite, that it must be one or the other. But what about negative integers, or 0, or 1 itself? The definition of a composite number is limited to just the positive integers. A composite number is any positive integer that is divisible by some positive integer other than 1 and itself. Since 0 is divisible by all other integers, it would be tempting to call it a composite number. But the definition only applies to strictly positive numbers. Thus, we see that 0 and 1 are neither prime nor composite, further emphasizing that they are special cases and almost always have to be carefully dealt with accordingly, either included or excluded as appropriate.

Perhaps the strongest reason for defining a prime number to exclude 1, 0, and negative numbers, is that it lets us state an extremely powerful property of positive integers. So powerful that it's called, the fundamental theorem of arithmetic. It says that every integer greater than 1, notice the caveat, it does not apply to all integers, just those strictly greater than 1, can be written as a product of prime numbers, and this product is unique up to the ordering of the factors. If 1 were a prime number, then we could write, say, 12, in an infinite number of ways. But since 1 is not a prime number, by definition, only the first of these is possible, not counting the permutations on the ordering of the factors. Since all prime numbers are positive and strictly greater than 1, there's no way to write a prime factorization for 0, 1, or any negative integer. Hence why the definition is the way that it is. The next concept we'll consider is the notion of common divisors in general and the greatest common divisor in particular. A common divisor of the integers a and b is any integer c, such that a = c* m, and b = c * n, where m and n are some integers. Another way of saying it, is that c is an integer, such that c divides a, and c divides b. Notice that we place no restrictions, at least yet on a, b, and c as far as being positive, negative, or zero. The greatest common devisor, or gcd, is simply the common divisor that is larger than any other. The gcd is always a positive integer, and no special caveat is needed to make this the case. Since 1 is always a common divisor of two integers, and since any positive integer is larger than any non-positive integer, the gcd will always be at least 1. But what if either a or b or both happens to be zero? Can our present definition deal with it? Or is this a special case? If only one of them is zero, then the other is the greatest common divisor. However, if both of them are zero then the gcd is undefined since every integer is a common divisor and there is no greatest. So we really should say that we are talking about any two integers a and b, not both equal to zero. And this is the usual definition.

When the gcd of two integers a and b is 1, we have a situation that is so important, in so many instances, that we give it a special name. We say that a and b are relatively prime or some prefer to call them co-prime. Note that a and be may or may not be prime themselves. We only know that they don't share any prime number factors. If a and b are positive integers greater than 1 and, hence, have prime factorizations, then we know that those factorizations are disjoint, meaning they have no factors in common.

In this lesson we've looked at the definitions of integers and several subsets that we'll be using. We've also looked at the definition and some fine points regarding the notion of divisibility. We used this to carefully define what a prime number is and to use that to define the fundamental theorem of arithmetic. In some regards, most of this was to be able to define what we mean by the greatest common divisor, and the concept of two numbers being relatively prime. The concepts of prime, gcd, and relatively prime, are concepts that we will use over and over in the future lessons. We also learned that not everyone defines things the same way. Something you will need to be mindful of as you research topics on your own. Two sources might appear to be contradicting one another, but if you look carefully at their definitions, they might actually be in perfect agreement. We also saw that certain numbers, particularly zero and one, often have to be carefully considered as separate cases. At least, to determine whether or not they need to be treated as separate cases. With this foundation regarding integers, we are prepared to begin exploring modular arithmetic, which is the real work horse of modern cryptography.

Divisibility, Primes, GCD

Mathematical Foundations for Cryptography

Meet the Instructors