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

Jérémy Marrez
email: jeremy.marrez@sorbonne-universite.fr

Thomas Plantard
email: tplantard@paypal.com

Pascal Véron
email: pascal.veron@univ-tln.fr

ON POLYNOMIAL MODULAR NUMBER SYSTEMS OVER Z/pZ

Keywords: 2020 Mathematics Subject Classification: Primary: 11T06, 11T71; Secondary: 11H06, 94A60, 68W99 Polynomial Modular Number System, polynomial roots, finite field, modular arithmetic

Since their introduction in 2004, Polynomial Modular Number Systems (PMNS) have become a very interesting tool for implementing cryptosystems relying on modular arithmetic in a secure and efficient way. However, while their implementation is simple, their parameterization is not trivial and relies on a suitable choice of the polynomial on which the PMNS operates. The initial proposals were based on particular binomials and trinomials. But these polynomials do not always provide systems with interesting characteristics such as small digits, fast reduction, etc.

In this work, we study a larger family of polynomials that can be exploited to design a safe and efficient PMNS. To do so, we first state a complete existence theorem for PMNS which provides bounds on the size of the digits for a generic polynomial, significantly improving previous bounds. Then, we present classes of suitable polynomials which provide numerous PMNS for safe and efficient arithmetic.

Introduction

Context of the modular arithmetic. Modular arithmetic is at the core of modern cryptography [START_REF] Stinson | Cryptography Theory and Practice[END_REF]. Modular operations (essentially multiplication and addition) appear in most of today's public key cryptography. Widely used cryptographic protocols such as RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF], DSA [START_REF]Digital Signature Standard (DSS)[END_REF] and their counterparts based on elliptic curves [START_REF] Miller | Use of elliptic curves in cryptography[END_REF][START_REF] Koblitz | Elliptic curve cryptosystems[END_REF] are at the core of modern communication. The main cost of all these cryptosystems is due to modular arithmetic. Their potential successors, currently competing in the post-quantum cryptography standardization contest organized by the U.S. National Institute of Standards and Technology NIST [START_REF] Alagic | Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process[END_REF], also rely heavily on modular arithmetic. As an example, lattice based proposals such as Kiber [START_REF] Bos | Crystals-kyber: A CCA-secure module-lattice-based KEM[END_REF], NTRU [START_REF] Hoffstein | NTRU: A ring-based public key cryptosystem, Algorithmic Number Theory[END_REF], Saber [START_REF] D'anvers | Saber: Module-lwr based key exchange, CPA-secure encryption and CCA-secure KEM[END_REF], Falcon [START_REF] Prest | Falcon: Fast-Fourier Lattice-Based Compact Signatures Over NTRU[END_REF], or isogeny based key exchange (SIKE [START_REF] Jao | SIKE: Supersingular Isogeny Key Encapsulation[END_REF]) rely all on fast modular arithmetic. Furthermore, pairing based cryptography offers revolutionary protocols [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF] which rely as well on modular arithmetic on large moduli. Specific modular arithmetic. As improving modular arithmetic has such a wide impact on the efficiency of modern cryptographic protocols, special classes of moduli have been investigated. These special moduli are generally inspired by Mersenne numbers (integers of the form 2 m -1) to perform a modular reduction as fast as possible, namely Pseudo Mersenne [START_REF] Crandall | Method and Apparatus for Public Key Exchange in a Cryptographic System[END_REF], Generalized Mersenne [START_REF] Solinas | Generalized Mersenne Numbers[END_REF]. Other ones have been created to be particularly efficient when used with some specific algorithm. As an example, Montgomery-friendly primes [START_REF] Hamburg | Fast and compact elliptic-curve cryptography[END_REF][START_REF] Bos | Fast cryptography in genus 2[END_REF][START_REF] Bajard | Montgomery-friendly primes and applications to cryptography[END_REF] have been created to be operated with Montgomery reduction [START_REF] Montgomery | Modular multiplication without trial division[END_REF]. However, these classes are by definition limited and multiple cryptosystems require a free choice of the moduli on which they operate.

The origin of PMNS. To obtain efficient modular arithmetic for all moduli, and not only for a class of special moduli, the PMNS [START_REF] Plantard | Arithmétique Modulaire Pour la Cryptographie[END_REF] were proposed as an effective representation system. They operate without carry propagation and offer both the advantages of fast polynomial arithmetic and easy parallelization for arbitrary moduli p. Specifically, a PMNS is a modular system, where any integer a modulo p (which is not necessarily a prime) is represented as a polynomial A(X) of degree smaller than a fixed integer n. Modular multiplication and addition of two integers a and b in Z/pZ are then computed using their representatives A(X) and B(X) in the PMNS. The coefficients of the polynomials are the digits and are bounded by an integer ρ, which is small relatively to p (ρ p 1/n ). The construction of such systems is based on sparse polynomials whose roots γ are used as radices for this kind of positional representation, that is to say, A(γ) ≡ a (mod p). The interest of these sparse polynomials lies in the efficiency of the spawned modular arithmetic. The operations in PMNS are done in two steps. First, the operations are carried out on polynomials modulo a sparse polynomial E(X), called reduction polynomial, which is of degree n, and this reduction ensures that the degree of the result is smaller than n. In other words, to compute a b ( representing an addition or a multiplication), one computes C(X) = A(X) B(X) mod E(X). Then, a coefficient reduction is performed involving a lattice associated with the system [START_REF] Hanrot | Algorithms for the shortest and closest lattice vector problems[END_REF][START_REF] Plantard | LLL for ideal lattices: Re-evaluation of the security of gentry-halevi's fhe scheme[END_REF][START_REF] Galbraith | Mathematics of Public Key Cryptography[END_REF]; this operation guarantees that the coefficients of the result C(X) are bounded by ρ.

A method for constructing a prime p which has an efficient PMNS, has been published in 2004 [START_REF]Modular number systems: Beyond the Mersenne family, Selected Areas in Cryptography[END_REF]. The system is built from two sparse polynomials with good reduction properties (one is the reduction polynomial E(X), the other one is used for the coefficient reduction), in order to derive the corresponding integer p through the computation of a resultant, and also of one root γ. In order to be able to work with an arbitrary p, prime or not, another approach has been developed in [START_REF] Bajard | Arithmetic operations in the polynomial modular number system[END_REF] by constructing PMNS from an integer p, a number of digits n and an integer polynomial E(X) of the form E(X) = X n + aX + b satisfying some assumptions. Moreover, this result guarantees the existence of a PMNS with a bound on the digit size ρ allowing the representation of all numbers modulo p. Nevertheless, building such systems for a given p is not trivial.

The structure of the reduction polynomial E(X) gives the complexity of the polynomial reduction. Then, with p and a root γ of E(X) modulo p, we can define an associated lattice which allows to define the bound ρ on the coefficients of the representation and also provides the method of reduction of the coefficients. Therefore, it is interesting, for a given p, to find polynomials E(X) giving efficient polynomial modular reductions and roots γ to define the associated lattice and the reduction of the coefficients.

