The power of logarithmic quantizations and computations has been recognized as a useful tool in optimizing the performance of large ML models. In this article, we provide results that demonstrate significantly better quantization signal-to-noise ratio performance thanks to multiple-base logarithmic number systems (MDLNS) in comparison with the floatingpoint quantizations that use the same number of bits. On a hardware level, we present details about our Xilinx VCU-128 FPGA design for dot product and matrixvector computations. The MDLNS matrix-vector design significantly outperforms equivalent fixed-point binary designs in terms of area (A) and time (T) complexity and power consumption as evidenced by a 4× scaling of AT2metric for VLSI performance, and 57% increase in computational throughput per watt compared to fixed-point arithmetic.

A set of congruence relations is a z-covering if each integer belongs to at least one congruence class from that set. In this paper, we first show that most existing scalar multiplication algorithms can be formulated in terms of covering systems of congruences. Then, using a special form of covering systems called exact n-covers, we present a novel uniformly randomized scalar multiplication algorithm with built-in protections against most passive side-channel attacks. Our algorithm randomizes the addition chain using a mixed-radix representation of the scalar. Its reduced overhead and purposeful robustness could make it a sound replacement to several conventional countermeasures. In particular, it is significantly faster than Coron's scalar blinding technique for elliptic curves when the choice of a particular finite field tailored for speed compels to double the size of the scalar, hence the cost of the scalar multiplication.

Current processors typically embed many cores running at high speed. The main goal of this paper is to assess the efficiency of software parallelism for low level arithmetic operations by providing a thorough comparison of several parallel modular multiplications. Famous methods such as Barrett, Montgomery as well as more recent algorithms are compared together with a novel k-ary multipartite multiplication which allows to split the computations into independent processes. Our experiments show that this new algorithm is well suited to software parallelism.

This paper proposes a robustness evaluation of an RSA cryptosystem against collision attacks and correlation electromagnetic analysis. Our hardware co-processor is based on the Residue Number System (RNS) in order to perform modular operations over large numbers. To increase its robustness against Side-Channel Analysis, we implemented two different countermeasures. The first one spatially permutates the elements of the RNS bases in order to blur electromagnetic emanations. The second countermeasure aims at randomizing RNS bases before each modular exponentiation. To the best knowledge of authors, this is the first paper that explores the robustness of RNS-RSA against EM analyses.

Single and double scalar multiplications are the most computational intensive operations in elliptic curve based cryptosystems. Improving the performance of these operations is generally achieved by means of integer recoding techniques, which aim at minimizing the scalars' density of nonzero digits. The hybrid binary-ternary number system provides both short representations and small density. In this paper, we present three novel algorithms for both single and double scalar multiplication. We present a detailed theoretical analysis, together with timings and fair comparisons over both tripling-oriented Doche-Ichart-Kohel curves and generic Weierstrass curves. Our experiments show that our algorithms are almost always faster than their widely used counterparts.

Multi-exponentiation is a common and time consuming operation in public-key cryptography. Its elliptic curve counterpart, called multi-scalar multiplication is extensively used for digital signature verification. Several algorithms have been proposed to speed-up those critical computations. They are based on simultaneously recoding a set of integers in order to minimize the number of general multiplications or point additions. When signed-digit recoding techniques can be used, as in the world of elliptic curves, Joint Sparse Form (JSF) and interleaving w-NAF are the most efficient algorithms. In this paper, a novel recoding algorithm for a pair of integers is proposed, based on a decomposition that mixes powers of 2 and powers of 3. The so-called Hybrid Binary-Ternary Joint Form require fewer digits and is sparser than the JSF and the interleaving w-NAF. Its advantages are illustrated for elliptic curve double-scalar multiplication; the operation counts show a gain of up to 19%.

This paper explores the use of the double-base number system (DBNS) for constant integer multiplication. The DBNS recoding scheme represents integers - in this case constants in a multiple-radix way in the hope of minimizing the number of additions to be performed during constant multiplication. On the theoretical side, we propose a formal proof which shows that our recoding technique diminishes the number of additions in a sublinear way. Therefore, we prove Lefevre's conjecture that the multiplication by an integer constant is achievable in sublinear time. In a second part, we investigate various strategies and we provide numerical data showcasing the potential interest of our approach.

In this paper, we propose a complete set of algorithms for the arithmetic operations in finite fields of prime medium characteristic. The elements of the fields IFpkare represented using the newly defined Lagrange representation, where polynomials are expressed using their values at sufficiently many points. Our multiplication algorithm, which uses a Montgomery approach, can be implemented in O(k) multiplications and O(k2log k) additions in the base field IFp. For the inversion, we propose a variant of the extended Euclidean GCD algorithm, where the inputs are given in the Lagrange representation. The Lagrange representation scheme and the arithmetic algorithms presented in the present work represent an interesting alternative for elliptic curve cryptography

We propose the first general multiplication algorithm in GF(2/sup k/) with a subquadratic area complexity of O(k/sup 8/5/) = O(k/sup 1.6/). Using the Chinese remainder theorem, we represent the elements of GF(2/sup k/); i.e. the polynomials in GF(2) [X] of degree at most k-1, by their remainder modulo a set of n pairwise prime trinomials, T/sub 1/,...,T/sub n/, of degree d and such that nd /spl ges/ k. Our algorithm is based on Montgomery's multiplication applied to the ring formed by the direct product of the trinomials.

We propose a new number representation and arithmetic for the elements of the ring of integers modulo p. The so-called polynomial modular number system (PMNS) allows for fast polynomial arithmetic and easy parallelization. The most important contribution of this paper is the fundamental theorem of a modular number system, which provides a bound for the coefficients of the polynomials used to represent the set /spl Zopf//sub p/. However, we also propose a complete set of algorithms to perform the arithmetic operations over a PMNS, which make this system of practical interest for people concerned about efficient implementation of modular arithmetic.

In this paper we propose an architecture for the implementation of fault-tolerant computation for a high throughput multirate equalizer used in a 1 Gbps asymmetrical wireless LAN. Exploiting the algebraic structure of the modulus replication residue number system (MRRNS) minimizes the area overhead, and the area cost to correct a fault in a single computational channel is 82.7%. Generalized results for single error correction showing significant area savings are also presented.

We present the first implementation of RSA in the residue number system (RNS) which does not require any conversion, either from radix to RNS beforehand or RNS to radix afterward. Our solution is based on an optimized RNS version of Montgomery multiplication. Thanks to the RNS, the proposed algorithms are highly parallelizable and seem then well suited to hardware implementations. We give the computational procedure both parties must follow in order to recover the correct result at the end of the transaction (encryption or signature).

We present a new multiplication algorithm for the implementation of elliptic curve cryptography (ECC) over the finite extension fields GF(p/sup k/) where p is a prime number greater than 2k. In the context of ECC we can assume that p is a 7-to-10-bit number, and easily find values for k which satisfy: p>2k, and for security reasons log/sub 2/(p)/spl times/k/spl sime/160. All the computations are performed within an alternate polynomial representation of the field elements which is directly obtained from the inputs. No conversion step is needed. We describe our algorithm in terms of matrix operations and point out some properties of the matrices that can be used to improve the design. The proposed algorithm is highly parallelizable and seems well adapted to hardware implementation of elliptic curve cryptosystems.

A recently introduced double-base number representation has proved to be successful in improving the performance of several algorithms in cryptography and digital signal processing. The index-calculus version of this number system can be regarded as a two-dimensional extension of the classical logarithmic number system. This paper builds on previous special results by generalizing the number system both in multiple dimensions (multiple bases) and by the use of multiple digits. Adopting both generalizations the paper shows that large reductions in hardware complexity are achievable compared to an equivalent precision logarithmic number system.

The aim of this paper is to accelerate division, square root, and square root reciprocal computations when the Goldschmidt method is used on a pipelined multiplier. This is done by replacing the last iteration by the addition of a correcting term that can be looked up during the early iterations. We describe several variants of the Goldschmidt algorithm, assuming 4-cycle pipelined multiplier, and discuss obtained number of cycles and error achieved. Extensions to other than 4-cycle multipliers are given. If we call G/sub m/ the Goldschmidt algorithm with m iterations, our variants allow us to reach an accuracy that is between that of G/sub 3/ and that of G/sub 4/, with a number of cycle equal to that of G/sub 3/.