Efficient and secure modular operations using the Adapted Modular Number System
This work addresses the need for faster and more secure modular arithmetic in cryptography, offering incremental improvements by extending existing AMNS frameworks.
The paper generalizes the Adapted Modular Number System (AMNS) to allow generation of multiple systems for a given prime using polynomials of the form X^n - λ, and provides a complete set of algorithms for efficient and secure modular arithmetic operations without conditional branching.
The Adapted Modular Number System (AMNS) is a sytem of representation of integers to speed up arithmetic operations modulo a prime p. Such a system can be defined by a tuple (p, n, γ, ρ, E) where E is in Z[X]. In [13] conditions are given to build AMNS with E(X) = {X^n +1}. In this paper, we generalize their results and show how to generate multiple AMNS for a given prime p with E(X)={X^n-λ} and λ in Z. Moreover, we propose a complete set of algorithms without conditional branching to perform arithmetic and conversion operations in the AMNS, using a Montgomery-like method described in [15].