A Note on the Computation of the Modular Inverse for Cryptography

Abstract

In literature, there are a number of cryptographic algorithms (RSA, ElGamal, NTRU, etc.) that require multiple computations of modulo multiplicative inverses. In this paper, we describe the modulo operation and we recollect the main approaches to computing the modulus. Then, given a and n positive integers, we present the sequence ${\left(z_j\right)}_{j\ge 0}$, where $z_j=z_{j-1}+a{\beta }_j-n$, $a<n$ and $\mathrm{GCD}(a,n)=1$. Regarding the above sequence, we show that it is bounded and admits a simple explicit, periodic solution. The main result is that the inverse of a modulo n is given by $a^{-1}=\lfloor im\rfloor +1$ with $m=n/a$. The computational cost of such an index i is $\mathcal{O}\left(a\right)$, which is less than $\mathcal{O}(nlnn)$ of the Euler’s phi function. Furthermore, we suggest an algorithm for the computation of $a^{-1}$ using plain multiplications instead of modular multiplications. The latter, still, has complexity $\mathcal{O}\left(a\right)$ versus complexity $\mathcal{O}\left(n\right)$ (naive algorithm) or complexity $\mathcal{O}(lnn)$ (extended Euclidean algorithm). Therefore, the above procedure is more convenient when $a<<n$ (e.g., $a<lnn$).

1. Introduction

The modulo operation returns the remainder of a division, after one number is divided by another number called “modulus”. In other terms, given two positive numbers a and n, $amodn$ is the remainder of the Euclidean division of the dividend a by the divisor n.

A modular multiplicative inverse of an integer a is an integer x such that the product $ax$ is congruent to 1 with respect to the modulus n, and it is denoted as

$$ax\equiv 1(modn).$$

Modulo n is an equivalence relation. The equivalence class of the integer a, denoted by ${\overline{a}}_n$, is the set $\{\dots ,a-2n,a-n,a,a+n,a+2n,\dots \}$. This set, consisting of all the integers congruent to a modulo n, is called congruence class or residue class of the integer a modulo n.

If a has an inverse modulo n, then there are an infinite number of solutions that belong to the congruence class with respect to the said modulus. In addition, any integer that is congruent to a will have any element of x’s congruence class as a modular multiplicative inverse. In other terms, denoted with the symbol ${·}_n$, the multiplication of equivalence classes modulo n, the modulo multiplicative inverse of the congruence class $\overline{a}$ is the congruence class $\overline{x}$ such that:

$$\overline{a}{·}_n\overline{x}=\overline{1}.$$

This multiplication is the analogue of the multiplicative inverse in the set of real numbers where numbers are replaced by congruence classes. Therefore, a fundamental use of this operation is to solve (whenever possible) linear congruences of the form

$$ax\equiv b(modn).$$

(1)

The solution of Equation (1) has practical applications in the field of public-key cryptography and, in particular, in the Rivest–Shamir–Adleman (RSA) algorithm [1] where encryption and decryption are performed by using a pair of large prime numbers that are multiplicative inverses with respect to a selected modulus.

When invented, RSA was considered one of the most effective algorithms because there was no key exchange in the encryption and decryption processes. In the RSA algorithm, the strength depends on the factorization problem that is NP complete [2] and the key length was the only way to protect systems. However, the RSA key is broken from time to time due to the development of both software and computer speed. To counter that, developers have increased key length from one time to another to maintain a high security and privacy to systems that are protected by the RSA. Other countermeasures vary from using multiple public and private keys [3] to enhance and secure the RSA public key cryptosystem (ESRPKC) algorithm using the Chinese remainder theorem [4], from the use of a pair of random numbers and their modular multiplicative inverse [5] to the Cuckoo Search Optimization (CSA) algorithm for securing data integrity in the cloud [6]. For a survey, see Mumtaz et al. [7].

