  We present a method to increase the dynamical range of a Residue Number
System (RNS) by adding virtual RNS layers on top of the original RNS, where the
required modular arithmetic for a modulus on any non-bottom layer is
implemented by means of an RNS Montgomery multiplication algorithm that uses
the RNS on the layer below. As a result, the actual arithmetic is deferred to
the bottom layer. The multiplication algorithm that we use is based on an
algorithm by Bajard and Imbert, extended to work with pseudo-residues
(remainders with a larger range than the modulus). The resulting Recursive
Residue Number System (RRNS) can be used to implement modular addition,
multiplication, and multiply-and-accumulate for very large (2000+ bits) moduli,
using only modular operations for small (for example 8-bits) moduli. A hardware
implementation of this method allows for massive parallelization.
  Our method can be applied in cryptographic algorithms such as RSA to realize
modular exponentiation with a large (2048-bit, or even 4096-bit) modulus. Due
to the use of full RNS Montgomery algorithms, the system does not involve any
carries, therefore cryptographic attacks that exploit carries cannot be
applied.
