- [Voiceover] We need a numerical procedure,
which is easy in one direction and hard in the other.
This brings us to modular arithmetic,
also known as clock arithmetic.
For example, to find 46 mod 12,
we could take a rope of length 46 units
and rap it around a clock of 12 units,
which is called the modulus,
and where the rope ends is the solution.
So we say 46 mod 12 is congruent to 10, easy.
Now, to make this work, we use a prime modulus,
such as 17, then we find a primitive root of 17,
in this case three, which has this important property
that when raised to different exponents,
the solution distributes uniformly around the clock.
Three is known as the generator.
If we raise three to any exponent x,
then the solution is equally likely
to be any integer between zero and 17.
Now, the reverse procedure is hard.
Say, given 12, find the exponent
three needs to be raised to.
This is called the discrete logarithm problem.
And now we have our one-way function,
easy to perform but hard to reverse.
Given 12, we would have to resort
to trial and error to find matching exponents.
How hard is this?
With small numbers it's easy,
but if we use a prime modulus
which is hundreds of digits long,
it becomes impractical to solve.
Even if you had access to all
computational power on Earth,
it could take thousands of years
to run through all possibilities.
So the strength of a one-way function
is based on the time needed to reverse it.