As mentioned, cryptographic algorithms rely on multiple computations of modulo multiplicative inverses. Examples are the RSA cryptographic algorithm by [8,9], RSA with digital signature [10], ElGamal cryptocol [11]; encryption and decryption schemes based on extraction of square roots [12], NTRU cryptosystem [13], modular multiplicative inverse (MMI) for cryptanalysis of public-key cryptographic protocols [14], etc. Recently, Boolean functions have gained attraction because of some interesting properties from a cryptographic point of view such as “nonlinearity, propagation criterion, resiliency, and balance” [15]. However, following similar research on RSA cryptographic algorithms, we focused on the problem of encrypting/decoding information based on the use of the vector-modular methods. For example, Yakymenko et al. [16] suggest a modular exponential to “replace the complex operation of modular multiplication with the addition operation, which increases the speed of the RSA cryptosystem”. In our case, instead, we investigate the properties of the sequence ${\left(z_j\right)}_{j\ge 0}$ in Definition 1, which we show to be useful for computing the inverse modulo. In particular, for the above sequence, we show that it is bounded and admits a simple explicit, periodic solution. Next, we illustrate that the inverse of a modulo n is given by $a^{-1}=\lfloor im\rfloor +1$ with $m=n/a$. The advantage is that the computational cost of such an index i is $\mathcal{O}\left(a\right)$ versus $\mathcal{O}(nlnn)$ of the Euler’s phi function. Finally, we suggest an algorithm for calculating $a^{-1}$ using plain multiplications instead of modular multiplications. The latter, again, has complexity $\mathcal{O}\left(a\right)$ versus complexity $\mathcal{O}(lnn)$ of the extended Euclidean algorithm. Therefore, the above procedure is more convenient when $a<<n$ (e.g., $a<lnn$). Those results are new in literature.

This work is divided as follows: Section 2 describes the main approaches to the computation of modulus. Section 3 illustrates the sequence ${\left(z_j\right)}_{j\ge 0}$ along with some of its properties. Section 4 presents the conclusions.

2. Main Approaches to the Computation of Modulus

In the following, we describe the most common methods to compute the inverse modulo n.

2.1. Naive Method (Recursive Multiplications)

This is the simplest way to compute the inverse of a positive integer a, modulo n, with $a<n$ and greatest common divisor $\mathrm{GCD}(a,n)=1$. We have to multiply a by all the elements of ${\mathbb{N}}_n^{*}=\{1,2,\dots ,n-1\}$ and the first of them which gives a product equal to 1 (modulo n) will be the inverse of a. The complexity in this case is $\mathcal{O}\left(n\right)$.

Example 1.

To find the inverse of $a=6$ modulo $n=7$, we have to multiply a by every element of ${\mathbb{N}}_7^{*}=\{1,2,\dots ,6\}$, i.e.,

$$1·6=6(mod7),2·6=12\equiv 5(mod7),3·6=18\equiv 4(mod7),$$

$$4·6=24\equiv 3(mod7),5·6=30\equiv 2(mod7),6·6=36\equiv 1(mod7).$$

Therefore, $a^{-1}=6$ modulo 7.

2.2. Euler’s Phi Function

The following approach was introduced in modern terms by Gauss with reference to Euler (even though the method has been reported before [17]). Given a positive integer n, the Euler’s phi function $\Phi \left(n\right)$ (or Euler’s totient function) counts the number of primes, up to n, which are relatively prime to n. It can be expressed as

$$\Phi \left(n\right)=n\prod _{p_j|n}\left(1-\frac{1}{p_j}\right),$$

with $p_j$’s being the primes dividing n. Given a positive integer a, with $a<n$ and $\mathrm{GCD}(a,n)=1$, one has

$$a^{\Phi \left(n\right)}\equiv 1(modn)$$

due to the well-known Fermat’s little theorem. The above relation provides an explicit formula for the inverse of a modulo n that is

$$a^{-1}=a^{\Phi \left(n\right)-1}.$$

(2)

However, the calculation of $\Phi \left(n\right)$ is equivalent to doing the prime factorization of n, hence the complexity of Formula (2) is $\mathcal{O}(nlnn)$. Thus, despite (2) giving a closed formula, it is less convenient than a recursive algorithm (like those of Section 2.1 and Section 2.3).

Example 2.

To compute the inverse of 23 modulo 36 through Formula (2), one has

$$\Phi \left(36\right)=36\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=12,$$

and ${23}^{12-1}\equiv 11(mod36)$, i.e., ${23}^{-1}\equiv 11(mod36)$.

2.3. Extended Euclidean Algorithm

