The hardware implementation of the modulo operation for input data of high bit width on the basis of reduction and correction blocks

Abstract

The hardware implementation of the modulo operation for input data of high bit width on the basis of reduction and correction blocks

Solovyev R.A., Telpukhov D.V., Balaka E.S., Rukhlov V.S., Mihmel A.S.

Incoming article date: 20.06.2018

The operation of finding the remainder of division is an arithmetic operation that plays a big role in number theory. The most important role this operation has in the design of devices using, modular arithmetic. Modular arithmetic has high parallelism and is often used with high-dimensional data to speed up computations. When working with modular arithmetic, data of large dimensions (about 128-512 bits) are often used. To find modular representation of data, effective way is needed to find the remainder from the division of multi-digit numbers by the corresponding set of moduli. The article explores the methods for constructing devices for finding the remainder of the division, for large dimensions of input data, in which the divisor p - is a constant and is known at the device design stage. The options for implementing such devices are investigated, their optimal parameters are determined, and the delay and area compared with the Verilog operation "%", both in the VLSI and in the FPGA synthesis.

Keywords: residue number system, remainder of division, modulo operation, cad