An Alternative Approach to Polynomial Modular Number System Internal Reduction - Archive ouverte HAL Access content directly
Journal Articles IEEE Transactions on Emerging Topics in Computing Year : 2022

An Alternative Approach to Polynomial Modular Number System Internal Reduction

(1)
1

Abstract

The Polynomial Modular Number System (PMNS) is an alternative to the binary multi-precision representation that allows to transport the arithmetic of a finite field to a polynomial ring. The most important operation in that system is the internal reduction that follows any arithmetic operation. All recent works on the subject use the same algorithm derived from Montgomery's modular multiplications to perform this internal reduction. This paper designs and analyzes two new algorithms to perform the internal reduction, both based on Babai's Closest Vector algorithms. It allows to significantly reduce the number of additions needed to perform this operation. A comprehensive experimental analysis shows that one of those algorithms is also faster in practice. For that matter, a C code generation tool has been developed in order to produce implementations for any prime number field.
Fichier principal
Vignette du fichier
pmns_babai_major_revision.pdf (344.52 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03635347 , version 1 (08-04-2022)
hal-03635347 , version 2 (08-06-2022)

Identifiers

Cite

Nicolas Méloni. An Alternative Approach to Polynomial Modular Number System Internal Reduction. IEEE Transactions on Emerging Topics in Computing, 2022, ⟨10.1109/TETC.2022.3190368⟩. ⟨hal-03635347v2⟩

Collections

UNIV-TLN IMATH
60 View
45 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More