Main content
Course: Computer science theory > Unit 2
Lesson 4: Modern cryptography- The fundamental theorem of arithmetic
- Public key cryptography: What is it?
- The discrete logarithm problem
- Diffie-hellman key exchange
- RSA encryption: Step 1
- RSA encryption: Step 2
- RSA encryption: Step 3
- Time Complexity (Exploration)
- Euler's totient function
- Euler Totient Exploration
- RSA encryption: Step 4
- What should we learn next?
© 2024 Khan AcademyTerms of usePrivacy PolicyCookie Notice
The fundamental theorem of arithmetic
Independent realization from an ancestor's perspective. Created by Brit Cruise.
Video transcript
Imagine we are living
in prehistoric times. Now, consider the following. How did we keep track
of time without a clock? All clocks are based on some
repetitive pattern which divides the flow of time
into equal segments. To find these
repetitive patterns, we look towards the heavens. The sun rising and falling
each day is the most obvious. However, to keep track of
longer periods of time, we looked for longer cycles. For this we looked
to the moon, which seemed to gradually grow
and shrink over many days. When we count the number
of days between full moons, we arrive at the number 29. This is the origin of a month. However, if we try to
divide 29 into equal pieces, we run into a problem. It is impossible. The only way to divide
29 into equal pieces is to break it back
down into single units. 29 is a prime number. Think of it as unbreakable. If a number can be broken
down into equal pieces greater than one, we call it
a composite number. Now, if we are curious, we may
wonder how many prime numbers are there, and how
big do they get? Let's start by dividing all
numbers into two categories. We list the primes on the
left, and the composites on the right. At first they seem to
dance back and forth. There is no obvious
pattern here. So let's use a modern technique
to see the big picture. The trick is to
use a Ulam spiral. First we list all
possible numbers in order in a growing spiral. Then we color all the
prime numbers blue. Finally, we zoom out to
see millions of numbers. This is the pattern of primes,
which goes on and on forever. Incredibly, the entire
structure of this pattern is still unsolved today. We are on to something. So let's fast forward to around
300 BC in ancient Greece. A philosopher known as
Euclid of Alexandria understood that
all numbers could be split into these two
distinct categories. He began by realizing that
any number can be divided down over and over until you
reach a group of smallest equal numbers. And by definition,
these smallest numbers are always prime numbers. So he knew that all
numbers are somehow built out of smaller primes. To be clear, imagine the
universe of all numbers, and ignore the primes. Now, pick any composite
number and break it down, and you are always left
with prime numbers. So Euclid knew that
every number could be expressed using a
group of smaller primes. Think of these as
building blocks. No matter what
number you choose, it can always be built with
an addition of smaller primes. This is the root
of his discovery, known as the fundamental theorem
of arithmetic, as follows. Take any number, say 30, and
find all the prime numbers it divides into equally. This we know as factorization. This will give us
the prime factors. In this case, 2, 3, and 5
are the prime factors of 30. Euclid realized
that you could then multiply these prime
factors a specific number of times to build
the original number. In this case, you simply
multiply each factor once to build 30. 2 times 3 times 5 is the
prime factorization of 30. Think of it as a special
key, or combination. There is no other
way to build 30 using some other groups of prime
numbers multiplied together. So every possible number
has one, and only one prime factorization. A good analogy is to
imagine each number as a different lock. The unique key for
each lock would be its prime factorization. No two locks share a key. No two numbers share
a prime factorization.