One of the ancient methods to compute the GCD between two integers $a,b$, with $a>b$, is given by the Euclidean algorithm. It is based on the following property: if both a and b divide a same integer c, then also their difference $a-b$ divides c. The algorithm states that $\mathrm{GCD}(a,b)=b$ if the difference $d=a-b$ is equal to b; otherwise, $a,b$ are replaced by $max\{a-b,b\}$ and $min\{a-b,b\}$, respectively, and the previous procedure is repeated by computing the new difference d.

Table 1. Pseudocode of the Euclidean algorithm (repeated differences).

1. Initialize $i=0$, $a_i=a,b_i=b$ and $Flag=0$;

2.while$Flag=0$

3. set $d_i=a_i-b_i$;

4.. if $a_i-b_i=b_i$

5. set $Flag=1$;

6.else set $i=i+1$, $a_i=max\{a_{i-1}-b_{i-1},b_{i-1}\}$, and $b_i=min\{a_{i-1}-b_{i-1},b_{i-1}\}$;

7.end

8.end

9. set $\mathrm{GCD}(a,b)=d_i$.

describes the pseudocode of the algorithm.

An interesting extension of such method works with repeated divisions instead of the repeated differences. By computing the following quotients $q_i$ and remainders $r_i$,

$$a=b·q_0+r_0,$$

$$b=r_0·q_1+r_1,$$

$$r_0=r_1·q_2+r_2,$$

$$⋮$$

$$r_{i-1}=r_i·q_{i+1}+r_{i+1},$$

$$⋮$$

it is possible to say that $\mathrm{GCD}(a,b)$ is the last non-zero remainder $r_i$. The complexity of this method is $\mathcal{O}(lnn)$. The pseudocode of this procedure is reported in

Table 2. Pseudocode of the Euclidean algorithm (repeated divisions).

1. Initialize $i=0$, $a_i=a,b_i=b$, and let $q_i$, $r_i$ be the quotient and the remainder of $a_i/b_i$, respectively;

2.if $r_0=0$

3. let $\mathrm{GCD}(a,b)=b$;

4.else

5.while $r_i\ne 0$

6. set $i=i+1$, $a_i=b_{i-1}$,$b_i=r_{i-1}$, and let $q_i$, $r_i$ be the quotient and the remainder of $a_i/b_i$, respectively;

7.end

8. set $\mathrm{GCD}(a,b)=r_{i-1}$.

9.end

.

The above method allows us to compute the inverse modulo n through the so-called Bézouts’s identity which states that there exist two integer $s,t$ such that

$$\mathrm{GCD}(a,b)=s·a+t·b.$$

The numbers $s,t$ can be computed from the quotients $q_i$ ($i\ge 0$), by reversing the order of the equations in the Euclidean algorithm (with repeated divisions). Beginning with the last non-zero remainder $r_i$, we can write

$$\mathrm{GCD}(a,b)=r_i=r_{i-2}-q_i·r_{i-1}.$$

The quantity $r_{i-1},r_{i-2}$ may be likewise expressed in terms of their quotients and preceding remainders, i.e.,

$$r_{i-1}=r_{i-3}-q_{i-1}·r_{i-2},$$

$$r_{i-2}=r_{i-4}-q_{i-2}·r_{i-3}.$$

Substituting these formulas into the first equation yields $\mathrm{GCD}(a,b)$ as a linear sum of $r_{i-3},r_{i-4}$. The process of substituting remainders by formulas involving their predecessors can be continued until a and b are reached, as follows:

$$⋮$$

$$r_2=r_0-q_2·r_1,$$

$$r_1=b-q_1·r_0,$$

$$r_0=a-q_0·b.$$

After all the remainders $r_i$ ($i\ge 0$) have been replaced, the final equation expresses $\mathrm{GCD}(a,b)$ as the linear combination $s·a+t·b$.

In the special case that $\mathrm{GCD}(a,b)=1$, then t is the multiplicative inverse of b, modulo a, or, equivalently, s is the multiplicative inverse of a, modulo b.

The pseudocode of this method is shown in

Table 3. Pseudocode of the inverse modulo n (through the extended Euclidean algorithm).

1. Compute $q_j,r_j$, $-2\le j\le i$ (where $r_{-1}=a,r_{-2}=n$ and $r_i=1$ is the last remainder) by the extended Euclidean algorithm (see Table 2) between a and n;

2.for $j=i:-1:-2$

3. write $r_j$ as linear combination of $r_{j-1}$ and $r_{j-2}$;

4.end

