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.

Â