Study of Different Arithmetic Operations Number System Polynomial

Efficient implementation of modular arithmetic is an important prerequisite in today's public-key cryptogra-phy [10]. The celebrated RSA algorithm [13], and the cryp- tosystems based on the discrete logarithm problem, such as Diffie-Hellman key exchange [6], need fast arithmetic modulo integers of size 1024 to roughly 15000 bits. For the same level of security, elliptic curves defined over prime fields, require operations modulo prime numbers whose size range approximately from 160 to 500 bits [8]. Classic implementations use multiprecision arithmetic, where long integers are represented in a predefined high- radix (usually a power of two depending on the word size of the targeted architecture). Arithmetic operations, namely modular reduction and multiplication, are performed using efficient algorithms, such as as Montgomery [12], or Barrett [3]. (For more details, see [10], chapter 14.) These general algorithms do not require the divisor, also called modulus, to be of special form. When this is the case, however, modular multiplication and reduction can be accelerated considerably. Mersenne numbers, of the form 2m — 1, are the most common examples. Pseudo-Mersenne numbers [5], generalized Mersenne numbers [14], and their extension [4] are other examples of numbers allowing fast modular arithmetic. In a recent paper [2], we have defined the so-called Modular Number Systems (MNS) and Adapted Modular Number Systems (AMNS) to speed up the arithmetic operations for moduli which do not belong to any of the previous classes. In this paper, we propose a new representation, and the corresponding arithmetic operations for the elements of the ring of integers modulo p. (The integer p does not have to be a prime, although it is very likely to be prime for practical cryptographic applications.) We define the Polynomial Modular Number System (PMNS), over which integers are represented as polynomials. Compared to the classical (binary) representation, polynomial arithmetic offers the advantages of no carry propagation and easiest paral- lelization. The main contribution of this paper is the fundamental theorem of a MNS, which provides a bound for the coefficients of the polynomials used to represent the elements ofThis theorem is presented in Section 3. It uses results from lattice reduction theory [9, 11]. The second half of the paper focuses on the arithmetic operations; in Section 4, we propose algorithms for the basic operations - addition, multiplication, conversions - which all require a final step, called coefficient reduction ,that we present in details in Section 5. A numerical example is provided in Section 6.

In classic positional number systems, every non-negative integer, x, is uniquely represented in radix r as If xn-1 =0, x is said to be a n-digit radix-r number. In most public-key cryptographic applications, compu-tations have to be done over finite rings or fields. In prime fields gf (p), we deal with representatives of equivalence classes modulo p (for simplicity we generally use the set of positive integers {0,1,...,p — 1}), and the arithmetic operations - addition and multiplication - are performed modulo p. In order to represent the set of integers modulo p, we define a

2

Definition 1 (MNS) A Modular Number System, B, is a quadruple such that every positive integers, satisfy The vector (x0,..., xn-1)B denotes a representation of x in In the rest of the paper, we shall omit the subscript (.)B when it is clear from the context. We shall represent the integer, a, either as the vector, a, or the polynomial, A, without distinction. We shall use ai to represent both for the ith element of a, and the ith coefficient of A. (Note that we use a left-to-right notation; i.e., a0, the left-most coefficient of A, is the constant term.) Hence, depending on the context, we shall use to refer to the norm of the vector, or the corresponding polynomial. We shall also use the notation ai to refer to the ith vector within a set of vectors or a matrix. Example 1 Let us consider a MNS defined with p = Over this system, we represent the elements of as polynomials inof degree at most 2, with coefficients in { — 1,0,1} (cf. table 1).

In example 1, we remark that the number of polynomials of degree 2, with coefficients in {—1,0,1} is equal to 33 = 27. Since we only have to represent 17 values, the system is clearly redundant. For example, we have= The level of redundancy depends on the parameters of the MNS. Note yet that, in this paper, we shall take advantage of the redundancy only by considering different representations of zero. coefficients of those polynomials? Are they bounded by some value which depends on the parameters of the MNS? In other words, given the integers p and n, are we able we determineand construct a MNS? We answer these questions in the next section. We prove the fundamental theorem of a MNS, using results from lattice reduction theory, and we introduce the concept of Polynomial Modular Number System (PMNS).