PMNS in a cryptographic context. The efficiency of this system of representation was the subject of an in-depth study in [START_REF] Didier | Efficient modular operations using the adapted modular number system[END_REF] for binomials E(X) = X n -λ. Such a representation system is called an AMNS (Adapted Modular Number System) [START_REF]Modular number systems: Beyond the Mersenne family, Selected Areas in Cryptography[END_REF]. It has been observed that, for primes p whose size fits the standard sizes used in elliptic curve cryptography (ECC), the AMNS representation allows to compute modular multiplications in a much more efficient way than the classical libraries OpenSSL and GnuMP (even if using for the latter the low level arithmetic functions and the undocumented Montgomery multiplication function). Later, this study has been confirmed in [START_REF] Coladon | Mphell: A fast and robust library with unified and versatile arithmetics for elliptic curves cryptography[END_REF] which described a specific library for ECC, named MPHELL, and compared it with other dedicated cryptographic libraries. The results show that on a 64-bit architecture, the AMNS representation gives the best results inside MPHELL for ECDSA/EdDSA signatures (generation and verification). Moreover, it offers also competitive timings on an ARM v8 architecture or a STM32F4 board. In [START_REF] Bouvier | An alternative approach for SIDH arithmetic, Public-key cryptography-PKC 2021[END_REF], the authors extend the AMNS representation system to F p k and show how it can be used in order to improve the performances of SIKE [START_REF] Jao | SIKE: Supersingular Isogeny Key Encapsulation[END_REF], one of the alternate KEM candidate of the NIST post-quantum standardization process [START_REF] Moody | Status Report on the Second Round of the Nist Post-Quantum Cryptography Standardization Process[END_REF]. A first hardware implementation of the AMNS is described in [START_REF] Chaouch | Two hardware implementations for modular multiplication in the AMNS: Sequential and semiparallel[END_REF]. To end, it is shown in [START_REF] Didier | Randomization of arithmetic over polynomial modular number system[END_REF][START_REF] Negre | Side Channel Counter-Measures Based on Randomized AMNS Modular Multiplication[END_REF] that some "random steps" can be injected in AMNS multiplication in order to resist to a side channel analysis.

Motivation and main results. The major motivation and result of this paper is an effective construction of efficient PMNS for any integer p. The efficiency is measured in particular by the minimality of the digit size ρ which depends on a reduced basis of the associated lattice that we explicitly construct. In Section 4, we give bounds and properties and used them in Sections 5 and 6 to define what is a suitable polynomial for PMNS. The main results can be summarised as follows :

1. Theorem 4.2 lays down critical result on PMNS existence. It relates the digit size ρ to the infinity norm of the transpose of a reduced basis (seen as a matrix) of the associated lattice. The reduction criterion consists, in this context of PMNS, in searching for a basis such that the infinity norm of its transpose is close to a minimal. 2. In Proposition 4.1, we first construct a reduced basis for a sublattice built from a short vector of the initial associated lattice. Proposition 4.2 specifies this point when E(X) is an irreducible polynomial. In this case, we give a bound for the digit size ρ depending only on p and E(X). Then, Corollaries 4.1 and 4.2 provide concrete construction methods for reduced lattice bases.

Then we introduce effective constructions of efficient PMNS introduced in

Sections 5 and 6. We provide multiple classes of polynomial E(X) over which PMNS can be efficiently used, with studies on both their irreducibility and the size of the set of their roots in Z/pZ, two key parameters for their usability.

Organization of the paper. This paper is organized as follows: Sections 2 and 3 recall the necessary background respectively on lattice theory and PMNS. Then Section 4 presents theorems, propositions and their corollaries, which provide criteria for constructing concrete efficient PMNS for any p. In Section 5, we specify what is a suitable reduction polynomial E(X), and propose main classes of suitable irreducible polynomials; they allow efficient reductions, and their roots can be clearly identified in a finite prime field Z/pZ. Section 6 studies the number of roots in a finite prime field Z/pZ of the reduction polynomial E(X).

Lattice basics

Lattice theory, also known as geometry of numbers, was introduced by H. Minkowski in 1896 [START_REF] Minkowski | Geometrie der Zahlen[END_REF].

A comprehensive discussion on the basics of lattice theory is presented in [START_REF] Cassels | An Introduction to the Geometry of Numbers[END_REF][START_REF] Lovász | An Algorithmic Theory of Numbers, Graphs and Convexity[END_REF][START_REF] Conway | Sphere Packings, Lattices and Groups, Grundlehren der mathematischen Wissenschaften[END_REF]. We present in this section only the different definitions and results useful for the comprehension of our paper. Definition 2.1 (Lattice). A lattice L is a discrete subgroup of R n , that is, the set of all the integral combinations of d n linearly independent vectors over R:

L = Z b 1 + • • • + Z b d , b i ∈ R n .
Here, B = (b 1 , ..., b d ) is called a basis of L and d, the dimension of L. We note L(B) a lattice of basis B. If d = n, the lattice is called full-rank.

The determinant of L defined by det L = det (BB T ) is invariant for any basis B of L.

Lattice theory problems are based on minimising the distance between vectors. The natural norm used in lattice theory is the euclidean norm. The euclidean norm of a vector v is computed by

v 2 = n i=1 v 2 i .
Other l p -norm, v p = ( n i=1 |v i | p ) 1/p , can also be used. If p = ∞, then the norm is called the max-norm v ∞ = max n i=1 |v i |. One of the most studied lattice problems is the Shortest Vector Problem (SVP). Definition 2.2 (SVP). Given a lattice L, solving the Shortest Vector Problem, amounts to finding a vector u ∈ L such that ∀v ∈ L \ {0}, 0 < u v for a given norm . . The norm u of such vector u is called the first minimum and is denoted as λ 1 . Moreover, λ i will represent the norm of the i th minimum (the minimum norm of i linearly independent vectors). If the norm is not specified, one will assume λ i to be the i th minimum of L for the Euclidean norm, λ i,p will represent the i th minimum of L for the l p norm.

