0:00

In this lesson, we're going to look at discrete logarithms

which are logarithms in which all the values are integers.

We'll first review the basic concepts of logarithms,

you'er hopefully already comfortable with,

and then see to what degree these concepts carry over first

to the integer world and then to a modular arithmetic world.

The basic definition of the logarithm is extremely simple.

If you can express a value as b raised to some exponent,

then the base b logarithm of that value is simply the exponent.

Similarly, the exponential function of a number to

the base b is nothing more than b raised to that number.

Hence, the logarithm and exponential functions are reciprocal functions,

one undoes the other.

In the system of real numbers,

we can choose any strictly positive value other than one as our base.

Unless the context of use makes the choice of base obvious,

we generally subscript the function name with the value of the base.

While our base can be smaller than one,

this is practically unheard of and so our discussion from

this point forward will assume that our base is strictly greater than one.

We have two very widely used bases.

The natural laws use Euler's number,

e, as the base.

The value of e is an irrational number approximately equal to 2.718.

The notation commonly seen on scientific calculators

for the natural logarithm function is ln(x),

and then e_to_the_x for the reciprocal exponential function.

We also have the common logs,

which is a base of 10.

Most calculators use the word log for this function.

But as you've likely already encountered,

mathematicians prefer to use this to mean

the natural log and then use the subscript 10 for the common logs.

The point being, don't assume that everyone uses the same notation that you or I do.

In addition, particularly in computer science,

it is often convenient to use a base of two and this is commonly indicated

using lg for the name of the logarithm function to the base two.

Throughout this lesson, we won't assume

any particular base unless we specify it but we will assume

that the same base is used both for the log and

the exponential functions if we don't specify it otherwise.

Let's review some of the basic properties of logarithms.

We've already restricted our base to being a positive real number greater than one.

The concept of logarithms can be readily extended beyond this,

for instance, into the set of complex numbers but for our purposes,

it is cleaner to restrict ourselves to just the positive real values,

if for no other reason than we already know that we are going to further

restrict this to positive integers when we move to a modular world.

The first property is that the logarithm of one is always zero regardless of the base.

Next, the logarithms of zero or any negative number are undefined.

As we approach zero from the positive side,

the logarithm x approaches negative infinity.

However, while the value we are taking a logarithm of must be positive,

the logarithm itself can be any real number,

positive, negative, or zero.

The logs of values between zero and one are negative,

the log of one is zero,

and the logs of values greater than one are positive.

Third, the logarithm is a continuous, monotonically increasing function.

Meaning that given two values of x and y,

if x is greater than y,

then the log of x is greater than the log of y.

This property alone makes finding the logarithms of

an arbitrary number straightfoward because we can use any of

several iterative techniques such as Newton-Raphson or binary search,

to efficiently find the answer to an arbitrary level of accuracy.

As a side note,

if the base is smaller than one,

then the logarithm function is monotonically decreasing.

Furthermore, there is a one-to-one mapping between

the positive real numbers and their logarithms in a particular base.

Each number has exactly one logarithm and vice versa.

Next, we have a couple of properties that follow directly from

the properties of exponentials and the definition of the logarithm.

The first is that the log of a product is the sum of the log of the factors.

The other is that the logarithm of a number raised to

a power is the product of the power and the logarithm of

the number so logarithms transform multiplication

into addition and exponentiation into multiplication.

One of the properties that makes logarithms very powerful,

and that we tend to take for granted,

is that they are relatively easy to calculate.

One thing that makes this true is that if we know how

to find the logarithm of a number in one base,

we can find the logarithm of that number in

any other base since they differ only by a multiplicative constant.

If you aren't confident that you can derive

these last three properties from the definition of the logarithm,

and the basic properties of exponentials,

then I'd strongly recommend that you pause the video at

this point and spend some time reviewing the fundamentals of logarithms.

It will likely make your life easier as we move forward.

To avoid spending any more time on continuous logarithms,

we'll end with the observation,

