Explore
For Enterprise
Join for Free
Log In

artes y humanidades
Negocios
Ciencias de la Computación
Ciencia de Datos
Tecnología de información
salud
Matemáticas y Lógica
Desarrollo Personal
Ciencias Físicas e Ingeniería
Ciencias sociales
Aprendizaje de un idioma
Grados
Certificados

Explorar todo lo que Coursera tiene para ofrecer

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

Eulers Totient Function

Loading...

Mathematical Foundations for Cryptography

Sistema Universitario de Colorado

4.7 (62 calificaciones) | 2.7K estudiantes inscritos

Curso 2 de 4 en Introduction to Applied Cryptography Programa Especializado

Welcome to Course 2 of Introduction to Applied Cryptography. In this course, you will be introduced to basic mathematical principles and functions that form the foundation for cryptographic and cryptanalysis methods. These principles and functions will be helpful in understanding symmetric and asymmetric cryptographic methods examined in Course 3 and Course 4. These topics should prove especially useful to you if you are new to cybersecurity. It is recommended that you have a basic knowledge of computer science and basic math skills such as algebra and probability.

Revisiones

4.7 (62 calificaciones)

5 stars
44 ratings
4 stars
15 ratings
3 stars
3 ratings

De la lección

Modular Exponentiation

A more in-depth understanding of modular exponentiation is crucial to understanding cryptographic mathematics. In this module, we will cover the square-and-multiply method, Eulier's Totient Theorem and Function, and demonstrate the use of discrete logarithms. After completing this module you will be able to understand some of the fundamental math requirement for cryptographic algorithms. You will also have a working knowledge of some of their applications.

Eulers Totient Function12:14

Impartido por:

William Bahn
Lecturer
Richard White
Assistant Research Professor
Sang-Yoon Chang
Assistant Professor

Transcripción

In the previous lesson, we saw that the exponent in a modular expression lives in

a different modular world than the expression itself.

And that the relationship between the two is that the modulus for

the exponent is the totient of the modulus for the overall expression.

For completeness, we also saw that this is only valid when the base of the exponent

is relatively prime to the expression modulus.

We've also seen that the totient of a positive integer is equal to the number of

positive integers that are both less than, and relatively prime to, the number.

In this lesson, we'll see how to actually calculate the totient of a number,

other than by brute force enumeration,

of all positive integers that are less than and relatively prime to it.

The key lies in the fundamental theorem of arithmetic,

which you might recall states that every integer greater than

one can be written as a unique product of prime factors.

We can write this, very compactly, as a product expression,

in which each unique prime factor is raised to a corresponding exponent.

In theory, we could specify that the ith prime factor is the ith prime number.

Starting with 2 as being p1, 3, p2, 5 being p3, and so on,

up through the largest number that less than N.

Actually we only have to go up to the square root of n, but

that's a distinction we can ignore.

With any prime number that does not divide N, we just have a exponent of 0.

But in practice, there are almost always way too many prime factors, and

nearly all of them have 0 exponents.

So it's almost always understood that the product only includes the specific prime

numbers that divide N.

While the order of the prime factors doesn't matter,

we usually think of them being ordered from smallest to largest.

Without proof, let's look at the equation for the totient function.

This says that if I know the prime factors of N, that to find the totient,

I merely multiply N by a series of fractions, each of which is the ratio of

1 less than one of the prime factors, divided by that prime factor.

Notice that the prime factor is repeated, I don't need to know how

many times it's repeated, I only need to know the distinct prime factors of N.

Before we set out to prove this, let's look at a few special cases.

The simplest case is when our number is prime,

in this situation the totient is one less than the number.

This is actually quite obvious, since the fact that it is prime number

means that every positive integer less than it is relatively prime to it.

This result is sufficiently obvious that we can go ahead and

consider this case proven.

So for example, since 89 and 97 are both prime numbers,

the totient of 89 is 88, while the totient of 97 is 96.

What about when N is a product of prime numbers, without any repeats?

In that case, the product of all the prime factors that builds up

in the denominator is equal to N, cancelling it out.

The result is that the totient is the product of factors,

each equal to 1 less than the corresponding prime factor.

The fact that this is correct isn't immediately obvious, but

it's not too hard to reason out.

However the approach we will take in a little bit will make this result

an obvious special case.

Using the two prime numbers from our previous example,

the totient of 8633, which is the product of 89 and

97, is 8448, the product of 88 and 96.

The product of the first ten prime numbers,

which is all prime numbers less than 30, is 6 billion, and

a bunch of change, and its totient is little over 1 billion.

As you can see, our numbers can get very large, very quickly.

In fact the growth of the product of the first k primes

grows at a rate on the order of, but not quite as fast as,

the factorial function, which makes sense if you think about it.

What about a value of N that is an integer power of a prime number?

This means that we have a single prime factor, and so

our totient function reduces to one of several useful forms.

The one that is probably the most useful for us is the first one, since it will be

the one that is the easiest to prove when we get there in a bit.

Consider the totient of an integer power of 2,

it turns out that this is exactly half of the integer.

For instance, the totient of 1024, which is 2 to the 10th, is 512.

This make sense considering that if the only prime factor of a number is 2,

then any even number is not relatively prime to it, while every odd number is.

Hence, exactly half of the numbers less than 2 to the k are relatively

prime to it.

But don't fall into the trap of thinking that the totient of p to the k

