Keywords:

The hardware implementation of modular exponentiation for very large integers is a well-known topic in digital arithmetic. An effective approach for obtaining parallel and carry-free implementations consists in using the Montgomery exponentiation algorithm and executing the necessary operations in RNS. Two efficient methods for performing the RNS Montgomery exponentiation have been proposed by Kawamura et al. and by Bajard and Imbert. The above approaches mainly differ in the algorithm used for implementing the base extension. This paper presents a modified RNS Montgomery exponentiation algorithm, where several multiplications are moved outside the main execution loop and replaced by an effective pre-processing stage producing a significant saving on the overall delay. Since the proposed modification can be applied to both the above algorithms, two versions are specifically discussed.

In order to evaluate the effect of the designed modification, the implementations by Kawamura et al. and by Bajard and Imbert. are selected as a reference, and a sharp comparison between the common part of these algorithms and the proposed approach is carried out. This analysis focuses on the arithmetic-algorithmic level, and it is aimed at quantifying the specific weight of each multiplication operation, by taking into account the impact of the number of parallel multipliers in each RNS cell and the level of pipelining. The analysis shows that the application of the proposed approach could produce a consistent reduction in the number of execution steps, thanks to the removal of the most computationally expensive multiplications. The improvement is particularly relevant for fast implementations, as the reduction factor increases with the number of pipeline stages and parallel multipliers per arithmetic cell.

Since the base extension methods used in the two reference algorithms require different arithmetic cells, an analysis at the architecture level is also carried out, with the aim of further characterizing the improvement provided by the proposed approach. Thus, a cell architecture based on work by Kawamura et al. is presented and analyzed at first. Then, a novel architecture adapted to the algorithm by Bajard and Imbert. is designed. The overall comparison shows that with the proposed approach, a 18.5% speedup can be achieved for an implementation over 1024 bits, without any significant area overhead.

I. INTRODUCTION

The computation of the Montgomery exponentiation (ME) in the Residue Number System (RNS) [START_REF] Szab | Residue Arithmetic and Its Applications to Computer Technology[END_REF] allows limiting the delay due to carry propagation and reaching a high degree of parallelism [START_REF] Szerwinski | Exploiting the power of GPUs for asymmetric cryptography[END_REF]. This approach mainly requires the execution of a set of Montgomery multiplications (MMs) [START_REF] Montgomery | Modular multiplication without trial division[END_REF]. However, in RNS, some operations (e.g. division, comparison, modulo) are natively difficult to execute. Hence, several approaches have been proposed in order to fully exploit the potential of RNS for modular exponentiation, by minimizing the impact of related drawbacks.

A fast RNS ME algorithm has been presented in [START_REF] Posch | Modulo reduction in residue number systems[END_REF]. This approach requires two Base Extensions (BEs) for each RNS MM. The algorithm employed for performing BE, that has been presented in [START_REF]Base extension using a convolution sum in residue number systems[END_REF], is particularly expensive from the computational point of view. It executes BE through iterated approximations.

The approximation is correct in the majority of the cases, and when there is an offset, it is corrected.

In [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], Kawamura et al. proposed a RNS ME technique applied to RSA, with an improved BE algorithm.

The new BE is characterized by a summation that provides a result modulo a small multiple of the base, which is corrected after the sum of each element. The proposed approach has been detailed in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF], where an architecture has also been presented.

In [START_REF] Bajard | An RNS Montgomery modular multiplication algorithm[END_REF], Bajard et al. proposed an implementation of the MM based on both the RNS and the Mixed Radix Number System (MRS), where the MRS corresponds to a weighted system associated with the RNS. Then, in [START_REF]Modular multiplication and base extensions in residue number systems[END_REF], the same authors proposed a Montgomery multiplication method fully implemented in RNS. This approach employs an approximated BE and the algorithm proposed in [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF], where the result is approximated and corrected by using an extra modulo. Finally in [START_REF] Bajard | A full RNS implementation of RSA[END_REF], Bajard and Imbert detailed the application of the previous ME approach in the context of RSA.

The RNS MM has also been studied in different contexts, out of the exponentiation. In [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over Fp[END_REF], an implementation for elliptic curve cryptography on FPGA is presented. This implementation employs the algorithm proposed in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] with some pre-computations suitable to the particular architecture presented in the paper. In [START_REF] Szerwinski | Exploiting the power of GPUs for asymmetric cryptography[END_REF], an implementation of RNS MM on GPU is presented. Experimental results achieved in the above context show that the algorithm described in [START_REF]Modular multiplication and base extensions in residue number systems[END_REF] provides the best performance. This paper proposes a modified ME algorithm for RNS. The novelties of the algorithm are in the pre-processing stage, which is used to reduce the number of multiplications performed in the loop of the exponentiation algorithm. It is worth observing that, even though in the specific case the ME is considered, the basic approach used here is more general and can be easily applied in other contexts. In particular, the analysis of the designed pre-processing method for generic modular multiplication is presented in [START_REF] Blind | Pre-processing in RNS Montgomery multiplication[END_REF].

The differences with respect to previous approaches consist in the values that are pre-computed, and in the new ME and MM algorithms. The modifications discussed in the current work are applicable to both the state-of-the-art MM algorithms [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], [START_REF]Modular multiplication and base extensions in residue number systems[END_REF], which mainly differ for the BE correction methods. Hence, in the following, the proposed modifications will be presented in two versions specifically tailored to the characteristics of these methods.

The authors of the above works evaluate the time performance of their RNS MM algorithms according to the number of modular multiplications. By calling k the number of elements for RNS base, the number of modular multiplications is reduced from 2k 2 + 9k and 2k 2 + 8k, to 2k 2 + 6k and 2k 2 + 5k by Kawamura and Bajard BE, respectively.

In order to evaluate the weight of each modular multiplication required by the proposed and by the state-of-the-art algorithms, a detailed algorithmic analysis has been carried out. The analysis compares the proposed approach with the common part of the state-of-the-art algorithm [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], [START_REF] Bajard | A full RNS implementation of RSA[END_REF]. The evaluation is focused on the number of execution stages required by each multiplication, according to the number of pipeline stages and parallel multipliers present in each arithmetic cell. When an architecture with k cells is considered, the number of execution steps required by the RNS MM algorithm used in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], [START_REF] Bajard | A full RNS implementation of RSA[END_REF] (not considering the BE correction) is 2 k/M -2 + 1/(p + M -1) + 8p, where p is the number of pipeline stages of the arithmetic cells and M ≤ k is the number of parallel multipliers per cell. The proposed approach allows achieving a reduction equal to 4p -1/(p + M -1) execution steps; hence, the improvement is proportional to the number of pipeline stages and, for this, it is more suitable to high speed architectures.

An analysis at the architectural level is also carried out, in order to fully exploit the effects of the two versions of the proposed approach. An architecture based on the work presented in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF] is designed and analyzed. Then, a new architecture suitable to the algorithm proposed in [START_REF] Bajard | A full RNS implementation of RSA[END_REF] is proposed, and an overall comparison is presented, showing that with the proposed approach a 18.5% speedup can be achieved for an implementation over 1024 bits, without any significant area overhead.

The remaining of the paper is organized as follows: in Section II, the proposed RNS ME algorithm is presented, while in Section III, it is analyzed and compared to related works. In Section IV, the implementation of the arithmetic cells is analyzed, and the effects of the proposed approach are discussed.

Finally in Section V, some conclusions are drawn.

; ∀j; 1 ≤ j ≤ k b i i th element of the base B; ∀i; 1 ≤ i ≤ k A Q k j=1 a j B Q k i=1 b i A j A a j ; ∀j; 1 ≤ j ≤ k B i B b i ; ∀i; 1 ≤ i ≤ k A -1 j Multiplicative inverse of A j on a j B -1 i Multiplicative inverse of B i on b i B -1 A Multiplicative inverse of B on A B -1 N Multiplicative inverse of B on N c i 2 r -a i h

A. RNS

In RNS, a number is represented according to a base A = (a 1 , a 2 , ..., a k ), which is made up of k relative prime numbers, where k is called the base size. Therefore, any number x, where 0 ≤ x < A = ∏ k i=1 a i is uniquely represented by a sequence of positive integers (x 1 , x 2 , ..., x k ), where x i = x mod a i , ∀i :

1 ≤ i ≤ k.
It is worth observing that, because of the independence of all the elements, in RNS the multiplication, addition, and subtraction operations can be carried out independently and in parallel for each element.