5. set $a^{-1}$ equal to the coefficient multiplied by a in the final recursive relation.

.

Example 3.

Consider $a=27$ and $n=392$. Obviously, $\mathrm{GCD}(27,392)=1$. The extended Euclidean algorithm gives

$$392=27·14+14,$$

$$27=14·1+13,$$

$$14=13·1+1.$$

By rewriting the next steps backward, we obtain

$$1=14-13·1=14-(27-14·1)=2·14-2=2(392-27·14)-27=2·392+27(-29),$$

where $-29\equiv 363(mod392)$. Hence, we can conclude that ${27}^{-1}\equiv 363(mod392)$.

3. The Sequence ${\mathit{z}}_{\mathit{j}}$: Definition and Properties

In this section, given a and n positive integers, we define the sequence ${\left(z_j\right)}_{j\ge 0}$, where $z_j=z_{j-1}+a{\beta }_j-n$, $a<n$ and $\mathrm{GCD}(a,n)=1$. For the said sequence, we illustrate some properties and results useful to the computation of the inverse modulo.

3.1. Definitions and Main Results

Definition 1.

Given two positive integers $a,n$ with $a<n$ and $\mathrm{GCD}(a,n)=1$, define the sequence ${\left(z_j\right)}_{j\ge 0}$ as follows:

$$z_j=z_{j-1}+a{\beta }_j-n(j\ge 1),$$

(3)

starting from $z_0=0$, with

