WEBVTT

00:00:01.365 --> 00:00:03.843
- [Voiceover] We need
a numerical procedure,

00:00:03.843 --> 00:00:07.481
which is easy in one direction
and hard in the other.

00:00:07.481 --> 00:00:10.394
This brings us to modular arithmetic,

00:00:10.394 --> 00:00:13.122
also known as clock arithmetic.

00:00:13.122 --> 00:00:17.046
For example, to find 46 mod 12,

00:00:17.046 --> 00:00:20.023
we could take a rope of length 46 units

00:00:20.023 --> 00:00:22.981
and rap it around a clock of 12 units,

00:00:22.981 --> 00:00:25.220
which is called the modulus,

00:00:25.220 --> 00:00:28.385
and where the rope ends is the solution.

00:00:28.385 --> 00:00:33.385
So we say 46 mod 12 is
congruent to 10, easy.

00:00:34.003 --> 00:00:37.873
Now, to make this work,
we use a prime modulus,

00:00:37.873 --> 00:00:42.694
such as 17, then we find
a primitive root of 17,

00:00:42.694 --> 00:00:46.056
in this case three, which
has this important property

00:00:46.056 --> 00:00:48.630
that when raised to different exponents,

00:00:48.630 --> 00:00:53.050
the solution distributes
uniformly around the clock.

00:00:53.545 --> 00:00:56.439
Three is known as the generator.

00:00:56.439 --> 00:01:00.157
If we raise three to any exponent x,

00:01:00.157 --> 00:01:02.032
then the solution is equally likely

00:01:02.032 --> 00:01:05.714
to be any integer between zero and 17.

00:01:05.745 --> 00:01:09.097
Now, the reverse procedure is hard.

00:01:09.097 --> 00:01:11.939
Say, given 12, find the exponent

00:01:11.939 --> 00:01:14.576
three needs to be raised to.

00:01:14.576 --> 00:01:18.097
This is called the
discrete logarithm problem.

00:01:18.097 --> 00:01:20.697
And now we have our one-way function,

00:01:20.697 --> 00:01:24.201
easy to perform but hard to reverse.

00:01:24.201 --> 00:01:26.286
Given 12, we would have to resort

00:01:26.286 --> 00:01:30.194
to trial and error to
find matching exponents.

00:01:31.164 --> 00:01:32.925
How hard is this?

00:01:32.925 --> 00:01:35.031
With small numbers it's easy,

00:01:35.031 --> 00:01:36.896
but if we use a prime modulus

00:01:36.896 --> 00:01:39.194
which is hundreds of digits long,

00:01:39.194 --> 00:01:41.782
it becomes impractical to solve.

00:01:41.782 --> 00:01:43.629
Even if you had access to all

00:01:43.629 --> 00:01:45.522
computational power on Earth,

00:01:45.522 --> 00:01:47.323
it could take thousands of years

00:01:47.323 --> 00:01:49.768
to run through all possibilities.

00:01:49.768 --> 00:01:51.962
So the strength of a one-way function

00:01:51.962 --> 00:01:55.208
is based on the time needed to reverse it.