Using the Chinese Remainder Theorem (CRT) [START_REF]Algorithmic algebraic number theory[END_REF], it is possible to convert a value x from an RNS base to a radix system, thus achieving a high parallelism. The reconstruction expression is: Algorithm 1: State-of-the-art RNS Montgomery exponentiation [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], [START_REF] Bajard | A full RNS implementation of RSA[END_REF] Input: x in A ∪ B and e = (e g-1 ...e 1 e 0 ) b Output: z = (x e ) mod N in A ∪ B Precomputation: if e i = 1 then 7:

B 2 mod N , B mod N in A ∪ B 1: x ← -MM (x, B 2 mod N ) - 2: z bi = (B mod N ) bi for i = 1...
z ← -MM(z, x)

B 2 mod N , B mod N in A ∪ B,
A j mod a j and A -1 j mod a j for j = 1...k 1: x ← -MM (x, B 2 mod N ) 2: xaj = xj A -1 j mod a j for j = 1...k 3: z bi = (B mod N ) bi for i = 1...k 4: ẑaj = (B mod N ) aj A -1 j mod a j for j = 1...k 5: for i from g -1 down to 0 do

6: ẑ ← -MM (ẑ, ẑ) 7: if e i = 1 then 8: ẑ ← -MM(ẑ, x) 9:
end if 10: end for 11: ẑ ← -MM(ẑ, 1) 12: z aj = ẑaj A j mod a j for j = 1...k

x = ( k ∑ i=1 ((x i A -1 i ) mod a i )A i ) mod A ( 1
)
where

A i = A a i and A -1 i is the multiplicative inverse of A i on a i . The result of ( ∑ k i=1 ((x i A -1 i ) mod a i )A i is equal to x+λA,
where λ < k. In order to complete the BE, the modular reductions of x by the elements of the new base must be performed.

B. Montgomery Exponentiation (ME)

The ME is based on the MM, where MM(x × y mod N ) gives w = xyR -1 mod N . ME computes x e mod N at the average cost of 3/2 log 2 e+2 MMs. Let us denote x and ȳ, such that x = xR mod N and ȳ = yR mod N ; then z = xȳR -1 mod N = xyR mod N . Therefore, the exponentiation can be executed by iterating MM on x.

The comparison between the state-of-the-art RNS ME algorithm (the main part of the ME algorithm is common to both [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] and [START_REF] Bajard | A full RNS implementation of RSA[END_REF]) and the proposed algorithm is shown in Figure 1. Step 1 of both the algorithms calculates x, as previously described. Steps 2 and 3 in Algorithm 1 [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], [START_REF] Bajard | A full RNS implementation of RSA[END_REF] initialize the exponentiation process, which is executed in the loop from step 4 to step 9. The proposed RNS ME algorithm (Algorithm 2) executes 3 multiplication steps more than Algorithm 1. Before executing the loop, all the values on base A are multiplied by A -1 j (steps 2 and 4). The multiplication by A -1 j is used in the state-of-the-art BE algorithm, in order to extend the values from A to B. In the proposed algorithm both the input values in A of the RNS MM are pre-multiplied by A -1 j so a multiplication by A j in Algorithm 3: State-of-the-art RNS Montgomery multiplication [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], [START_REF]Modular multiplication and base extensions in residue number systems[END_REF] Input: x, y, and N in A∪B∪a r , such that

I A = ∏ k j=1 a j , B = ∏ k i=1 b i , and gcd (A, B) = 1, gcd(N, B) = 1, 0 ≤ xy < N B, B > 4N , and A > 2N Output: w ≡ xyB -1 N (mod N ), w < 2N in A ∪ B ∪ a r Precomputation: B -1 A , N in A ∪ a r ; N -1 in B 1: s = xy in B 2: s = xy in A ∪ a r 3: u = s(-N -1 ) in B 4: u in A ∪ a r ⇐ BE1(u in B) 5: t = uN in A ∪ a r 6: v = s + t in A ∪ a r 7: w = vB -1 A in A ∪ a r 8: w in B ⇐ BE2(w in A ∪ a r ) Algorithm 4: Proposed RNS Montgomery multiplica- tion Input: x, ŷ, and N in A∪B∪a r , such that I A = ∏ k j=1 a j , B = ∏ k i=1 b i , and gcd (A, B) = 1, gcd(N, B) = 1, 0 ≤ xy < N B, B > 4N , and A > 2N Output: w ≡ xyB -1 N (mod N ), w < 2N in B, ŵ ≡ xyB -1 N A -1 j (mod N ) in A ∪ a r Precomputation: 1: s = xy in B 2: ŝ = xŷ in A ∪ a r - 3: ŵ in A ∪ a r ⇐ BE1(s in B, ŝ in A) - - - 4: w in B ⇐ BE2( ŵ in A ∪ a r ) I With BBEs B > (k + 1) 2 N and A > (k + 1)N Fig. 2.
Comparison between the proposed RNS Montgomery multiplication and the state-of-the-art algorithm the RNS MM is required to reach the value for that BE. In contrast to the original multiplication, the correction can be merged to another multiplication, decreasing the number of modular multiplications in the loop. The values that are multiplied by A -1 j in A are represented with a hat accent. In order to reach the correct result of the exponentiation, another multiplication by A j is required after the loop of RNS MMs (step 12).

C. RNS Montgomery Multiplication

In general, in RNS the MM [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], [START_REF]Modular multiplication and base extensions in residue number systems[END_REF] is performed on two RNS bases, A = (a 1 , ..., a k ) and B = (b 1 , ..., b k ),

such that A = ∏ k j=1 a j , B = ∏ k i=1 b i ,
= xyB -1 N mod N , in A ∪ B, where B -1
N is the multiplicative inverse of B modulo N . The relevant characteristics of MM implementation in RNS are described in the following. Step 3 is only performed on B, so that the modular reduction by B does not require additional operations. After the modular reduction, the BE to A of step 4 is required, since a subsequent step requires a different base in order to perform a division by B and gcd (A, B) = 1. The multiplication in step 5 and the addition in step 6 are only performed on A, since the result of the multiplication in B is equal to the additive inverse on B of the result of step 1 and so the result of the addition in B is 0. The multiplication by B -1 in step 7, which corresponds to the division in MM step 6, is only performed on A, since gcd (B, B) = 1. The last operation is the BE to B, so that the result can be used as input for other MMs.

In [START_REF]Modular multiplication and base extensions in residue number systems[END_REF] and [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], the respective authors have proposed two different techniques to perform the BE. Both techniques are based on (1), but avoid the last modular reduction by A in order to save computational effort. In [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], the final modular reduction of both BEs required by the RNS MM are replaced by an approximation and a correction. In [START_REF]Modular multiplication and base extensions in residue number systems[END_REF], the final modular reduction of the first BE is not executed, so all the subsequent results are obtained modulo a multiple of the base. However, the second BE gives the exact value due to a correction executed at the end of the summation of multiplications. The adopted correction technique has been presented in [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF], and it requires that all the values calculated on A are also calculated on an additional base element a r . This paper presents a new RNS MM, Algorithm 4, which requires less modular multiplication steps.

In order to reach this result, some values are pre-computed and the algorithm is modified accordingly:

1) The multiplication by -N -1 in B of Algorithm 3 step 3 can be moved into the subsequent BE, and merged with the multiplication by B -1 i in B, which corresponds to

x i A -1 j in (1). Therefore, -N -1 B -1
i must be pre-computed in order to avoid a multiplication step.

2) The multiplication by N in A of Algorithm 3 step 5 can be moved into the previous BE, and merged with the summation of multiplications by A j in A of (1). Therefore, A j N must be pre-computed in order to avoid a multiplication step.

3) The multiplication by B -1

A can be split in two parts. One part can be moved in the first BE, and merged with the summation of multiplications by A j N in A of (1). Therefore, A j N B -1 A (instead of A j N ) must be pre-computed. Also s in A must be multiplied by B -1 A , so the number of multiplication steps is not reduced, but the new multiplication can be moved in the first BE.

4) The input values in A are pre-multiplied by A -1 j (Algorithm 2, steps 2 and 4), so a multiplication by A j is required to reach the correct value for the second BE. This correction can be merged to the multiplication by B -1

A and no additional execution steps are required. For this, B -1 A A -1 j must be pre-computed.

