Welcome to Course 2 of Introduction to Applied Cryptography. In this course, you will be introduced to basic mathematical principles and functions that form the foundation for cryptographic and cryptanalysis methods. These principles and functions will be helpful in understanding symmetric and asymmetric cryptographic methods examined in Course 3 and Course 4. These topics should prove especially useful to you if you are new to cybersecurity. It is recommended that you have a basic knowledge of computer science and basic math skills such as algebra and probability.
Divisibility, Primes, GCD
Loading...
Del curso dictado por University of Colorado System
Mathematical Foundations for Cryptography
46 calificaciones
University of Colorado System
46 calificaciones
Curso 2 de 4 en SpecializationIntroduction to Applied Cryptography
De la lección
Integer Foundations
Building upon the foundation of cryptography, this module focuses on the mathematical foundation including the use of prime numbers, modular arithmetic, understanding multiplicative inverses, and extending the Euclidean Algorithm. After completing this module you will be able to understand some of the fundamental math requirement used in cryptographic algorithms. You will also have a working knowledge of some of their applications.
Conoce a los instructores
William BahnLecturer
Computer Science
Richard WhiteAssistant Research Professor
Computer Science
Sang-Yoon ChangAssistant Professor
Computer Science
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.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
