Friendly primes for efficient modular arithmetic using the Polynomial Modular Number System

ePrint Report: Friendly primes for efficient modular arithmetic using the Polynomial Modular Number System
Fangan Yssouf Dosso, Nadia El Mrabet, Nicolas Méloni, François Palma, Pascal Véron

The Polynomial Modular Number System (PMNS) is a non-positional number system designed for modular arithmetic. Its efficiency, both in software and hardware, has been demonstrated for integers commonly used in Elliptic Curve Cryptography. In recent papers, some authors introduce specific prime forms that are particularly well-suited for PMNS arithmetic. In this work, we extend their results to a broader class of prime numbers. In practice, our approach yields performance that is competitive with, and in some cases superior to, Pseudo-Mersenne arithmetic. As a result, we expand the set of prime numbers that are well-suited for modular arithmetic. Furthermore, we contribute a database of proof of concept Elliptic Curves constructed with those primes that verify the Brainpool Standard.

Go to Source