In 1998, M. Ajtai [START_REF] Ajtai | The shortest vector problem in l 2 is NP-hard for randomized reductions[END_REF] proved that SVP is NP-hard under a randomized reduction. Therefore, the best algorithm to compute SVP in polynomial space uses exponential time. It was proposed by R. Kannan in 1983 and relies on strongly reducing each vector of a basis by recursion. It is often referenced as HKZ for Hermite-Korkin-Zolotareff. Its current best time estimation is at 2 O(d) d d 2e [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm[END_REF]. Furthermore, some polynomial solutions exist as well such as LLL [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] or BKZ [START_REF] Schnorr | Block reduced lattice bases and successive minima[END_REF]. However, these solutions return vectors whose norm is equal to the size of the shortest vector times an exponential factor.

Nevertheless, certain bounds do exist on the first minimum and were given by Minkowski's initial work:

Theorem 2.3 (Minkowski). Let L a lattice of dimension d, then λ 1,∞ (det L) 1 d .
This bound is tight in max-norm. However, it is still an open problem for the Euclidean Norm. A second key problem of lattice theory is the Closest Vector Problem (CVP). Definition 2.4 (CVP). Given a lattice L and a vector w, to solve CVP is to find a vector u ∈ L such that ∀v ∈ L, w -u w -v . The quantity w -u is noted dist(w, L).

The problem CVP is NP-Hard as well [START_REF] Van Emde | Another NP-Complete Problem and the Complexity of Computing Short Vectors in Lattices[END_REF]. Finally, a key invariant has been studied to try to evaluate the orthogonality of a lattice, i.e., the Covering Radius. Definition 2.5 (Covering Radius). Let L be a full rank lattice. The covering radius of L, noted µ(L), is the supremum of distances between any vector of R d and L, i.e., µ(L) = max

v∈R d dist(v, L) .
No polynomial algorithm exists to find the covering radius [START_REF] Guruswami | The complexity of the covering radius problem on lattices and codes[END_REF]. However, we know that for any l p -norm [START_REF] Guruswami | The complexity of the covering radius problem on lattices and codes[END_REF], we have

µ p (L) λ d,p 2 .
For the Euclidean norm, we know that µ 2 (L) √ dλ d (L) [START_REF] Guruswami | The complexity of the covering radius problem on lattices and codes[END_REF]. By simple norm relation, we obtain that µ ∞ (L) √ dλ d (L).

Polynomial Modular Number System

In this section, we recall basic definitions and results on PMNS.

Definition 3.1 (Polynomial Modular Number System). Let p 3, n 2, γ ∈ [1, p -1] and ρ ∈ [1, p -1] be integers. Let E(X) ∈ Z[X] be a monic polynomial of degree n that satisfies E(γ) ≡ 0 (mod p). A Polynomial Modular Number System (PMNS) is a set B ⊂ Z[X] such that: 1. ∀A(X) ∈ B, deg(A(X)) < n, 2. ∀A(X) = n-1 i=0 a i X i ∈ B, -ρ < a i < ρ for all i, 3. ∀a ∈ {0, . . . p -1}, ∃A(X) ∈ B such that A(γ) ≡ a (mod p). The polynomial E(X) is called reduction polynomial with respect to p.
A PMNS is thus a system of representation for elements in Z/pZ where

a ∈ Z/pZ with a ≡ n-1 i=0 a i γ i (mod p) = A(γ) mod p and -ρ < a i < ρ for all .
It looks a priori like the classic γ-ary positional system but since the γ i mod p are not ordered, there is no obvious way to compare two representatives A(X) and B(X) without computing A(γ) mod p and B(γ) mod p. This is clearly shown in Example 1.

Throughout this paper, we use the notation B = (p, n, γ, ρ) E to recall that the PMNS B is determined by these five parameters. Also, with a polynomial A(X) = a 0 + a 1 X + • • • + a n-1 X n-1 we associate the vector A = (a 0 , a 1 , . . . , a n-1 ). We will switch between both notation when it is best suited for comprehension.

Operations in B are first done modulo E(X), and then a coefficient reduction process is performed, by subtracting an appropriate polynomial having γ as root modulo p, to guarantee that all the coefficients are bounded by ρ in absolute value [START_REF] Plantard | LLL for ideal lattices: Re-evaluation of the security of gentry-halevi's fhe scheme[END_REF][START_REF] Didier | Efficient modular operations using the adapted modular number system[END_REF].

Example 1. Table 1 shows how to represent elements of Z/31Z as polynomials of degree lower or equal to 3 and coefficients belonging to {-1, 0, 1}.

0 1 2 3 4 5 (0, 0, 0, 0) (1, 0, 0, 0) (-1, 1, -1, 1) (-1, -1, -1, 1) (-1, 0, 0, -1) (-1, 0, 1, 1) (0, 1, -1, 1) (0, -1, -1, 1) (0, 0, 0, -1) (0, 0, 1, 1) (1, 1, -1, 1) (1, -1, -1, 1) (1, 0, 0, -1) (1, 0, 1, 1) 6 7 8 9 10 11 (-1, 1, -1, 0) (-1, -1, -1, 0) (-1, 0, 1, 0) (0, 1, -1, 0) (0, -1, -1, 0) (0, 0, 1, 0) (1, 1, -1, 0) (1, -1, -1, 0) (1, 0, 1, 0) (-1, 1, -1, -1) (-1, 1, 0, 1) (-1, -1, -1, -1) (-1, -1, 0, 1) (-1, 0, 1, -1) (0, 1, -1, -1) (0, 1, 0, 1) 12 13 14 15 16 17 (0, -1, -1, -1) (0, -1, 0, 1) (0, 0, 1, -1) (1, 1, -1, -1) (1, 1, 0, 1) (1, -1, -1, -1) (1, -1, 0, 1) (1, 0, 1, -1) (-1, 1, 0, 0) (-1, -1, 0, 0) (0, 1, 0, 0) (0, -1, 0, 0) (1, 1, 0, 0) (1, -1, 0, 0) 18 19 20 21 22 23 (-1, 0, -1, 1) (-1, 1, 0, -1) (-1, 1, 1, 1) (-1, -1, 0, -1) (-1, -1, 1, 1) (0, 0, -1, 1) (0, 1, 0, -1) (0, 1, 1, 1) (0, -1, 0, -1) (0, -1, 1, 1) (1, 0, -1, 1) (1, 1, 0, -1) (1, 1, 1, 1) (1, -1, 0, -1) (1, -1, 1, 1) (-1, 0, -1, 0) (-1, 1, 1, 0) (-1, -1, 1, 0) (0, 0, -1, 0) (0, 1, 1, 0) 24 25 26 27 28 29 (0, -1, 1, 0) (1, 0, -1, 0) (1, 1, 1, 0) (1, -1, 1, 0) (-1, 0, -1, -1) (-1, 0, 0, 1) (-1, 1, 1, -1) (-1, -1, 1, -1) (0, 0, -1, -1) (0, 0, 0, 1) (0, 1, 1, -1) (0, -1, 1, -1) (1, 0, -1, -1) (1, 0, 0, 1) (1, 1, 1, -1)
(1, -1, 1, -1) 30 (-1, 0, 0, 0) Table 1. Elements of Z/31Z are represented as polynomials in γ, noted as vectors with lowest degree first. The reduction polynomial is E

(X) = X 4 -2 and γ = 15 is a root of E(X). The digit set is {-1, 0, 1} (i.e., ρ = 2 )
We note that some values have more than one representation. This redundancy is not studied here, but it is useful in some applications [START_REF] Didier | Randomization of arithmetic over polynomial modular number system[END_REF]. Since all the elements of Z/pZ are represented, the value of ρ satisfies n √ p ≤ 2ρ -1, and redundancy starts

when n √ p+1 2 < ρ.
Remark 1. In [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF], the authors proved that for every quadruple (p, n, γ, ρ), there always exists a polynomial

E(X) ∈ Z[X] satisfying E(γ) ≡ 0 mod p, deg E(X) = n and E(X) = X n -c with |c| 2 n 2 .
However, one cannot hope to obtain fast primitives for modular arithmetic using a polynomial E(X) with such a coefficient c exponential in n. Indeed, it is important to understand that modular operations are replaced in a PMNS by polynomial operations modulo E(X), so that the degree of the result be still less than or equal to n. The small size of the coefficients and the low density of the reduction polynomial E(X) play a key role in the efficiency of modular reductions and in maintaining concise arithmetic.

Moreover, from a cryptographic point of view in the context of Side Channel Resistance, it could be of interest to build a PMNS from a polynomial E(X) which has numerous roots modulo p, since distinct roots yield distinct associated PMNS. In other words, from one execution to another one, for a fixed polynomial E(X), a same secret value k could be represented by a polynomial K(X) which depends on the root used to build the PMNS.

Consequently, once the parameters p and n are given, or in other words, once it has been held that the integers modulo p will be encoded on n symbols, the key question that arises is then which polynomials E(X)

1. allow one to find a parameter ρ as small as possible, 2. offer a good modular reduction, 3. have a large number of roots γ in Z/pZ.

Next sections of this paper are devoted to these questions.

Construction and specifications of PMNS

In this section, we give conditions to ensure the existence of a PMNS B = (p, n, γ, ρ) E for a generic E(X).

Theorem 4.1. Let p 2 and n 2 be two integers, E(X) be a monic polynomial of degree n in Z[X] and γ an integer which is a root of E(X) in Z/pZ. Let L be the n-dimensional lattice generated by the polynomials in Z[X] of degree at most n-1 for which γ is a root modulo p. This lattice L is generated by the following n × n matrix A (with respect to the canonical monomial basis, with polynomials represented in lines) Proof. Let a ∈ [0, p -1] and let T a (X) = a. We know that for any vector

(1) A =           p 0 . . . . . . 0
T ∈ R n there exists V ∈ L such that T -V ∞ µ ∞ (L). Hence, there exists V a ∈ L such that T a -V a ∞ µ ∞ (L) < ρ, and (T a -V a )(γ) ≡ T a (γ) -V a (γ) ≡ a mod p (since V a ∈ L). In consequence, for any a ∈ [0, p -1], T a -V a is a polynomial which fulfills the condition of Theorem 3.1. We conclude that B = (p, n, γ, ρ) E is a PMNS.
Currently, there is no efficient algorithm to compute the covering radius of a lattice. In the next two sections, we describe how to obtain an effective calculation of the bound on ρ.

Relation between the lattice's basis and the PMNS.

Theorem 4.2. Let p 2 and n 2 be two integers, E(X) be a monic polynomial of degree n in Z[X] and γ be a root of E(X) in Z/pZ.

Let L be the lattice of polynomials in Z[X] of degree at most n -1, for which γ is a root modulo p , B a basis of L and B the matrix associated to this basis (each row is an element of B). Then,

for any ρ > 1 2 B T ∞ = max j n-1 i=0 |b i,j | , B = (p, n, γ, ρ) E is a Polynomial Modular Number System.
Proof. Following the proof of Theorem 4.1, we only have to show that for any polynomial S(X), one can find a polynomial T (X)

∈ L such that S -T ∞ 1 2 B T ∞ . Let S ∈ R n .
We define: • S as the vector whose coordinates are integers equal to the rounding to nearest integer of those of S; • frac(S) as the vector (S) = S -S ; notice that frac(S) ∞ 1 2 . Let S ∈ R n . We search a close vector T ∈ L using a Babaï round-off approach [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF]. We have,

T = B T • (B T ) -1 • S , thus S = B T • (B T ) -1 • S = T + B T • frac (B T ) -1 • S with frac (B T ) -1 • S ∞ 1 2 . Then S -T ∞ = B T • frac (B T ) -1 • S ∞ 1 2 B T ∞ .
In order to minimize ρ, a natural strategy is to choose a basis B so that B T ∞ is small. Such a basis can be computed from A (Theorem 4.1, Eq. ( 1)) using algorithms like LLL, BKZ or HKZ.

The next strategies can be applied when the polynomial E(X) is irreducible.

4.2.

The case of irreducible reduction polynomials. Notice that Theorem 4.2 states that for any vector S ∈ R n , one can compute a vector T in a lattice L such that S -T ∞ be smaller than 1 2 B T ∞ , where B is a basis of L and B its matrix form. The result holds for any lattice L and any basis B of this lattice. As a consequence, it can be applied to any basis B of a sublattice L of the lattice L linked to the PMNS. The strategies described in this section are based on this remark.

Let E(X) = X n + a n-1 X n-1 + • • • + a 1 X + a 0 , and let C be the companion matrix of E(X):

(2) C =          0 1 0 . . . 0 0 0 0 1 . . . 0 0 . . . . . . . . . . . . . . . . . . 0 0 0 . . . 1 0 0 0 0 . . . 0 1 -a 0 -a 1 -a 2 . . . -a n-2 -a n-1          .
Let V = (v 0 , . . . , v n-1 ) be the vector representing the coefficients of the polynomial V (X) = n-1 i=0 v i X i , then V.C is the vector whose coordinates are the coefficients of the polynomial X.V (X) mod E(X). Proposition 4.1. Let V be a non-zero vector of L, the lattice of rank n defined by A (Theorem 4.1, Eq. (1)). Let B i = V • C i be the row vector whose coordinates are the coefficients of the polynomial B i (X) = X i • V (X) mod E(X). Let B be the n × n matrix whose i th row is the vector

B i . If V (X) is inversible modulo E(X) then: • the matrix B defines a sublattice L ⊆ L of rank n (i.e., B = (B 0 , . . . , B n-1 )
is a basis of L ), • and V ∈ L .

Proof. The B i are linearly independent. Indeed, let us suppose that there exists a non-zero vector (t 0 , t 1 , . . . , t n-1 ) ∈ Z n such that

n-1 i=0 t i B i = 0. It means that n-1 i=0 t i X i V (X) = 0 mod E(X), or equivalently T (X)V (X) = 0 mod E(X), with T (X) = n-1 i=0 t i X i . Then T (X)V (X)V -1 (X) mod E(X) = T (X) = 0, since V (X)
is inversible modulo E(X) and degree of T (X) is at most n -1. Hence the rows of B are a basis of a sublattice L ⊆ L of rank n, and V ∈ L (which corresponds to the first row of B).

Corollary 4.1. Let V be a non-zero vector of L, the lattice of rank n defined by A (Theorem 4.1, eq. (Eq. (1))).

If E(X) is irreducible, then • V defines a sublattice L ⊆ L of rank n, (i.e., B = (B 0 , . . . , B n-1 ), defined in Proposition 4.1 is a basis of L ), A possible strategy to lower the bound on ρ is then to take a short vector V ∈ L, that is, a vector which satisfies the Minkowski bound V ∞ αp 1/n with α ∈ ]0, 1]. From this vector V , we build the basis B of the sublattice L to compute the lower bound on ρ.

