Fast Modular Reduction Methods

Modular reduction is a major operation in public key cryptographic protocols,which accounts for about half cost of running a public key cryptographic protocol.Therefore, the research of modulus reduction algorithm is of great practical significance.There are four general modular reduction methods: classical algorithm, Barrett’sreduction algorithm, Montgomery’s reduction algorithm and modular reduction algo-rithms based on lookup table. In1985, Montgomery invented an elegant reductionmethod. Some experiments show that the algorithm will win a certain advantage forlarger modulus. In1986, Barrett proposed a novel reduction method, which only needsa multiplication and some simple shift operations. This method is more efective whenthe size of the modulus is moderate. Modular reduction algorithms based on lookuptable need hardware support, which are very suitable for servers with strong processingability.The first contribution in this paper is to put forth an improvement of Barrett’salgorithm. Barrett’s algorithm requires a suitably-chosen base b≥3. We show that thesetting will cause the problem of data expansion and require more cost for performingthe unique multiplication which dominates the cost of this algorithm. We shall provethat the base b can be replaced by the usual base2. The improvement gives a little ofcost saving.The second contribution is to introduce a new lookup-table-based reduction method.The existing lookup-table-based reduction methods partition the binary string of aninteger into fixed-length blocks such as32bits or64bits. They then add those fig-ures searched from the relevant tables together. This approach requires a moderatesize table and a fixed amount of looking up tables. It also requires a fixed number ofadditions. We propose a new lookup-table-based reduction method which partitionsthe binary string of an integer into its runs, instead of some fixed-length blocks. Thenew method can efciently reduce the amount of looking up tables. The theoreticalanalysis shows that the new method is almost twice as fast as the Barrett’s algorithm.