Symbolic Computation Group

Residue number systems (RNS) based on pairwise relatively prime moduli are a powerful tool for accelerating integer computations via the Chinese Remainder Theorem. We study families of sparse moduli exhibiting scalable modular inverses that enable the acceleration of all aspects of modular arithmetic: conversion to RNS, intra-RNS operations, and reconstruction from modular images.

Our unified approach is to represent moduli as the evaluations of sparse polynomials at powers of 2. Two moduli can be checked for scalability by evaluating a single polynomial resultant. If the polynomials are suitable, one can generate sets of moduli of arbitrary length with closed-form modular inverses. We also discuss different strategies to evaluate scalable moduli to further eliminate RNS overhead.

We show that this approach is universal by using it to test well-known sets of moduli for scalability.