• moreover V ∈ L . Proof. If E(X) is irreducible, then V (X)
In this context, we can provide a bound such that if ρ is greater than this, then we are guaranteed to have a PMNS. Let us consider the (2n-1)×n matrix M whose rows are the coefficients of X i mod E(X) for 0 i 2n -2. For any polynomial T (X) of degree at most 2n -2, the coefficients of T (X) mod E(X) are computed as the vector-matrix product T M . Proposition 4.2. Let E(X) be an irreducible polynomial, let M be the (2n -1) × n matrix whose rows are the coefficients of X i mod E(X), for 0 i 2n -2, and

s = M T ∞ . If ρ > 1 2 p 1/n (1 + (n -1)s) ( 1 2 B T ∞ ), then B = (p, n, γ, ρ) E is a Polynomial Modular Number System.
Proof. Let V be a short vector of the lattice L, hence V ∞ p 1/n . From Proposition 4.1, the matrix B is a basis of a sublattice L . Each row B i contains the coefficients of X i V (X) mod E(X). These coefficients are computed as the vectormatrix product T (i) M where T

(i) (X) = X i V (X). Hence B i ∞ s V ∞ for i 1, and B 0 ∞ p 1/n . Therefore B T ∞ p 1/n (1 + (n -1)s).
We conclude using Theorem 4.2.

A second strategy is to use the companion matrix C of E(X) for computing a basis B of L . Corollary 4.2. Let L be the lattice of rank n given by A (Theorem 4.1, eq. Eq. (1)), let C be the companion matrix of E(X), and let L D be the lattice of rank n in Z n 2 defined by D = (A|A

• C 1 | • • • |A • C n-1 ).
reducing modulo E(X), E(X) must respect some criteria, in particular with respect to the size of the digits in B = (p, n, γ, ρ) E . We thus define what can be a suitable PMNS irreducible reduction polynomial. 5.1. Suitable PMNS reduction polynomial. Definition 5.1. A polynomial E(X) is a suitable PMNS reduction polynomial, if:

1

. E(X) is irreducible in Z[X], 2. E(X) = X n + a k X k + • • • + a 1 X + a 0 ∈ Z[X],
with n 2 and k n 2 , 3. most of the coefficients a i are zero, other ones are very small (if possible equal to ±1) compare to p 1/n .

The second item ensures that the polynomial reduction modulo E(X) of a polynomial T (X) of degree lower than 2n is done in two steps, i.e., by two times, we split T (X) = T 1 (X)X n + T 0 (X) with T 1 (X) and T 0 (X) of degree lower than n, and we substitute X n mod E(X) = -(

k i=0 a i X i ) mod E(X).
The third item allows one to give a bound on the coefficients of T (X) mod E(X), namely T (X) mod E(X) ∞ < s T (X) ∞ , where s is the l1-norm of the (2n -1) × n matrix S whose row i represents the coefficients of X i (mod E(X)) for i = 0 . . . 2n -1 (see Prop. 2.3 of [START_REF] Didier | Randomization of arithmetic over polynomial modular number system[END_REF]). As a consequence, if G(X) and F (X) are two elements of the PMNS, i.e., F (X)

∞ < ρ and G(X) ∞ < ρ, then F (X) × G(X) ∞ < nρ 2 and F (X) × G(X) (mod E(X)) ∞ < snρ 2 .

Why consider alternatives for E(X)