$$\left\{\begin{array}{c}{\beta }_1=M\hfill \\ {\beta }_j=⌊\frac{n-z_{j-1}}{a}⌋+1j\ge 2,\hfill \end{array}\right.$$

(4)

with M being the ceiling part of $m:=n/a$.

Observe that ${\beta }_j$’s represent the (ceiling) difference between n and $z_j$ relative to a.

Next, the Proposition gives an explicit expression for the sequence ${\left(z_j\right)}_{j\ge 0}$.

Proposition 1.

The explicit form of the sequence ${\left(z_j\right)}_{j\ge 0}$ defined in (3) is given by

$$z_j=a\sum _{h=1}^j{\beta }_h-jn.$$

(5)

Proof. 

The proof is immediate, indeed starting from definition (3), one has

$$z_1=a{\beta }_1-n,$$

$$z_2=z_1+a{\beta }_2-n=a({\beta }_1+{\beta }_2)-2n,$$

$$⋮$$

$$z_j=z_{j-1}+a{\beta }_j-n=a\sum _{h=1}^j{\beta }_h-jn.$$

□

The following Proposition gives an explicit, and more convenient, expression for the sequence ${\left({\beta }_j\right)}_{j\ge 1}$.

Proposition 2.

Let ${\left({\beta }_j\right)}_{j\ge 1}$ be the sequence defined in (4). For any $j\ge 1$, it holds that

$${\beta }_j=\lfloor jm\rfloor -\lfloor (j-1)m\rfloor ,$$

(6)

with $m=n/a$. Moreover,

$$\sum _{h=1}^j{\beta }_h=\lfloor jm\rfloor +1.$$

(7)

Proof. 

First of all, observe that (6) implies that the partial sum is (7), since

$$\sum _{h=1}^j{\beta }_h=\sum _{h=1}^j\left(\lfloor hm\rfloor -\lfloor (h-1)m\rfloor \right)=$$

$$\lfloor jm\rfloor -\lfloor (j-1)m\rfloor +\lfloor (j-1)m\rfloor -\lfloor (j-2)m\rfloor +\dots +\lfloor 3m\rfloor -\lfloor 2m\rfloor +\lfloor 2m\rfloor -\lfloor m\rfloor +M=$$

$$\lfloor jm\rfloor -\lfloor m\rfloor +M=\lfloor jm\rfloor +1,$$

being $\lfloor m\rfloor =M-1$.

Formula (6) can be proved by induction on j. Indeed, if $j=2$, by relation (3), one has

$${\beta }_2=⌊\frac{n-z_1}{a}⌋+1=⌊\frac{n-aM+n}{a}⌋+1=\lfloor 2m\rfloor -M+1=\lfloor 2m\rfloor -\lfloor m\rfloor .$$

Now, if (6) holds true up to the index $(j-1)$, then, by relations (5) and (7), it is easy to see that

$${\beta }_j=⌊\frac{n-z_{j-1}}{a}⌋+1=⌊\frac{n-a{\sum }_{h=1}^{j-1}{\beta }_h+(j-1)n}{a}⌋+1=\lfloor jm\rfloor -\lfloor (j-1)m\rfloor -1+1=$$

$$\lfloor jm\rfloor -\lfloor (j-1)m\rfloor .$$

□

Corollary 1.

The sequence ${\left(z_j\right)}_{j\ge 0}$ defined in (3) can be rewritten as

$$z_j=a\left(\lfloor jm\rfloor +1\right)-jn(j\ge 1),$$

(8)

with $z_0=0$.

Proof. 

The assertion results by combining relations (5) and (7). □

Now, we are able to state the main results of this section.

Theorem 1.

Consider two positive integers $a,n$ with $a<n$ and $\mathrm{GCD}(a,n)=1$. Let ${\left(z_j\right)}_{j\ge 0}$ be the sequence defined in (3) and $i\ge 1$ the index such that $z_i=1$. Then, due to (8), the inverse of a modulo n is given by

$$a^{-1}=\lfloor im\rfloor +1,$$

(9)

with $m=n/a$.

Proof. 

Since $\mathrm{GCD}(a,n)=1$, from the Bézouts’s identity, there exists an index $i\ge 1$ such that $z_i=1$. Indeed, without loss of generality, there exist a pair of positive integers $g,i$ such that

$$1=ga-in.$$

Fixing i, from the above equation, we obtain

$$g=im+\frac{1}{a}=\lfloor im\rfloor +{\phi }_i+\frac{1}{a}=\lfloor im\rfloor +1,$$

(10)

where we denote by

$${\phi }_j=jm-\lfloor jm\rfloor (j\ge 0),$$

(11)

the fractional part function of $jm$. In particular, the last equality of (10) holds true because both g and $\lfloor im\rfloor$ are positive integers. Thus, as ${\phi }_i$ and $\frac{1}{a}$ belong to $(0,1)$ we can say that ${\phi }_i+\frac{1}{a}$ must be equal to 1. Hence,

$$1=a\left(\lfloor im\rfloor +1\right)-in,$$

and, more specifically,

$$a\left(\lfloor im\rfloor +1\right)\equiv 1(modn),$$

which implies

$$a^{-1}\equiv \lfloor im\rfloor +1(modn),$$

where the last equality comes from Proposition 2. Finally, notice that $\lfloor im\rfloor +1<n$ (see Corollary 2) and this concludes the proof. □

3.2. Properties of the Sequence $z_j$

To better understand the nature of the sequence ${\left(z_j\right)}_{j\ge 0}$, we illustrate the following properties.

Proposition 3.

The sequence ${\left(z_j\right)}_{j\ge 1}$ defined in (3) is periodic with a period equal to a.

Proof. 

For any $j\ge 1$, we have to prove that $z_{j+a}=z_j$. Let us proceed by induction on j. If $j=1$,

$$z_{1+a}=a(\lfloor (1+a)m\rfloor +1)-(1+a)n=aM+an-n-an=z_1.$$

Now, if the assertion holds true for $(j-1)$, from relation (3), we may write

$$z_{j+a}=z_{(j-1)+a}+a{\beta }_{j+a}-n=z_{j-1}+a\left(\lfloor (j+a)m\rfloor -\lfloor (j+a-1)m\rfloor \right)-n,$$

where

$$\lfloor (j+a)m\rfloor -\lfloor (j+a-1)m\rfloor =\lfloor jm+n\rfloor -\lfloor (j-1)m+n\rfloor =\lfloor jm\rfloor -\lfloor (j-1)m\rfloor .$$

Therefore, we get

$$z_{j+a}=z_{j-1}+a\left(\lfloor jm\rfloor -\lfloor (j-1)m\rfloor \right)-n=z_{j-1}+a{\beta }_j-n=z_j.$$

□

Corollary 2.

The sequence ${\left(z_j\right)}_{j\ge 0}$ defined in (3) is less than n. In particular, the modular inverse defined in (9) is also less than n.

Proof. 

From Proposition 3, we have to prove that $z_j<n$ for any $0\le j\le a$. For this purpose, distinguish the following three cases:

(i)

The $j=0$ is trivial.

(ii)

If $0<j<a$, we have

$$z_j=a(jm-{\phi }_j+1)-jn=a(1-{\phi }_j)<a<n.$$

(iii)

The case $j=a$ may be proved analogously to ii).

