REIST Division: An Implementation-Oriented Framing of Centered Remainder Arithmetic for Modular Addition

Abstract

Traditional integer division constrains the remainder to be non-negative, an assumption that simplifies arithmetic but introduces asymmetries and inefficiencies. Centered remainder intervals are classical in number theory and widely used in FFT/NTT implementations. The contribution of REIST in this report is therefore not a new algebraic object, but an implementation-oriented framing and a systematic treatment of the remainder as an explicit signed correction term, together with an empirical evaluation on modern CPUs.

This work presents REIST Division (Remainder-Extended Inversion and Subtraction Technique) as a generalized framework that allows bounded negative remainders and interprets the remainder as a signed correction term rather than a passive residue. The formalism yields a centered remainder interval, aligns naturally with balanced modular arithmetic and rounding functions, and provides a convenient language for modeling error-feedback and phase-alignment processes in logistics, scheduling, digital signal processing, robotics and CPU micro-architectural correction loops.

Beyond the conceptual framework, this Version 2.0 report includes an extended empirical evaluation of REIST in cryptographic workloads. Using an open-source benchmark suite, we compare classical modulo-based reductions with REIST-style symmetric remainders on both ARMv8-A (aarch64) and x86-64 (Intel Core i9-14900K). The evaluation quantifies speedups at the level of the basic arithmetic primitive, not against fully optimized Montgomery or Barrett reductions used in state-of-the-art cryptographic libraries.

On ARM, REIST achieves about 2.5× speedup for synthetic modular-add counters and roughly 6× speedup for polynomial modular addition. On x86-64, the same patterns yield around 9× speedup for modular addition and up to 15× speedup for polynomial modular addition, while full remainder computations and ARX ciphers remain essentially unchanged and hash-mixers exhibit slight slowdowns.

Together, these results show that REIST Division is not only a mathematically natural extension of classical division, but also a practically relevant primitive for high-performance modular arithmetic across two distinct CPU architectures.

Citation

Stepan, R. (2025). REIST Division: An Implementation-Oriented Framing of Centered Remainder Arithmetic for Modular Addition (2.0).
Zenodo. https://doi.org/10.5281/zenodo.17897540
        

Links & Registries

• Zenodo / DOI Record
• ORCID Author Profile
• Academia.edu Profile
• Google Scholar

Version Notes

• Version: 2.0
• Last updated: 2025