is always p raised to the k-1, this is true only for p equals 2, and

that's just because 2 minus 1 is 1.

Let's consider 7 raised to the k, here we see that we pick up an extra

factor of 6, making the totient of 343 equal to 294.

Meaning that more than 85% of the numbers less than 343 are relatively prime to it.

Let's look at one final example,

before we turn to deriving the totient formula itself.

We can take our formula for

the totient function, and combine it with the fundamental theorem of arithmetic.

To get the result that the totient of an arbitrary number N can be expressed as

the product of totients of the individual prime powers that are the factors of N.

This is a consequence of the multiplicative property of the totient

function, which says that the totient of the product of two positive integers

is the product of the totient of the two integers.

But it only applies when the two integers are relatively prime.

However, we know it applies here, because if a and b are both prime powers

of different prime numbers, then by definition they are relatively prime.

By way of example, let's find the totient of 1100,

which has prime factors 2, 5, and 11.

Using the first form of the totient function we get a result of 400.

Not surprisingly,

this matches the result we get if we use the multiplicative property.

Now, which form is easier to use?

Well that depends on the situation, and

having both forms available gives us greater flexibility in doing our work.

As we now turn our attention to proving our formula for

the totient function, we see that we really only have to do two things.

First, we have to prove that the totient function is true for the special case of

a prime power, and second we have to prove that the multiplicative property is true.

Everything else are, then, simply special cases.

To prove our formula for the totient of a prime, p, raised to an integer power k.

We only need to subtract the number of integers less than N that are not

relatively prime to N, from the number of integers that are candidates.

Since any strictly positive integer x that is less than N is a candidate for

being relatively prime to N, the number of candidates is N-1.

Next, we need to identify the number of these integers that are not relatively

prime, meaning those values of x for which the gcd(x,N) is greater than 1.

Since N only has a single prime factor, if x is not relatively prime to N,

it must also have the same prime factor, meaning that x is a multiple of p.

The values that m can take on, and keep x within the allowed range,

is anything from 1, up to 1 less than the ratio of N/p,

since p times N/p is N, which is not a candidate.

Next, we just take the difference of these two quantities, and

by writing N in terms of p and k, we get the result that we expect.

Next we need to show that the totient function is multiplicative when finding

the totient of the product of two relatively prime numbers, P and Q.

Keep in mind that P and Q do not need to be prime themselves,

only relatively prime to each other.

There are a number of ways to do this proof, and

perhaps the most straightforward is using the Chinese Remainder Theorem.

But since we haven't gone through that yet,

we'll take a somewhat less elegant approach.

We know that the integers we need to consider are 1 through N-1,

giving us a total of N-1 integers that are candidates.

If it makes things more convenient for us, we can include either 0 or

N as a potential integer candidate, and

since neither is relatively prime to N, nothing changes.

So to make the bookkeeping easier,

we will include 0 by considering all of the nonnegative integers less than N.

By using two indices, lowercase p and q, that can take

on values from 0 up to, but not including, uppercase P and Q, respectively.

We can generate all of the allowed values of x as

a linear combination of our two indices.

If we tabulate this in a two-dimensional table,

where each row represents a particular value of p, and

each column represents a particular value of q, we get this.

Here's where things start to get a little tricky, so follow along closely.

If we choose a value of little p that is not relatively primed to big P,

then little p and

big P can both be written in terms of a common factor, which we'll call c.

Using our equation for x, in terms of little p and

little q, we can factor out c, which means that every integer on that

row is divisible by c, which is a factor of big P and hence a factor of N.

So none of the integers on that row count toward the totient of the N.

Therefore the only rows that we need to consider are the rows for

which little p is relatively prime to big P.

The number of such rows is, by definition, the totient of big P.

Now let's consider an arbitrary row, and

see how many of the integers on that row are relatively prime to big Q.

If you thought the last part was tricky, get ready for a bit of a mind bender.

As we go across each row, we add big P to the previous value.

Since we know that big P and big Q are relatively prime, and since we have big Q

columns, each integer in the row is in a different residue class, and

each residue class is present exactly once.

At this point you might be asking, how do we know this?

How do we know at don't have repeats of some residue classes, and

others that aren't represented at all?

We've actually done proofs like this before,

particularly in the lesson on the totient theorem.

The key is to assume that there does exist two integers on the same row,

that are in the same residue class.

And use the fact that the difference between any two integers has

to be a multiple of big P, combined with the fact that big P and

big Q relatively prime, to show that this results in a contradiction.

I'll leave doing that proof up to you,

since you can use the totient theorem lesson as a template.

Once we know that every integer on a row must be in a different residue class mod

Q, we can use the pigeonhole principle to establish that every residue class

is represented exactly once.

Once we are at that point, we can ask how many of those elements are relatively

prime to big Q, with the answer being that it is the totient of big Q.

Note that this is therefore the same number for every row.

Bringing this together, we have the totient of P

rows that contains any elements relatively prime to N, and

each of those rows contains the totient of Q such elements.

Thus the total number of elements is the torsion of P times the totient of Q,

thereby proving our multiplicative property of the totient function,

when the two factors are relatively prime.

We can easily extend this multiplicative property

to an integer that is the product of m relatively prime factors, by induction.

Since any partitioning of the factors into two groups

results in two overall factors of N, that are relatively prime.

This completes our proof of the formula for Euler's totient function.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados