HyPoRes: An Hybrid Representation System for ECC - Sorbonne Université Access content directly
Conference Papers Year : 2019

HyPoRes: An Hybrid Representation System for ECC


The Residue Number System (RNS) is a numeral representation enabling for more efficient addition and multiplication implementations. However, due its non-positional nature, modular reductions, required for example by Elliptic Curve (EC) Cryptography (ECC), become costlier. Traditional approaches to RNS modular reduction resort to the Montgomery algorithm, underpinned by large basis extensions. Recently, Hybrid-Positional Residue Number Systems (HPRs) have been proposed, providing a trade-off between the efficiency of RNS and the flexibility of positional number representations. Numbers are represented in a positional representation with the coefficients represented in RNS. By crafting primes of a special form, the complexity of reductions modulo those primes is mitigated, relying on extensions of smaller bases. Due to the need of crafting special primes, this approach is not directly extensible to group operations over currently standardised elliptic curves. In this paper, the Hybrid-Polynomial Residue Number System (HyPoRes) is proposed, enabling for improved modular reductions for any prime. Experimental results show that the modular reduction of HyPoRes, although at most 1.4 times slower than HPR for HPR-crafted primes, is up to 1.4 times faster than a generic RNS approach for primes of ECC standards.
Fichier principal
Vignette du fichier
idea-2.pdf (280.56 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02337787 , version 1 (29-10-2019)



Paulo Martins, Jérémy Marrez, Jean-Claude Bajard, Leonel Sousa. HyPoRes: An Hybrid Representation System for ECC. 2019 IEEE 26th Symposium on Computer Arithmetic (ARITH), Jun 2019, Kyoto, Japan. pp.207-214, ⟨10.1109/ARITH.2019.00049⟩. ⟨hal-02337787⟩
93 View
131 Download



Gmail Facebook X LinkedIn More