0:00

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.

Â 1:36

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.

Â 2:05

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.

Â 4:32

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.

Â 5:32

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.

Â 6:30

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.

Â 7:10

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.

Â 8:25

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.

Â 10:28

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.

Â 12:51

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.

Â 13:25

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.

Â