In this section, we consider special cases of modular number systems, whereis a root (modulo p) of a given polynomial E. In the following fundamental theorem of a MNS, we prove that ifis greater than a certain bound, then it is always possible to define a valid MNS. Roughly speaking, Theorem 1 says that there exists a MNS, where one can represent every integer less than p, as a polynomial of degree at most n — 1, with coefficients all less than C x p1/n, where C is a small constant. Theorem 1 (Fundamental theorem of a MNS) Let us define p,n > 1, and a polynomial with such that (mod p), and E irre ducible in If then, the parametersdefine a modular number system, Sketch of proof: (A complete, detailed, proof can be found in [1].) The proof is based on the theory of lattice reduction [9, 11]. A lattice is a discrete sub-group of or equiv- alently the set of all the integral combinations of linearly independent vectors over The matrix A = (a1,..., ad) is called a basis ofIt is known that, every vector over can be reduced, modulo the lattice, within the fundamental domain ofgiven by In order to prove Theorem 1, we first define the lattice, of all the multiples of p in B; or equivalently, the set of vector of defined by

From Minkowski's theorem [9, 7], and because we have we prove that there exists a vector such that We then define a second lattice, of dimension n, with B=(b1,..., bn), such that To conclude the proof, we simply remark that every integer, can be first associated with the vector a = (a, 0,..., 0), and reduced modulo to a vector which belongs to the fundamental domain Since can be overlapped by spheres of radius and centers the vertices of and because all the points of a lattice are equivalent, we conclude that Definition 2 (PMNS) A modular number system which satisfies the conditions of Theorem 1 is called a Polynomial Modular Number System (PMNS). We shall denote In practice, we shall define the polynomial E with as small as possible. Example 2 We define the PMNS with We easily check that = 13 is a root of E in and E is irreducible in We represent the elements of as polynomials of degree at most 2, with coefficients in { — 1,0,1}.

In this paper, we have proposed a new representation for the elements of Zp, the ring of integers modulo p, called Polynomial Modular Number Systems. In this system, integers are represented as polynomials in 7, of degree less than n, with coefficients bounded by (|a| + |ft|)p1/n, where a, ft are very small integers. Since p1/n is a minimum value,

only a few extra bits are required for each coefficient. Compared to the classic multiprecision representation, the polynomial nature of PMNS allows for no-carry propagation, and efficient polynomials arithmetic. The algorithms presented in this paper for the arithmetic operations must be seen as a first step in doing the arithmetic over this new representation. Many improvements are still to come...

1. J.-C. Bajard, L. Imbert, and T. Plantard. Arithmetic operations in the polynomial modular number system. Research Report 04030, LIRMM - CNRS, 161 rue Ada, 34392 Mont- pellier cedex 5, France, Sept. 2004. Available electronicaly at http://www.lirmm.fr/~imbert. 2. J.-C. Bajard, L. Imbert, and T. Plantard. Modular number systems: Beyond the Mersenne family. In Selected Areas in Cryptography: 11th International Workshop, SAC 2004, volume 3357 of LNCS, pages 159-169. Springer-Verlag, Jan. 2005. 3. P. Barrett. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In A. M. Odlyzko, editor, Advances in Cryptol- ogy - CRYPTO '86, volume 263 of LNCS, pages 311-326. Springer-Verlag, 1986. 4. J. Chung and A. Hasan. More generalized mersenne numbers. In M. Matsui and R. Zuccherato, editors, Selected Areas in Cryptography - SAC 2003, volume 3006 of LNCS, pages 335-347. Springer-Verlag, 2004.

4

number 5159632, 1992. 6. W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT- 22(6):644-654, November 1976. 7. C. Dwork. Lattices and their applications to cryptography. Lecture notes, Stanford University, 1998. 8. D. Hankerson, A. Menezes, and S. Vanstone. Guide to Elliptic Curve Cryptography. Springer-Verlag, 2004. 9. L. Lovasz. An Algorithmic Theory of Numbers, Graphs and Convexity, volume 50 of CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM Publications, 1986. 10. A. Menezes, P. C. Van Oorschot, and S. A. Vanstone. Handbook of applied cryptography. CRC Press, 1997. 11. D. Micciancio and S. Goldwasser. Complexity of Lattice Problems, A Cryptographic Perspective. Kluwer Academic Publishers, 2002. 12. P. L. Montgomery. Modular multiplication without trial division. Mathematics of Computation, 44(170):519-521, Apr. 1985. 13. R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM, 21(2):120-126, February 1978.