As already said, the proposed approach is presented in two versions, which employ different BE algorithms. The only difference in the MM algorithm is the presence of the RNS base element a r , since this special correction base is required only by the version based on the approach proposed in [START_REF]Modular multiplication and base extensions in residue number systems[END_REF], which uses the BE of [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF] for the second one. According to this version, Algorithm 3 and 4 include the base element a r .

The input values of the proposed RNS MM (Algorithm 4) are x and ŷ in A ∪ B ∪ a r (which correspond Algorithm 5: First Base Extension proposed Kawamura et al. [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] Input:

u in B, α = 0 Output: u in A Precomputation: B -1 i mod b i for i = 1...k, B i in A for i = 1...k, -B in A. 1: q i = u bi B -1 i mod b i for i = 1...k 2: c = α 3: u aj = 0 for j = 1...k 4: for i = 1 to k do 5: c = c + trunc(q i ) 2 r
6:

f I = c 7: c = c -f 8:
u aj = (u aj + q i B i + f (-B)) mod a j for j = 1...k 9: end for Algorithm 6: First Base Extension based on the algorithm by Kawamura et

al. (KBE1) Input: s in B, α = 0, ŝ in A Output: ŵ in A Precomputation: -N -1 B -1 i mod b i for i = 1...k, B i N B -1 A A -1 j in A for i = 1...k, -BN B -1 A A -1 j , B -1 A A j in A. 1: q i = (s bi (-N -1 B -1 i )) mod b i for i = 1...k 2: c = α 3: ŵaj = ŝaj B -1 A A j for j = 1...k 4: for i = 1 to k do 5: c = c + trunc(q i ) 2 r
6:

f I = c 7: c = c -f 8: ŵaj = ( ŵaj + q i B i N B -1 A A -1 j + f (-BN B -1 A A -1 j
)) mod a j for j = 1...k 9: end for I f ∈ {0, 1} Fig. 3. Comparison between the first BE presented in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] and the proposed BE (KBE1) Algorithm 7: Second Base Extension proposed Kawamura et al. [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] Input: w in A, α = 0.5 Output: w in B Precomputation:

A -1 j mod a j for j = 1...k, A j in B for j = 1...k, -A in B. 1: q j = w aj A -1 j mod b j for i = 1...k 2: c = α 3: w bi = 0 for i = 1...k 4: for j = 1 to k do 5: c = c + trunc(q j ) 2 r
6:

f I = c 7: c = c -f 8:
w bi = (w bi + q j A j + f (-A)) mod b i for i = 1...k 9: end for

Input: ŵ = q in A, α = 0.5 Output: w in B Precomputation: A j in B for j = 1...k, -A in B. - 1: c = α 2: w bi = 0 for i = 1...k 3: for j = 1 to k do 4: c = c + trunc(q j ) 2 r
5:

f I = c 6: c = c -f 7:
w bi = (w bi + q j A j + f (-A)) mod b i for j = 1...k 8: end for I f ∈ {0, 1} Fig. 4. Comparison between the second BE presented in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] and the proposed BE (KBE2) to x and y in B and xA -1 j and yA -1

j in A ∪ a r ). The output is ŵ, which is equivalent to (xyB -1 N ) (mod N ) < 2N in B, and to ((xyB -1 N ) (mod N ))A -1 j in A ∪ a r .
In the following, the steps of the algorithms in Fig. 2 are analyzed in details.

Step 1 of Algorithm 3 corresponds to step 1 of the proposed algorithm (Algorithm 4).

Step 2 of Algorithm 4 is the multiplication of two values pre-multiplied by A -1 j ; thus, it provides the same results of step 2 in Algorithm 3, multiplied by A -2 j . In Algorithm 4, steps 3, 5, 6, and 7 of Algorithm 3 are moved into the first BE. Moreover, the multiplication by A j , which is required to correct the input, is also moved into the first BE.

D. BE based on the approach by Kawamura et al. (KBE)

Fig. 3 shows the first BE proposed by Kawamura et al. in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] (Algorithm 5), and the proposed BE based on Kawamura et al. approach (KBE1) (Algorithm 6). KBE1 includes all the operations of Algorithm 5 as well as the operations of Algorithm 3 steps 3, 5, 6, and 7.

The modular reductions by A in the first BE and by B in the second BE would require a great computational effort, so they are replaced by an approximation and a correction, that are expected to be able to reduce the delay. The result of the summation in the BE of x from A to B is x = x + λA, where λ ∈ Z and 0 ≤ λ < k. Instead of performing the modular reduction in order to reach x, the algorithm proposed by Kawamura et al. calculates the approximate value of λ,

λ = α + ∑ k 0 trunc(q i )/2 r ∑ k 0 q i /b i .
The value of λ is estimated accumulating the most significant bits of q i , cut by trunc() and divided by 2 r . Moreover, trunc(q i ) = q i ∧ (1 (r) ...1 (r-+1) 0 (r-) ...0 (1) ) (2) , and ∧ means a bitwise AND operation.

Kawamura et al. introduced a further variable (α), which represents the starting value of the parameter

that is used to correct the error introduced by the approximation. In [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], two theorems prove that with correct values of α, with a low , and by selecting the base elements so that 2 r is close to b i , the approximation does not introduce errors. During the first BE α = 0 and the input is unknown; thus, according to Theorem 2 in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], the result of the BE is x < 2B, which is approximate. During the second BE α = 0.5 and the input is lower then 2N ; hence, according to Theorem 1 in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], the result of the BE is correct. With r = 32, k = 33, and max(2 r -a i ; 2 r -b i ) < 2 16 , ∀i, it is possible to choose ≥ 7. This approach requires that A ≥ 2N and B ≥ 4N . The two BEs have the same algorithm with exchanged bases, but according to the theorems presented in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], the first BE produces an approximate result, which is corrected by the second BE.

Step 1 of Algorithm 5 is the multiplication of each x i by B -1 i , modulo b i . In KBE1, this multiplication is merged to the multiplication by -N -1 of Algorithm 3 step 3; thus, instead of

B -1 i , -N -1 B -1 i is pre-computed.
It can be easily demonstrated that the result of this operation is the same as the result of the corresponding operation in the Kawamura et al. BE, for the associative property.

Step 3 of Algorithm 5 is a simple initialization. In KBE1, step 3 executes the multiplication in step 7

of Algorithm 3 merged with the multiplication by A j , used to correct the A -2 j factor. Therefore, A j B -1 A must be pre-computed.

Step 8 of Algorithm 5 requires, for each base element a j , the summation of the results of the multiplications of each result of step 1 by the corresponding B i mod a j , and of -B, when the floor f of the Algorithm 9: First Base Extension employed by Bajard et al. [START_REF]Modular multiplication and base extensions in residue number systems[END_REF], [START_REF] Bajard | A full RNS implementation of RSA[END_REF] Input:

u in B Output: ũ in A ∪ a r Precomputation: B -1 i mod b i for i = 1...k, B i in A ∪ a r for i = 1...k. 1: q i = u bi B -1 i mod b i for i = 1...k 2: ũaj = ∑ k i=1 q i B i mod
s in B, ŝ in A ∪ a r Output: ŵ = q in A ∪ a r Precomputation: -N -1 B -1 i mod b i for i = 1...k, B i N B -1 A A -1 j in A for i = 1...k, B -1 A A j in A. 1: q i = s bi (-N -1 B -1 i ) mod b i for i = 1...k 2: ŵaj = ŝaj B -1 A A j + ∑ k i=1 q i (B i N B -1 A A -1 j
) mod a j for j = 1...k and j = r Fig. 5. Comparison between the first BE used in [START_REF]Modular multiplication and base extensions in residue number systems[END_REF] and the proposed BE (BBE1) Algorithm 11: Second Base Extension employed by Bajard et al. [START_REF]Modular multiplication and base extensions in residue number systems[END_REF]- [START_REF] Bajard | A full RNS implementation of RSA[END_REF] Input: A in Algorithm 3 step 7, and by A -1 j in the second BE.

