Discrete Logarithm Problem

Discrete Logarithm Problem - modular arithmetic

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 can take a rope of length 46 units,

and wrap it around a clock 12 units which is called the modulist,

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 modulist, such as 17.

Then we find a primitive root of 17, in this case, 3.

Which has this important property that when raised to different exponents,

the solution distributes uniformly around the clock.

3 is known as the generator. If we raise 3 to any exponent x,

then the solution is equally likely to be any integer between 0 and 17.

Now, the reverse procedure is hard.

Say, given 12, find the exponent 3 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?

Well with small numbers it's easy, but if we use a prime modulist 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.