Journal of Cryptographic Engineering Computer Networks and Communications

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

Dosso, Fangan Yssouf, El Mrabet, Nadia, Méloni, Nicolas, Palma, François, Véron, Pascal
Springer Nature · 2025-09-26 · DOI 10.1007/s13389-025-00382-8

Abstract

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 [ 1 , 2 ]. In [ 3 , 4 ], the 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.

Read at publisher →