Division in residue number systems involving length indicators

摘要

In residue number systems many arithmetic operations, like addition and multiplication, can be done in constant time. But, among others, division is more complex. This paper introduces a division algorithm which is in its complexity comparable to the conventional integer division algorithm. The algorithm exhibits nice properties, especially for long integer arithmetic as it does not involve numbers with many significant digits, and is thus superior to comparable algorithms published recently. The algorithm copes well with parallel implementations of residue number systems' arithmetic.