Since the definition of the PMNS representation system, all the research focused on the polynomial E(X) = X n -λ because the external reduction can be efficiently performed when λ is "small" (often a power of 2 to use logical operator) [START_REF]Modular number systems: Beyond the Mersenne family, Selected Areas in Cryptography[END_REF][START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF][START_REF] Mrabet | Finite field multiplication combining AMNS and DFT approach for pairing cryptography[END_REF][START_REF] Mrabet | Efficient multiplication over extension fields, Arithmetic of Finite Fields[END_REF][START_REF] Didier | Randomization of arithmetic over polynomial modular number system[END_REF][START_REF] Didier | Efficient modular operations using the adapted modular number system[END_REF][START_REF] Bouvier | An alternative approach for SIDH arithmetic, Public-key cryptography-PKC 2021[END_REF][START_REF] Coladon | Mphell: A fast and robust library with unified and versatile arithmetics for elliptic curves cryptography[END_REF][START_REF] Negre | Side Channel Counter-Measures Based on Randomized AMNS Modular Multiplication[END_REF]. Now, from proposition 4.2, we know that the size of the coefficients used in the PMNS representation system depends on the parameter s which in turn depends on the coefficients of the polynomial E(X) since s = M T ∞ where M is the (2n-1)×n matrix whose rows are the coefficients of X i mod E(X). Hence the smaller s is, the smaller ρ is. As a toy example, let us consider n = 6 and the irreducible polynomial E(X) = X 6 + 4, then it is easy to see that s = 5 since each column of M contains only two elements (1 and -4), except the last one which contains only one element equal to 1. Now let us consider E(X) = X 6 -X -1, then it is irreducible (see proposition 5.5) and a simple computation gives s = 3. This value for s can also be obtained considering the polynomial E(X) = X 6 -2 which corresponds to the AMNS case. In fact, for the AMNS case, one can see that s = |λ| + 1, hence s is proportional to λ. So, the only way to minimize s is to take λ = ±2 (a simple argument shows that λ = ±1 does not allow to build an AMNS). Notice that the reduction modulo X 6 -X -1 is very efficient and competitive with the one computed with X 6 -2. Our goal to study suitable PMNS reduction polynomial is thus to enlarge the set of polynomials which can be used to define a PMNS without being restricted to the exclusive choise of the AMNS subset taking λ = ±2. We propose to developpers a set of polynomials for which the value s can easily be computed so that depending on the context (software or hardware), they can select the better choice which fits their constraints.

Another point of view concerns countermeasure to side channel attack. In the spirit of what has been proposed in [START_REF] Bajard | Leak resistant arithmetic[END_REF], one may consider to build for a fixed prime p numerous PMNS representations. Let us consider the ECC context. Once kP must be computed, first we choose the PMNS system to use, than we compute kP . This approach complements other countermeasures described in [START_REF] Didier | Randomization of arithmetic over polynomial modular number system[END_REF][START_REF] Negre | Side Channel Counter-Measures Based on Randomized AMNS Modular Multiplication[END_REF]. Now, from a practical point of view, if we focus on the polynomials E(X) = X n -λ with λ a power of 2, this will drastically reduce the choice of possible PMNS. Hence our goal is to enlarge the possible choice of PMNS for a prime p by considering other polynomials E(X) with small coefficients so that the external reduction can be efficiently performed and so that ρ be small.

According to the first item of Theorem 5.1, a suitable polynomial is irreducible. In the sequel, we adapt some classical irreducibility criteria and give examples of irreducible polynomials with few non-zero coefficients satisfying the two other items.

Classical polynomial irreducibility criteria.

To verify the first item of Theorem 5.1, we can use general criteria such as the Schönemann-Eisenstein criterion, Dumas' criterion [START_REF] Dumas | Sur quelques cas d'irreductibilité des polynômes à coefficients rationnels[END_REF] or the generalization given by N. C. Bonciocat in [START_REF]Schönemann-Eisenstein-Dumas-type irreducibility conditions that use arbitrarily many prime numbers[END_REF]. We adapt these criteria to our purpose, namely to a monic polynomial E

(X) = X n + a k X k + • • • + a 1 X + a 0 , with k n
2 . Proposition 5.1 (from Dumas' criterion [START_REF] Dumas | Sur quelques cas d'irreductibilité des polynômes à coefficients rationnels[END_REF]). If there exists a prime µ and an integer α such that, µ α | a 0 , µ α+1 a 0 , µ α(n-i)/n | a i , and

gcd(α, n) = 1, then E(X) = X n + a k X k + • • • + a 1 X + a 0 is irreducible over Z[X].
For example, E(X) = X n + µX k + µ is irreducible according to this criterion. If k < n/2 and µ << p 1/n , then E(X) is a suitable PMNS reduction polynomial.

Proposition 5.2 (from Corollary 1.2 [10]). Let E(X) = X n +a k X k +• • •+a 1 X +a 0 , a 0 = 0, let t
2 and let µ 1 , . . . , µ t be pairwise distinct numbers, and α 1 , . . . , α t positive integers. If, for j = 1, . . . , t, and i = 0, . . . , k, µ αj j | a i , µ αj +1 j a 0 , and

gcd(α 1 , . . . , α t , n) = 1, then E(X) is irreducible over Z[X]. For example, E(X) = X n + µ α1 1 µ α2 2 X k + µ α1 1 µ α2 2 , with gcd(α 1 , α 2 , n) = 1
, is irreducible with this criterion. If k < n/2 and µ α1 1 µ α2 2 << p 1/n , then E(X) is a suitable PMNS reduction polynomial.

Suitable cyclotomic polynomials for PMNS.

A well-known set of irreducible polynomials in Z [X] is the set of cyclotomic polynomials. Let us denote by ClassCyclo(n) the class of suitable cyclotomic polynomials for PMNS, whose degree is n. Proposition 5.3. For n > 1, Φ m (X) the m-th cyclotomic polynomial is a suitable polynomial if and only if ϕ(m) = n = 2 i 3 j with i 1, j 0.

(i.e., ClassCyclo(n) = ∅ if and only if n = 2 i 3 j with i 1, j 0.)

Proof. For m > 1 Φ m (X) the m-th cyclotomic polynomial, is self-reciprocal, Φ m (X) = X n Φ m ( 1 X ) with n = ϕ(m)
the degree of Φ m (X), (i.e.,the coefficients a i of the term X i are equal to those a n-i of the terms X n-i for all i). Thus, suitable cyclotomic polynomials will be of the form X 2n + aX n + 1 with n = 2n .

If X 0 is a root of a cyclotomic X 2n + aX n + 1, then X n 0 is a root of unity and a root of X 2 + aX + 1, as its conjugate too, hence we have a = 2 • cosθ. Since a is an integer, we have a = ±2, ±1, 0. But, for a = ±2 the polynomial X 2n ± 2X n + 1 = (X n ± 1) 2 is not irreducible. Therefore a = ±1, 0.

• a = 0, we consider

X n + 1. If n = 2 i • t with t > 1 odd then X n + 1 = (X 2 i + 1)(X 2 i •(t-1) + X 2 i •(t-2) + • • • + 1
). Thus n = 2 i and the cyclotomic polynomials are Φ 2 i+1 (X) = X 2 i + 1.

• a = 1, then we look for Φ m (X) = X 2n + X n + 1, and e 2iπ 3n

is a root of this polynomial. e 2iπ 3n is also a root of X 3n -1. We know that X 3n -1 is the product of the cyclotomic Φ d (X) with d|3n and e 2iπ 3

is one of its roots, thus

e 2iπ 3
is a root of

X 3n -1 X 2n +X n +1 = X n -1.
Hence n is a multiple of 3 and by induction n = 3 j and Φ m (X) = Φ 3 j+1 (X) = X 2•3 j + X 3 j + 1 with j ≥ 0.

• a = -1, then we look for Φ m (X) = X 2n -X n + 1. Let n = 2 i-1 • α, with α odd and i ≥ 1, then X 2 i α -X 2 i-1 α + 1 = (-X 2 i-1 ) 2α + (-X 2 i-1 ) α + 1,
we can refer to the previous case to deduce that α = 3 j . Thus Φ m (X) =

Φ 2 i 3 j+1 (X) = X 2 i •3 j -X 2 i-1 3 j + 1 with i ≥ 1 and j ≥ 0. We have proved that for n > 1, if ClassCyclo(n) = ∅ then n = 2 i 3 j with i 1, j 0.
Reciprocally, for n = 2 i 3 j , i 1, j 0, we have to show that there exists a suitable cyclotomic polynomial whose degree is n.

