Unfortunately, the factoring problem cannot be used directly for asymmetric cryptographic schemes. However, we can use a more complex but related problem to this effect: the RSA problem.

To understand the RSA problem, we will need to understand a number of theorems and propositions from number theory. These are presented in this section in three subsections: (1) the order of N, (2) invertibility modulo N, and (3) Euler’s theorem.

Some of the material in the three subsections has already been introduced in Chapter 3. But I will here restate that material for convenience.

An integer is coprime or a relative prime with an integer , if the greatest common divisor between them is 1. While 1 is by convention not a prime number, it is a coprime of every integer (as is ).

For instance, consider the case when and . These are clearly coprimes. The greatest integer which divides into both 18 and 37 is 1. By contrast, consider the case when and . These are clearly not coprimes. Both numbers are divisible by 2, which is greater than 1.

We can now define the order of as follows. Suppose that is an integer greater than 1. The order of N is, then, the number of all coprimes with such that for each coprime , the following condition holds: .

For instance, if , then 1, 5, 7, and 11 are the only coprimes that meet the requirement above. Hence, the order of 12 is equal to 4.

Suppose that is a prime number. Then any integer smaller than but greater or equal to 1 is coprime with it. This includes all the elements in the following set: . Hence, when is prime, the order of is . This is stated in proposition 1, where denotes the order of .

Proposition 1. when is prime

Suppose that is not prime. You can, then, calculate its order using Euler’s Phi function. While calculating the order of a small integer is relatively straightforward, Euler’s Phi function becomes particularly important for larger integers. The proposition of Euler’s Phi function is stated below.

Theorem 2. Let equal , where the set consists of all the distinct prime factors of and each indicates how many times the prime factor occurs for . Then,

Theorem 2 shows that once you have broken down any non-prime into its distinct prime factors, it is easy to calculate the order of .

For instance, suppose that . This is clearly not a prime number. Breaking down into its prime factors yields the expression: . According to Euler’s Phi function, the order of is then as follows:

Suppose next that is a product of two primes, and . Theorem 2 above, then, states that the order of is as follows:

This is a key result for the RSA problem particularly, and is stated in Proposition 2 below.

Proposition 2. If is the product of two primes, and , the order of is the product .

To illustrate, suppose that . This integer can be factored into two primes, namely 7 and 17. Hence, Euler’s Phi function suggests that the order of 119 is as follows:

In other words, the integer 119 has 96 coprimes in the range from 1 until 119. In fact, this set includes all integers from 1 until 119, which are not multiples of either 7 or 17.

From here on, let’s denote the set of coprimes that determines the order of as . For our example where , the set is far too large to list completely. But some of the elements are as follows:

We can say that an integer is invertible modulo N, if there exists at least one integer such that . Any such integer is referred to as an inverse (or multiplicative inverse) of given reduction by modulo .

Suppose, for example, that and . There are many integers by which you can multiply 5, so that . Consider, for instance, the integers 20 and 31. It is easy to see that both these integers are inverses of 5 for reduction modulo 11.

While 5 has many inverses reduction modulo 11, you can show that only a single positive inverse of 5 exists which is less than 11. In fact, this is not unique to our particular example, but a general result.

Proposition 3. If the integer is invertible modulo , it must be the case that exactly one positive inverse of is less than . (So, this unique inverse of must come from the set ).

Let's denote the unique inverse of from Proposition 3 as . For the case when and , you can see that , given that .

Notice that you can also obtain the value 9 for in our example by simply reducing any other inverse of by modulo 11. For instance, . So whenever an integer is invertible modulo , then must also be invertible modulo .

It is not necessarily the case that an inverse of exists reduction modulo . Suppose, for example, that and . There is no , or any specifically, such that . This is because any value of will always produce a multiple of 2, so no division by 8 can ever yield a remainder that equals 1.

How exactly do we know if some integer has an inverse for a given ? As you may have noticed in the example above, the greatest common divisor between 2 and 8 is higher than 1, namely 2. And this is actually illustrative of the following general result:

Proposition 4. An inverse exists of an integer given reduction modulo , and specifically a unique positive inverse less than , if and only if the greatest common divisor between and is 1 (that is, if they are coprimes).

For the case when and , we concluded that , given that . It is important to note that the reverse is also true. That is, when and , it is the case that .

Before moving onto the RSA problem, we need to understand one more crucial theorem, namely Euler’s theorem. It states the following:

Theorem 3. Suppose two integers and are coprimes. Then, .

This is a remarkable result, but a little confusing at first. Let's turn to an example to understand it.

Suppose that and . These are indeed coprimes as Euler’s theorem requires. We know that the order of 7 equals 6, given that 7 is a prime number (see Proposition 1).

What Euler’s theorem now states is that must be equal to . Below are the calculations to show that this is indeed true.

The integer 7 divides into 15,624 a total of 2,233 times. Hence, the remainder of dividing 16,625 by 7 is 1.

Next, using Euler’s Phi function, Theorem 2, you can derive Proposition 5 below.

Proposition 5. for any positive integers and .

We will not show why this is the case. But merely note that you have already seen evidence of this proposition by the fact that when and are primes, as stated in Proposition 2.

Euler’s theorem in conjunction with Proposition 5 has important implications. See what happens, for instance, in the expressions below, where and are coprimes.

Hence, the combination of Euler’s theorem and Proposition 5 allow us to simply calculate a number of expressions. In general, we can summarize the insight as in Proposition 6.

Proposition 6.

Now we have to put everything together in a tricky last step.

Just as has an order which includes the elements of the set , we know that the integer must in turn also have an order and a set of coprimes. Let's set . Then we know that there is also a value for and a set of coprimes .

Suppose that we now select an integer from the set . We know from Proposition 3 that this integer only has one unique positive inverse less than . That is, has one unique inverse from the set . Let's call this inverse . Given the definition of an inverse, this means that .

We can use this result to make a statement about our original integer . This is summarized in Proposition 7.

Proposition 7. Suppose that . Then for any element of the set it must be the case that .

We now have all the number theoretic results needed to state the RSA problem clearly.