In our previous lesson,

we showed that division is not defined in

modular arithmetic and then even when it might appear that it should work,

it might not, and therefore,

should always be avoided.

We also mentioned that there was an analog to division,

which is the multiplicative inverse.

In this lesson, we'll introduce the concept of a multiplicative inverse,

explore what is required for such an inverse to exist,

and learn how to use the Euclidean Algorithm to

find the greatest common divisor of two numbers,

which will tell us whether a multiplicative inverse actually exists.

We'll then look at how efficient this algorithm

is and finally prove that it actually works.

This will set the stage for a future lesson in which

we will extend the Euclidean algorithm so that

we can use it not only to determine if

a multiplicative inverse exists but to actually find it.

Let's recast our division into multiplication.

We know that dividing by some number is the same as multiplying by its reciprocal

and that the reciprocal can be written as the power raised to the negative one power.

We also know that another name for the reciprocal of

a number is its multiplicative inverse because,

by definition, the product of a number and

its multiplicative inverse is the multiplicative identity, which is one.

Note that some authors argue, with some justification,

that using an exponent of minus one to indicate the multiplicative inverse is an abuse

of notation since it is so strongly associated with the vision in normal arithmetic.

Nonetheless, it is perhaps the most common notation

used and others argue, again with merit,

that not only does it have a lot to recommend it so that is no more of

an abuse than many other common notations that have far greater potential for ambiguity.

You'll even see some authors use the division operator with

the understanding that since division isn't defined in modular arithmetic

that this indicates multiplication by the multiplicative inverse of

the denominator but most people feel this is too much of an abuse and more to the point,

far too likely to lead people to improperly perform the division itself.

So we'll stick with the negative one exponent.

We can use this definition directly in the mods in world.

For example, consider a mod-7 world,

we can build a multiplication table very easily and then pick

off the multiplicative inverses of each residue class by inspection.

Note that zero does not have a multiplicative inverse.

Hardly surprising since anything multiplied by zero is zero and hence,

there is nothing we can multiply it by to get one,

but all other residue classes do have a multiplicative inverse.

Sometimes, it's itself, again, hardly surprising,

since in the normal integers one is its own multiplicative inverse.

In a mod-n world,

it turns out that in minus one is also always its own multiplicative inverse.

You might see if you can prove that this must be the case.

There are a couple of fairly easy ways to do this.

You might also see if you can construct a modulus such that some number other than

one and in minus one is its own multiplicative inverse.

But what about in a mod-15 world?

We see that while some residues do have multiplicative inverses,

many don't and that three is among them.

So, when we try to divide 15 by three,

this must be equivalent to multiplying 15 by the multiplicative inverse of three,

which is a number that doesn't exist.

Therefore, it's not surprising that we can get nonsensical answers.

It's sort of like those proofs that we've all seen that

two equals one and when we look at them carefully,

we discover that at some point,

we had to divide by an expression that was equal to zero, another undefined operation.

The next reasonable question is,

"Why do some numbers have multiplicative inverses in

a particular modular world and others don't?"

A related question is,

"How can we determine whether or not a number has

a multiplicative inverse in a given modular world?"

Let's look at our mod-15 table and see if we notice anything that

distinguishes those numbers that have multiplicative inverses from those that don't.

It may not jump out at you immediately,

but the only numbers that have multiplicative inverses

are those that are relatively prime to the modulus.

This turns out to be both a necessary and a sufficient

condition for the multiplicative inverse of a number to exist,

but can we prove this?

We need to prove this claim in both directions.

First, let's prove the sufficient claim.

Assume that we have a number a and a modulus m that are relatively prime.

Now, let's create a sequence containing m values by multiplying

a by every non-negative integer less than m. Now,

pick any two different multipliers x and y in this range.

Meaning that they are not congruent modular m. Can x

times a and y times a be in the same residue class?

This requires that the difference of x and y multiplied by a must be

a multiple of m. Since a and m do not contain any common prime factors,

this means that x minus y must be a multiple of

m. Since x and y are both strictly less than m,

there are difference lies strictly between minus m and plus m,

making the only possible multiple zero,

which requires x and y to be the same but we specify that they are different.

The conclusion is that no two members of our sequence can be in

the same residue class and since there are m members and m residue classes,

the Pigeonhole principle thus demands that every residue class is represented in

that sequence exactly once including the residue class containing one.

Whatever coefficient of a corresponds to this member is, by definition,

the multiplicative inverse of a mod m. Thus,

being relatively prime to the modulus is sufficient to have a multiplicative inverse.

Now, let's tackle the necessary claim.

When a and m are not relatively prime,

the GCD of a and m,

let's call it c, is greater than one.

This means that we can write a and m in terms of c and

two other integers b and n that are relatively prime,

otherwise c would not be the greatest common divisor.

The requirement that we had before on x minus y in terms of a and m reduces to

the same problem as before except in terms of

b and n. This is the same problem we just solved.

Meaning, that we know that as we multiply b by every non-negative integer less than n,

we produce all possible n residues including one.

To get back to the residues produced by multiplying

a by all of the non-negative integers less than m,

we just multiply all of the residues in this sequence by c. We can conclude two things.

First, we can only produce m divided by the GCD,

distinct residues, so each will be repeated that many times.

Second and most important,

one will not be among them.

In order for a number to have a multiplicative inverse in a certain modular world,

it is necessary for that number to be relatively prime to the modulus.

If you look back at our multiplication table for our mod-15 world and

look at say row a equal six for instance,

you'll notice that since the GCD of six and 15 is three,

the residues are all multiples of three and there are three instances of each.

How do we determine whether a and m are relatively prime?

We find the GCD of a and m and see if it is one.

How do we find the GCD of two integers?

By using the oldest-known mathematical algorithm,

namely the Euclidean algorithm,

which states that given two integers x and y with x greater than y,

the GCD of x and y is the same as the GCD of y and x reduced modular y.

Notice that the requirement that x be greater than y is merely for convenience.

We simply choose to put the largest value first.

And, again, for convenience,

we'll use the % sign to indicate modular reduction.

Let's see if 1024 and 2017 are relatively prime.

After just three iterations,

we have the GCD of something and one,

which is clearly one.

Thus, these two numbers are relatively prime.

If they hadn't been relatively prime,

then the residue would have become zero before becoming one and

the value just before that happened would be the GCD we are looking for.

Before we prove that the Euclidean Algorithm actually works,

let's look at the efficiency that it affords if it does work.

After two iterations, the larger of the two numbers goes from x to x%y.

What is the largest that x%y can be relative to x?

There are three possibilities.

The first is only worth noting in passing and that's if y is

equal to x over two then y%x is zero.

If y is less than x over two then

x%y is less than x over two since the residue is always less than y.

But if y is greater than x over two then the residue of x%y is simply x minus y,

and since y is greater than half of x,

the difference must be less than half of x.

Thus, if x is greater than y,

x%y is less than half of x.

So every two iterations of the algorithm,

we reduce the larger argument by at least a factor of two.

The furthest we can go is when we get to a GCD of one.

Thus, a limit on the number of iterations is on the order of

the base two logarithm of the larger of the two numbers.

Since a larger number is usually the modulus and

the base two logarithm is also the number of bits needed to represent a number.

The worst case performance for the Euclidean Algorithm

is generally twice the number of bits in the modulus,

but it almost always does much, much better.

Now, comes the question of whether or not it actually works?

As long as the claim is true that the GCD of two integers is identical to

the GCD of the smaller the integers

and the larger one reduced by the smaller then it works.

Let's call c the GCD of x and y.

This means that c divides both x and y.

Let's write x in terms of its residue and then solve for the residue,

r which is x%y.

Since c divides both x and y,

then it can be factored out of both terms.

Meaning that it also divides r and is thus a common factor of

all three and specifically of y and r. Now,

it may not be the GCD of y and r,

but we know that the GCD of y and r is at least this large.

So, the GCD of y and r is at least as large as the GCD of x and y.

Now, let's look at it the other way around.

If d is the GCD of y and r,

this means that d divides both y and r. Going back to our expression for x,

we can thus factor d out of both terms.

And therefore, d is a factor of both x and y.

But the GCD of x and y might be larger.

The only way that both of these inequalities can be

simultaneously satisfied is the GCD of

x and y is identically equal to the GCD of y and r. Remembering that r is x%y,

we have thus proven that the claim underlying the Euclidean Algorithm is true.

Personally, I find it remarkable that one of

the most efficient algorithms to find

the greatest common divisor is also the oldest algorithm known.

In fact, many of our bedrock algorithms in cryptography can

trace their roots to work that is centuries or even millennia old.

But perhaps this isn't so surprising.

People back then were just as intelligent as we are today.

But they lack the computing tools that we enjoy.

Hence, they had great motivation to devise ways to do things very efficiently by hand

and efficient hand algorithms generally lend

themselves to efficient programmatic implementations.

Recapping, in this lesson,

we learned the specifics of what a multiplicative inverse means in

a modular world and that they exist only for

numbers that are relatively prime to the modulus.

We also learn that the Euclidean Algorithm efficiently finds the GCD of two numbers,

which is the information we need to

know in order to determine if they are relatively prime.

Finally, we prove that the Euclidean Algorithm really does work.

Coming up next, we'll extend the Euclidean Algorithm and

use it to not only determine if a multiplicative inverse exists,

but also to find out what it is in a very efficient way.

Multiplicative Inverses

Mathematical Foundations for Cryptography

Conheça os instrutores