Let n = 2 i (i 1), since n = ϕ(m), then m = 2 i+1 and Φ 2 i+1 (X) = X 2 i + 1 is a suitable cyclotomic polynomial.

Let n = 2.3 j (j 1), since n = ϕ(m), then m = 3 j+1 and Φ 3 j+1 (X) = X 2.3 j + X 3 j + 1 is a suitable cyclotomic polynomial.

Let n = 2 i 3 j (i 2, j 1), since n = ϕ(m), then m = 2 i 3 j+1 and

Φ 2 i 3 j+1 (X) = X 2 i 3 j -X 2 i-1 3 j + 1 is a suitable cyclotomic polynomial.
5.4. Suitable reduction {-1, 1}-quadrinomials. In [START_REF] Finch | On the irreducibility of {-1, 0, 1}-quadrinomials[END_REF], Finch and Jones give criteria of irreducibility for polynomials X a + βX b + γX c + δ with β, γ, δ ∈ {-1, 1} and a > b > c > 0.

Proposition 5.4 (Theorem 2 in [START_REF] Finch | On the irreducibility of {-1, 0, 1}-quadrinomials[END_REF] ). The quadrinomial X a + βX b + γX c + δ with β, γ, δ ∈ {-1, 1} and a > b > c > 0, is irreducible over Z[X] if and only if gcd(a, b, c) = 2 t m with m odd, and it satisfies one of the following conditions :

1. (β, γ, δ) = (1, 1, 1) and abc ≡ 1 (mod 2),

2. (β, γ, δ) = (-1, 1, 1), b -c ≡ 0 (mod 2a), b ≡ 0 (mod 2b) and a -b ≡ 0 (mod 2c), 3. (β, γ, δ) = (1, -1, 1), b -c ≡ 0 (mod 2a), a -c ≡ 0 (mod 2b) and c ≡ 0 (mod 2c), 4. (β, γ, δ) = (1, 1, -1), a ≡ 0 (mod 2a), b ≡ 0 (mod 2b) and c ≡ 0 (mod 2c), 5. (β, γ, δ) = (-1, -1, -1), a ≡ 0 (mod 2a), a -c ≡ 0 (mod 2b) and a -b ≡ 0 (mod 2c). Where a = a/2 t , b = b/2 t , c = c/2 t and a = gcd(a , b -c ), b = gcd(b , a -c ), c = gcd(c , a -b ).
We call this class of suitable reduction quadrinomials ClassQuadrinomials, and ClassQuadrinomials(n) is the set of such quadrinomials of degree n.

For example, E(X) = X 2 t 7m + X 2 t 3m + X 2 t m + 1, with m odd, is a suitable PMNS reduction quadrinomial verifying the first condition. 5.5. Suitable reduction {-1, 1}trinomials. In this part we refer to a paper of W.H. Mills [START_REF] Mills | The factorization of certain quadrinomials[END_REF] and one of W. Ljunggren [START_REF] Ljunggren | On the irreducibility of certain trinomials and quadrinomials[END_REF]. The first one gives a criterion on quadrinomials and roots of unity, the second one gives an application to trinomials. Proposition 5.5. We note gcd(n, m) = d and n

= d•n 1 , m = d•m 1 . If n 1 +m 1 ≡ 0 mod 3, then the polynomial X n + βX m + δ with δ, β ∈ {-1, 1} and n > 2m > 0 is irreducible over Z[X].
The class of the suitable reduction trinomials verifying these criteria is named ClassTrinomials, and ClassTrinomials(n) represents the set of the trinomials of degree n.

Proof. Let us transform, like in [START_REF] Ljunggren | On the irreducibility of certain trinomials and quadrinomials[END_REF], E(X) = X n + βX m + δ in quadrinomial:

(X n + βX m + δ) (X n -δ) = X 2n + βX n+m -βδX m -1 = F (X).
Theorem 2 of [START_REF] Mills | The factorization of certain quadrinomials[END_REF] states that if F (X) = A(X)E(X), where every root of A(X) and no root of E(X) is a root of unity, then E(X) is irreducible except if there exists r such that:

• (2n, n + m, m) = (8r, 7r, r) and (β, δ) = (1, -1) or (-1, -1),

• or (2n, n + m, m) = (8r, 4r, 2r) and (β, δ) = (1, -1),

• or (2n, n + m, m) = (8r, 6r, 4r) and (β, δ) = (-1, -1).

It is easy to check that there is no integer r which satisfies any of these 3 constraints, hence we only have to verify that no root of E(X) is a root of unity. First notice that, because n = dn 1 and m = dm 1 with gcd(n 1 , m 1 ) = 1, if λ is a root of E(X), then λ d is root of X n1 + βX m1 + δ. Hence, if the roots of X n1 + βX m1 + δ are not roots of unity, then no root of E(X) = X n + βX m + δ is a root of unity.

Let us assume that λ is a root of X n1 + βX m1 + δ, which is also a root of unity. Then there exit t > 1 and k with gcd(k, t) = 1, such that: Last equality implies that sin( kπ(n1+m1) t ) = 0 or cos( kπ(n1-m1) t ) = 0. Since δ = 0, the first equation implies that cos( kπ(n1-m1) t ) = 0, hence k(n1+m1) t is an integer. Since gcd(k, t) = 1, t | (n 1 + m 1 ). This last result implies that the first equation can be reduced to

λ = e
cos kπ(n 1 -m 1 ) t = ± 1 2 because δ = ±1. It means that kπ(n 1 -m 1 ) t = j π 3 , j = 1, 2, 4, 5 (mod 6). Hence, t | 3(n 1 -m 1 ), since gcd (k, t) = 1.
Assume that β = -1. The system becomes:

cos( 2n1kπ t ) -cos( 2m1kπ t ) = -2 sin( kπ(n1+m1) t ) sin( kπ(n1-m1) t ) = -δ sin( 2n1kπ t ) -sin( 2m1kπ t ) = 2 cos( kπ(n1+m1) t ) sin( kπ(n1-m1) t ) = 0.
The first equation implies that sin( kπ(n1-m1) t ) = 0, hence the second equation gives kπ(n1+m1) t = j π 2 for j odd, which implies t | 2(n 1 +m 1 ). Since kπ(n1+m1) t = j π 2 for j odd, then the first equation can be reduced to sin( , m 1 ) = 1. We conclude that t = 2 and λ = 1 or -1 is a root of E(X) which is impossible.

The case (b) implies that if 3 t, then t | 2(n 1 -m 1 ), thus t = 4, and λ = i, -i, 1 or -1 is a root of E(X), which is impossible.

Hence, if one root of E(X) is a root of unity, then 3 divides t, and n 1 + m 1 ≡ 0 mod 3.

In conclusion, if gcd(n 1 , m 1 ) = 1 and n 1 + m 1 ≡ 0 mod 3, then X n1 + βX m1 + δ and X n + βX m + δ are irreducible.

, n) = 1, then the polynomial X n + c, with c ∈ Z, |c| 2, is irreducible over Z[X].
We call this class of suitable polynomials ClassBinomial, and, for n and c satisfying this proposition, ClassBinomial(n, c) is the singleton {X n + c}.

Proof. It is a direct application of Corollary 1.2 of a paper due to Nicolae Ciprian Bonciocat [START_REF]Schönemann-Eisenstein-Dumas-type irreducibility conditions that use arbitrarily many prime numbers[END_REF]. 5.7. Polynomials with bounds on the modules of their complex roots. The two propositions given in this section are inspired by the Perron irreducibility criterium, which is proved thanks to Rouché's theorem [START_REF] Bonciocat | On an irreducibility criterion of Perron for multivariate polynomials[END_REF]. Proposition 5.7. For a fixed n 2 and a prime µ, let P

