Jean Claude Bajard
email: jean-claude.bajard@sorbonne-universite.fr

Sylvain Duquesne
email: sylvain.duquesne@univ-rennes1.fr

Montgomery-friendly primes and applications to cryptography

This paper deals with Montgomery-friendly primes designed for the modular reduction algorithm of Montgomery. These numbers are scattered in the literature and their properties are partially exploited. We exhibit a large family of Montgomery-friendly primes which give rise to efficient modular reduction algorithms. We develop two main uses. The first one is dedicated directly to cryptography, in particular for isogeny based approaches and more generally to Elliptic Curves Cryptography. We suggest more appropriate finite fields and curves in terms of complexity for the recommended security levels, for both isogeny-based cryptography and ECC. The second use is purely arithmetic, and we propose families of alternative RNS bases. We show that, for dedicated architectures with word operators, we can reach, for a same or better complexity, larger RNS bases with Montgomery-friendly pairwise co-primes than the RNS bases generally used in the literature with Pseudo-Mersenne numbers. This is particularly interesting for modular arithmetic used in cryptography.

Introduction

Montgomery-friendly primes were introduced in [START_REF] Hamburg | Fast and compact elliptic-curve cryptography[END_REF][START_REF] Bos | Fast cryptography in genus 2[END_REF][START_REF] Bos | Selecting elliptic curves for cryptography: an efficiency and security analysis[END_REF] for cryptographic applications on elliptic or hyperelliptic curves. They are an alternative to Mersenne or pseudo-Mersenne primes as long as the Montgomery reduction is used. More precisely, they have the form p = 2 e 2 α ± 1 where 2 e 2 is an upper bound for the reduction coefficient 2 r in Montgomery reduction, so that the reduction steps are simplified by the fact that p = ±1 mod 2 r . In isogeny-based cryptography, the involved primes naturally have this form, so that optimized Montgomery reduction can be used for efficient implementations [START_REF] Azarderakhsh | Supersingular isogeny key encapsulation[END_REF]. In fact, the initial motivation of this work was to propose efficient Montgomery-friendly primes of the form 2 e 2 α -1 for isogeny-based cryptography. However, the results obtained eventually went fare beyond this field and proved to have particularly interesting applications in a wider range of areas of both public-key cryptography and Residue Number Systems (RNS) arithmetic. As an example, we exhibit new prime numbers for elliptic curve cryptography which provide a simpler reduction algorithm than the ones obtained with the prime numbers given in [START_REF] Hamburg | Fast and compact elliptic-curve cryptography[END_REF][START_REF] Bos | Selecting elliptic curves for cryptography: an efficiency and security analysis[END_REF]. We thus present three main results. We propose new primes for SIKE-like isogeny-based protocols. They are are better balanced between the powers of 2 and 3, and therefore offer better complexity costs in function of the security level. Then, we construct Montgomery-friendly primes which offer both efficient modular reduction and secure elliptic curves for ECC (Elliptic Curve Cryptography). And we suggest some Montgomery-friendly RNS bases offering an efficient internal reduction algorithm, which makes them competitive with respect to pseudo-Mersenne reductions.

The organization of the paper is as follows. We first present in Section 1 a brief review of the primes offering specific efficient modular reduction algorithms like the Mersenne primes, the pseudo-Mersenne primes and their generalization as Solinas primes. We also recall the Montgomery reduction as well as its Residue Number System (RNS) version, and remind that most of the bases in the literature use pairwise pseudo-Mersenne co-primes. Then, in Section 2, we give general modular reduction algorithms for Montgomery-friendly primes and explain how to smartly choose their parameters. Section 3 is dedicated to the analysis of the SIKE protocol based on isogeny, and we produce new primes offering an optimized complexity for a given security. We also exhibit, in Section 4, new primes and curves for elliptic curves cryptography that can be very interesting alternatives to the existing ones (e.g. Curve25519) from an efficiency viewpoint. Section 5 is devoted to the construction of RNS bases with Montgomery's pairwise co-primes, and to the adaptation of the RNS Montgomery reduction, as could be used in cryptography. We compare our approach with those in the literature.

Modular arithmetic for prime fields

The goal of this section is to recall the main techniques for efficient modular reduction in large prime fields of characteristic p. It will be used in the context of modular multiplication in F p , which means that we want to reduce an integer a which is smaller than p 2 (as the result of the multiplication step). For simplicity reasons and without loss of generality, we will in fact assume that a < 2 e p if p is e-bits long.

Use of Mersenne or pseudo-Mersenne primes

Mersenne primes

The simplest prime numbers for efficient reduction are the so-called Mersenne primes. They have the form p = 2 e -1 and are historically used to break large prime numbers records. In this case, we use that 2 e = 1 mod p to get the reduction Algorithm 1: the input a is split after e bits and the sum of the low and the high parts equals to a modulo p and is less than 2p. We then only have to substract p if this sum is greater than or equal to p to get the expected reduction. As this comparison with p is not trivial, we used the standard trick which consists in subtracting p -2 e (which is -1 in this case) and then compare with 2 e (which is easy in base 2).

Algorithm 1: Reduction modulo a Mersenne prime

Data: p = 2 e -1 a Mersenne prime Input: 0 ≤ a < 2 e p Result: r = a mod p and 0 ≤ r < p Write a = a 1 2 e + a 0 // division by 2 e r ← a 0 + a 1 r ← r + 1 // r ← r -p + 2 e if r ≥ 2 e then r ← r mod 2 e // r ← r -p if r ≥ p end if return r

The complexity of this algorithm is one addition of e-bits numbers and one incrementation. It is very attractive especially if e is a multiple of the word-size w. Unfortunately, very few Mersenne primes are available for cryptographic sizes. The most known is P 521 = 2 521 -1 discovered by Robinson in 1954 [START_REF] Robinson | Mersenne and fermat numbers[END_REF] and used as a standard for elliptic curve cryptography at the 256-bits security level. 2 127 -1 is also used for hyperelliptic curve cryptography at the 128-bits security level [START_REF] Bernstein | Kummer strikes back: New dh speed records[END_REF][START_REF] Renes | µKummer: efficient hyperelliptic signatures and key exchange on microcontrollers[END_REF] for efficiency reasons.

Remark 1 Using primes of the form 2 e + 1 provides an equivalent reduction algorithm. However there is no such primes for classical cryptographic sizes.

Pseudo-Mersenne primes

Pseudo-Mersenne numbers were introduced in order to improve modular reduction as a generalization of Mersenne primes. They have the form p = 2 e -c with usually 0 < c < 2 Input: 0 ≤ a < 2 e p Result: r = a mod p and 0 ≤ r < p Write a = a 1 2 e + a 0 // a 0 < 2 e and a

1 < p b ← a 1 × c + a 0 // b ≤ 2 3e 2 Write b = b 1 2 e + b 0 // b 0 < 2 e and b 1 ≤ 2 e 2 r = b 1 × c + b 0 // r < 2.2 e < 3p r ← r + c // r ← r -p + 2 e if r ≥ 2 e then // else r < p r ← r -2 e // r ← r -p if r ≥ p r ← r + c // repeat the if r ≥ 2 e then // previous step r ← r -2 e
// if r ≥ p return r are:

• one multiplication of a e-bits number (a 1 ) with a e 2 one (c), denoted M e, e 2 , • one multiplication of 2 e 2 -bits number (b 1 and c) denoted M e 2 , • 2 additions of e-bits numbers (a 0 , b 0 ), denoted A e ,

• at worst 2 additions of c which has at most e 2 bits.

So the overall cost of Algorithm 2 is at most

M e, e 2 + M e 2 + 2A e + 2A e 2 .
Remark 2 In this paper, complexities for additions are given in terms of the smallest number involved. In other words, we do not take into account carry propagation. We made this choice because it is more representative of the complexity in average and it has no consequence on our results which are relative ones (long carry propagation may exceptionally occur in our methods as well as in any other one).

The value of c plays of course a central role in the complexity of Algorithm 2. Then, in 1992, Crandall suggested pseudo-Mersenne primes such that c is small (in the sense that it fits on a machine word) [START_REF] Crandall | Method and apparatus for public key exchange in a cryptographic system[END_REF]. The most known for cryptographic applications is probably 2 255 -19 that has been used by Bernstein to define the elliptic curve Curve25519 [START_REF] Bernstein | Curve25519: New diffie-hellman speed records[END_REF].

In 1999, Solinas from NSA published a report on generalized Mersenne numbers [START_REF] Solinas | Generalized Mersenne numbers[END_REF] to counter Crandall's patent. These primes are such that p = f (2 k ) where

f (t) = t d -c 1 t d-1 -• • • -c d with |c i | small integers (|c i | << 2 k
) or null. The polynomial f (t) should be irreducible [START_REF] Murty | Prime numbers and irreducible polynomials[END_REF] and |c d | odd. The goal is to get simple multiplications by c in Algorithm 2 using sparse values for c instead of small ones. Solinas numbers are suggested by the NIST 1 and included in many standards for elliptic curve cryptography. For example p 256 = 2 256 -2 224 + 2 192 + 2 96 -1 is used for the 128-bits security level. Note that, contrary to the Solinas primes suggested by the NIST for other security levels, c > 2 e 2 for p 256 , so more rounds are needed in Algorithm 2.

Use of Montgomery arithmetic

The Montgomery reduction [START_REF] Montgomery | Modular multiplication without trial division[END_REF] is used when the modulo does not have a special form allowing fast reduction. This algorithm is regularly used in cryptography, like for RSA [START_REF] Rivest | A Method for Obtaining Digital Signatures and Public-key Cryptosystems[END_REF], or all the approaches based on finite field arithmetic like Elliptic Curve Cryptography [START_REF] Koblitz | Elliptic curve cryptosystems[END_REF][START_REF] Miller | Use of elliptic curves in cryptography[END_REF], pairingbased protocols [START_REF] Joux | A one round protocol for tripartite diffie-hellman[END_REF] or more recently isogeny key exchanges [START_REF] Jao | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF].

Principle of Montgomery reduction

The main idea is to replace divisions by p by much simpler divisions by a power of the radix, in other words to replace divisions by shifts. For example, with radix 2, if p is a e-bits number, the reduction Red(a) of a < 2 e p involves 2 steps:

• q = -ap -1 mod 2 e • r = (a + qp)/2 e
It is then easy to prove that r < 2p and r = a2 -e mod p which is not exactly the expected reduction of a mod p. Of course, we can subtract p as we did for Mersenne primes to get r < p. On the other hand, the fact that r = a2 -e mod p instead of a can be handled using the so-called Montgomery representation of numbers defined by x = x 2 e mod p for any 0 ≤ x < p. This representation is indeed stable for the addition (x + y = x + y) but also for the multiplication with the Montgomery modular reduction Red: Red(x y) = x y 2 -e mod p = x y 2 e mod p = x y mod p.

