Paper 2025/090 Original: eprint.iacr.org/2025/090 ↗
Friendly primes for efficient modular arithmetic using the Polynomial Modular Number System
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. 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.
Metadata
- Available format(s)
PDF- Category
- Applications
- Publication info
- Preprint.
- History
- 2025-01-21: last updated
- 2025-01-21: published
- Short URL
- https://ia.cr/2025/090
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2025/090,
author = {Fangan Yssouf Dosso and Nadia El Mrabet and Nicolas Méloni and François Palma and Pascal Véron},
title = {Friendly primes for efficient modular arithmetic using the Polynomial Modular Number System},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/090},
year = {2025},
url = {https://eprint.iacr.org/2025/090}
}