Fast Hardware Computation of x mod z

Abstract

We show a high-speed hardware implementation of xmod z that can be pipelined in O(n ° m) stages, where x is represented in n bits and z is represented in m bits. It is suitable for large x. We offer two versions. In the first, the value of z is fixed by the hardware. For example, using this circuit, we show a random number generator that produces more than 11 million random numbers per second on the SRC-6 reconfigurable computer. In the second, z is an independent input. This is suitable for RNS number system applications, for example. The second version can be pipelined in O(n) stages.