Modular multiplication method and the system for processing data

Abstract From the Canadian patent

To markedly improve the computational speed of A x B modulo N computation as compared with the prior-art Baker's method where A denotes a multiplicand; B denotes a multiplier; and N denotes a modulus, the number of multiply-additions and division (modular) subtractions is reduced on the basis of any given same higher radix number r. In practice, the modular subtracters c(k)N are previously determined on the basis of the partial products b(k-1)A at the succeeding processing stage (k-1) to reduce the absolute value of the partial remainder R(k) down to a value less than a modulus N, so that bit overflow from a predetermined computational range can be prevented. For instance, when the partial …