Extended Euclid’s Algorithm

Loading...

Do curso por University of California San Diego

Number Theory and Cryptography

82 classificações

University of California San Diego

Number Theory and Cryptography

82 classificações

Curso 4 de 5 em Specialization Introduction to Discrete Mathematics for Computer Science

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.

Na lição

Euclid's Algorithm

This week we'll study Euclid's algorithm and its applications. This fundamental algorithm is the main stepping-stone for understanding much of modern cryptography! Not only does this algorithm find the greatest common divisor of two numbers (which is an incredibly important problem by itself), but its extended version also gives an efficient way to solve Diophantine equations and compute modular inverses.

Greatest Common Divisor10:57

Euclid’s Algorithm15:06

Extended Euclid’s Algorithm10:09

Conheça os instrutores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

In this video we are going to further extend the Euclid's algorithm for

computing the greatest common divisor.

Let's start with the following motivational question.

So imagine that somebody computed the greatest common divisor of two

integers a and b, and now would like to convince us that it is equal to d.

So, how can this be done?

First of all, we can of course check that d divides a and b.

This will convince us that d is indeed a common divisor of a and b but

this gives us no information whether it is the greatest or not, right?

Because it's still not excluded that there exists a larger

number than d that divides both a and b.

It turns out, however, that to convince us that d is the greatest

divider of a and b, it is enough to represent it.

And in the form ax plus by, where x and y are integers, okay let's prove it.

Assume that d divides a and b and

assume that d is equal to ax plus by where x and y are integers.

Then necessarily d is equal to the greatest common divisor of a and b.

So in a sense, x and y in this case is a certificate

of the fact that d is the greatest common divisor of and b.

So let's prove this theorem.

So first of all since d divides a and b, it is a common divisor of a and b.

And since GCD of a, b is the greatest such common divisor,

it implies that d is at most GCD of a and b.

Once again, this is just because d is some common divisor of a and b and

GCD of a and b is the greatest common divisor.

So some divisor is definitely at most the greatest common divisor.

Okay, on the other hand, so GCD of a and b is some common divisor of a and b.

But this means, in fact, that it should divide d.

So why is that?

So GCD of a, b divides a and b.

It means that it also divides a times x and b times y.

And it also divides the sum of them.

So we conclude that gcd of a, b divides d.

But this, in turn, means that GCD of a and

b is at most d because no number larger than d can divide d.

So all in all we conclude that the d is equal to GCD of a, b.

Once again, this is just because we've just proved that d

is at most the greatest common divisor of a and b.

And at the same time the greatest common divisor of a and b is at most d.

So these two numbers are equal, okay?

So this is nice and let me illustrate this with a couple of examples.

So the great common divisor of 10 and 6 is equal to 2.

And this you can see here it indeed can be represented as a linear

combination of 10 and 6.

Namely, if you multiply 10 by -1 and if you multiply 6 by 2s and

then you compute the sum, you get exactly 2.

So this says, -10 plus 12, it gives us 2.

So the greatest common divisor of 7 and 5 is equal to 1.

And it can be represented as 7 times -5, times -2,

I'm sorry, which gives us -14 plus 5 times 3,

which is 15, so -14 plus 15 is equal to 1,

which is the greatest common divisor of 7 and 5.

So two more examples which are not so easy to compute by hand here on the fly.

But still, so the greatest common divisor of 239 and 299 is equal to 23.

And it can be checked so it can be also represented as a linear combination so

the numbers 391 and 299, okay?

Okay, now let's try to extend the Euclid's algorithm so

that besides of computing the greatest common divisor itself,

it also gives us a certificate.

And by certificate I mean these two numbers, x and y.

So first of all recall that the Euclid's algorithm that we

discovered in the previous video does the following.

To compute the greatest common divisor of a and b it actually makes a recursive call

for computing the greatest common divisor of b and the remainder of a divided by b.

So this happens when a is at least b, okay?

So assume that we've just made such a recursive call, and

it actually returned us not only the greatest common divisor d itself.

But also representation of this greatest common divisor

of the linear combination of the parameters.

And by parameters here I mean these two parameters b and a mod b, so

the remainder of a divided by b.

I assume that we know that its representation,

the representation of d is a linear combination of these two parameters.

Namely, that d is equal to bp plus a mod b times q.

So p and q is a certificate in this case.

So now what we would like to do is to transform this

certificate into a certificate of the pair a and b, okay?

So for this we need a little bit of calculations.

Okay, so we know that d is equal to b times p plus a mod b times q.

First of all, let's do the following, let's rewrite a mod b using just a and b.

So just by definition a mod b is a remainder of a when divided by b.

So this means that when we subtract enough copies of b,

so what is left is some number which is smaller than b, okay?

So this is, for this we need to subtract from a some number of copies of b.

Okay, and this is exactly, so a divided by b is an integer part of a divided

by b is exactly what we get when we divide a by b, okay?

So this is a number of copies that we subtract.

So a mod b is equal to a minus a divided by b.

So in the integer part of it divide and multiply by b.

Okay, so when we rewrite it like this, we can now regroup all the terms.

So what we see is that from here we get a times q and

this is exactly what we see here and.

To get the multiplier for b what we get is that this is b

times p plus b, this b times a divided by b by q.

And this gives us the following expressions.

So this is a new certificate for a and b.

So to get d we need to multiply a by q and

we need to multiply b by this expression, okay?

And this can be implemented as an algorithm which is known as

an extended Euclid's algorithm.

So let's go through this code line by line once again.

So again we assume in this case that a is at least b,

that the first parameter is always at least the second one.

It is convenient in this case.

So b is at least 0 and not both of them are equal to 0.

So first of all, if b is equal to 0.

So if smaller number's equal to 0 then we return the result immediately.

So, in this case d the greatest common divisor is equal to a,

to the larger number, right?

And the certificate x and y are equal to just 1 and 0, right.

So x and y are equal to 1 and 0.

So why is that?

So recall that in this case, b is equal to 0.

So where and d is equal to a.

So a is represented as a times 1 plus was

b times 0, which is clearly correct.

So d is equal to a, so this is our greatest common divisor and we represented

this as a linear combination of a and b, so this is x, this is y.

So in this case, the output is clearly direct.

In the opposite case, when b is greater than 0, we make a recursive call.

Recall that in this case, we swap the parameters.

So our first parameter is b,

our second parameter is the remainder of a divided by b.

This is just because we want our first parameter to be larger

than the second one.

So we make this recursive call and

it gives us the greatest common divisor, and also a certificate b, q.

And using the formula from the previous slide, we can view the new certificate.

So x is just equal to q and y is equal to b minus q times a divided by b.

And here we use this integer division.

So this a divided by b gives us just exactly what we get,

exactly an integer number a divided by b, okay?

So this is y.

So before we turn in the result, we check that d divides a, d divides b,

and that d represents, d can be represented by ax plus by.

So in the end we return the result d, x, y.

So as you see, just a simple extension of the original Euclid's algorithm allows

us to produce not only the greatest common divisor, but

also the certificate of this greatest common divisor.

And we will use this essentially in the next part to compute inverses modular n,

which we discussed already is an essential part of modern integrated protocols.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play