The Polynomial Modular Number System (PMNS) and the Residue Number System (RNS) are integer number systems which aim to speed up modular arithmetic. Their parallel properties make them suitable for the implementation of cryptographic applications on modern processors with SIMD instructions. In this work, we will show the implementation choices made for the modular multiplication in both systems and compare their implementation performances for several sizes of moduli. We target the Intel 64-bit sequential instruction set and the Intel AVX-512 vector instruction set. This instruction set allows significant speed-ups up to 1 621 bit size moduli, while the vectorized PMNS implementation is up to 2.5 times faster than the vectorized RNS, though the vectorized RNS becomes slightly better for 3 251 bits, due to the difficulty to find a PMNS with a suitable parameter$n$. The vectorized RNS implementations reach performance levels close the state-of-the-art GMP library, while the retired instruction counts are lower for sizes between 401 and 3 251 bits.

The Polynomial Modular Number System (PMNS) is an integer number system designed to speed up arithmetic operations modulo a prime p. Such a system is defined by a tuple B = (p, n, γ, ρ, E) where E ε Z[X] and E(γ) = 0 mod p. In a PMNS, an element a of Z/pZ is represented by a polynomial A such that: A(γ) = a mod p, deg A <; n ||A||∞ <; p. In [6], the authors mentioned that PMNS can be highly redundant but they didn't really take advantage of this possibility. In this paper we use, for the first time, the redundancy of PMNS to protect algorithms against Side Channel Attacks (SCA). More precisely, we focus on elliptic curve cryptography. We show how to randomize the modular multiplication in order to be safe against existing SCA and we demonstrate the resistance of our construction. We describe the generation of a PMNS while guaranteeing, for all elements of Z/pZ, the minimum number of distinct representations we want. We also show how to reach all these representations.

This article studies the design of custom circuits for division by a small positive constant. Such circuits can be useful for specific FPGA and ASIC applications. The first problem studied is the Euclidean division of an unsigned integer by a constant, computing a quotient and remainder. Several new solutions are proposed and compared against the state-of-the-art. As the proposed solutions use small look-up tables, they match well with the hardware resources of an FPGA. The article then studies whether the division by the product of two constants is better implemented as two successive dividers or as one atomic divider. It also considers the case when only a quotient or only a remainder is needed. Finally, it addresses the correct rounding of the division of a floating-point number by a small integer constant. All these solutions, and the previous state-of-the-art, are compared in terms of timing, area, and area-timing product. In general, the relevance domains of the various techniques are different on FPGA and on ASIC.

We present a new RNS modular multiplication for very large operands. The algorithm is based on Montgomery's (1985) method adapted to residue arithmetic. By choosing the moduli of the RNS system reasonably large, an effect corresponding to a redundant high-radix implementation is achieved, due to the carry-free nature of residue arithmetic. The actual computation in the multiplication takes place in constant time, where the unit of time is a few simple residue operations. However, it is necessary twice to convert values from one residue system into another, operations which take O(n) time on O(n) processors, where n is the number of moduli in the RNS systems. Thus these conversions are the bottlenecks of the method, and any future improvements in RNS base conversions, or the use of particular residue systems, can immediately be applied.

We present a new RNS modular multiplication for very large operands. The algorithm is based on Montgomery's method adapted to mixed radix, and is performed using a residue number system. By choosing the moduli of the RNS system reasonably large and implementing the system on a ring of fairly simple processors, an effect corresponding to a redundant high-radix implementation is achieved. The algorithm can be implemented to run in O(n) time on O(n) processors, where n is the number of moduli in the RNS system, and the unit of time is a simple residue operation, possibly by table look-up. Two different implementations are proposed, one based on processors attached to a broadcast bus, another on an oriented ring structure.

The authors present a new RNS modular multiplication for very large operands. The algorithm is based on Montgomery's method adapted to mixed radix, and is performed using a residue number system. By choosing the moduli of the RNS system reasonably large, and implementing the system an a ring of fairly simple processors, an effect corresponding to a redundant high-radix implementation is achieved. The algorithm call be implemented to run in O(n) time on O(n) processors, where n is the number of moduli in the RNS system, and the unit of time is a simple residue operation, possibly by table look-up.

We propose in this paper a new algorithm and architecture for performing divisions in residue number systems. Our algorithm is suitable for residue number systems with large moduli, with the aim of manipulating very large integers on a parallel computer or a special-purpose architecture. The two basic features of our algorithm are on one hand the use of a high-radix division method, and on the other hand the use of a floating-point arithmetic that should run in parallel with the modular arithmetic.