(X) = X n + n/2 i=1 ε i X i ± µ with ε i ∈ {-1, 0, 1}. If µ > 1 + n/2 i=1 |ε i |, then the polynomial P (X) is irreducible over Z[X].
They represent the fifth class of suitable reduction polynomials. We call this class ClassPrimeCst, and ClassPrimeCst(n, µ) represents all the polynomials of this class with n 2 and µ a prime number.

Proof. Since µ > 1 + n/2 i=1 |ε i |, there exists δ > 1 such that µ > δ n   1 + n/2 i=1 |ε i |   . Let us consider C = {z ∈ C / |z| = δ}, P (X) = X n + n/2 i=1 ε i X i + εµ (ε i ∈ {-1, 0, 1}, ε ∈ {-1, 1}), F (X) = εµ and G(X) = P (X) -F (X).
For any z ∈ C, we have

|G(z)| δ n   1 + n/2 i=1 |ε i |   < µ = |F (z)|.
Since F (z) and G(z) are holomorphic functions, Rouché's theorem states that F (z) and P (z) = F (z) + G(z) have the same number of roots inside C. Hence P (z) has no root inside C since F (z) is constant. In other words, any root α of P (z) satisfies |α| δ > 1.

Assume now that P (X) is reducible over Z [X]. Hence, P (X) = H(X)Q(X) with H(X) and Q(X) two monic polynomials. Since |P (0)| = µ (a prime number), we can assume that |H(0)| = µ and |Q(0)| = 1. Now |z i | = 1, where z i are all the roots of Q(X). But the roots of Q(X) are also roots of P (X) which is not possible since any root α of P (X) is such that |α| δ > 1. Hence, P (X) is irreducible over Z

[X]. Remark 2. If µ > n/2 + 1, then ClassPrimeCst(n, µ) contains 3 n/2 elements (for each ε i three possibilities), else µ-2 i=0 n/2 i 2 i+1 elements. Proposition 5.8. For a fixed n 2, let P (X) = X n + n/2 i=2 ε i X i + a 1 X ± 1 with ε i ∈ {-1, 0, 1} and a 1 ∈ Z * . If |a 1 | > 2 + n/2 i=2 |ε i |, then the polynomial P (X) is irreducible over Z[X].
We call this class ClassPerron, and ClassPerron(n, a 1 ) represents all the polynomials of this class with n 2, a 1 ∈ Z * .

Proof. The proof is similar to the previous one. In this section, we determine for each class, the reduction polynomials which have one or more roots γ in Z/pZ. The number of roots in Z/pZ defines the number of possible PMNS.

As we have to build, for a given prime p and a given number of digits n, many PMNS with an efficient arithmetic, finding relevant reduction polynomials is crucial. Now that we have described classes of irreducible polynomials with specific reduction properties, we need to identify for a prime p which polynomials have at least one root in Z/pZ, and if possible, how many. We begin with a presentation of two special cases where the reduction polynomials are cyclotomics or binomials, then 6.3. Number of PMNS in the general case. In this part, we propose a general method to count the minimum number of PMNS we can reach from a prime p and any irreducible polynomial E(X) in Z[X]. Proposition 6.3. Let p be a prime number, n > 2, E(X) a polynomial of degree n and irreducible in Z[X], and D(X) = gcd(X p -X, E(X)) mod p.

There exist deg(D(X)) Polynomial Modular Number Systems (p, n, γ i , ρ) E(X) .

Proof. The proof is immediate considering, when p is prime, that the roots of X p -X mod p are the p elements of Z/pZ.

Remark 5. Proposition 6.1 can be considered as a corollary of Proposition 6.3.

The computation of gcd(X p -X, E(X)) mod p = gcd(X p-1 -1, E(X)) mod p (E(X) is irreducible in Z/pZ) can be done, in a reasonable time, in two steps:

1. we compute X p-1 mod E(X) mod p with a square and multiply exponentiation algorithm, and we compute F (X) = X p-1 -1 mod E(X) mod p, 2. then, we compute D(X) = gcd(F (X), E(X)) mod p with polynomials of degrees lower than or equal to n.

The first step represents O(log 2 (p)) squares and additions of polynomials of degree lower than n in Z/pZ[X], and the second step represents at most n iterations of the Euclidean algorithm.

The roots can be found using the method of Cantor-Zassenhaus [START_REF] Cantor | A new algorithm for factoring polynomials over finite fields[END_REF] for separating the roots of D(X) = gcd(X p -X, E(X)) mod p.

As X p -X = z∈Z/pZ (X -z), then D(X) = k i=1 (X -e i ) with k = deg(D(X)) and e i ∈ Z/pZ all distinct.

Due to the Chinese Remainder Theorem, any polynomial A(X) of degree strictly lower than k, can be represented by its values modulo the (X -e i ): a i = A(X) mod (X -e i ) in Z/pZ for i = 1, . . . , k .

Let us consider a polynomial A(x) such that a i ∈ {0, 1, -1} and A(X) = 0, 1, -1 mod D(X) (i.e., a i are not all equal). We note T = {i, a i = 1} and S = {i, a i = 0}. As A(X) = 0, 1, -1 mod D(X), at least one of this two sets is not empty with a cardinal strictly lower than k. We can obtain a proper factor of D(X) by computing; gcd(D(X), A(X) -1) = i∈T (X -e i ) or gcd(D(X), A(X)) = i∈S (X -e i ) .

To find such a polynomial A(X), we consider a random polynomial B(X) ∈ (Z/pZ)[X] of degree lower than k. We note b i = B(X) mod (X -e i ) in Z/pZ.

If B(X)

p-1 2 = 0, 1, -1 mod D(X), then we choose A(X) = B(X)

p-1 2 mod D(X). If gcd(D(X), A(X) -1) and gcd(D(X), A(X)) are trivial factors, then we draw randomly another polynomial B(X), else we iterate this method with the found non trivial factors gcd(D(X), A(X) -1), gcd(D(X), A(X)) and D(X) divided by these factors, until all the factors are of degree 1.

Example 8. We consider p = 7826474692469460039387400099999297 and the reduction polynomial E(X) = X 5 + X 2 + 1. First, we compute R(X) = X p-1 -1 mod E(X) in (Z/pZ)[X] = 3659189086300930014207106583318421 X 4 +7322126259420098177093985099094624 X 3 +1727826215301243349042222461135262 X 2 +7098030983909056985211630090182831 X +7372958503626664659096728485020294

Then we obtain D(X) = gcd(R(X), E(X)) in (Z/pZ)[X] = X 2 + 1305849998419067291000337897705258 X +1793073000954204546034194068098826

Next, we randomly draw B(X) mod D(X) in (Z/pZ)[X],

B(X) = 7090634213741414696606254289781859 X +4896184070237294585014544822120651

We compute A(X) = B(X)

p-1 2 mod D(X) in (Z/pZ)[X] = 6630612051164461204925113188582895 X +7099602401400966247478428555087365 We obtain a first factor in (Z/pZ)[X],

T (X) = gcd(A(X) -1, D(X)) = X + 2974625651330718059716669102633643.

By division we find the second factor, D(X)/T (X) = X -1668775652911650768716331204928385 6.4. Example giving all the possible PMNS for a given p. This example was produced with SageMath subroutines for the 256-bits prime p: p = 57896044618658097711785492504343953926634992332820282019728792003956566811073, and n = 9. We consider the PMNS B = (p, n, γ, ρ) E such that:

• E(X) = X 9 + a k X k + • • • + a 1 X + a 0 ∈ Z[X],
where k 4,

• the coefficients a i satisfy |a i | 1 for 1 i k and |a 0 | 3,

• ρ 2 31 . The number of PMNS B = (p, n, γ, ρ) E that can be built for different polynomials verifying the criteria is equal to 354.

Most of the time, the best ρ is obtained 266 times by LLL but BKZ or HKZ are 46 times better than LLL , then 42 are better than the previous ones with Corollary 4.1 or Corollary 4.2 or Proposition 4.1 with a short vector.

Conclusion

