We all learn numbers from the childhood. Some of us like to count, others hate it, but any person uses numbers everyday to buy things, pay for services, estimated time and necessary resources. People have been wondering about numbers’ properties for thousands of years. And for thousands of years it was more or less just a game that was only interesting for pure mathematicians. Famous 20th century mathematician G.H. Hardy once said “The Theory of Numbers has always been regarded as one of the most obviously useless branches of Pure Mathematics”. Just 30 years after his death, an algorithm for encryption of secret messages was developed using achievements of number theory. It was called RSA after the names of its authors, and its implementation is probably the most frequently used computer program in the word nowadays. Without it, nobody would be able to make secure payments over the internet, or even log in securely to e-mail and other personal services. In this short course, we will make the whole journey from the foundation to RSA in 4 weeks. By the end, you will be able to apply the basics of the number theory to encrypt and decrypt messages, and to break the code if one applies RSA carelessly. You will even pass a cryptographic quest! As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.
Modular Subtraction and Division
Loading...
Из курса от партнера University of California San Diego
Number Theory and Cryptography
67 оценки
University of California San Diego
67 оценки
Курс 4 из 5 — Specialization Introduction to Discrete Mathematics for Computer Science
Из урока
Modular Arithmetic
In this week we will discuss integer numbers and standard operations on them: addition, subtraction, multiplication and division. The latter operation is the most interesting one and creates a complicated structure on integer numbers. We will discuss division with a remainder and introduce an arithmetic on the remainders. This mathematical set-up will allow us to created non-trivial computational and cryptographic constructions in further weeks.
Познакомьтесь с преподавателями
Alexander S. KulikovVisiting Professor
Department of Computer Science and Engineering
Michael LevinLecturer
Computer Science
Vladimir PodolskiiAssociate Professor
Computer Science Department
Recall that any number is congruent to its remainder
modulo m. What we can do if you are talking about congruent to its modulo m,
if we're looking for remainders modulo m?
We can just present any number by its remainder and also recall what we
have shown that arithmetic operations addition, multiplication preserve congruence.
If you would like to apply arithmetic operations to some numbers and you would
like to do it modulo some m then we can
apply them with operations to numbers with the congruent to the original numbers.
For example, instead of applying operations
to original numbers we can apply them directly to remainders of
original numbers and the remainder of the result of the operation
depends only on the remainder of the original numbers to which we apply our operations.
What we can do? We can create
tables for arithmetic operations for remainders over some modulo.
Lets do it, for example, for modulo four m equals to seven and here is addition table.
Rows are labeled by one of the sum,
some columns are labeled by our sum and in the cell on intersection of row and column,
we write to the remainder of the result of addition.
For example, if we consider the sum of
four and one then we will get the row labeled by four,
look at the column labeled by one and in intersection we've
five so five is the remainder of the result if we add four and one.
This is easy to see. Let's consider one more example.
For example, let's consider the six plus six so
when we have to look at bottom right corner
of this table and here we have five and then we add
six and six it is 12 and modulo seven,
it is congruent to five.
So five is the remainder of the result of addition of two numbers
having the remainders six modulo seven so the remainder of the sum will be equal to five.
Note that this table has nice and simple structure.
We can consider the same table for multiplication for multiplication modulo seven.
Again, we've a table,
rows of the table correspond to the remainders modulo seven.
Columns correspond to remainders modulo seven again,
and in the cell,
we write the remainder which corresponds to
the product of the number in the row and in the column.
Again, let's consider a couple of examples.
For example, if you consider the product of four and three
then it is 12 and the remainder modulo seven is five.
This is what we have in our table, and,
for example, let's consider product six of six and six, six by six is 36.
Note that 35 is divisible by seven.
So, the remainder is one and this is what we have in bottom right corner of the table.
So, that's what we have.
Now, note that using these tables,
we can perform modular computation.
If you have some arithmetic expression with some numbers,
we can substitute all numbers in the arithmetic expression by
their remainders and apply operations according to the table.
So each time we will look at operation we look at the table and just like
the usual addition and multiplication table in school,
we can just apply these operations one-by-one and do the computation.
Also, these tables are convenient to observe properties to operations.
Let's just try to this.
Let's just consider if modular subtraction is possible.
So what is modular subtraction?
Let's consider a following questions.
Suppose we have two numbers a and b.
Is there such a number x such that a + x is congruent to b modulo seven?
Note that x will play a role b minus a in our modular arithmetic.
Is this always possible?
For this, we can just look at this table and we can observe that each row of
this table contains all possible remainders, okay?
Why is this good?
Note that in this expression a + x is congruent to b. a plays
the role of a row of this table.
x plays the role of the column and b
plays the role of the value in the cell of the table.
The question is following: so the question we are asking is,
suppose we have some row of a table and suppose we have some target value b.
Is there a column such that in
the intersection of our row and this column, we have our target value.
Note that in each row we have all possible values.
Whatever row we are given and whatever target value we have in
case there is some still this target value and so there is some x which is equal to,
which satisfies this congruence such that a + x is congruent to b modulo seven.
If x exists for all a and b, and okay,
what we can do now we can consider this x given a and b,
we can consider this x such that a + x is congruent to b modulo seven.
Note that the same argument holds for
all modules m. If you substitute seven by any number m still x exists,
x plays the role of modular subtraction.
It plays the role of b minus a in modular arithmetic.
Note that the existence of x is natural.
We can just pick b minus a as an integer and
consider the corresponding remainder modulo seven.
The equation will be satisfied since congruence is preserved under addition.
Okay. Now, let's consider modular division.
Suppose we have two numbers a and b and now a should be non-zero.
Is there a such an x that a times x is congruent times to b modulo seven?
Okay, note that x correspond to
b divided by a in modular arithmetic and know that a should be non-zero because,
okay, if you multiply zero by anything it will be zero.
Of course, so a is zero,
this is not always possible but if a is non-zero,
we can ask this question: Is it true that x exists?
And here we can look at a multiplication table.
Again, we can see that x always exists if a is non-zero.
Again, each non-zero row,
each row which is not the first one contains all possible remainders.
Again, a here corresponds to a row,
b corresponds to the target value in this row and x is a column.
If you pick any row which is not the first one then we can
see all possible values in this row.
Whatever target value, whatever b we have,
there is a column having this value on intersection with our row.
Modular division is always possible.
Given a that is not equal to zero and b we can always consider x
such that a times x is congruent to b modulo seven.
We have shown that such x exists and again x plays the role of modular division.
It is b divided by a in modular arithmetic.
Note that x is still some integer number,
it's some remainder modulo seven.
It just plays the role of division in our modular arithmetic.
Everything is finally good,
it seems like this and the construction of modular arithmetic is complete.
We have addition, multiplication, subtraction, division.
Is this right?
It turns out that no and for this let's just consider some other module,
instead of seven let's just consider six.
Let's consider multiplication modulo six.
Here is the table.
Observe that rows that correspond to numbers two, three, and four.
They do not contain all possible remainders.
There are some remainders and we present here.
In particular, if we pick a to be equal to three so if we pick
row labeled by three and we pick value one in the right-hand side.
Then there is no such x,
there is no such column such that three times x is congruent to one modulo six.
This is not always possible.
For modulo seven, we found that modular division is always possible.
For modulo six, it turned out to be not the case.
What is going on?
Why it happens that, we have
division modulo seven but we do not have division modulo six?
What is the difference between seven and six?
Why it works in one case and doesn't work in the other?
It turns out that the modular division is actually more
complicated than it seemed before than it seemed after we considered modulo seven?
We will discuss these differences,
these complications in further in this course.
We will see what is the difference between seven and six that
makes division impossible for modulo six.
Okay, let us discuss what we have in this course.
We have started with some simple notions divisibility and remainders.
Then from them we developed more advanced things.
We developed the basics of modular arithmetic.
We have addition, multiplication, subtraction,
modulo some number, but
the things are complicated and we do not understand them completely.
The division turned out to be complicated.
Okay. Is it well that things are complicated?
It is bad for us in any sense?
In some sense, yes.
We would like the things to be more simple because we would like to use
our number theory for computations.
We would like to compute the things effectively.
And if something is complicated,
it is harder for us to compute but maybe in some sense complicated is good.
It turns out that yes this is true.
Complicated things are also important and they are crucial for cryptography.
Cryptography relies on things that are hard to compute.
If you have something that is hard to compute this is actually,
in some other sense, this is good for us.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