The Montgomery representation of any x ∈ [0, p[ can be easily obtained by x = Red(x y) if y = 2 2e mod p. Reciprocally, the value of x mod p can be recovered with x = Red(x).

Word version of the Montgomery reduction and complexity

We did not give a precise general algorithm for the Montgomery reduction in the previous section because it is mainly used in its word version. We assume in the following that p fits on n w-bits words and denote β = 2 w . The word version of the Montgomery reduction of any a < pβ n modulo p < β n ( [START_REF] Montgomery | Modular multiplication without trial division[END_REF][START_REF]Topics in Computational Number Theory Inspired by Peter L. Montgomery[END_REF]) is Algorithm 3. Each step of the for loop of this algorithm requires • 1 word multiplication M w (to compute µr 0 ),

• 1 multiplication of a word (q) by a n-words number (p) for computing r. Such a multiplication requires of course nM w but also (n -1)A w ,

• 1 addition with a (n + 1)-words number (qp), namely (n + 1)A w .

i = 0 to n -1 do r 0 ← r mod β // word truncation q ← µ × r 0 mod β r ← (r + q × p)/β // r + qp multiple of β end for r ← r -p + β n if r ≥ β n then // else r < p r ← r mod β n // r ← r -p if r ≥ p return r
So, the for loop requires (n 2 + n)M w + 2n 2 A w . Finally, one addition of β n -p is required to ensure that r < p. The overall complexity of Algorithm 3 is then

(n 2 + n)M w + (2n 2 + n)A w
Remark 3 There also exists an interleaved version of the modular multiplication ( [START_REF] Montgomery | Modular multiplication without trial division[END_REF][START_REF]Topics in Computational Number Theory Inspired by Peter L. Montgomery[END_REF]) that has some advantages (smaller intermediate results) and some drawbacks (only compatible with schoolbook multiplication). We do not give it here because we are only interested in the reduction step but it can be used with all the Montgomery-like reduction algorithms given in this paper (as long as Karatsuba like technique is not used).

Use of RNS arithmetic

Principle of RNS arithmetic

The Residue Number Systems have their origin in the Chinese Remainder Theorem [START_REF] Garner | The Residue Number System[END_REF]. We consider a set of co-prime numbers {m 1 , . . . , m n } and M = n i=1 m i . Then, an integer 0 ≤ a < M is fully defined by the set (a 1 , . . . , a n ) with a i = a mod m i for i ∈ {1, . . . , n}. In practice, the m i would fit on one or two machine word. Additions and multiplications modulo M can be performed on each modulo independently:

a + b mod M = (a 1 + b 1 mod m 1 , . . . , a n + b n mod m n ) ab mod M = (a 1 b 1 mod m 1 , . . . , a n b n mod m n ) 1.3.

RNS Montgomery reduction

When we want to speed up computations in cryptography using RNS, we need to support modular reduction operations related to the finite ring or finite field on which the cryptographic system is defined. This is the case of many cryptographic approaches: RSA [START_REF] Bajard | A Full RNS Implementation of RSA[END_REF], ECC [START_REF] Antao | Elliptic Curve point multiplication on GPUs[END_REF] or Pairing [START_REF] Cheung | FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction[END_REF], Homomorphic Encryption [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF][START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF]... Thus, we consider arithmetics over finite rings like Z/pZ (or finite fields if p prime), where p is a huge number, as it occurs in cryptography. In general p is not the product of small numbers, thus the reduction modulo p must use a specific algorithm like the modular reduction algorithm of Montgomery given in Section 1.2.1. Indeed, this algorithm deals with the least significant digits of the handled values, thus its adaptation to RNS is natural [START_REF] Posch | Modulo Reduction in Residue Number Systems[END_REF][START_REF] Bajard | An RNS montgomery modular multiplication algorithm[END_REF][START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF]. The main idea, as the set B = {m 1 , . . . , m n } represents the RNS base, is to use M = n i=1 m i as the Montgomery factor of reduction instead of 2 e . If we consider 0 ≤ a < pM , the modular reduction can be done with a Montgomery approach assuming 2p < M and the use of a second base B = {m 1 , . . . , m n } such that 2p < M = n i=1 m i . This second base is necessary, because we must divide by M (or multiply by M -1 ) which cannot be done modulo M . This algorithm works in four main steps:

Algorithm 4: RNS Montgomery Reduction

Data:

• B = {m 1 , . . . , m n } and B = {m 1 , . . . , m n } 2 RNS bases s.t. 2p < M = n i=1 m i and 2p < M = n i=1 m i • µ = -p -1 mod M precomputed in B Input: 0 ≤ a < pM given in B and B Result: r = aM -1 mod p and r < 2p q ← a × µ mod M , in B conversion of q from B to B r ← (a + q × p) × M -1 mod M , in B conversion of r from B to B return r given in B and B
As it was already the case for the classical Montgomery reduction, the result of Algorithm 4 is not exactly a mod p (it is multiplied by the constant value M -1 mod p), but the result is reduced (r < 2p), and r mod M = r mod M = r because 2p < M, M . Again, this can be handled using the Montgomery representation defined in this case by a = aM mod p and a < 2p. It can of course also be easily obtained by applying Algorithm 4 to aM 2 and the value of a mod p can be recovered by applying Algorithm 4 to a.

Remark 4 When we want to perform sequences of operations, we need at least 4p 2 < M M to assume the representation of the product of two values smaller than 2p. The condition 2p < M then becomes 4p < M so that a product of 2 numbers smaller than 2p followed by a Montgomery reduction will give a result smaller than 2p. Of course operations should be done in Montgomery representation because it is stable for the addition and for the multiplication followed by a Montgomery Reduction.

RNS bases and conversions

General pseudo-Mersenne numbers are massively used in RNS arithmetic. For example, Kawamura et al [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF] use bases of n moduli m i , = 2 w -c i (w represents the number of bits of the basic words) and c i < 2 w/2 . In fact this approach works under a condition which is roughly speaking

c i < 2 w
n , but they use c i < 2 w/2 due to the internal modular reduction for each element of the RNS base. In [START_REF] Bajard | Double level montgomery cox-rower architecture, new bounds[END_REF], a double Montgomery reduction is suggested to avoid internal modular reduction constraint and the use of pseudo-Mersenne. In 2017, J. van der Hoven suggests in [START_REF] Van Der Hoven | Fast chinese remaindering in practice[END_REF] to use s-gentle moduli, for example for s = 2, m i = 2 2w -2 i with 0 ≤ i < 2 (w-1)/2 . To convert a RNS representation to a classical representation or to another RNS base, most of the approaches use a Lagrange interpolation:

if 0 ≤ X < M = n i=1 m i , and (x 1 , . . . , x n ) is the RNS representation of X in B = {m 1 , . . . , m n }, then, X = n i=1 x i M -1 i m i M i -αM where M i = M m i .
We note |.| m i the value modulo m i .

For [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF], the challenge is to compute α. They show that the first conversion in Algorithm 4 can be an approximation as q is then multiply by p that does not affect the result modulo p.

The second conversion needs to be exact, that is done if

w < 2p < (1 -1 ρ )M for ρ ≥ 2 and c i 2 w < 1 n (1 -1 ρ ).
In [START_REF] Bajard | Double level montgomery cox-rower architecture, new bounds[END_REF] the conditions are a little bit relaxed, but the philosophy stays the same. In [START_REF] Van Der Hoven | Fast chinese remaindering in practice[END_REF], the complexity is studied asymptotically so the author uses a binary tree construction with a logarithmic depth with a modulo reduction at each level. In Section 5 we introduce a new alternative of RNS bases using primes of the form p = 2 e 2 α ∓ 1 and which are well adapted to preconfigured words architectures (CPU, GPU, FPGA,...).

2 Primes of the form p = 2 e 2 α ∓ 1

In this paper, we focus on so-called Montgomery-friendly prime numbers [START_REF] Hamburg | Fast and compact elliptic-curve cryptography[END_REF][START_REF] Bos | Fast cryptography in genus 2[END_REF][START_REF] Bos | Selecting elliptic curves for cryptography: an efficiency and security analysis[END_REF], namely having the form p = 2 e 2 α -1 with e 2 larger than the word size w. Similar results are obtained for primes of the form 2 e 2 α + 1.

Remark 5 These prime numbers do not have significantly better reduction algorithm than the ones of Section 1 but they are attenuating their main default by providing more choices of primes suitable for cryptographic applications.

General reduction algorithm

The main interest of such primes is their nice behaviour with the word version of the Montgomery reduction (Algorithm 3) because -p -1 = 1 mod 2 w (because w ≤ e 2 ), so that the parameter µ equals 1.Then, the only operation to perform in the for loop is the computation of (r + qp)/β where β = 2 w and q is simply r mod β. This can be simplified if p is written as β2 e 2 -w α -1. Indeed, assuming that r = r i β i at the beginning of each step of the for loop, then:

(r + qp)/β = r i β i + r 0 β2 e 2 -w α -r 0 /β = i =0 r i β i-1 + r 0 2 e 2 -w α
So the cost of each step of the for loop is reduced to one multiplication of a single word by α2 e 2 mod w , a shift of e 2 div w words which is for free and the addition of the result of this multiplication. The final addition requires n word additions. Assuming α2 e 2 mod w fits on n α words, this gives the overall complexity for Algorithm 5:

nn α M w + n (2n α + 1) A w Remark 6
We get the same result if p = 2 e 2 α + 1. The only difference is that Algorithm 5 involves -r 0 α2 e 2 -w instead of +r 0 α2 e 2 -w

Choice of e 2 and α

The complexity of Algorithm 5 is dominated by multiplications by α. As a consequence, when it is possible, good choices of α allow to improve the complexity of the reduction modulo prime

≤ r < p r ← a for i = 0 to n -1 do r 0 ← r mod β r ← (r -r 0 )/β + r 0 × α2 e 2 -w end for r ← r + (β n -p) if r ≥ β n then r ← r -β n return r
numbers p of the form 2 e 2 α ∓ 1. The best possible choice for α is of course 1 but p would then be a Mersenne prime. In order to get more candidates, we can choose small values of α or use the same process than in Section 1, namely considering α of the form 2 e 2 -c with c small (as an equivalent of pseudo-Mersenne primes) or sparse involving only coefficients of the word size (as an equivalent of the Solinas primes). The other way to optimize the complexity of Algorithm 5 is to assume that e 2 (and e 2 ) is a multiple of the word size. This may reduce the word size n α to the one of α. If both α and e 2 can be wisely chosen as above, the cost of each step of the for loop is only one multiplication of a single word by c and the addition of the result of this multiplication. The best choice for c is of course ±1. However this case is similar to Mersenne primes in the sense that such primes are very rare for real world cryptographic applications. For example, if w = 32, there are only 4 of them in the cryptographic range for elliptic and hyperelliptic curve cryptography:

• p 192 = 2 64 (2 128 -1) -1, used in most standards,

• p 448 = 2 224 (2 224 -1) -1, used for the curve Ed448 [START_REF] Hamburg | Ed448-goldilocks, a new elliptic curve[END_REF],

• p 480 = 2 448 (2 32 -1) -1,

• p 512 = 2 32 (2 480 -1) -1, Remark 7 There are all for high security levels and only p 192 can be used if w = 64. Considering primes of the form 2 e 2 (2 e 2 -1) + 1 provides 7 additional primes but only one can be used if w = 64 and it is 576-bits long.

If c is assumed to be small, typically if it fits on a word (of size w), Algorithm 5 requires only one word multiplication (r 0 c) as well as 3 word additions (one for adding r 0 2 e 2 to (r -r 0 )/β and 2 for adding r 0 c2 e 2 -w which fits on two words because e 2 -w is a multiple of the word size. The final addition is also simpler than in the general case, because β n -p = c2 e 2 + 1 so that computing r requires only 2 word additions. Consequently, if p = 2 e 2 (2 e 2 -c) -1 where c fits on one word and both e 2 and e 2 are multiples of the word size w, the complexity of Algorithm 5 becomes

nM w + (3n + 2)A w .
Of course, if c is sufficiently small, the M w can be replaced by some A w .

Let us now assume that c is written in the form c i 2 wi (in the spirit of Solinas primes). The c i can be chosen of any sign and size, but they should be very small in practice for efficiency reasons. In this case, multiplying r 0 by c and adding the result to (r -r 0 )/β requires at most |c i | word additions. One more word addition is necessary to add r 0 2 e 2 . As in the previous case, the final addition is simplified by the form of β n -p and computing r requires only 1 + #{c i } c i =0 word additions. Then the complexity of Algorithm 5 in this case is at most

n + 1 + n |c i | + #{c i } c i =0 A w .

2.3

The case e 2 ≥ log 2 (p)/2

In this section, we assume that e 2 ≥ e/2 where p is e-bits long and that e 2 is a multiple of the word size, which is n-n α if p (resp. α) fits on n (resp. n α ) words. We can then introduce a new version of the Montgomery reduction that is intermediate between the word version and the general case and that is still optimized in the sense that the parameter µ involved is ±1. The idea is to perform 2 Montgomery reduction steps modulo 2 e 2 (instead of one step modulo 2 e in the general case or n steps modulo β = 2 w in the word version) using that µ = -p -1 = ±1 mod 2 e 2 . More precisely, the first step of such a reduction of some a < 2 e p ≤ 2 2e 2 p will be 1. q 0 = a(-p -1 ) mod 2 e 2 = ±a mod 2 e 2 2. r 0 = (a + q 0 p)/2 e 2 = (a -a mod 2 e 2 )/2 e 2 + q 0 α It is then easy to prove that r 0 has been reduced compared to a but it is only smaller than 2 e 2 p so that a second Montgomery reduction step is necessary to get a full reduction of a. We then get Algorithm 6 for the modular reduction in this case. Input: 0 ≤ a < 2 e p Result: r 1 = a2 -2e 2 mod p and 0 ≤ r 1 < p q 0 ← a mod 2 e 2 r 0 ← (a -q 0 )/2 e 2 + q 0 × α // first reduction q 1 ← r 0 mod 2 e 2 r 1 ← (r 0 -q 1 )/2 e 2 + q 1 × α // second reduction

r 1 ← r 1 -p + 2 e if r 1 ≥ 2 e then r 1 ← r 1 mod 2 e // r ← r -p if r ≥ p return r 1
It is obvious that the output of this algorithm is a2 -2e 2 mod p as it was already the case in classical Montgomery reduction. Moreover, it is less than p because at the end of the 2 reduction steps

r 1 = (a+q 0 p) 2 e 2 + q 1 p 2 e 2 = a + (q 0 + q 1 2 e 2 )p 2 2e 2 < 2 2e 2 p + (2 2e 2 -1)p 2 2e 2 < 2p
The operations involved in Algorithm 6 are the following ones:

• a mod 2 e 2 and (a -q 0 )/2 e 2 is a simple truncation which is for free because e 2 is assumed to be a multiple of the word size,

• q 0 α and q 1 α are 2 multiplications of n -n α by n α words numbers,

• 2 additions of two n-words numbers (q 0 α and q 1 α),

• a final addition of 2 e -p which is less than n-words long.

This algorithm is of course optimal when 2 e 2 fits on n/2 words, namely n α = n/2. In this case, its complexity is the same as the one of Algorithm 5 if schoolbook method is used for computing the q i α. But thanks to this approach, alternative multiplication algorithms like Karatsuba's one can be used to reduce the global complexity of Algorithm 6. Of course, this will only be interesting if α cannot be chosen with small coefficients.

Remark 8

We get the same result if p = 2 e 2 α + 1. The only difference is that Algorithm 6 involves -q i α instead of +q i α.

Comparison with other methods

The complexities we obtain have the same order than the one for pseudo-Mersenne or Solinas primes. We will give more precise comparison for each application in the following. But the main interest of this new form of primes is that we get new prime numbers having an efficient reduction algorithm that can be used when pseudo-Mersenne or Solinas primes are too rare. The situation is in fact even better with the new prime numbers we introduced because, contrary to pseudo-Mersenne primes, the value of c can be even in our case. As a consequence, for the same size of primes we will be able to find roughly twice more candidates. This will for example be very interesting for generating RNS bases as we will see in Section 5.

New Primes for Isogeny-based cryptography

Isogeny-based protocols such as SIDH are based on a shared secret which is the j-invariant of some elliptic curve. They have been introduced in cryptography by Couveignes in 1997 [START_REF] Couveignes | Hard homogeneous spaces[END_REF] and have been recently developed as an alternative for quantum resistant cryptography [START_REF] Jao | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF][START_REF] Costello | Efficient algorithms for supersingular isogeny diffiehellman[END_REF][START_REF] Costello | Efficient compression of sidh public keys[END_REF][START_REF] Koziel | Post-quantum cryptography on fpga based on isogenies on elliptic curves[END_REF]. SIKE is now a second-round candidate for the NIST post-quantum cryptography standardization process [START_REF]NIST: Post-quantum cryptography standardization[END_REF]. We will present it here briefly in a simplified form.

The SIKE protocol

The public parameters are

• a prime number p = 2 e 2 3 e 3 -1 such that 2 e 2 3 e 3 ,

• a supersingular elliptic curve E 0 defined over F p 2 ,

• two points of order 2 e 2 ,

P 2 ∈ E 0 F p 2 \E 0 (F p ) and Q 2 ∈ E 0 (F p ),
• two points of order 3 e 3 , P 3 ∈ E 0 F p 2 \E 0 (F p ) and

Q 3 ∈ E 0 (F p ).
The points P 2 and Q 2 (resp. P 3 and Q 3 ) then form a base for the full 2 e 2 (resp. 3 e 3 ) torsion of E 0 . The key exchange process is as follows

• Alice chooses = 2 or 3 (let m be the other one) and a secret key sk < e . She computes a point S = P + sk Q ∈ E 0 F p 2 which defines an isogeny φ of degree e as its kernel. This isogeny can be easily computed as a sequence of -isogenies and Alice's public key is given by φ (P m ) and φ (Q m ). The elliptic curve E = φ (E 0 ) is also part of the public key but it is deduced from φ (P m ), φ (Q m ) and φ (P m -Q m ) in practice.

• Bob follows the same process exchanging and m. His public key is then E m , φ m (P ) and φ m (Q ).

• Alice repeats the process with E m and S = φ m (P )+sk φ m (Q ). She then gets an isogeny φ with kernel generated by S = φ m (S ) so that φ • φ m has kernel generated by S and S m .

• Again, Bob do the same exchanging and m and gets φ m such that φ m • φ has the same kernel.

• Allice and Bob can then both compute their share secret, the j-invariant of the target elliptic curve of φ • φ m and φ m • φ which are the same.

Most of the computations involved are then elliptic curves operations and 2 or 3-isogenies computation over F p or F p 2 . Modular reductions modulo p then have a key role in the computational cost of the SIKE protocol. The computational security of this protocol is based on the degrees of the isogenies involved and then on 2 3.2 Primes of the form 2 e 2 3 e 3 -1

According to the constraints above, the original SIKE proposal [START_REF] Azarderakhsh | Supersingular isogeny key encapsulation[END_REF] recommended to use respectively the prime numbers p503, p751 and p964 (given in Table 1) to meet the security requirements of NIST categories 1, 3 and 5. However, it has been recently shown that the hardness of computing isogenies on quantum computers were overestimated [START_REF] Adj | On the cost of computing isogenies between supersingular elliptic curves[END_REF]. As a consequence the second round proposal of SIKE [START_REF] Azarderakhsh | Supersingular isogeny key encapsulation[END_REF] provides new primes p434 and p610 suitable for NIST categories 1 and 3. Note that the reference implementation of SIKE (that we will use for comparisons) only uses p503 and p751. Reductions are done using the word version of the Montgomery reduction algorithm (or its interleaved version, see Remark 3) for this specific form of primes, namely Algorithm 5 with α = 3 e 3 . Assuming p fits on n w-bits words, and that α2 e 2 mod w fits on n α words, the cost of the reduction is then nn α M w + n (2n α + 1) A w Remark 9 Remember that we did not consider the carry propagation cost for simplicity but also because it will not significantly change the cost evaluation and it will occur in the same way in our proposal. Then this assumption will not affect the results of this work. For example, for p 503 we have n = 8 if w = 64 and α = 3 159 2 58 so that n α = 5 and the overall cost of the reduction algorithm is then 40M 64 + 88A 64 (which fits with the reference implementation of SIKE). The complexities for reducing modulo the SIKE primes are given in Table 3. We explained in Section 2.2 that it would be interesting to choose e 2 to be a multiple of the word-size in order to reduce the cost of Algorithm 5. This is not the case for the primes given in Table 1. That is the reason why we propose here new primes for the SIKE protocol satisfying this property.

New primes proposed

The only condition on the form of p for SIKE-like protocols is that p+1 is divisible by sufficiently large powers of 2 and 3 which ensures the existence of the isogenies φ 2 and φ 3 . It is then not restrictive to consider primes p with a small cofactor f , namely of the form p = f.2 e 2 3 e 3 -1. This is besides mentioned in the SIKE proposals [START_REF] Azarderakhsh | Supersingular isogeny key encapsulation[END_REF][START_REF] Azarderakhsh | Supersingular isogeny key encapsulation[END_REF] but discarded because they was enough candidates satisfying all the conditions with f = 1. For efficiency reasons, we consider here the new condition that e 2 is a multiple of the word size. This is of course quite restrictive so we do need to consider non-trivial cofactors in this case. We give in Table 2 the new values we propose for SIKE primes such that e 2 is a multiple of 64 (so that e 2 is always a multiple of the word size in real world applications). These primes provide at least the same security level that the ones of Table 1 (because min(e 2 , log 2 (3 e 3 )) is always larger in our case) and p requires the same number of words. For the security category 1, considering 32-bits word may be more appropriate. Indeed 64-bits word implies that the e 2 and e 3 parts of p both fit on 4 words while they can fit on 7 32-bits words. We then give the prime p448 for which e 2 is only a multiple of 32.

Because of our new constraint, both sides of the protocol are not balanced anymore at first glance. This can be solved by shortening the longest loop considering public points of lower order. For example, with p630, 2 e 2 is 320-bits long while 3 e 3 is only 305. So the 2-side of the protocol should have 320 steps while only 305 are necessary for this security level. In this case, we only have to choose P 2 and Q 2 having order 2 305 instead of 2 320 to shorten the 2-side loop.

The security level remains the same because it was determined by the 3-side of the protocol. The value of α is f.3 e 3 and is smaller than 2 e 2 by construction. As a consequence, e 2 ≥ log 2 (p)/2 so that Algorithm 6 can be used for reducing modulo these primes. Of course, Algorithm 5 can also be used with the same complexity if schoolbook method is used in Algorithm 6 because in any case, p fits in n words and α in n/2 words. This complexity is given by , so that Karatsuba method can be used to compute q 0 × α and q 1 × α. In our case, α and the q i are all n/2-words numbers. For example if we perform one Karatsuba step in the case of p512, the cost of q i × α is 3M 128 + 7A 128 instead of 4M 128 + 4A 128 so that only 24 M 64 are necessary instead of 32 (but of course, more additions). We give in Table 3 a reduction complexity comparison between SIKE primes of Table 1 and our new proposals given in Table 2. This table clearly shows that the new primes we propose may have an great interest for efficient implementations of SIKE-like protocols.

n 2 2 M w + n(n + 1)A w .
Remark 10 Complexities involving Karatsuba should be considered carefully because practice and theory may differ. That is the reason why we did not give the complexities for all the possibilities of using this method in Table 3 (one could for example make more Karatsuba steps to get a better theoretical complexity). Note also that α is constant and used 2 times in Algorithm 6 so that some precomputations could be done to reduce the number of additions involved in a Karatsuba implementation of the multiplication by α.

Application to Elliptic curve cryptography

Because of their efficient reduction algorithm, particular forms of prime are used in elliptic curve cryptography for a long time. For example, Solinas primes are used in the FIPS 186-3 standards [START_REF] Gallagher | Fips pub 186-3 federal information processing standards publication digital signature standard[END_REF] and the prime used for Ed25519 curve is the pseudo-Mersenne prime 2 255 -19 [START_REF] Bernstein | Curve25519: New diffie-hellman speed records[END_REF].

Several authors already proposed to use Montgomery-friendly primes of the form 2 e 2 (2 e 2 -c) ± 1 and provide elliptic curves defined over such prime fields which are suitable for cryptographic use [START_REF] Hamburg | Fast and compact elliptic-curve cryptography[END_REF][START_REF] Bos | Selecting elliptic curves for cryptography: an efficiency and security analysis[END_REF][START_REF] Bos | Montgomery Arithmetic from a Software Perspective[END_REF]]. They are for example recommending the primes 2 240 (2 16 -88)-1 and 2 240 (2 14 -127) -1 for the 128-bits security level. However these proposals are not satisfying what we identified in Section 2.2 as good choice for the parameters e 2 and e 2 . In particular there are not multiples of the word size. We propose in this paper new primes satisfying this condition and then providing a more efficient reduction step. We will first focus on the 128-bits security level because it is the most commonly used in practice and we will then give the results we obtained for higher security levels.

The 128-bits security level

The first step is to find a prime p of the form 2 e 2 (2 e 2 -c) ± 1 such that multiplications by c is as inexpensive as possible and such that e 2 and e 2 are mutliples of the word size. We assume that the word size is 64 to cover as many use cases as possible. For each security level, we made an exhaustive search of such p with c small or sparse.

The best result we get for the 128-bits security level is given by e 2 = 192, e 2 = 64 and c = 4

p 256 = 2 192 (2 64 -4) -1
In this case, each of the 4 step of the for loop of Algorithm 5 consists in the computation of r-r 0 2 64 +r 0 2 64 -4r 0 which requires only 4 word-additions. The final addition step of Algorithm 5 is the computation of r -p + 2 256 = r -4.2 192 + 1 which is a very fast operation. Finally, the word version of the Montgomery reduction algorithm requires approximately 17A 64 . Algorithm 6 can be also used for this prime if one wants to use some Karatsuba steps into the reduction algorithm. Moreover, p = 3 mod 4 which allows efficient modular square root computations. As a comparison, with the prime 2 240 (2 16 -88) -1, each step of the for loop of Algorithm 5 would require M 64 + 2A 64 because α fits on one word in this case. Again, the final addition can be simplified in the same way, so that the complexity of Algorithm 5 is approximately 4M 64 + 9A 64 . As a consequence, assuming we are working on a plateform for which additions of 64-bits words are at least twice faster than multiplications, the reduction step is always faster with the prime p 256 introduced in this paper. Of course, this result is also valid for any platform using less than 64-bits words.

Reducing modulo 2 240 (2 14 -127) -1 or 2 255 -19 will also require some multiplications (so we get a similar result) but allow to avoid the final addition step.

Remark 11 Choosing e 2 and e 2 multiples of the word size implies that the final addition of the Montgomery reduction step cannot be avoided assuming 4p < 2 256 as it is the case for 2 240 (2 14 -127) -1. But, the gain obtained thanks to our choice outreaches this additional addition, especially because it is not a full addition due to the form of p.

The second step is to generate an elliptic curve satisfying all security requirements. We follow the process explained in [START_REF] Bos | Selecting elliptic curves for cryptography: an efficiency and security analysis[END_REF] to generate parameters A and d 0 defining the isogeneous elliptic curves in Montgomery and twisted Edwards forms

M A : y 2 = x 3 + Ax 2 + x E d 0 : -x + y 2 = 1 + d 0 x 2 y 2
These parameters are chosen such that the cardinalities of the curve and its twist are almost prime with the minimal cofactor (which is 4) in order to guarantee the expected security level both on the curve and its twist. For efficiency reasons, A and d 0 have to be chosen as small as possible. It is explain in [START_REF] Bos | Selecting elliptic curves for cryptography: an efficiency and security analysis[END_REF] that under some conditions (that will be satisfied in our cases), A 2 -4 is not a square (which simplifies notions of completeness [START_REF] Bernstein | Curve25519: New diffie-hellman speed records[END_REF]) and d 0 can be chosen equal to -(A+2)/4. By the way, this value is the one involved in the Montgomery ladder formulas. So, in any case, it is necessary to select the parameter A such that (A+2)/4 is as small as possible in order to improve the global efficiency. This is what is done in [START_REF] Bos | Selecting elliptic curves for cryptography: an efficiency and security analysis[END_REF]. However, using Montgomeryfriendly primes implies that the operands have to be in Montgomery representation. So the value that has to be small is not (A + 2)/4 or d 0 but its Montgomery representation d 0 = -(A + 2)2 256 /4 mod p. Of course, we also checked that the curves obtained are satisfying the security requirements given in [START_REF] Bernstein | Safecurves: choosing safe curves for elliptic-curve cryptography[END_REF]. For the 128-bits security level, the smallest values we get for the Montgomery representation of -(A + 2)/4 are d 0 = 5919 and -9869 which both fit on 16 bits contrary to the values given in [START_REF] Bos | Selecting elliptic curves for cryptography: an efficiency and security analysis[END_REF] or Curve25519. This may be an advantage for small devices.

Finally, using the prime p 256 = 2 192 (2 64 -4) -1 for elliptic curve cryptography seems to be a better choice than the other ones given in the literature for efficiency reasons. This should of course be verified by a practical implementation but in any case, it provides an interesting alternative to Curve25519. More generally considering primes of the form 2 e 2 (2 e 2 -c) ± 1 allows to get more choice for efficient elliptic curve cryptography than using only Bernstein-like curves.

Higher security levels

At the 192-bits security level, we found the prime

p 384 = 2 128 (2 256 -2 192 + 2 64 + 1) -1
and the elliptic curve defined by the parameter A or d 0 such that the Montgomery representation d 0 of -A+2 4 equals -10498.2 128 which still fits on one (shifted) 16-bits word. The prime p = 2 192 (2 192 -2 128 + 2 64 -2) -1 could also be considered with d 0 = 39737. One more addition is required for each step of Algorithm 5 but, contrary to p 384 , it is compatible with Algorithm 6. Concerning the 256-bits security level, we found three primes ensuring the same complexity for Algorithm 5 and well suited for 64-bits architectures. One can for example choose

p 512 = 2 128 (2 384 -2 128 + 2 64 -1) -1
and the elliptic curve defined over F p 512 by the parameter A or d 0 such that d 0 = -60237 which also fits on one 16-bits word. The two other primes are

• 2 64 (2 448 -2 192 -2 128 + 1) -1 and • 2 192 (2 320 -2 128 + 2) -1 5 Alternative RNS bases with m i = 2 e 2 (2 e 2 -c i ) ∓ 1
We consider in this section RNS bases made of co-prime numbers {m 1 , . . . , m n } such that for i ∈ {1, . . . , n}, m i = 2 e 2 (2 e 2 -c i ) ∓ 1 with 0 < c i < 2 e 2 (when c i = 0 then m i = 2 e 2 +e 2 -1). In this case, the reduction modulo each m i uses Algorithm 6 for the internal modular reduction. If such number system is implemented on a word-architecture (w-bits unit) like GPU or FPGA (DSP-unit), a good choice is to have e 2 = e 2 = w so that each m i is coded on two words to fit well Algorithm 6. We consider in this part that e 2 -1 ≤ e 2 ≤ e 2 which seems the most adapted to our purpose, but a generalisation is always possible.

RNS addition

The addition of a = {a 1 , . . . , a n } and b = {b 1 , . . . , b n } is of course done by computing r i = a i + b i mod m i for each modulo m i . The reduction can then be obtained by computing r i = r i + (2 e 2 c i ± 1): if r i ≥ 2 e 2 +e 2 then r i is replaced by r i mod 2 e 2 +e 2 .

RNS multiplication

The multiplication is also done component by component. But, in this case, a stronger modular reduction, like the one of Montgomery (Algorithm 6) must be applied. The result of each reduction will then be r i = a i b i 2 -2e 2 mod m i with r i < 2m i .

Montgomery RNS representation

Even at the moduli level it is then interesting to use a Montgomery representation: a = a2 2e 2 mod M , in other words (a 1 , . . . , a n ), with a i = a i 2 2e 2 mod m i for i ∈ {1, . . . , n}. We obviously have a+b = a + b mod M so the addition is stable for the Montgomery representation. But the multiplication is not.

The operator ⊗

We then introduce the operator ⊗ defined by a ⊗ b = ab2 -2e 2 . It is said stable for the Montgomery representation with reduction factor equals to 2 -2e 2 because a⊗b = ab2 2e 2 = ab mod M . The operator ⊗ also has the following properties modulo M that can be used for switching between representations:

a ⊗ 2 4e 2 = a a ⊗ 1 = a a ⊗ b = ab
5.1 Modular reduction modulo a given p in RNS with bases of the form

2 e 2 (2 e 2 -c i ) ∓ 1
In this section, we consider bases B and B such that Algorithm 7: RNS Montgomery reduction with specific RNS bases Data:

m i = 2 e 2 (2 e 2 -c i ) ∓ 1 and m i = 2 e 2 (2 e 2 -c i ) ∓ 1 with 0 < c i , c i < 2 e 2 (
• 2 co-prime RNS bases B = (m 1 , . . . , m n ) and B = (m 1 , . . . , m n ) s.t. m i = 2 e 2 (2 e 2 -c i ) ∓ 1 and m i = 2 e 2 (2 e 2 -c i ) ∓ 1 with 0 ≤ c i , c i < 2 e 2 • a prime p s.t. 2p < M = m i and 2p < M = m i • the precomputed values µ = -p -1 2 2e 2 mod M , λ = M -1 2 2e 2 mod M and γ = pM -1 2 2e 2 mod M
Input: a given in B and B with 0 ≤ a < pM Result: r = aM -1 mod p and r < 2p

q ← a ⊗ µ in B // q = a -p -1 mod M (1) conversion of q from B to B r ← a ⊗ λ + q ⊗ γ in B // r = (a + qp)M -1 mod M (2) conversion of r from B to B return r in B and B As we have, a ⊗ b = ab2 -2e 2 , then q = a ⊗ µ = a -p -1 2 2e 2 2 -2e 2 = a -p -1 mod M (1)
r = a ⊗ λ + q ⊗ γ = aM -1 + qpM -1 = (a + qp)M -1 mod M . (2)
As 0 ≤ a < pM , then (a + qp) < 2pM . Thanks to (1), a + qp is a multiple of M , so (a+qp)M -1 < 2p < M , and Equation ( 2) is in fact not true only modulo M . As a consequence, the result of Algorithm 7 satisfies r = aM -1 mod p and r < 2p.

In most cases, the input of Algorithm 7 will be given in Montgomery representation for the moduli m i and m i as the result of a product of two values in Montgomery representation a = b ⊗ d = bd2 2e 2 mod M M in B and B . If the input is a with a < pM , then Algorithm 7 will compute q = a ⊗ µ = aµ = a -p -1 2 2e 2 mod M in B instead of q = a -p -1 mod M , thus we cannot ensure that q < M and then that (a + qp) M -1 < 2p. Finally, the result will not be less than 2p as expected. Hence, we must adapt this algorithm in order to have q = a -p -1 mod M . For this we will compute q = a ⊗ µ in B and then r with r ← a ⊗ λ + q ⊗ γ = (a + qp) M -1 in B , and finally we obtain r = (a + qp) M -1 mod M < 2p. This adaptation is presented in Algorithm 8.

m i = 2 e 2 (2 e 2 -c i ) ∓ 1 with 0 ≤ c i , c i < 2 e 2 • a prime p s.t. 2p < M = m i and 2p < M = m i • the precomputed values µ = -p -1 mod M λ = M -1 2 2e 2 mod M and γ = pM -1 2 4e 2 mod M
Input: a = a2 2e 2 given in B and B with 0 ≤ a < pM Result: r = r2 2e 2 with r = aM -1 mod p and r < 2p q ← a ⊗ µ in B // q = a(-p -1 ) mod M conversion of q from B to B r ← a ⊗ λ + q ⊗ γ in B // r = (a + qp)M -1 mod M conversion of r from B to B return r in B and B Remark 12 Two levels of Montgomery representations can occur, one due to the moduli operator ⊗ and one due to the RNS Montgomery reduction: we note a = (aM mod p) 2 2e 2 mod M this double level of Montgomery representation. As in the previous cases of Montgomery representation, a can be easily obtained: let τ = M 2 mod p, if we compute a ⊗ τ = aτ with aτ < pM , then Algorithm 8 returns a.

Remark 13

As usual, if we consider a sequence of operations, the input data could be the product of two previous results lower than 2p. Then, we need to have 4p 2 < pM (in other words 4p < M instead of 2p < M ) to ensure that the input is lower than pM .

Bases conversion with specific RNS bases

Algorithms like the Cox-Rover approach [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF] are dependent of the RNS bases elements seen as pseudo-Mersenne close to a power of two. So they will clearly not work directly with m i = 2 e 2 (2 e 2 -c i ) ∓ 1. Hence, we consider approaches like the one of [START_REF] Bajard | Modular multiplication and base extensions in residue number systems[END_REF] where the first conversion is a partial Chinese remainder Theorem method without a final reduction (only the summation is done). The second conversion is exact using an auxiliary modulo [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF]. Let 0 ≤ X < M given by its residues x i modulo the m i . The CRT construction gives

X = n i=1 ξ i m i M -αM with ξ i = x i M -1 i m i .
Thus, the integer part n i=1 ξ i m i equals α. With our specific bases we can have an approach which looks like the Kawamura et al one [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF] to recover α.

A general approach

We develop

n i=1 ξ i m i using m i = 2 e 2 (2 e 2 -c i ) ∓ 1 , n i=1 ξ i m i = n i=1 ξ i 2 e 2 (2 e 2 -c i ) ∓ 1 = n i=1 ξ i 2 e 2 +e 2 + ξ i c i 2 e 2 ± ξ i 2 e 2 +e 2 2 e 2 (2 e 2 -c i ) ∓ 1
And, because 0 ≤ ξ i < 2 e 2 (2 e 2 -c i ) ∓ 1 and c i = 0 only when m i = 2 e 2 +e 2 -1, we have

n i=1 ξ i m i < n i=1 ξ i 2 e 2 +e 2 + c i 2 e 2 ± 1 2 e 2 +e 2 < n i=1 ξ i 2 e 2 +e 2 + c i 2 e 2 + 1 2 e 2 +e 2
Now, if we consider that

n i=1 c i + 1 2 e 2 < 2 e 2 , then n i=1 ξ i 2 e 2 +e 2 < n i=1 ξ i m i < n i=1 ξ i 2 e 2 +e 2 + 1
and we are in a case similar to Kawamura et al one [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF]. We can conclude that, when

n i=1 c i + 1 2 e 2 < 2 e 2 , n i=1 ξ i 2 e 2 +e 2 ≤ n i=1 ξ i m i ≤ n i=1 ξ i 2 e 2 +e 2 + 1.
In Algorithm 7, the first conversion "of q from B to B " can then be done with an algorithm similar to the one of [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF]. It will compute q or q + M in B . As this value is multiplied by γ = pM -1 2 2e 2 mod M , that will not affect the result modulo p.

Example 1 We consider 2 e 2 = 2 e 2 = 2 16 , for example in a case of a 16-bits architecture. With a trivial algorithm it is possible to construct a set of 180 pairwise 32-bits co-primes satisfying

n i=1 c i + 1 2 e 2 <

An exact conversion

Now, we consider ρ ≥ 2 such that X < 1 ρ M as for the second conversion in Kawamura et al [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF].

If n i=1 c i + 1 2 e 2 < 2 e 2 1 - 1 ρ , then n i=1 ξ i 2 e 2 +e 2 < n i=1 ξ i m i < n i=1 ξ i 2 e 2 +e 2 + 1 - 1 ρ . As X < 1 ρ M, n i=1 ξ i m i equals n i=1 ξ i m i + 1 -1 ρ , so we have n i=1 ξ i m i = n i=1 ξ i 2 e 2 +e 2 + 1 - 1 ρ .
That means that in Algorithm 7, the second "conversion of r from B to B" can be done exactly as in [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF].

A conversion with truncated values

The two previous conversions require the calculation of n i=1 ξ i 2 e 2 +e 2 = 1 2 e 2 +e 2 n i=1 ξ i . Suppose our architecture is on (e 2 + e 2 )-bits. Since we are only interested in the most significant digits of the n i=1 ξ i , it might be interesting to consider a truncated summation that stays on less than (e 2 + e 2 )-bits. So, we can, as in Kawamura et al [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF], compute instead the sum n i=1 ξ i 2 t , with 2 t ≥ n.

In this case we have

n i=1 ξ i m i < n i=1 ξ i 2 e 2 +e 2 + c i 2 e 2 + 1 2 e 2 +e 2 < 1 2 e 2 +e 2 n i=1 ξ i 2 t 2 t + |ξ i | 2 t + n i=1 c i 2 e 2 + 1 2 e 2 +e 2 < 2 t 2 e 2 +e 2 n i=1 ξ i 2 t + n2 t 2 e 2 +e 2 + 1 2 e 2 n i=1 c i + 1 2 e 2 .
Thus, if

n i=1 c i + 1 2 e 2 < 2 e 2 - n2 t 2 e 2 , we have 2 t 2 e 2 +e 2 n i=1 ξ i 2 t ≤ n i=1 ξ i m i < 2 t 2 e 2 +e 2 n i=1 ξ i 2 t + 1, so that n i=1 ξ i m i =            2 t 2 e 2 +e 2 n i=1 ξ i 2 t or 2 t 2 e 2 +e 2 n i=1 ξ i 2 t + 1.
If we consider ρ ≥ 2 such that X < 1 ρ M and if we assume

n i=1 c i + 1 2 e 2 < 2 e 2 1 - 1 ρ - n2 t 2 e 2 , then n i=1 ξ i m i = 2 t 2 e 2 +e 2 n i=1 ξ i 2 t + 1 - 1 ρ .
Note that the larger t is, the smaller the architecture needed to calculate this summation is.

Summary

In this work, we introduced the RNS bases of coprimes

m i = 2 e 2 (2 e 2 -c i ) ∓ 1 with 0 ≤ c i < 2 e 2 for i = 1 . . . n. If 0 ≤ X < M is represented in this base by (x 1 , . . . , x n ), ξ i = x i M -1 i m i and α = n i=1 ξ i m i , the CRT construction is given by X = n i=1 ξ i m i M -αM.
Let us summarize how to find α in the general case:

• Assuming n i=1 c i + 1 2 e 2 < 2 e 2 , we have α = 1 2 e 2 +e 2 n i=1 ξ i or 1 2 e 2 +e 2 n i=1 ξ i + 1. • If 2 t ≥ n and n i=1 c i + 1 2 e 2 < 2 e 2 - n2 t 2 e 2 , α = 2 t 2 e 2 +e 2 n i=1 ξ i 2 t or 2 t 2 e 2 +e 2 n i=1 ξ i 2 t + 1.
If ρ ≥ 2 such that X < 1 ρ M , we get an exact result:

• Assuming n i=1 c i + 1 2 e 2 < 2 e 2 1 - 1 ρ , we have α = 1 2 2e 2 n i=1 ξ i + 1 - 1 ρ . • If 2 t ≥ n and n i=1 c i + 1 2 e 2 < 2 e 2 1 - 1 ρ - n2 t 2 e 2 , α = 2 t 2 e 2 +e 2 n i=1 ξ i 2 t + 1 - 1 ρ .

Some comparisons

The main difference between our approach with Montgomery's RNS bases and pseudo-Mersenne bases, and the approach of Kawamura et al [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF] lies in the internal modular reduction modulo m i , the elements of the RNS bases. In the first one, we use Algorithm 6 which uses two multiplications of a value on e 2 -bits by c i , then in the second one we use Algorithm 2 with a multiplication by c i of a value on (e 2 + e 2 )-bits and one by c i of a value on e 2 -bits. Depending on the architecture, size or even shape, the c i values are therefore important. Another difference is the upper bound for c = max c i . In the general case we need that c + 1 2 e 2 < 2 e 2 n -2 t 2 e 2 while Kawamura et al requires c < 2 e 2 +e 2 n -2 t . Our upper bound is then smaller than the one given by Kawamura et al [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF]. More precisely it is essentially 2 e 2 times smaller and the situation is similar for the exact conversion with ρ ≥ 2. But, on the other hand, for the same selection criterion of the c i , we have at least 4 times more candidates for the same bound on the c i (2 times because of the ±1 concerned and 2 times because we can consider even values of c i contrary to [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF]). Consequently, we are able to build bases with smaller c i . Similarly, if the maximum size of c i is supposed to be small, we can build bases larger than [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF]. e = e2 + e 2 ec ρ t n (Kawamura et al [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF]) n (this paper) our approach becomes a little bit better, see for exemple e = 16 or e = 32. These phenomena correspond to the bounds given on c which are smaller in our case so that t may have greater influence.

(m i < 2 e ) (c i < 2 ec ) (m i = 2 e 2 +e 2 -c i ) (m i = 2 e 2 (2 e 2 -c i ) ∓ 1) 16
Another interesting point comes from the use of Algorithm 6. This algorithm has the advantage of being able to use basic RNS elements of twice the size of the architecture because the multiplications are on e 2 -bit values instead of (e 2 + e 2 )-bits. For example, for an architecture of 16-bits, we can consider e = e 2 + e 2 = 32 and e 2 = 16. As a consequence RNS-based arithmetic can be considered for larger fields or rings on such architectures. For example, a RNS-based implementation of RSA-1024 can be done on a 16-bits architecture (we need 64 moduli with e 2 = 16 for this) while it cannot be done directly with pseudo-Mersenne 16-bits moduli (128 are required with e = 16) and are more costly with 32-bits moduli due to Algorithm 2. In a recent paper, Kawamura et al [START_REF] Kawamura | Rns montgomery reduction algorithms using quadratic residuosity[END_REF] give an interesting survey of different approaches [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF][START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over fp[END_REF][START_REF] Cheung | FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction[END_REF][START_REF] Gandino | An algorithmic and architectural study of montgomery exponentiation in rns[END_REF] about RNS ECC implementations. They also suggest an original approach using bases where each element is a square modulo the others and p is a square modulo each element of the bases (the elliptic curve is defined over F p ). The bases proposed by our approach are compatible with all the previous approaches and also with the one of [START_REF] Kawamura | Rns montgomery reduction algorithms using quadratic residuosity[END_REF]. Moreover, one can see in Table 5 that our approach offers smaller c i than [START_REF] Kawamura | Rns montgomery reduction algorithms using quadratic residuosity[END_REF].

256

Table 5: Comparison of our approach with the one of Kawamura et al [START_REF] Kawamura | Rns montgomery reduction algorithms using quadratic residuosity[END_REF]. p defines the finite field, e = e 2 + e 2 , ec > log 2 (c i ), t is the truncation size, and 2n the number of m i for the two bases needed. We return the set of c i defining the RNS bases.

In [START_REF] Bajard | Double level montgomery cox-rower architecture, new bounds[END_REF], the authors propose a double Montgomery reduction in a Cox-Rover like architecture which is more general than our current approach (which also involves a double level of Montgomery reduction). In their approach, the Kawamura et al. condition c < 2 e 2 +e 2 n (1 -1 ρ ) -2 t becomes c < 2 e 2 +e 2 n (1 -1 ρ ) -2 e 2 +e 2 -t + 1. As a consequence, they can generate more bases than [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF] as they allow bigger c i . This could be very interesting when e 2 + e 2 is small, but the cost of the multiplication by c i can become costly depending of the architecture and this approach has the same drawback than [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF] compared to ours. When e 2 + e 2 ≥ 32 our approach is clearly very attractive.

Conclusions

Montgomery-friendly prime numbers, which are particularly suitable for Montgomery modular reductions, form a large family. They offer new prime numbers that can be used in many cryptographic contexts such as elliptic curve or isogeny based cryptography or RNS arithmetic for large numbers. For isogenies, we have proposed new primes that significantly improve the complexity of the modular reduction step for each of the NIST security categories. For ECC, we provide new primes for base fields for the 3 standard security levels as alternatives to the pseudo-Mersenne primes like 2 255 -19, or other Montgomery-friendly primes like 2 240 (2 16 -88) -1. Again, the modular reduction is expected to better depend on the relative costs of word additions versus word multiplications. Note that we get curves with smaller coefficients than the existing ones which can be an advantage for small devices. The use of Montgomery Friendly moduli for RNS implementations offers several advantages. It is indeed possible to obtain larger sets of pairwise co-prime numbers with very small c i parameters. The size of this parameter is a very important criterion for the cost of the modular reduction at the moduli level. Moreover, Algorithm 6 allows the use of moduli with a size that is twice the size of the operators of the targeted architecture.

e 2 .

 2 The reduction of an integer a < 2 e p modulo p follows the Algorithm 2 which essentially consists in replacing two times 2 e by c in the input. The costs of the steps of this reduction algorithm Algorithm 2: Pseudo-Mersenne Reduction Data: p = 2 e -c with 0 < c < 2 e 2

Algorithm 5 :

 5 Word version of the Montgomery reduction if p = 2 e 2 α -1 Data: p < β n with β = 2 w and w ≤ e 2 Input: 0 ≤ a < pβ n Result: r = aβ -n mod p and 0

Algorithm 6 :

 6 Intermediate Montgomery reduction for p = 2 e 2 α -1 with e 2 ≥ log 2 (p)/2 Data: A e-bits long prime p = 2 e 2 α -1 s.t. e 2 ≥ e/2

e 2 and 3 e 3 .

 3 Known classical attacks are in O √ e and quantum once are in O 3 √ e . In order to achieve a close balance on both sides of the protocol, e 2 and e 3 are chosen such that 2 e 2 3 e 3 .

  we can have c i or c i = 0 then m i or m i = 2 e 2 +e 2 -1), and the Montgomery reduction modulo each element of the bases. The global RNS Montgomery reduction algorithm is Algorithm 7. The only difference with Algorithm 4 is that the precomputed values are affected by the Montgomery representation on each modulo.

Algorithm 8 :

 8 RNS reduction with specific bases in Montgomery representation Data: • 2 co-prime RNS bases B = (m 1 , . . . , m n ) and B = (m 1 , . . . , m n ) s.t. m i = 2 e 2 (2 e 2 -c i ) ∓ 1 and

Table 1 :

 1 Primes of the SIKE NIST proposals[START_REF] Azarderakhsh | Supersingular isogeny key encapsulation[END_REF][START_REF] Azarderakhsh | Supersingular isogeny key encapsulation[END_REF]

	prime e 2	e 3 log 2 (3 e 3 )	security symmetric category key size
	p434 216 137	218	1	128 bits
	p503 250 159	253	2
	p610 305 192	305	3	192 bits
	p751 372 239	379	4
	p964 486 301	478	5	256 bits

Table 2 :

 2 New primes proposed for SIKE-like protocols

	prime	min(e 2 , log 2 (3 e 3 ))	security symmetric category key size
	p448 262.2 224 3 136 -1	216	1
	p477 37.2 256 3 136 -1	216	1	128 bits
	p512 31.2 256 3 158 -1	251	2
	p630 39.2 320 3 192 -1 p765 214.2 384 3 235 -1	305 373	3 4	192 bits
	p996 69.2 512 3 301 -1	478	5	256 bits

Table 3 :

 3 Complexity comparison for modular reduction in SIKE-like protocols For example, using p 512 = 31.2 256 3 158 -1 instead of p 503 = 2 250 3 159 -1 provides a reduction that costs 32M 64 + 72A 64 instead of 40M 64 + 88A 64 . This is substantially better and will give a speed-up around 20% of the reference implementation of SIKE. Moreover, as explained in Section 2.3, contrary to Algorithm 5, large multiplications are directly involved in Algorithm 6

  2 e 2 with a maximal value of c i equal to 360 < 2 16 180 -1 2 16 and we have 2 5759 ≤ 180 i=1 m i < 2 5760 . This means that one can perform RNS arithmetic with p up to 2878 bits on a 16 bits plateform. If we want the m i to be prime, for example in an homomorphic context, we can obtain 106 primes with c i ≤ 616 < 2 16 106 -1 2 16 and 2 3391 ≤ m i < 2 3392 . If we impose small values for the c i , e.g. c i < 2 8 , we can obtain 136 co-primes moduli with c i ≤ 253 < 2 16 136 -1 2 16 and 2 4351 ≤ m i < 2 4352 . We can also easily obtain 45 primes with c i ≤ 255 < 2 16 45 -1 2 16 and 2 1439 ≤ m i < 2 1440 .

  Example 2 As in Example 1, we consider 2 e 2 = 2 e 2 = 2 16 , adding ρ = 2. In this case, we can construct a set of 132 co-primes with 2 4223 ≤ 132 i=1 m i < 2 4224 and a maximal value of c i equals to 243 < 2 15 132 -1 2 16 . But also 75 primes with 2 2399 ≤ m i < 2 2400 and c i ≤ 436 < 2 16 106 -1 2 16 or 45 if the c i are chosen less than 2 8 and then 2 1439 ≤ m i < 2 1440 and c i ≤ 255 < 2 16 45 -1 2 16 .

 [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF]and our approach with a greedy search algorithm based on increasing the c i Using a greedy algorithm based on increasing the c i , we give in Table 4 the largest size n of the RNS bases that can be reached by Kawamura et al [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF] approach and by ours. It is given in function of the parameters e = e 2 + e 2 (the bitsize of the moduli), ec (the maximal bitsize expected for the c i ), ρ and t (the truncation size), knowing that at least 2n base elements are required. We note that, as expected, our approach reaches bigger RNS bases than Kawamura et al for small c i (which is important in term of efficiency because the internal modular reduction modulo m i uses multiplications by c i ). We remark also that, by changing the size of the truncation,


Matthias Hesse
email: hesse@i3s.unice.fr

Jérôme Lebrun
email: lebrun@i3s.unice.fr

Luc Deneire
email: deneire@i3s.unice.fr

L2 Orthogonal Space Time Code for Continuous Phase Modulation

To combine the high power efficiency of Continuous Phase Modulation (CPM) with either high spectral efficiency or enhanced performance in low Signal to Noise conditions, some authors have proposed to introduce CPM in a MIMO frame, by using Space Time Codes (STC). In this paper, we address the code design problem of Space Time Block Codes combined with CPM and introduce a new design criterion based on L 2 orthogonality. This L 2 orthogonality condition, with the help of simplifying assumption, leads, in the 2x2 case, to a new family of codes. These codes generalize the Wang and Xia code, which was based on pointwise orthogonality. Simulations indicate that the new codes achieve full diversity and a slightly better coding gain. Moreover, one of the codes can be interpreted as two antennas fed by two conventional CPMs using the same data but with different alphabet sets. Inspection of these alphabet sets lead also to a simple explanation of the (small) spectrum broadening of Space Time Coded CPM.

I. INTRODUCTION

Since the pioneer work of Alamouti [START_REF] Alamouti | A simple transmit diversity technique for wireless communications[END_REF] and Tarokh [START_REF] Tarokh | Space-time block codes from orthogonal designs[END_REF], Space Time Coding has been a fast growing field of research where numerous coding schemes have been introduced. Several years later Zhang and Fitz [START_REF] Zhang | Space-time coding for rayleigh fading channels in CPM system[END_REF], [START_REF] Zhang | Space-time code design with continuous phase modulation[END_REF] were the first to apply the idea of STC to continuous phase modulation (CPM) by constructing trellis codes. In [START_REF] Zajić | A space-time code design for partial-response CPM: Diversity order and coding gain[END_REF] Zajić and Stüber derived conditions for partial response STC-CPM to get full diversity and optimal coding gain. A STC for noncoherent detection based on diagonal blocks was introduced by Silvester et al. [START_REF] Silvester | Diagonal space-time code design for continuous-phase modulation[END_REF].

The first orthogonal STC for CPM for full and partial response was developed by Wang and Xia [START_REF] Wang | An orthogonal space-time coded CPM system with fast decoding for two transmit antennas[END_REF], [START_REF] Wang | An orthogonal space-time coded partial response CPM system with fast decoding for two transmit antennas[END_REF]. The scope of this paper is also the design of an orthogonal STC for CPM. But unlike Wang-Xia aprroach [START_REF] Wang | An orthogonal space-time coded partial response CPM system with fast decoding for two transmit antennas[END_REF] which starts from a QAM orthogonal Space-Time Code (e.g. Alamouti's scheme [START_REF] Alamouti | A simple transmit diversity technique for wireless communications[END_REF]) and modify it to achieve continuous phases for the transmitted signals, we show here that a more general L 2 condition is sufficient to ensure fast maximum likelihood decoding with full diversity.

In the considered system model (Fig. 1), the data sequence d j is defined over the signal constellation set

Ω d = {-M + 1, -M + 3, . . . , M -3, M -1} (1)
for an alphabet with log 2 M bits. To obtain the structure for a Space Time Block Code (STBC) this sequence is mapped to data matrices D (i) with elements d

(i)
mr , where m denotes the transmitting antenna, r the time slot into a block and (i) a parameter for partial response CPM. The data matrices are then used to modulate the sending matrix

S(t) = s 11 (t) s 12 (t) s 21 (t) s 22 (t) . ( 2
)
Each element is defined for where E s is the symbol energy and T the symbol time. The phase φ mr (t) is defined in the conventional CPM manner [START_REF] Anderson | Digital Phase Modulation[END_REF] with an additional correction factor c mr (t) and is therewith given by

(2l + r -1)T ≤ t ≤ (2l + r)T as s mr (t) = E s T e j2πφmr (t) (3)
φ mr (t) = θ m (2l + r) + h 2l+r i=2l+1+r-γ d (i) mr q(t -(i -1)T ) + c mr (t) (4)
where h = 2m 0 /p with m 0 and p relative primes is called the modulation index. The phase smoothing function q(t) has to be a continuous function with q(t) = 0 for t ≤ 0 and q(t) = 1/2 for t ≥ γT .

The memory length γ determines the length of q(t) and affects the spectral compactness. For large γ we obtain a compact spectrum but also a higher number of possible phase states which increases the decoding effort. For full response CPM, we have γ = 1 and for partial response systems γ > 1.

The choice of the correction factor c mr (t) in Eq. ( 4) is along with the mapping of d j to D (i) , the key element in the design of our coding scheme. It will be detailed in Section II. We then define θ m (2l + r) in a most general way

θ m (2l + 3) = θ m (2l + 2) + ξ(2l + 2) = θ m (2l + 1) + ξ(2l + 1) + ξ(2l + 2). (5)
The function ξ(2l + r) will be fully defined from the contribution c mr (t) to the phase memory θ m (2l + r). For conventional CPM system, c mr (t) = 0 and we have ξ(2l + 1) = h 2 d 2l+1-γ . The channel coefficients α mn are assumed to be Rayleigh distributed and independent. Each coefficient α mn characterizes the fading between the m th transmit (Tx) antenna and the n th receive (Rx) antenna where n = 1, 2, . . . , L r . Furthermore, the received signals

y n (t) = α mn s mr (t) + n(t) (6)
are corrupted by a complex additive white Gaussian noise n(t) with variance 1/2 per dimension. At the receiver, the detection is done on each of the L r received signals separately. Therefore, in general, each code block S(t)

has to be detected by block. E.g. for a 2x2 block, estimating the symbols dj implies computational complexity proportional to M 2 . Now, this complexity can be reduced to 2M by introducing an orthogonality property as well as simplifying assumptions on the code. Criteria for such STBC are given in Section II. In Section III, the criteria are used to construct OSTBC for CPM. In Section IV we test the designed code and compare it with the STC from Wang and Xia [START_REF] Wang | An orthogonal space-time coded partial response CPM system with fast decoding for two transmit antennas[END_REF]. Finally, some conclusions are drawn in Section V.

II. DESIGN CRITERIA

The purpose of the design is to achieve full diversity and a fast maximum likelihood decoding while maintaining the continuity of the signal phases. This section shows how the need to perform fast ML decoding leads to the L 2 orthogonality condition as well as to simplifying assumptions, which can be combined with the continuity conditions. For convenience we only consider one Rx antenna and drop the index n in α mn .

A. Fast Maximum Likelihood Decoding

Commonly, due to the trellis structure of CPM, the Viterbi algorithm is used to perform the ML demodulation . On block l each state in the trellis has M 2 incoming branches and M 2 outgoing branches with a distance

D l = (2l+1)T 2lT y(t) - 2 m=1 α m s m1 (t) 2 dt + (2l+2)T (2l+1)T y(t) - 2 m=1 α m s m2 (t) 2 dt. (7)
The number of branches results from the blockwise decoding and the correlation between the sent symbols s 1r (t) and s 2r (t).

A way to reduce the number of branches is to structurally decorrelate the signals sent by the two transmitting antennas, i.e. to put to zero the inter-antenna correlation

α 2 α * 1 (2l+1)T 2lT s 21 (t)s * 11 (t) dt + α 1 α * 2 (2l+1)T 2lT s 11 (t)s * 21 (t) dt + α 2 α * 1 (2l+2)T (2l+1)T s 22 (t)s * 12 (t) dt + α 1 α * 2 (2l+2)T (2l+1)T s 12 (t)s * 22 (t) dt = 0. ( 8
)
Pointwise orthogonality as defined in [START_REF] Wang | An orthogonal space-time coded partial response CPM system with fast decoding for two transmit antennas[END_REF] is therefore a sufficient condition but not necessary. A less restrictive L 2 orthogonality is also sufficient. From Eq. ( 8), the distance given in Eq. ( 7) can then be simplified to

D l = (2l+1)T 2lT f 11 (t) + f 21 (t) -|y(t)| 2 dt + (2l+2)T (2l+1)T f 12 (t) + f 22 (t) -|y(t)| 2 dt (9) with f mr (t) = |y(t) -α m s mr (t)| 2 .
When each s mr (t) depends only on d 2l+1 or d 2l+2 the branches can be split and calculated separately for d 2l+1 and d 2l+2 . The complexity of the ML decision is reduced to 2M . The complexity for detecting two symbols is thus reduced from pM γ+1 to pM γ . The STC introduced by Wang and Xia [START_REF] Wang | An orthogonal space-time coded partial response CPM system with fast decoding for two transmit antennas[END_REF] didn't take full advantage of the orthogonal design since s mr (t) was depending on both d 2l+1 and d 2l+2 . The gain they obtained in [START_REF] Wang | An orthogonal space-time coded partial response CPM system with fast decoding for two transmit antennas[END_REF] was then relying on other properties of CPM, e.g. some restrictions put on q(t) and p. These restrictions may also be applied to our design code, which would lead to additional complexity reduction. However, this is not in the scope of this paper and is be the subject of another upcoming paper.

B. Orthogonality Condition

In this section we show how L 2 orthogonality for CPM, i.e. S(t) 2 L2 = (2l+2)T 2lT S(t)S H (t) dt = 2I, can be obtained. As such, the correlation between the two transmitting antennas per coding block is cancelled if

(2l+2)T 2lT s 1r (t)s * 2r (t) dt = (2l+1)T 2lT s 11 (t)s * 21 (t) dt + (2l+2)T (2l+1)T s 12 (t)s * 22 (t) dt = 0. ( 10
)
Replacing s mr (t) by the corresponding CPM symbols from Eq. ( 4), we get

(2l+1)T 2lT exp j2π θ1(2l + 1) + h 2l+1 i=2l+2-γ d (i) 1,1 q(t -(i -1)T ) + c1,1(t) -θ2(2l + 1) -h 2l+2 i=2l+3-γ d (i) 2,1 q(t -(i -1)T ) -c2,1(t) dt+ (2l+2)T (2l+1)T exp j2π θ1(2l + 2) + h 2l+2 i=2l+3-γ d (i) 1,2 q(t -(i -1)T )+c1,2(t) -θ2(2l + 2) -h 2l+1 i=2l+2-γ d (i+1) 2,2 q(t -iT ) -c2,2(t) dt = 0. (11)
The phase memory θ m (2l + r) is independent of time and has not to be considered for integration. Using Eq. ( 5) to replace phase memory θ m (2l + 2) of the second time slot, we obtain

(2l+1)T 2lT exp j2π h 2l+1 i=2l+2-γ d (i) 1,1 q(t -(i -1)T ) + c1,1(t) -h 2l+1 i=2l+2-γ d (i) 2,1 q(t -(i -1)T ) -c2,1(t) dt+ exp j2π ξ1(2l + 1) -ξ2(2l + 1) • (2l+1)T 2lT exp j2π h 2l+1 i=2l+2-γ d (i+1) 1,2 q(t -(i -1)T ) + c1,2(t + T )- h 2l+1 i=2l+2-γ d (i+1) 2,2 q(t -(i -1)T ) -c2,2(t + T ) dt = 0. (12)

C. Simplifying assumptions

To simplify this expression, we factor Eq. ( 12) into a time independent and a time dependent part. For merging the two integrals to one time dependent part, we have to map d

(i) m2 to d (i)
m1 and c mr (t) to a different c m ′ r ′ (t). Consequently, for the data symbols d (i) mr there exist three possible ways of mapping:

• crosswise mapping with d

(i) 1,1 = d (i) 2,2 and d (i) 1,2 = d (i) 2,1 ; • repetitive mapping with d (i) 1,1 = d (i) 1,2 and d (i) 2,1 = d (i) 2,2 ; • parallel mapping with d (i) 1,1 = d (i) 2,1 and d (i) 1,2 = d (i) 2,2 .
The same approach can be applied to c mr (t):

• crosswise mapping with c 11 (t) = -c 22 (t -T ) and c 12 (t) = -c 21 (t -T );

• repetitive mapping with c 11 (t) = c 12 (t -T ) and c 21 (t) = c 22 (t -T );

• parallel mapping with c 11 (t) = c 21 (t) and c 12 (t) = c 22 (t). For each combination of mappings, Eq. ( 12) is now the product of two factors, one containing the integral and the other a time independent part. To fulfill Eq. ( 12) it is sufficient if one factor is zero, namely 1 + e j2π[ξ1(2l+1)-ξ2(2l+1)] = 0, i.e. if

k + 1 2 = ξ 1 (2l + 1) -ξ 2 (2l + 1) (13)
with k ∈ N. We thus get a very simple condition which only depends on ξ m (2l + 1).

D. Continuity of Phase

In this section we determine the functions ξ m (2l + 1) to ensure the phase continuity. Precisely, the phase of the CPM symbols has to be equal at all intersections of symbols. For an arbitrary block l, it means that φ m1 ((2l + 1)T ) = φ m2 ((2l + 1)T ). Using Eq. ( 4), it results in

ξ m (2l + 1) = h 2l+1 i=2l+2-γ d (i) m,1 q((2l + 2 -i)T ) + c m,1 ((2l + 1)T ) -h 2l+2 i=2l+3-γ d (i) m2 q((2l + 2 -i)T ) -c m2 ((2l + 1)T ). (14)
For the second intersection at (2l + 2)T , since φ m2 ((2l + 2)T ) = φ m1 ((2l + 2)T ), we get

ξ m (2l + 2) = h 2l+2 i=2l+3-γ d (i) m2 q((2l + 3 -i)T ) + c m2 ((2l + 2)T ) -h 2(l+1)+1 i=2(l+1)+2-γ d (i) m,1 q((2l + 3 -i)T ) -c m,1 ((2l + 2)T )]. (15)
Now, by choosing one of the mappings detailed in Section III, these equations can be greatly simplified. Hence, we have all the tools to construct our code.

III. ORTHOGONAL SPACE TIME CODES

In this section we will have a closer look at two codes constructed under the afore-mentioned conditions.

A. Existing Code

As a first example, we will give an alternative construction of the code given by Wang and Xia in [START_REF] Wang | An orthogonal space-time coded partial response CPM system with fast decoding for two transmit antennas[END_REF]. Indeed, the pointwise orthogonality condition used by Wang and Xia is a special case of the L 2 orthogonality condition, hence, their ST-code can be obtained within our framework.

For the first antenna Wang and Xia use a conventional CPM with d = -d i-1 for i = 2l + 3 -γ, 2l + 4 -γ, . . . , 2l + 2. Using this cross mapping makes it difficult to compute ξ m (2l + 1) since the CPM typical order of the data symbols is mixed. Wang and Xia circumvent this by introducing another correction factor for the second antenna

c 2r (t) = γ-1 i=0 (h(d 2l+1-i + d 2l+2-i ) + 1)q 0 (t -(2l + r -1 -i)T ) (16)
By first computing ξ m (2l + 1) with Eq. ( 17) and then Eq. ( 13), we get the L 2 orthogonality of the Wang-Xia-STC.

B. Parallel Code

To get a simpler correction factor as in [START_REF] Wang | An orthogonal space-time coded partial response CPM system with fast decoding for two transmit antennas[END_REF], we designed a new code based on the parallel structure which permits to maintain the conventional CPM mapping for both antennas. Hence we choose the following mapping:

d (i) m1 = d (i-1) m2 = d i for i = 2l + r + 1 -γ, 2l + r + 2 -γ, .
. . , 2l + r. Then, Eq. ( 14) and ( 15) can be simplified into

ξ m (2l + 1) = h 2 d 2l+2-γ + c m1 ((2l + 1)T ) -c m2 ((2l + 1)T ) (17)
ξ m (2l + 2) = h 2 d 2l+3-γ + c m2 ((2l + 2)T ) -c m1 ((2l + 2)T ). (18)
With this simplified functions, the orthogonality condition only depends on the start and end values of c mr (t), i.e.

k + 1 2 = c 11 ((2l + 1)T ) -c 12 ((2l + 1)T ) -c 21 ((2l + 1)T ) + c 22 ((2l + 1)T ). (19)
To merge the two integrals in Eq. ( 12) not only the mapping of d

(i)
mr is necessary but also an equality between different c mr (t). From the three possible mappings, we choose the repeat mapping because of the possibility to set c mr (t) to zero for one antenna. Hence we are able to send a conventional CPM signal on one antenna and a modified one on the second. Using Eq. ( 19) and the equalities for the mapping, we can formulate the following condition

k + 1 2 = c 12 (2lT ) -c 12 ((2l + 1)T ) -c 22 (2lT ) + c 22 ((2l + 1)T ). (20)
With c 11 (t) = c 12 (t) = 0, we can take for c 21 (t) = c 22 (t) any continuous function which is zero at t = 0 and 1/2 at t = T . Another possibility is to choose the correction factor of the second antenna with a structure similar to CPM modulation, i.e.

c 2r (t) = 2l+1 i=2l+1-γ q(t -(i -1)T ) (21)
for (2l + r -1)T ≤ t ≤ (2l + r)T . With this approach, the correction factors can be included in a classical CPM modulation with constant offset of 1/h. This offset may also be expressed as a modified alphabet for the second antenna

Ω d2 = {-M + 1 + 1 h , -M + 3 + 1 h , . . . , M -3 + 1 h , M -1 + 1 h } (22)
Consequently, this L 2 -orthogonal design may be seen as two conventional CPM designs with different alphabet sets Ω d and Ω d2 for each antenna. However, in this method, the constant offset to the phase may cause a shift in frequency. But as shown by our simulations in the next section, this shift is quite moderate.

IV. SIMULATIONS

In this section we verify the proposed algorithm by simulations. Therefore a STC-2REC-CPM-sender with two transmitting antennas has been implemented in MATLAB. For the signal of the first antenna we use conventional Gray-coded CPM with The channel used is a frequency flat Rayleigh fading model with additive white Gaussian noise. The fading coefficients α mn are constant for the duration of a code block (block fading) and known at receiver (coherent detection). The received signal y n (t) is demodulated by two filterbanks with pM 2 filters, which are used to calculate the correlation between the received and candidate signals. Due to the orthogonality of the antennas each filterbank is independently applied to the corresponding time slot k of the block code. The correlation is used as metric for the Viterbi algorithm (VA) which has pM states and M paths leaving each state. In our simulation, the VA is truncated to a path memory of 10 code blocks, which means that we get a decoding delay of 2 • 10T .

E b /N 0 BER 1Tx, 1Rx 2Tx, 1Rx 2Tx, 1Rx, Wang 2Tx, 2Rx
From the simulation results given in Figure 2, we can reasonably assume that the proposed code achieves full diversity. Indeed, the curves for the 2x1 and 2x2 systems respectively show a slope of 2 and 4. Moreover, the curve of the 2x1 systems follows the same slope as the ST code proposed by Wang and Xia [START_REF] Wang | An orthogonal space-time coded partial response CPM system with fast decoding for two transmit antennas[END_REF], which was proved to have full diversity. Note also that the new code provides a slightly better performance.

A main reason of using CPM for STC is the spectral efficiency. Figure 3 show the simulated power spectral density (psd) for both Tx antennas of the proposed ST code (continuous line) and the ST code proposed by Wang and Xia [START_REF] Wang | An orthogonal space-time coded partial response CPM system with fast decoding for two transmit antennas[END_REF]. The first antenna of our approach uses a conventional CPM signal and hence shows an equal psd. The spectrum of the second antenna is shifted due to adding an offset c mr (t) with a non zero mean. Minimizing the difference between the two spectra by shifting one, result in a phase difference of 0.375 measured in normalized frequency f • T d , where T d = T / log 2 (M ) is the bit symbol length. The first antenna of the Wang-Xia-algorithm has almost the same psd while the spectrum of the second antenna is shifted by approximately 0.56f • T d . This means that the OSTC by Wang and Xia requires a slightly larger bandwidth than our OSTC.

V. CONCLUSION

In applications where the power efficiency is crucial, combination of Continuous Phase Modulation and Space Time Coding has the potential to provide high spectral efficiency, thanks to spatial diversity. To address this power efficiency, ST code design for CPM has to ensure both low complexity decoding and full diversity. To fulfill these requirements, we have proposed a new L 2 orthogonality condition. We have shown that this condition is sufficient to achieve low complexity ML decoding and leads, with the help of simplifying assumption to a simple code. Moreover, simulations indicate that the code most probably achieves full diversity. Further work will be concentrated on the design of other codes based on L 2 orthogonality as in the meanwhile, we have been able to obtain the design of full diversity, full rate L 2 orthogonal codes for 3 antennas [START_REF] Hesse | L2 OSTC-CPM: Theory and design[END_REF].

Fig. 1 .

 1 Fig. 1. Structure of a MIMO Tx/Rx system

  = d i for i = 2l + r + 1 -γ, 2l + r + 2 -γ, . . . , 2l + r and c 1r (t) = 0. The symbols of the second antenna are mapped crosswise to the first d (i) 21 = -d i+1 for i = 2l + 2 -γ, 2l + 3 -γ, . . . , 2l + 1 and d (i-1) 22

Fig. 2 .Fig. 3 .

 23 Fig. 2. Simulated BER for different numbers of Tx and Rx antennas of the proposed STC and of the Wang-Xia-STC

The work of Matthias Hesse is supported by the EU by a Marie-Curie Fellowship (EST-SIGNAL program : http://est-signal.i3s.unice.fr) under contract No MEST-CT-2005-021175.