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.
Implications of Unique Factorization
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）
從本節課中
Building Blocks for Cryptography
Cryptography studies ways to share secrets securely, so that even eavesdroppers can't extract any information from what they hear or network traffic they intercept. One of the most popular cryptographic algorithms called RSA is based on unique integer factorization, Chinese Remainder Theorem and fast modular exponentiation. In this module, we are going to study these properties and algorithms which are the building blocks for RSA. In the next module we will use these building blocks to implement RSA and also to implement some clever attacks against RSA and decypher some secret codes.
與講師見面
Alexander S. KulikovVisiting Professor
Department of Computer Science and Engineering
Michael LevinLecturer
Computer Science
Vladimir PodolskiiAssociate Professor
Computer Science Department
Hi. In this video we're going to draw
some useful implications of
the unique factorization theorem that we proved in the previous video.
First, is some simple divisibility criterion that we now have.
So, when does m divide n if you know their prime factorization?
And the answer is, if we consider canonical representations of both m and n,
then m divides n when first,
all prime factors of m are among prime factors of n,
and if PI is equal to QJ,
if prime factor of M corresponds to the J_th prime factor
of N. Then it must be that the corresponding degree in
which this prime factor goes into M is less than or equal to
the degree in which this prime factor goes into the representation of N. So,
we can just compare the sets of prime factors of
both numbers and then we can compare the degrees of the corresponding prime factors.
If this set of prime factors of M is a subset of the set of prime factors of
N and the corresponding degrees for M are less than or equal to the degrees for N,
then M divides N. Another question that we want to answer easily is,
when numbers M and N are coprime.
And integers M and N are called coprime is their Greatest Common Divisor is equals to 1.
And given canonical representations,
this again easier to say that M and N
basically don't have any common divisors and in particular,
they don't have any common prime factors and so Greatest Common Divisor
of M and N is equals to 1 if and only if there are
no common prime factors between prime factors of
M and prime factors of N. So we just compare the sets
of prime factors in the canonical representations and if
those sets don't intersect then numbers M and N are coprime.
Another question is how to compute the Greatest Common Divisor
itself in case it maybe not equal to 1?
So, that set of numbers P1,
P2 and so on up to Pk be all the prime divisors of M and N both of them,
not just one of these numbers,
but the union of the sets of prime factors of both these numbers.
Then we can represent both numbers M and N as product of these primes in some degree.
Note that some of these degrees alpha I and beta I can be equal to zero.
In this case but still it can represent them
both as products of the same primes in some different degrees.
And then what we need to take is in each column,
we need to take this prime in some degree and this degree must be less than or equal to
the corresponding degree in both M and N because this number must
divide both M and N and we just learned the divisibility criterion,
that the degree of the prime factor in the number that divides
another number should be less than or equal
to the corresponding degree in the number it divides.
So, for the Greatest Common Divisor that divides both M and N,
the degrees must be less than or equal to the degrees in both M and N but this is
the greatest common divisor so this should be
the greatest degrees which still satisfy this property.
And these are the minimums of the corresponding Alpha I and beta I.
So greatest common divisor of M and N is the product of P1 to the power of minimum of
Alpha 1 and beta 1 times P2 to the degree of minimum of alpha 2 and beta 2 and so on.
Because these minimums are less than the corresponding alpha I and beta I,
and these are the greatest degrees possible which are less than both alpha I and beta I.
So, now that computing greatest common divisor is
actually algorithmically much easier than prime factorization.
Computing greatest common divisor can be done with
Euclid's algorithm that we learned in the previous model.
And still no efficient algorithm is known for prime factorization.
So, you shouldn't actually try to do prime factorization to compute GCD.
It is just convenient to know how to compute GCD
given prime factorization because it can lead to some other useful conclusions.
But if you want to actually compute GCD,
you should use Euclid's algorithm.
It is fast and pretty simple.
Another useful function of two numbers is called least common multiple.
It is very similar to the greatest common divisor,
but in some sense its vice versa.
So, the least common multiple LCM of two integers A and
B is the smallest positive integer X such that both A and B divide X.
Now, let's consider some examples.
The least common multiple of 1 and 10 is 10,
because 10 divides 10 and 1,
and of course, 10 is a common multiple of both 1 in 10.
But any number less than 10 cannot be the LCM because 10 must divide it,
and so it must be at least 10.
And for 2 and 3,
the smallest number such that both 2 and 3 divides it is 6 because 2 doesn't divide 3,
3 doesn't divide 4, 2 doesn't divide 5 and now
6 is the least common multiple because both 2 and 3 divide 6.
And to other example is least common multiple of 2 and 4 is 4 because 2 divides 4.
And in the case when A divides B,
the least common multiple is just B.
And the least common multiple of 4 and 6 is 12.
So now how to compute LCM it in the general case,
so let's again consider all the prime factors of both M and N,
P1, P2 and up to PK.
And then represent both M and N as products of these prime numbers in some degrees,
some of which can be zero.
Then the least common multiple must be a number that both M and N divide,
and so it must contain all these prime factors.
It doesn't need to contain any other prime factors
because then it won't be the least common multiple.
And now we need to determine which degrees of these prime factors do we need.
So, these degrees must be greater or equal to the corresponding degrees in both M and N,
so that both M and N divide this number.
So, we can just take the maximums of alpha I and
beta I and take PI in this corresponding degrees,
and that will be the least common multiple.
So, this formula is very similar.
As you can notice to the formula for Greatest Common Divisor,
we just replace minimum with maximum.
Now, that for any alpha and beta,
minimum of alpha and beta plus maximum of alpha
and beta is just equal to the sum of alpha and beta.
And so, if we multiply the corresponding factors in the GCD and LCM,
P1 to the degree of minimum of alpha 1 beta 1
times P1 to the degree of maximum of 1 beta 1,
we will get P1 to the sum of alpha 1 and beta 1.
And this is important because if we now represent M and N
as the product of these set of primes from P1 to Pk
and we also represent GCD and LCM as
products of these primes in the corresponding minimum and maximum degrees,
then we'll notice that the product of MN is product of
these PI in the degrees of alpha I plus beta I.
And also the product of GCD and LCM will be equal to the same number because minimums
and maximums when we sum them up is the same as if we summed up alpha I and beta I.
And so, the product of GCD and LCM for two numbers is equal to their product.
And this in turn gives us a way to
quickly compute LCM because we already know that to compute GCD
we can use Euclid's algorithm and now LCM can be represented as a MN divided by GCD.
So, we can easily compute the products to numbers,
and then we compute GCD and Euclid's algorithm.
And then by dividing those two we can get the least common multiple.
So, now, we have some useful conclusion from
the prime factorization although we don't need
prime factorization itself to compute either GCD or LCM.
From this presentation, we concluded
with a fast algorithm to compute LCM which we didn't know before.
So another Lemma that we're going to use in
the next lectures is that if A divides N and B divides N
and A and B are coprime then there are product divides N. So to prove it,
consider all prime factors of A and B
so all prime factors of A are among prime factors of N and
degrees of those factors in N are bigger or equal to the corresponding degrees in A.
The same goes for B and also as GCD of A and B equal to 1,
A and B don't share prime factors we learned that in the beginning of this video.
So now we can say that all prime factors of both A and B
are in N they don't intersect so all the prime factors of their product are
also in N and the degrees in which they
represent AB are also less than or equal to the degrees in which they represent N,
so AB divides N necessary.
And in conclusion, using the unique factorization theorem,
we made an easy criterion for
divisibility of two numbers given their prime factorizations.
We characterized coprime numbers that they don't share prime factors.
We can compute GCD and LCM using prime factorizations.
However, prime factorization is a hard problem and Euclid algorithm is fast.
So, actually, we need to use Euclid's algorithm to compute GCD
and given that GCD times LCM is equal to the product of the numbers.
We can also compute LCM from Euclid's algorithm and by computing MN and dividing by GCD.
And we know now that if two coprime numbers
divide some integer N then their product also divides integer N.