w in A ∪ a r Output: w in B Precomputation: A -1 j mod a j for j = 1...k, A -1 r mod a r , -A in B, A j in B for j = 1...k, A j mod a r for i = 1...k. 1: q j = w aj (A -1 j ) mod a j for j = 1...k 2: d r = ( ∑ k j=1 q j (A j mod a r )) mod a r 3: β = (d r -x r )(A -1 r ) mod a r 4: d i = ( ∑ k j=1 q j (A j )) mod b i for i = 1...k 5: w bi = (d i -(Aβ) mod b i ) mod b i for i = 1...k
Input: ŵ = q in A, w r in a r Output: w in B Precomputation: A -1 r mod a r , -A in B, A j in B for j = 1...k, A j mod a r for j = 1...k. - 1: d r = ( ∑ k j=1 q j (A j mod a r )) mod a r 2: β = (d r -x r )(A -1 r ) mod a r 3: d i = ( ∑ k j=1 q j (A j )) mod b i for i = 1...k 4: w bi = (d i -(Aβ) mod b i ) mod b i for i = 1...k

Instead of of B i mod a j and -B, B i N B -1

A A -1 j mod a j and -BN B -1 A A -1 j are pre-computed, respectively It can also be easily demonstrated that the result of step 8 of KBE1 is the same result of the corresponding operations in Algorithm 5, for the associative property and for the distributive property,

The second BE proposed in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], Algorithm 7 in Fig 4, uses the same algorithm of the first BE (Algorithm. 5), but with the bases switched. The proposed algorithm (KBE2), Algorithm 8, is the same, but it does not perform step 1 of Algorithm 7, since the input value is already multiplied by A -1 j .

E. BE based on the approach by Bajard et al. (BBE)

In [START_REF]Modular multiplication and base extensions in residue number systems[END_REF], Bajard at al. propose a MM algorithm requiring two different BEs; the former, Algorithm 9 in Fig. 5, trades approximation for speed, whereas the latter, Algorithm 11 in Fig. 6 originally proposed by Shenoy and Kumaresan [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF], corrects the result. The result of the approximate BE of x is x = x + λB, and no correction steps are performed in order to reach the correct results. Further details are presented in [START_REF] Bajard | A full RNS implementation of RSA[END_REF], where the algorithm is applied to the ME in the contexts of RSA. The approximation does not affect the final result of the MM, provided that overflows after the BE are avoided through the use of larger bases guaranteeing:

A, B > N (k + 2) 2 . ( 2
)
The First BE proposed in this work, Algorithm 10 in Fig. 5, is based on the approach by Bajard et al.

(BBE1) and includes the operations of Algorithm 9 as well as the operations of Algorithm 3 steps 3, 5, 6, and 7.

In BBE1, the multiplication of Algorithm 9 step 1, is merged to the multiplication by -N -1 of Algorithm 3 step 3; hence, instead of

B -1 i , -N -1 B -1 i is pre-computed.
It can be easily demonstrated that the result of this operation is the same of the corresponding operation in Algorithm 9.

In step 2 of BBE1, the summation is initialized with the multiplication of Algorithm 3 step 7 merged with the multiplication by A j , used to correct the A -2 j factor. Therefore, A j B -1 A must be pre-computed. The multiplications in the summation are merged to the multiplication by N in Algorithm 3 step 5, by

B -1
A in Algorithm 3 step 7, and by A -1 j in the second BE. Instead of B i mod a j , B i N B -1 A A -1 j mod a j is pre-computed. It can be easily proved that the result of this operation is the same of the respective operation in Algorithm 5.

The approximation correction is only performed after the second BE, and it requires an additional RNS base element a r , such that gcd(a r , A) = 1 and gcd(a r , B) = 1 (where a r is a power of 2). All the values in A are also calculated in a r , according to [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF].

The second BE employed in [START_REF]Modular multiplication and base extensions in residue number systems[END_REF], Algorithm 11, requires a correction in order to avoid the approximation.

Step 2 calculates the difference between the correct value of x in a r and the result of the approximate BE on a r , which correspond to:

t r = x mod a r -(x + λA) mod a r = λA mod a r .
(

The second proposed BE based on the approach by Bajard et al.(BBE2), Algorithm 12 in Fig. 6, corresponds to Algorithm 11 without step 1; this step can be avoided since the input of the BE is already multiplied by A -1 j .

2 + k k 2 + k k 2 + 2k k 2 + 2k First BE correction k 0 k 0 Second BE without correction k 2 + k k 2 + k k 2 k 2 Second BE correction k k k k Total without BE correction 2k 2 + 7k 2k 2 + 7k 2k 2 + 4k 2k 2 + 4k Total 2k 2 + 9k 2k 2 + 8k 2k 2 + 6k 2k 2 + 5k
s = xy B Full k p • • 2 s = xy A S ar Full parallelizable k 1 p+M -1 • • 3 u = s(-N -1 ) B Full k p • • 4 q = uB -1 i B Full k p • 5 ŵ = ŝB -1 A A j A S ar Full parallelizable k 1 p+M -1 • 6. . . k+5 q i B j A S ar Parallelizable k 2 k M -1 + p • • k+6 t = uN A S ar Full k p • k+7 w = vB -1 A A S ar Full k p • k+8 q = wA -1 j A Full k p • k+9. . . 2k+8 q j A j B S ar Parallelizable k 2 k M -1 + p • •
The multiplication is executed by the algorithm • The multiplication is not executed

III. ALGORITHM ANALYSIS

In this section, the proposed approach is evaluated and compared with the state-of-the-art algorithms.

The analysis is focused on the MM, which requires the majority of the total computational time. In particular, Section III-A performs an analysis taking into account the number of modular multiplications, as in previous works [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], [START_REF] Bajard | A full RNS implementation of RSA[END_REF]. Section III-B analyzes the characteristics of the operations performed by the algorithms, evaluating their weight. Finally, Section III-C summarizes the conclusions of the analysis.

A. Number of modular multiplications

Both the approaches in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] and [START_REF] Bajard | A full RNS implementation of RSA[END_REF] have been evaluated by the respective authors according to the number of modular multiplications required. Table III reports the comparison of the proposed RNS MM algorithm with the previous ones. It can be easily seen that the algorithm presented in [START_REF] Bajard | A full RNS implementation of RSA[END_REF] achieves a reduction of k modular multiplications with respect to [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], whereas the proposed algorithm allows a further saving of 3k modular multiplications.

B. Analysis and classification of the required multiplications

As shown in Table III, the described algorithms require 2k 2 and between 5k to 9k modular multiplications. All the necessary multiplications (not considering the BE correction) are listed and classified in • f ull, where the beginning of the operation must wait for the completion of the previous operation that calculates an input value; the number of required execution steps is p, where p corresponds to the number of pipeline stages;

• parallelizable, where a group of operations can be executed in parallel, or the first operation can be executed as full, and the subsequent ones can be pipelined;

• f ullparallelizable, where an operation can be executed in parallel to the previous and/or to the subsequent one; when the operation is executed by a parallel or pipelined cell the number of required execution steps is 0.

C. Remarks

Considering that k cells can perform k modular multiplications in one multiplication step, by analyzing Table IV it can be observed that, without considering the BE correction, the RNS MM involves: 6 full multiplication steps (IDs 1, 3, 4, k+6, k+7, and k+8), two groups of k parallelizable multiplication steps (IDs from 6 to k+5 and from k+9 to 2k+8), and 2 fully parallelizable multiplication steps (IDs 2 and 5).

When the RNS MM algorithm used in the previous approaches is analyzed, by considering M as the number of parallel multipliers per cell, it can be observed that the fully parallelizable step does not need the result of the previous operation. Hence, it can be fully parallelized by any pipelined architecture and it does not affects the overall delay. This step requires 1 p+M -1 execution steps. When executed by an architecture with M ≤ k, the two groups of consecutive parallelizable multiplications require p execution steps for the first multiplication step, and 1/M execution steps for each other multiplication step, corresponding to 2 k M -2 + 2p execution steps. Each full multiplication step requires p execution steps, which correspond to 6p execution steps.

Considering an architecture with k cells, the number of execution steps required by the RNS MM used in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], [START_REF] Bajard | A full RNS implementation of RSA[END_REF], without the BE correction, is IV, the proposed algorithm allows achieving a reduction of 4p steps (IDs 4, k+6, k+7, and k+8), and requires 1 p+M -1 additional steps (ID 5). Therefore, the improvement due to the proposed modification is directly matched to the number of pipeline stages and of parallel multipliers.

2 k M -2 + 1 p+M -1 + 8p.

As shown in Table

Considering p = 3, M = 1 and k = 33 as in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], without the error correction a delay reduction of 13.63% is obtained. With a higher degree of pipelining a larger reduction is achieved, e.g. 16.66% with p = 4 and M = 1, 19.23% with p = 5 and M = 1, 25% with p = 4 and M = 2, etc.

