Fast binary multiplication by performing dot counting and complement recoding

摘要

In this paper, we present a new computation method by combining the dots counting method and the complement recoding method to efficiently evaluate modular multiplication in binary multiplications. The LUT (Look-Up Table) technique can be adopted in our proposed method to efficiently reduce the number of multiplications. And the proposed method can be easily implemented for the hardware. Numerous examples are provided to show the efficient and easy operations of the binary multiplication method. In average case, the worst case for the Hamming weight of the product X∗Y is uv4, where u is the bit-length of multiplicand X, v is the bit-length of multiplier Y. If the proposed method is applied, we could effectively reduce the Hamming weight of the product X∗Y to 0.25u.