In this paper, we have shown with Theorem 4.1 the link between the existence of a PMNS and the lattice generated by its reduction polynomial and its modulo. We thus set a bound on the size of the PMNS digits depending on the covering radius of this lattice. Then, Theorem 4.2 provides a bound which can easily be computed from the infinity norm of a basis of the lattice. This second theorem has led us to consider PMNS defined by an irreducible polynomial. In this case, it is easy to define a basis of the lattice that can be associated with the PMNS (Proposition 4.1, Corollary 4.1 and Corollary 4.2). These results allowed us to produce PMNS with specific reduction polynomials allowing efficient reductions and whose roots give the bases (γ) of these systems. Now, we have the opportunity to offer for a given modulo p a wide variety of PMNS with small digits and reduced associated lattices.

Very recently, the use of PMNS to perform modular multiplications was reintroduced in [START_REF] Harvey | Faster integer multiplication using short lattice vectors[END_REF], where some interesting complexity theoretical bounds are given.

  0 -γ 1 . . . . . . any ρ > µ ∞ (L) (the covering radius for the max-norm), the system B = (p, n, γ, ρ) E is a Polynomial Modular Number System.

  is inversible and Proposition 4.1 gives B = (B 0 , . . . , B n-1 ), a basis of L , L ⊆ L of rank n, and V ∈ L .

5. 6 .

 6 Case of irreducibility of binomials X n + c, c ∈ Z, |c| 2, over Z. Proposition 5.6. Let |c| = k j=1 p mj j with p j pairwise distinct prime numbers, and m j positive integers. If gcd(m 1 , . . . , m k

From |a 1 | > 2 + n/ 2 i=2- 3 i=0n/ 2 -1 i 2 i+1 elements. 6 .

 122326 |ε i |, we can deduce that there exists δ > 1 such that |a 1 | > δ n 2 + n/2 i=2 |ε i | . Then, from Rouché's theorem, P (z) and F (z) = a 1 z have the same number of roots inside C = {z ∈ C / |z| = δ}. Hence P (z) has only one root whose module is strictly less than δ. Now, if P (X) is reducible over Z [X], then P (X) = H(X)Q(X), with H(X) and Q(X) two monic polynomials and |H(0)| = |G(0)| = 1. Hence, H(z) has at least one root z H such that |z H | 1 and G(z) has at least one root z G such that |z G | 1. It means that P (z) has at least two roots inside C, which is not possible. Hence, P (X) is irreducible over Z [X]. Remark 3. If |a 1 | > n/2+1, then ClassPerron(n, a 1 ) contains 2×3 n/2-1 elements, else |a1|Number of PMNS in function of their reduction polynomial in Z/pZ with p prime

1 ,

 1 -1 in Z/pZ .

  Hence t | 6(n 1 -m 1 ).To sum up, if λ is a t th root of unity ofX n1 + βX m1 + δ with δ, β ∈ {-1, 1}, then: (a) if β = 1, t | (n 1 + m 1 ) and t | 3(n 1 -m 1 ), (b) if β = -1, t | 2(n 1 + m 1 )and t | 6(n 1 -m 1 ). The case (a) implies that if 3 t, then t | (n 1 -m 1 ), thus t | 2n 1 and t | 2m 1 , as gcd(n

				kπ(n1-m1) t	) = ± 1 2 , which
	means that
	kπ(n 1 -m 1 ) t	= j	π 6	, j = 1, 5, 7, 11 (mod 12).

  [START_REF] Ajtai | The shortest vector problem in l 2 is NP-hard for randomized reductions[END_REF]

Acknowledgment

We thank Mrs. Valérie Berthé for her attentive proofreading and her judicious suggestions.

Funding. This work was partially supported by the ANR project ARRAND 15-CE39-0002-01 and the INRIA international associated team MACAO. All examples were coded with SageMath https://www.sagemath.org

For any

) is a basis of L ⊆ L.

Proof. V 0 is a linear combination of rows of A, hence it belongs to L. Next, since V i = V 0 • C i , for all i 1, then, due to Corollary 4.1, the vector (V 0 , V 1 , ..., V n-1 ) is a basis of a sublattice L ⊆ L.

Hence, the last strategy is to choose a short vector

) of L D and to build the basis B of L from V .

Some examples of PMNS.

In these examples we give the value of the norm B T ∞ for each reduced basis approach: LLL [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF]or BKZ [START_REF] Schnorr | Block reduced lattice bases and successive minima[END_REF] or HKZ reduction [START_REF] Korkine | Sur les formes quadratiques[END_REF][START_REF] Lagarias | Korkin-zolotarev bases and successive minima of a lattice and its reciprocal lattice[END_REF] of A, or the one of Corollary 4.1, or Corollary 4.2. We remark that the last two approaches offer the best results for polynomials E(X) with small coefficients. In Section 6.4, we give experimental results with exhaustive searches.

B T ∞ = 40733847267 5. Suitable irreducible polynomials for PMNS In Theorem 4.1, we proved that if E(X) is an irreducible polynomial, then we can define a PMNS B = (p, n, γ, ρ) E depending of E(X). For efficiency reason on we propose a method in the general case that works for any irreducible integer polynomial.

6.1. Number of PMNS with a cyclotomic reduction polynomial. Proposition 6.1. Let p be a prime number, p > 2, and an integer m 3 such that m | (p -1). Then the cyclotomic polynomial Φ m (X) satisfies Φ m (X) | (X p-1 -1) and Φ m (X) has ϕ(m) roots over Z/pZ.

Proof. We have (X

Thus Φ m (X) | (X p-1 -1), and Φ m (X) has ϕ(m) (its degree) roots over Z/pZ.

We apply Proposition 6.1 to the different cyclotomic polynomials of the class ClassCyclo(n) introduced in Proposition 5.3. Corollary 6.1. Let p be a prime number, n 2 such that n = 2 i 3 j , with i, j ∈ N.

If either one of these conditions folds, i.e.; a) i > 0, j = 0, (2 n) divides (p -1), and

, with γ i one of the n distinct roots modulo p of E(X). Example 6. Construction of PMNS from a cyclotomic reduction polynomial for p = 2 256 • 3 157 • 115 + 1 coded on 512 bits.

• E(X) = X 8 + 1: from its eight roots, the best ρ is obtained with Corollary 4.1 and Corollary 4.2., and it is 66 bits number. • E(X) = X 6 + X 3 + 1: from its six roots, the best ρ is obtained twice with LLL, else with Corollary 4.1 and Corollary 4.2, and it is 87 bits number. • E(X) = X 6 -X 3 + 1: from its six roots, the best ρ is obtained with Corollary 4.1 and Corollary 4.2, and it is 87 bits number.

Number of PMNS with reduction binomials

Proposition 6.2. Let E(X) = X n + c be an element of ClassBinomial(n, c) (Proposition 5.6). Let g be a generator of (Z/pZ) × and y such that g y ≡ -c mod p.

If gcd(n, p -1) divides y, then E(X) = X n + c has gcd(n, p -1) different roots.

Proof. Let X 0 be a solution of E(X) = 0 (mod p). Then there exists x 0 such that X 0 ≡ g x0 (mod p) and g n•x0 ≡ -c ≡ g y (mod p). In other words, n • x 0 ≡ y (mod p -1). Now, let δ = gcd(n, p -1). A classical result in modular arithmetic states that this linear equation admits δ solutions if and only if δ divides y, each solution being equal to x 0 + jp , where j ∈ {0, . . . , δ -1} and (p -1) = δp . Remark 4. If gcd(n, p -1) = 1, then E(X) = X n + c is guaranted to have one root.

Example 7. For p = 40993, 5 is a generator of (Z/40993Z) * . Let n = 4 and E(X) = X 4 + c. For c = 2, we can find y = 33788 such that -c = 5 y mod p. Since gcd(1, n) = 1, from Proposition 6.2, E(X) is irreducible. Moreover, gcd(n, p-1) = 4 divides y, hence four PMNS can be generated from E(X). For c = -2, we can find y = 13292 and gcd(n, p -1) = 4 divides y , giving once again four possible PMNS.