The proposed exponentiation algorithm requires 2p + 1 additional multiplication steps, but their impact on the total delay is negligible since it is equal to

(2p + 1)/(iteration × (2 k M -2 + 1 p+M -1 + 8p)
), e.g. < 0.01% with p = 3, M = 1, and iteration > 1024.

IV. IMPLEMENTATION AND RESULTS

In this section the state-of-the-art architectures exploited in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] and [START_REF] Bajard | A full RNS implementation of RSA[END_REF] are described and analyzed. Kawamura et al. presented some details about their architecture in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF]. This implementation is composed by a set of identical cells, where each is matched to one base element for each RNS base, or to a set of elements for each base. The cells are made up of a Modular Multiplier and Accumulator Unit (MMAU) with three stages of pipeline, a Cox Unit (CU) for the correction of the BE, and some memory. The details regarding the implementation based on the algorithm in [START_REF]Modular multiplication and base extensions in residue number systems[END_REF] have not been presented, so in this section a new architecture tailored to this particular case is proposed. Except for the correction unit, the architecture adopted by Kawamura et al. is also suitable for the approach proposed by Bajard et al., which nonetheless requires a separate cell for the redundant base element, instead of the Cox correction unit.

In order to reach an efficient implementation, the multiplications are performed through reduction trees of Carry Save Adders (CSAs), whereas the addition is achieved by means of Carry Look Ahead Adders. The algorithm proposed in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] can be implemented by adding to each cell a Cox Unit. This unit, which is illustrated in Fig. 8, is composed by an adder, a register and a set of AND gates. The delay of this unit corresponds to an adder and one AND gate. According to [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF], a suitable value for , which represents the size of the adder in the Cox Unit, is 9, with r = 32, h = 11, and k = 33; in this case, the delay required by the unit can be estimated in 22.6 inverters. Kawamura et al. use an architecture similar to Fig. 8, and they place the Cox Unit in parallel to the reduction tree. The area of the reduction three is r FA larger.

The area and the delay of the units with the additional input line are reported in Table VIII.

E. Error correction with the approach by Bajard et al.

The algorithm employed in [START_REF] Bajard | A full RNS implementation of RSA[END_REF] can be implemented by using the architectures previously described, but it requires an additional cell matched to a redundant base element. The aim of this cell is to calculate the BE correction, which is used by the other cells as a standard input value. Therefore, from the point of view of the cells matched to the base elements, the only difference is the sequence of operations.

The architecture of the redundant cell is shown in Fig. 8. It is composed by the Multiplier Unit (MU) and by the Adder Unit (AU). The number of represented bits is shorter than in other cells, according to the requirements, so two multiplications can be processed in parallel and added in a step. Moreover, a r can be a power of 2, so no reduction is required. The area overhead is similar to the approach proposed in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF]. The BE correction requires an additional step. However, as suggested in [START_REF] Bajard | A full RNS implementation of RSA[END_REF], it is possible to avoid a multiplication using tables, but the result from the table should be summed by adding an input line.

F. Overall comparison and concluding remarks

Table IX summarizes the results of the comparison among the considered approaches. It is possible to observe that the BE correction does not affect noticeably the area required by the cell. The most efficient cell is obtained by mixing the BE approach used in [START_REF] Bajard | A full RNS implementation of RSA[END_REF] with the proposed algorithm, since it does not require additional area and it provides a 18.5% delay reduction.

V. CONCLUSION

In this paper a novel RNS Montgomery exponentiation algorithm is proposed. The algorithm is presented in two versions, targeted to the BE approaches adopted in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] and in [START_REF] Bajard | A full RNS implementation of RSA[END_REF], respectively. The architecture proposed in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF], that is compliant with the approach in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], has been used as a reference point for the design of a new architecture suitable for the method adopted in [START_REF] Bajard | A full RNS implementation of RSA[END_REF].

An algorithmic analysis has shown that the proposed approach is capable of providing a reduction of 4p -1/(p + M -1) steps over the 2 k/M -2 + 1/(p + M -1) + 8p required by each RNS MM (without considering the BE correction). Then, an architectural analysis has shown that, with the

k 3 :

 3 z aj = (B mod N ) aj for j = 1...k 4: for i from g -1 down to 0 do 5: z ← -MM (z, z) 6:

Fig. 1 .

 1 Fig. 1. Comparison between the proposed RNS Montgomery exponentiation and the state-of-the-art algorithm

1 A

 1 and gcd (A, B) = 1. B is used as the Montgomery constant, so B -must be pre-computed on the base A, where B -1A is the multiplicative inverse on A of B. The input values of each RNS MM, Algorithm 3 in Fig.2, are x and y in A ∪ B, and the output is w

Algorithm 8 :

 8 Second Base Extension based on the algorithm by Kawamura et al. (KBE2)

  a j for j = 1...k and j = r Algorithm 10: First BE based on the algorithm by Bajard et al. (BBE1) Input:

Algorithm 12 :

 12 Second BE Based on the algorithm by Bajard et al. (BBE2)

Fig. 6 .

 6 Fig.6. Comparison between the second BE used in[START_REF]Modular multiplication and base extensions in residue number systems[END_REF] and the proposed BE (BBE2)

Fig. 7 .

 7 Fig. 7. MMAU architecture with three stages of pipelining

Fig. 8 .

 8 Fig. 8. Cox Unit (a) and Redundant Cell Matched to ar (b)

  The BE correction proposed by Bajard et al. requires an additional step (unless tables are used for the correction multiplication), but the Kawamura et al. correction increases the delay of the MAU, which represents the critical path of the cell. Therefore, the approach proposed by Bajard et al. provides a 5.8% time saving. The proposed algorithm provides a delay reduction linked to the BE correction algorithm, and it does not affect the area. With the Kawamura et al. correction, the delay reduction is 13.6%, while with the Bajard et al. correction it is 13.4%.

TABLE III NUMBER

 III OF MODULAR MULTIPLICATIONS REQUIRED BY THE CONSIDERED RNS MM ALGORITHMS

		[6]	[9]	Proposed (with KBE) Proposed (with BBE)
	Step 1, 3, and 4 of MM	5k	5k	2k	2k
	First BE without correction	k

TABLE IV CLASSIFICATION

 IV OF THE MULTIPLICATION STEPS OF THE MM ALGORITHM (WITHOUT BE CORRECTION)

	Multiplication	Operation	Base	Characteristics	Number of	Number of	Proposed [6], [9]
	ID				multiplications execution steps
	1

Table IV .

 IV It can be observed that 2k 2 modular multiplications correspond to 2k multiplications required for the BEs (IDs from 6 to k + 5 and from k + 9 to 2k + 8) performed on k base elements. Moreover, 8k modular multiplications correspond to 6 multiplications (ID 3, 4, 5, k + 6, k + 7, and k + 8) performed on k base elements, and to 1 multiplication (ID 1 and 2), performed on 2k base elements. Since each operation is performed on k base elements and only one multiplication is performed on a larger base, up to k cells can perform in parallel the required operations. Thus, considering that k cells can work in parallel, the multiplications shown in Table IV are organized in 2k + 8 multiplication steps, composed by k parallel multiplications. The multiplication steps are classified according to the opportuniy of parallelization and pipelining. These aspects are of paramount importance, since different multiplication steps can require a different number of execution steps. The identified types of multiplication steps are:

TABLE V BASIC

 V LOGIC LIBRARY IN CMOS TECHNOLOGY (MODEL FROM[START_REF] Gajski | Principles of Digital Design[END_REF])

		r	r		ρ		r	r-ρ	log 2 (k+1)	log 2 (k+1)	log 2 (k+1)	log 2 (k+1)
			r
		SEL		ρ			SEL	log 2 (k+1)	SEL	log 2 (k+1)
	Unit Multiplier/Adder		r				ρ		log 2 (k+1)	log 2 (k+1)
							ADD			CS-MUL	CS-MUL
	SEL r	2r-1	CS-MUL 2r-1	r	1 Cox Unit	ρ	ρ+1		Multiplier log 2 (k+1)	CS-MUL log 2 (k+1) log 2 (k+1)	log 2 (k+1)
	2r+log(k)			r					Unit
							ρ			log 2 (k+1)	log 2 (k+1)
			ADD
			2r+log(k)				REGISTER			REGISTER
	2r+log(k)									REGISTER	log 2 (k+1)
		REGISTER								log 2 (k+1)	log 2 (k+1)
									log 2 (k+1)	log 2 (k+1)
			2r+log(k)								SEL	SEL
										SEL
											log 2 (k+1)
										log 2 (k+1)	log 2 (k+1)	log 2 (k+1)
											ADD	Adder
										log 2 (k+1)	Unit
											REGISTER
											log 2 (k+1)
				(a)							(b)
					Gate		Area (transistors)	Delay (Inverter)
					Inverter		2		1
					NAND		4		1.4
					NOR		4		1.4
					XNOR		12	3.2
					NAND3		8		1.8
					NAND4		10	2.2
					REGISTER		15	4.8

