Fast RNS division algorithms for fixed divisors with application to RSA encryption (Q1334636)

Residue number systems (RNS) have received much attention for high- throughput computations due to its advantage of fast addition and multiplication over other number systems. This paper presents two algorithms for RNS division with fixed divisors that achieve \(O(n)\) time complexity for each division, where \(n\) is the number of moduli. The first algorithm uses the well-known division method of multiplying by the divisor reciprocal. The second algorithm, which is faster than the first one but requires more space, is based on the Chinese Remainder Theorem decoding and table lookup, and requires the divisor to be relative prime to all moduli. Adaptation of both algorithms for RSA encryption is also described. It is shown that the first and second algorithms respectively lead to \(4n + b\) and \(2n\) time steps per modular multiplication, where \(b\) is the number of bits in the largest modulus.