Unique Factorization

Loading...

From the course by University of California San Diego

Number Theory and Cryptography

60 ratings

University of California San Diego

Number Theory and Cryptography

60 ratings

Course 4 of 5 in the 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.

From the lesson

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.

Introduction7:50

Prime Numbers3:11

Integers as Products of Primes3:03

Existence of Prime Factorization2:34

Euclid's Lemma4:55

Unique Factorization9:59

Implications of Unique Factorization10:49

Meet the Instructors

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

Hi. In this video,

we're going to finally prove that the prime factorization of any integer is,

in some sense, unique.

So the theorem states that every integer n > 1

can be represented as a product of one or more prime numbers,

and any two such representations of the same integer n

can differ only by the order of prime factors.

Actually, we've already proven the first part,

that the representation, as a products of prime, exists.

Now, let us prove the uniqueness of the representation.

So first, assume that there can be

two different representations of n as product of primes,

which differ not only by the order of primes.

So that n is equal to both p_1 times p_2 times,

and so on, up to p_k,

where p_1, p_2, and so on,

up to p_k are prime numbers.

And also, n is equal to q_1,

q_2, and so on,

up to q_l, where these q's are also prime numbers,

and some of them are different from some of the p_1,

p_2, and so on,

up to p_k because these two representations differ not only by the order of products,

but also by sum of the factors.

So if there are some common factors in these two representations,

for example, p_1 is equal to q_2,

we can just cancel them until there are no common factors.

So just remove these common factors from

both the left part and the right part of the equality,

and the equality will stay true.

So now, assume that this still holds true,

there is nothing to reduce,

and there are two different representations of

the same integer n as product of primes without common factors.

And again, they still differ not only by the order of the factors.

Now, we see that p_1 times p_2 up to p_k is equal to q_1 times q_2 up to q_l.

And we know that the left part is a product of numbers which includes p_1.

So p_1 is a prime number,

and it divides this left part.

So it divides the right part of the equation.

So p_1 divides the product of q_1,

q_2 and up to q_l.

And by the corollary from the previous video,

we know that it follows that p_1 divides at least one of the integers q_1,

q_2 and up to q_l.

If p_1 divides some q_i for some i,

then given that q_i is also prime number,

and p_1 is a prime number,

p_1 might be a divisor of a prime number.

It cannot be equal to one because it is a prime number and one is not considered prime,

so p_1 must be equal to q_i.

But this is a contradiction because we have just assumed

that these are two representations without any common factors,

and we just found a common factor, p_1 and q_i.

So as we came to a contradiction,

our assumption that there can be two different representations

which differ not only by the order of factors for some integer n is false.

And so, actually, any two representations can only differ by the order of the primes.

And I want you to note that when we canceled some of the factors,

it doesn't change the fact,

because if we cancel two factors and then we return them back into representation, well,

that just changes the order of the factors,

but this factor appears in both representations.

So they don't start to differ in more than the order of factors.

So we've just proven that factorization is unique up to the order of factors.

And from this, we can make some useful conclusions.

For example, for any presentation of n as a product of primes,

we can sort these prime factors in ascending

order and then group all the equal primes together.

And then, we can get what is called the canonical representation of integer n. N is

equal to p_1 to the alpha one times p_2 to the alpha two,

and so on, up to p_k to the alpha k,

where p_1 is less than p_2 and so on,

and this is less than p_k.

And these are all the prime factors of n in ascending order,

in strictly ascending order.

And alpha one, alpha two, and so on,

up to alpha k are some strictly positive integers,

the degrees in which these primes

get into the representation of n as a product of primes.

It follows from the unique factorization theorem,

that the canonical representation of any integer n > 1 is unique.

Because, if any two representations differed only by the order of

prime factors and then we sorted these prime numbers in the ascending order,

then the orders are already the same in any two representations after this sorting.

And then, if we just group the same primes together,

well we have the same number of the same prime number as prime factor

in any two representations by the unique factorization theorem,

so alpha one, alpha two,

and so on, up to alpha k,

will also be always the same for any initial representation.

We can do it with another representation.

So, instead of just taking only prime factors of n which are divisors of n,

we can actually take any set of primes, p_1,

p_2 and up to p_m, such that all prime divisors of n are in this set.

But maybe, some primes which are not divisors of n are also in this set.

And then, we can represent n as a product of p_1

to alpha one times p_2 to alpha two, and so on,

up to p_m to alpha m. And we can, of course,

sort these numbers from the least p_1 to the biggest p_m.

However, in this case,

some alpha i's can be zero,

exactly for those prime factors which are not divisors of n. Actually,

we can do even more than that.

Particular, we can take the set of all prime numbers and

enumerate it from the smallest starting from p_1 = 2,

p_2 = 3, p_3 =5, and so on.

And then represent integer n,

any integer n bigger than one,

as a sequence alpha one,

alpha two, alpha three, and so on,

the degrees in which these prime factors from

the set of all prime factors get into the representation of n,

where alpha i will be equal to zero if some prime number p_i doesn't divide n. Otherwise,

alpha i is exactly the degree from

the canonical factorization of n corresponding to this prime factor p_i.

In this representation, all integers have the same set of prime factors,

although some of them,

get into degree zero.

And this is a useful representation.

For example, in this representation,

it is easy to multiply numbers.

If we consider two integers,

m and n, and for integer m,

we have sequence of degrees alpha one, alpha two, and so on.

And for integer n,

we have another sequence beta one,

beta two, and so on,

then the product of these two numbers,

mn corresponds to the sequence alpha one plus beta one,

alpha two plus beta two, and so on.

Why is that? Well, because when we multiply two numbers,

then the prime factors from one number get

added to the same prime factors of the second number.

So if we sort them again in ascending order,

and we grouped alpha one numbers p_1,

and then we grouped beta one numbers p_1 for n,

and then we group them together,

we get just alpha one plus beta one copies of the same prime number p_1.

And so, the degree of p_1 in the product mn is equal to alpha one plus beta one.

And the same goes for p_2,

for p_3, and so on.

So it is easy in this representation to multiply any two numbers.

However, there is no simple way to sum two numbers in this representation

because we don't know what will be the prime factors of m plus n,

and we cannot say how to

compute these prime factors and their degrees from just sequences alpha one,

alpha two, and so on, beta one, beta two, and so on.

So, in conclusion, now we know

that any integer can be represented as a product of primes.

Any two such representations differ only by the order of prime factors.

And there exists a canonical representation n is

equal to p_1 to the power

of alpha one times p_2 to the power two to the power of alpha two,

and so on, up to p_k to the power of alpha k such that p_1,

p_2 up to and p_k are all the prime factors,

all the prime divisors of n. And alpha one,

alpha two, and so on,

up to alpha k are the degrees in which

these prime factors get into the representation of n,

and these canonical representation is totally unique for any integer n. And also,

we can represent an integer n as a sequence of degrees

for all prime numbers starting from p_1 equal to two,

and then three, five, seven, and so on.

And we can represent n as a sequence, alpha one,

alpha two, and so on,

of degrees in which these prime numbers get into representation of n

where all these alphas are non-negative and they're equal to zero,

if the corresponding prime number doesn't divide n. Otherwise, it is bigger than zero.

And in the next video, we're going to study

some more useful conclusions from this unique factorization theorem.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play