that for several centuries,

in fact for about a decade after we put a man on the moon,

logarithms were almost exclusively calculated

manually using printed log tables and slide rules.

This started to wane only after affordable scientific calculators became

available starting somewhere in the mid to late 1970s.

The fact that continuous logarithms are so easy to compute is

perhaps the major difference between them and discrete logarithms,

and that turns out to largely be what makes

discrete logarithms useful for cryptographic algorithms.

Now, let's turn our attention first to the world of

integers before we move all the way into the world of modular arithmetic.

In a world where all of our numbers must be integers,

logarithms are referred to as

discrete logarithms because they can only take on distinct values.

First, what does a logarithm of 100 base 10?

Hopefully, you can see by inspection that it is two.

Similarly, the logarithm of 1000 base 10 is three.

But what about the discrete logarithm of 512 base 10?

It doesn't exist. It would have to lie somewhere

between two and three and we are restricted to integers.

However, the discrete logarithm of 512 base eight is

three so whether a number has

a discrete logarithm depends not only on the number but on the base.

This means that we do not have a one-to-one mapping between

a set of positive integers and their discrete logarithms.However,

while a particular integer may not have a logarithm,

if it does, that logarithm is unique.

In other words, since 10 to the three is 1000,

we know that there is no other integer k such that 10 to the k is a thousand.

While many, in fact the overwhelming majority,

of numbers fail to have logarithms in an integer world,

all of the other properties still hold.

In particular, the monotonic nature of

the relationship between a number and its logarithm.

This means that if the log does exist,

it is computationally easy to find,

and if it doesn't exist,

it is computationally easy to determine that fact.

But what about in a modular world?

First, it is tempting to call

these particular discrete logarithms by the name modular logarithms,

and I admit I think this is reasonable.

However, while you do see this term,

occasionally, it doesn't appear to be widespread.

Having said that, I think most people familiar with discrete logarithms would

intuitively know what it means but we'll stick with the usual name.

Let's consider a mod 13 world and construct a table of

all the possible bases in exponents just as

we have addition tables and multiplication tables.

This is an exponentiation table.

In this table, each column uses the value at the top of

the column as the base and the value at the left edge as the exponent.

To find the logarithm of a value to a particular base,

we look down the column for that base until we find the value we want the logarithm for,

and then the logarithm is simply the number at the left edge of the row.

For instance, the base seven logarithm of four is 10.

But what is the base seven logarithm of five?

Well, we know that it might not exist,

we might also expect that since base seven logarithm of five is 10,

for it to be larger than 10 if it does exist.

However, not only does it exist,

it turns out to be only three.

Thus our expectation of a monotonic relation simply doesn't hold.

But this shouldn't trouble us because the whole notion of ordering is

problematic in a modular world due to the very nature of the residue classes.

Nonetheless, this lack of monotonicity is perhaps

the single most important trait that makes finding discrete logarithms non-trivial.

Furthermore, our logarithms may not be unique.

Consider the base eight logarithm of five.

Our table quickly shows that it is three.

But if we look further,

we see that it is also seven and also 11.

In addition, we can see many instances in which b to the k yields

the same value for the same exponent using different values for the base.

While we expect this in the special case where the exponent is zero,

consider the exponent of three.

We see that four to the third, 10 to the third,

and 12 to the third are all congruent to 12 in a mod 13 world.

Another concept is the notion of a primitive root.

A primitive root is a value g such that

every integer that is relatively prime to the modulus can

be written as a power of g. This is also

known as a generator of the group in number theory.

Another way of phrasing this,

is that g is the primitive root mod N. If every residue class that is

relatively prime to N has a discrete logarithm base g. Looking at our mod 13 table,

we see that two, six,

seven, and 11 are primitive roots.

Although this is just one example,

we can still glimpse that there isn't any obvious pattern here.

Before actually looking at this table,

it might seem reasonable to expect that since our modulus is a prime number,

that all of the integers greater than one might be primitive roots.