Finally, it is clear that the modular inverse defined in (9), i.e., $\lfloor im\rfloor +1$, is less than n since $i\le a-1$. □

To see what was observed up to now, we shall consider a numerical example.

Example 4.

Choose $a=131$ and $n=621$. Obviously, $\mathrm{GCD}(a,n)=1$ that guarantees the existence of $a^{-1}$. It is obtained by $i=27$ and

$${131}^{-1}=⌊27·\frac{621}{131}⌋+1=128,$$

modulo 621. Figure 1 shows the behavior of the sequence ${\left(z_j\right)}_{j\ge 0}$. In particular, the blue line denotes the series when $1\le j\le 203$, while those colored in red represent the entire sequence from two consecutive unitary $z_i$’s (circled in red), i.e., $i=27$ and $i=158$. As proved, the series ${\left(z_j\right)}_{j\ge 1}$ is periodic with a period equal to 131 and any value less than 621.

3.3. Limitations and Future Challenges

A limitation of the proposed approach is that we have left the problem of determining the index i unsolved. In fact, by virtue of Theorem 1, we need to compute $z_i=1$, such that

$$a\left(\lfloor im\rfloor +1\right)-in=1.$$

(12)

Observe that $\lfloor im\rfloor =im-{\phi }_i$, where ${\phi }_i$ is defined by (11), and can be easily computed, as follows.

Proposition 4.

Let i be the solution of Equation (12); then, one has

$${\phi }_i=\frac{a-1}{a}.$$

(13)

Proof. 

Equation (12) gives

$$1=a\left(\lfloor im\rfloor +1\right)-in=a\left(im-{\phi }_i+1\right)-in=a(1-{\phi }_i),$$

which implies Formula (13). □

Example 5.

With reference to Example 4, we have $m=4.7405$ and $i=27$. By computing ${\phi }_i$ directly from i, we obtain the value $0.9924$, which coincides with that given by the a priori Formula (13).

The knowledge of ${\phi }_i$ jointly with the periodicity information given by Proposition 4 suggests to solve the problem (12) by the simple algorithm described in

Table 4. Pseudocode of a simple algorithm to solve (12).

1. Initialize $j=0$, $z_j=0$ and set $m=n/a$, $\phi =(a-1)/a$;

2.while$z_j\ne 1$

3. set $z_j=a(jm-\phi +1)-jn$ and $j=j+1$;

4.end

5. set $i=j-1$ and $a^{-1}=a(im-\phi +1)$.

.

Notice that the complexity of the algorithm just shown in Table 4 is $\mathcal{O}\left(a\right)$. Therefore, the above procedure is more convenient when $a<<n$ (e.g., $a<lnn$). In addition, when a is close to n, the algorithm in Table 4 is still better compared to the naive algorithm in Table 1 (since it involves simple multiplications instead of modular multiplications). Furthermore, Equation (9) represents a closed formula for the modular inverse, as does Equation (2), where the computational cost of the index i is $\mathcal{O}\left(a\right)$. This is less than $\mathcal{O}(nlnn)$ of the Euler’s phi function. These features are a clear advantage when n is large.

4. Conclusions

In this article, we have introduced the modulo operation and described the most common methods for computing the inverse modulo n. Hence, we have shown that, to solve the problem in Equation (12) through a closed formula, we need to investigate the properties of the sequence ${\left(z_j\right)}_{j\ge 0}$. The fact that the sequence ${\left(z_j\right)}_{j\ge 0}$ admits a simple explicit form which is periodic (for $j\ge 1$) helps us in understanding the features of ${\left(z_j\right)}_{j\ge 0}$. In particular, we have shown that the computational cost is $\mathcal{O}\left(a\right)$ versus $\mathcal{O}(nlnn)$ of Euler’s phi function. In terms of implementation, we suggest an algorithm for calculating $a^{-1}$ using plain multiplications instead of modular multiplications. From a practical point of view, this approach is quite convenient because it has complexity $\mathcal{O}\left(a\right)$ compared to $\mathcal{O}(lnn)$ of the extended Euclidean algorithm. This result is related to the characteristics of i, and, consequently, of $a^{-1}$. Next, research will focus on the determination of the index i such that $z_i=1$.