TABLE IX AREA

 IX AND DELAY COMPARISON WITH k = 33, r = 32, h = 11, M = 1, p = 3

	Algorithm	Correction	# steps	Step delay	MM delay (Inverter) Area (Transistor)
	[6], [9]	Kawamura et al. [6]	88	93	8184(100%)	99873 × 33
	Proposed	Kawamura et al. [6]	76	93	7068(86.4%)	99873 × 33
	[6], [9]	Bajard et al. [9]	89	86.6	7707(94.2%)	99840 × 33
	Proposed	Bajard et al. [9]	77	86.6	6669(81.5%)	99840 × 33

BE proposed in [6], the total number of steps and the reduction are the same, whereas with the BE approach used in [11], the reduction is the same but the MM requires one additional step. According to the algorithmic characteristics described in [6], [11], and to the architectural features described in [7], the delay reduction is equal to 13.6% or 13.4% depending on whether the BE adopted in [6] or in [11] is used, respectively.

A. Modular reduction

In the following, the operations used by the cells to perform the modular reduction are shown. The approach is the same used in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF].

In [START_REF] Bajard | Efficient RNS bases for cryptography[END_REF], the authors showed that the modulo reduction of x < 2 2r requires two multiplications and three additions, where a i = 2 r -c i , with c i < 2 h and h < r- 1 2 . The partial modular reduction y ≡ x (mod a i ) can be calculated by:

where x < 2 z , z > r, and c i < 2 h . Thus, it is y < max (2 r+1 , 2 z-r+h+1 ) and each iteration of this method can reach a reduction of r-h-1 bits. In order to reach a larger reduction per step with 2 2r < x < 2 4r-2h-1 , it is possible to calculate:

where x < 2 z , z > 2r, and c i < 2 h . Hence, it is y < max (2 r+h+1 , 2 z-2r+2h+1 ). Each iteration of this equation can therefore reach a reduction of 2r -2h -1 bits.

B. Cell architecture without BE correction

Without the error correction, a cell basically corresponds to a MMAU opportunely controlled. The starting point for the design is represented by the architecture proposed in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF], that is shown in Fig. 7 (p = 3 and M = 1). The MMAU is divided in three pipelined units:

• Multiplier Adder Unit (MAU), which performs the multiplications and the additions;

• First Modular Reduction Unit (FMRU), which performs the partial modular reduction (5);

• Second Modular Reduction Unit (SMRU), which calculates the final result of the modular reduction performing (4) and an addition.

C. Analysis of the Cell without BE Correction

In order to evaluate the area and delay of the analyzed architecture, the number of gates that compose the arithmetic cells, and that represent the critical path, have been counted. In order to present a more clear comparison, the delay and area cost of each logic gate have been also converted in the equivalent The values between curly brackets are obtained using merged reduction trees Step I MM (inverters) (inverters) [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], [START_REF]Modular multiplication and base extensions in residue number systems[END_REF] Prop.

I Bold numbers represent the longest delay, which is equivalent to critical path of the cell inverter delay, and in the equivalent number of transistors, respectively. For the conversion, the metric in [START_REF] Gajski | Principles of Digital Design[END_REF], which is summarized in Table V, was selected.

Table VI and VII show the area and delay characteristics of the described cells considering r = 32, k = 33, and h = 11, as in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF], [START_REF] Bajard | A full RNS implementation of RSA[END_REF]. In order to evaluate the delay of the described architecture, the time requested by the longest critical path must be multiplied by the number of steps required. According to the theoretical analysis, the considered architecture needs to execute 2k + 22 steps.

By contrast, the proposed RNS MM algorithm requires only 2k + 10 steps. Considering k = 33, with the described cell the proposed algorithm reaches a time saving of 13.63% compared with the previous ones, due to the smaller number of steps. These data confirm the results of the analysis in Section III-C.

D. Error correction with the approach by


domain: info math spi

text:
Giacomo Bacci

E Veronica Belmega

Luca Sanguinetti

DISTRIBUTED ENERGY-EFFICIENT POWER OPTIMIZATION IN CELLULAR RELAY NETWORKS WITH MINIMUM RATE CONSTRAINTS

In this work, we derive a distributed power control algorithm for energy-efficient uplink transmissions in interferencelimited cellular networks, equipped with either multiple or shared relays. The proposed solution is derived by modeling the mobile terminals as utility-driven rational agents that engage in a noncooperative game, under minimum-rate constraints. The theoretical analysis of the game equilibrium is used to compare the performance of the two different cellular architectures. Extensive simulations show that the shared relay concept outperforms the distributed one in terms of energy efficiency in most network configurations.

INTRODUCTION