Clearly, this isn't the case.

But barring that, it would seem likely that any prime number would be a generator,

yet neither three nor five are, okay?

But going the other way,

it might also seem likely that if a particular number is not

a generator then neither would any number that is a multiple of it.

Yet six is a generator even though three is not.

While it might seem like that properties like existence,

monotonicity, and uniqueness are fine print issues.

What about the basic properties of logarithms that we use all the time,

such as the property that the log of the product is the sum of the logs?

Let's constrain ourselves to a base that is

a primitive root and only use values whose logs exist.

From our table, we find that the base seven log of

eight is congruent to nine in our mod 13 world.

But since eight is the part of four and two,

it seems reasonable that the log of eight should be congruent to

the sum of the log of four and the log of two,

however this turns out to be congruent to eight.

So discrete logs in a modular world don't

even obey the normal rules even when they exist.

The reason for this is at least understandable.

Logarithms are exponents and exponents live in mod-totient world.

If we express our logarithms as exponents of the base,

then the totient influence becomes readily apparent.

And now we can see that we do get the expected behavior.

But certainly, this is very tricky ground and we have to walk very carefully.

The end result of all of this is that there just really aren't

any reliable patterns that discrete logarithms

obey that would allow us to make finding them easy.

In general as we look over our table,

we can see some apparent patterns such as reflections in rows.

But as we look closer,

we see that those patterns are erratic.

They hold for some basis and not others or for some exponents and not others.

With little rhyme or reason as to when they hold and when they don't.

This apparent chaos results in what is known as the discrete log problem,

which is the problem of finding the logarithm of

an integer in a modular world or determining that it doesn't exist.

There are currently no known computationally efficient solutions to this problem.

Recall that computationally efficient is jargon meaning,

an algorithm that runs in polynomial time as opposed to

exponential time in terms of the number of bits needed to represent the modulus.

We can always solve it using brute force trial multiplication,

and many algorithms have been devised that are significantly faster than this.

But all still grow exponentially with the size of the modulus and thus are

not sufficiently better to be useful at the scale of moduli use in cryptography.

So when we talk about solving the problem,

we mean devising a polynomial time algorithm for doing so.

You might have noticed that I included the caveat,

there is currently no known efficient algorithm.

The very problem of whether or not an efficient algorithm exists is itself,

one of the great unsolved problems in mathematics.

As a result, although we will see

that several critically important cryptographic algorithms

base their security on the assumption that

no efficient solution for the discrete log problem exists,

there is the possibility that some clever person might solve it.

Be it a world class mathematician or

just some seventh grader with a particular insight because they don't know any better.

Such a solution would break the systems wide open and render them useless.

Over the decades, countless very bright people have attempted to find

an efficient solution and many have made chipping away at the problem,

the focus of their life's work.

Their collective failure to do so leads

a lot of people to suspect that no such algorithm exists,

enough so that governments and militaries are willing to rely on that being the case.

But every year or so, we hear about another problem being

solved that was suspected of being unsolvable,

precisely because countless people had worked on it without success.

Sometimes for centuries.

So why are we really willing to protect our most vital secrets with

cryptographic algorithms that rely on no one being able to solve a problem,

when we don't know that someone can't find a solution tomorrow.

This seems like a contradiction when we call the designers of

cryptographic protocols are inherently extremely conservative,

as evidenced by the use of problems that are literally astronomical in size.

As we used to say when I worked the flight line fixing jet fighters,

"Sometimes you gotta do what you gotta do."

But provably secure algorithm is useless if it is so computationally

complex that it can't be used in useful time scales on today's hardware.

We live in a world of compromises.

And right now, the compromise between what is desirable and what is

possible forces us to use algorithms based on problems that we believe, hope really.

No one will solve any time soon.

But while we might be willing to tolerate the situation, we don't like it.

So we are always seeking out

more computationally tractable problems that are provably secure as well as developing

increasingly capable hardware with the goal of making

implementations of existing provably secure algorithms practical.