The use of fixed relays to convey messages from the base station (BS) to user equipments (UEs) through multihop communications is nowadays considered by many upcoming wireless standards (such as the 3GPP's LTE-Advanced [START_REF] Ghosh | LTE-advanced: Next-generation wireless broadband technology[END_REF]) as one of the most promising solutions to enhance cell-edge performance in cellular networks. One of the key challenges is to properly mitigate the intercell interference that arises among relays belonging to different neighboring cells. A possible solution is represented by the shared relay concept, originally proposed in IEEE 802.16m [2], that relies on the idea of placing a multiple-antenna relay at the intersection of two or more cells. The relay decodes the signals from the multiple users in neighboring cells using the multiple receive antennas to cancel interference, and then retransmits to the BSs of different cells using broadcast methods. Refs. [START_REF] Peters | Relay architectures for 3GPP LTEadvanced[END_REF][START_REF] Panah | Interference management schemes for the shared relay concept[END_REF][START_REF] Lin | Fair scheduling and resource allocation for wireless cellular network with shared relays[END_REF][START_REF] Adhikary | Joint spatial division and multiplexing -The large-scale array regime[END_REF] show that shared relays achieve a substantial improvement in terms of spectral efficiency compared to multiple relays placed within each macrocell. To the best of our knowledge, all works available in the literature focus on measuring the spectral effi-

The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Unions FP7 under REA Grant agreements no. PIOF-GA-2011-302520 GRAND-CRU and PIEF-GA-2012-330731 Dense4Green, and from the European Commission in the framework of the FP7 Network of Excellence in Wireless COMmunications NEWCOM# (Grant agreement no. 318306). ciency of the two different architectures, whereas the problem of energy-efficient communications is not taken into account. However, the latter is becoming increasingly important as battery technology has not kept up with the increasing requirements stemming from ubiquitous multimedia applications. This is witnessed by the large number of works accounting for the cost of energy in the performance metrics. To this aim, the concept of link capacity per unit cost, originally proposed in [START_REF] Verdú | On channel capacity per unit cost[END_REF], has been widely adopted in many different contexts (see for example [START_REF] Belmega | Energy-efficient precoding for multiple-antenna terminals[END_REF][START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF][START_REF] Xie | Energy-efficient resource allocation for heterogeneous cognitive radio networks with femtocells[END_REF][START_REF] Miao | Distributed interference-aware energy-efficient power optimization[END_REF] and references therein).

This work aims at revisiting the above concept to evaluate the energy efficiency of an uplink power control algorithm operating in conjunction with either multiple or shared relays. Unlike [START_REF] Peters | Relay architectures for 3GPP LTEadvanced[END_REF][START_REF] Panah | Interference management schemes for the shared relay concept[END_REF][START_REF] Lin | Fair scheduling and resource allocation for wireless cellular network with shared relays[END_REF][START_REF] Adhikary | Joint spatial division and multiplexing -The large-scale array regime[END_REF], we allow the multiple relays to interact in a distributed manner, by modeling the UEs as utility-driven rational agents that engage in a noncooperative game [START_REF] Fudenberg | Game Theory[END_REF], using their own local information while satisfying qualityof-service (QoS) requirements in terms of minimum achievable rates. Note that a similar framework has been recently adopted in [START_REF] Miao | Distributed interference-aware energy-efficient power optimization[END_REF][START_REF] Miao | Energy-efficient link adaptation in frequency-selective channels[END_REF] to study a K-user N -parallel Gaussian interference channel. Elaborating on this formulation, here we introduce the QoS requirements in the game, that thus becomes a generalized one [START_REF] Fudenberg | Game Theory[END_REF][START_REF] Facchinei | Generalized Nash equilibrium problems[END_REF], also providing a simple method to compute the equilibrium point as a function of the network parameters using a fixed-point system of equations.

SYSTEM AND SIGNAL MODEL

System model

We consider the uplink of an arbitrary hexagonal orthogonal frequency-division multiple-access (OFDMA) multicellular network with universal frequency reuse. Each cell is divided into an inner and outer sector. The macro BS is placed at the cell center, whereas the outer sector is further divided into a certain number of adjacent sectors that are served using two different architectures. The first one, depicted in Fig. 1(a), refers to a network in which each sector is served by a fixed relay. The second one, shown in Fig. 1(b), accounts for a network in which the three adjacent sectors are served by a shared relay placed at their intersection. In both cases, the UEs are assumed to be uniformly distributed within the cell, and equipped with single antennas, and perfect channel knowledge is assumed at the relays. The communication between the BS and the UEs takes place in a single-hop if the UEs are placed within the inner sector, whereas a two-hop protocol is needed if the UEs are within the outer sector. In the latter case, the information flows from the UE to the closest relay, and then from the relay to the BS. UEs within the same cell use orthogonal subcarriers to avoid mutual interference. However, interference may arise among UEs in adjacent clusters of neighboring cells sharing the same subcarrier.

To make the problem tractable, here we focus on one subcarrier only, that is still expedient to draw some insights on the problem at hand. Extensions to the multiple-carrier case are discussed in Section 5. Without loss of generality, let us focus on three adjacent clusters sharing the same subcarrier, and let K and M denote the total number of users simultaneously active over the same subcarrier within the three adjacent sectors, and the number of users served by each relay, respectively. Clearly, K ∈ {1, 2, 3}, and M = 1 in the case of distributed relays, and M = K when the (only) relay is shared across the cell sectors. For a fair comparison, the same number of antennas is employed in the two architectures. This means that, if we denote by D the number of receiving antennas for each relay in the scenario of Fig. 1(a), the shared relay of Fig. 1(b) will be equipped with M D receiving antennas.

Signal model

Let h ki ∈ C MD×1 denote the uplink channel vector whose entries [h ki ] m represent the channel gains from the ith UE to the mth receive antenna of user k's serving relay. Denoting by x k the vector collecting the samples received at UE k's serving relay, we may write

x k = K i=1 h ki √ p i s i + w k
, where p i and s i denote UE i's transmit power and data symbol, respectively, whereas w k ∈ C MD×1 is a Gaussian vector accounting for the additive noise and possibly other sources of interference, with zero mean and covariance matrix σ 2 I MD , where I L is the L × L identity matrix. To keep the complexity of the relay at a tolerable level, a simple linear detec-tion scheme is employed for data detection. This means that the entries of x k are linearly combined to form y k = g H k x k , where g k is the vector employed for recovering the data of a generic user k. The signal-to-interference-plus-noise ratio (SINR) achieved by user k at its serving relay takes the form

γ k (p) = g H k h kk 2 p k g k 2 σ 2 + i =k g H k h ki 2 p i = µ k (p \k )p k (1)
where we explicitly report the dependence on the vector p = [p 1 , . . . , p K ] T = [p k , p \k ], with p \k = p \ p k denoting the vector of all powers except user k's one. Using (1), user k's achievable data rate equals

r k (p) = B log 2 (1 + γ k (p)),
where B is the subcarrier bandwidth.

When multiple relays are used, a maximum ratio combing (MRC) technique is employed. This amounts to setting g k = h kk , which requires no channel knowledge of the interfering users within neighboring cells. On the other hand, when a shared relay is employed, we resort to a zero-forcing (ZF) strategy, by setting g k equal to the kth column of the matrix

H k (H H k H k ) -1 with H k = [h k,1 , h k2 , . . . , h kK ] ∈ C MD×K .
As seen, the computation of H k requires knowledge of all h ki for i = k. This can easily be acquired by the shared relay using conventional estimation schemes [START_REF] Peters | Relay architectures for 3GPP LTEadvanced[END_REF].

ENERGY-EFFICIENT POWER OPTIMIZATION

An accurate modeling of the system energy consumption is of primary importance when dealing with energy efficiency. To this end, note that, beside the radiative powers p at the output of the RF circuit, UEs also incur circuit power consumption during transmission. The overall power consumption p T,k of the kth UE is thus given by p T,k = p k + p c , where p c represents the average current power consumed by the device electronics, which is assumed to be independent of the transmission state and equal for all UEs. Following [START_REF] Miao | Energy-efficient link adaptation in frequency-selective channels[END_REF], the energy efficiency of the link can be measured by the utility function

u k (p) = r k (p) p T,k = B log 2 (1 + γ k (p)) p k + p c . (2)
Observe that, in cellular networks, UEs are usually required to satisfy r k (p) ≥ Bϕ k , where ϕ k ≥ 0 are the minimum normalized data rates (measured in b/s/Hz).

To sum up, the design of an energy-efficient power allocation scheme requires to solve the optimization problem1 :

p ⋆ = arg max p K k=1 u k (p) (3)
subject to p k ≥ 0 and r k (p)/B ≥ ϕ k whose solution is hard to compute, given the non-convex form of (3) caused by the QoS constraints.

To tackle with this, we investigate a distributed scenario in which every UE is a rational entity that chooses its transmit power to optimize its own link energy efficiency, measured by u k (p) in (2). The natural framework to model this kind of interactions is offered by non-cooperative game theory [START_REF] Fudenberg | Game Theory[END_REF]. In particular, the underlying game G is defined as the tuple G = [K, {A k }, {u k }], in which: K = {1, 2, . . . , K} is the player set; A k denotes the strategy set for which the constraints in (3) are satisfied; and u k is player k's payoff function defined in (2). Note that user k's action set depends on the actions of the other players, i.e., A k = A k (p \k ), because of the rate constraint r k ([p k , p \k ])/B ≥ ϕ k . In this case, the solution concept is the generalized Nash equilibrium (GNE) [START_REF] Facchinei | Generalized Nash equilibrium problems[END_REF], that collects all system states that are stable to unilateral deviations [START_REF] Fudenberg | Game Theory[END_REF].

Feasibility of the GNE problem

The feasibility of the GNE problem amounts to providing conditions ensuring that the overall action set A = × k∈K A k is not empty. For later convenience, let us define a matrix

F ∈ C K×K whose (k, i)-th element is [F] k,i = 0 i = k γ req k |g H k h ki | 2 |g H k h kk | 2 i = k (4)
with γ req k = 2 ϕ k -1 being the SINR such that r k = Bϕ k . Let ρ A also denote the spectral radius of a generic matrix A [START_REF] Seneta | Non-negative Matrices and Markov Chains[END_REF].

Lemma 1 The problem (3) is feasible if and only if ρ

F < 1.
Proof : The proof is articulated in two steps. First, we provide a necessary and sufficient condition under which the minimal target rates are met with equality for all users. This amounts to proving the existence of a vector p req = [p req 1 , . . . , p req K ] T , with p req k ≥ 0, such that

|g H k h kk | 2 p req k g k 2 σ 2 + K i=1,i =k |g H k h ki | 2 p req i = γ req k (5)
for any k ∈ K. By rearranging the terms, we rewrite (5) as

(I K -F) p req = s (6)
where s ∈ C K×1 is a vector with positive elements

[s] k = γ req k g k 2 σ 2 /|g H k h kk | 2 .
Since F is irreducible and nonnegative, from [15, Theorem 2.1] it follows that a solution p req ≥ 0 to (6) exists for any s ≥ 0 if and only if ρ F < 1.

For the second step, we have to prove that ρ F < 1 is also necessary and sufficient for the existence of a vector p = [p 1 , . . . , pK ]

T , with pk ≥ 0, such that γ k (p) = γk ≥ γ req k for all k ∈ K. While the sufficiency follows trivially, proving the necessity is more elaborated. Assume that such p ≥ 0 exists. Then, the spectral radius of the matrix F, defined as in (4) by replacing γ req k with γk , is such that ρ F < 1. Since F ≤ F, then ρ F ≤ ρ F [START_REF] Horn | Matrix Analysis[END_REF] and, thus, ρ F < 1. In conclusion, a vector p req ≥ 0 satisfying (6) always exists, and hence the necessity.

Analysis of the GNE

In this subsection, we focus on the analysis of the outcome of the game G. Let us denote by W (•) the Lambert function [START_REF] Corless | On the Lambert W function[END_REF] defined such that z = W (z) • exp(W (z)) for any z ∈ C. As stated in the following theorem, it turns out that, whenever Lemma 1 holds, G has a unique solution.

Theorem 1 If the GNE problem is feasible, then G has a unique GNE, achieved by the unique solution p ⋆ [p ⋆ 1 , . . . , p ⋆ K ] to the fixed-point system of equations

p ⋆ k = γ ⋆ k (p ⋆ \k ) µ k (p ⋆ \k ) (7)
where µ k (p ⋆ \k ) is defined as in (1) and the optimal SINR

γ ⋆ k (p ⋆ \k ) is given by γ ⋆ k (p ⋆ \k ) = max {γ req k , γk ( p ⋆ \k )} with γk (p ⋆ \k ) = exp W µ k (p ⋆ \k )p c -1 e + 1 -1. ( 8
)
Due to space limitations, we can only give the main guidelines of the proof (see [START_REF] Bacci | Energyefficient power control for relay-based multicellular networks[END_REF] for more details). The existence follows from the topology of the overall action set A k [START_REF] Facchinei | Generalized Nash equilibrium problems[END_REF], interpreted as a point-to-set mapping [START_REF] Hogan | Point-to-set maps in mathematical programming[END_REF], jointly with the continuity and quasi-concavity properties of the payoff function u k (•) as a function of p k for all k ∈ K [START_REF] Fudenberg | Game Theory[END_REF]. To prove the uniqueness, we use the best-response correspondence [START_REF] Fudenberg | Game Theory[END_REF], described by [START_REF] Verdú | On channel capacity per unit cost[END_REF], which ensures that its fixed point is the unique GNE of the underlying game. Since ( 7) turns out to be a standard function [START_REF] Yates | A framework for uplink power control in cellular radio systems[END_REF] (i.e., component-wise positive, monotonous, and scalable), it has a unique fixed-point [START_REF] Schubert | Solution of the multi-user downlink beamforming problem with individual SINR constraints[END_REF]. This amounts to saying that the GNE is unique. Note that, unlike other game-theoretic power control schemes (e.g., [START_REF] Saraydar | Pricing and power control in a multicell wireless data network[END_REF][START_REF] Bacci | A game-theoretic perspective on code synchronization for CDMA wireless systems[END_REF][START_REF] Bacci | A game-theoretic approach for energy-efficient contention-based synchronization in OFDMA systems[END_REF]), here not only the optimal power p ⋆ k , but also the optimal SINR γ ⋆ k depends on the others' actions p ⋆ \k through γk . This feature makes proving that ( 7) is a standard function rather challenging.

PERFORMANCE ASSESSMENT

Using the theoretical results derived in Section 3, we are interested in comparing the performance of the two relay configurations illustrated in Section 2.1, by means of an extensive simulation campaign. Throughout the simulations, we assume K = 3. To include the impact of spatial correlation among the M D colocated antennas, the channel power gains are computed as h ki = Θ 1/2 ζ ki , where Θ is a square matrix of size DM and elements [Θ] k,i = θ |k-i| , with θ denoting the correlation index between adjacent antennas [START_REF] Tse | Fundamentals of Wireless Communications[END_REF]. To simulate the effects of fading and shadowing, the coefficients [ζ kj ] m are modeled as zero-mean statistically independent and circularly symmetric Gaussian random variables with variance (R/d ki ) ς , where R is the cell radius, d ki is the distance between the kth UE and the UE i's receiving relay, and ς = 4 is the path-loss exponent. To average over all possible positions of the UEs within each sector, we use 10, 000 independent realizations of a feasible scenario, where the reference user is placed randomly in the observed vector at a normalized distance ξ ∈ [d/R, 1], where d = R/2 is the radius of the single-hop region, whereas the other two interfering users are placed randomly within their reference sectors. To account for all positions ξ, we use a discretized version of the range [d/R, 1], using a quantization step ∆ξ = 0.02, and we average using the theoretical probability density function f Ξ (ξ), derived in [START_REF] Bacci | Energyefficient power control for relay-based multicellular networks[END_REF] for a uniform distribution of UEs across the two-dimensional plane covered by the multicellular system under investigation. The shared relay is placed at the intersection of the three cells, as represented in Fig. 1(b), whereas the distributed relays are placed so as to minimize the average UE transmit power [START_REF] Bacci | Energyefficient power control for relay-based multicellular networks[END_REF]. To include the impact of variable QoS constraints, the reference user adopts ϕ k = 1.5 b/s/Hz, whereas the other two UEs select a random ϕ i uniformly distributed in [0, 3] b/s/Hz.

In Figs. 23, we evaluate the performance in terms of energy efficiency of the two architectures as a function of the antenna correlation θ. Dashed and solid lines depict the case when D = 1 and D = 3, respectively, whereas square and circular markers report the results obtained with the shared relay using ZF, and the multiple relays using MRC, respectively. Both transmit powers and circuit powers are normalized with respect to the noise power σ 2 . In particular, red lines correspond to the case p c /σ 2 = -10 dB, in which the circuit power is negligible with respect to the noise, whereas blue lines report the case p c /σ 2 = +10 dB, in which the circuit power is significantly higher than the noise. Fig. 2 reports the average normalized utility for the cases introduced above. As can be seen, the MRC-based distributed-relay configuration outperforms the ZF-based shared-relay solution only when the system is noise-limited. This is due to the fact that, when p c ≪ σ 2 , also p ⋆ k ≪ σ 2 , due to the increasing behavior of p ⋆ k with respect to p c [START_REF] Bacci | Energyefficient power control for relay-based multicellular networks[END_REF], and thus the system is noise-limited. In addition to this, when the number of antennas is limited (notably, D = 1 and thus M D = 3), the improvement brought by the multiple antennas at the shared relay is not sufficiently effective. In all other cases, the shared relay is shown to outperform the distributed relay configuration for reasonable values of θ.

For the sake of completeness, Fig. 3 reports the average normalized rate at the GNE as a function of θ, yielding similar conclusions. It is worth mentioning that the minimum rate ϕ k = 1.5 b/s/Hz is met not only on average, but also at every realization of the simulation.

CONCLUSIONS

We have studied the performance of a relay-based cellular network using an energy-efficient uplink power control, formulated in terms of achieved rate per unit of energy consumed, also considering the impact of the circuit power. To this aim, we have considered two different relay architectures: a multiple-antenna shared relay that serves multiple macrocells, and a set of distributed relays, each serving a sector within one macrocell. Numerical results have revealed that the distributed-relay solution outperforms the shared relay only when the system is noise-limited. In all other cases, the benefits given by multiuser cancellation increase as the impact of multiple access interference increases. Interestingly, this conclusion is in line with other recent studies (e.g., [START_REF] Peters | Relay architectures for 3GPP LTEadvanced[END_REF][START_REF] Panah | Interference management schemes for the shared relay concept[END_REF][START_REF] Lin | Fair scheduling and resource allocation for wireless cellular network with shared relays[END_REF][START_REF] Adhikary | Joint spatial division and multiplexing -The large-scale array regime[END_REF]) focusing instead on spectral efficiency. Moreover, although here we focused on a relay-based network, the analysis can be applied to many other scenarios, such as small cells [START_REF] Bacci | Distributed energy-efficient power and subcarrier allocation for OFDMA-based small cells[END_REF]. Future work is needed to assess the performance when considering a multicarrier system, thus also introducing subcarrier allocation, and also measuring the receiver computational costs, and the installation and maintenance costs.

Fig. 1 .

 1 Fig. 1. Cellular relay network configurations.

3 pc/σ 2 =Fig. 2 .

 322 Fig. 2. Average norm. utility at the GNE as a function of θ.

Fig. 3 .

 3 Fig. 3. Average norm. rate at the GNE as a function of θ.

For analytical convenience, no upper bound on p k is considered, as (2) inherently prevents the UEs from using unnecessarily high power levels.