High-Radix Design of a Scalable Montgomery Modular Multiplier With Low Latency
Bo Zhang, Zeming Cheng, Massoud Pedram
Abstract
The proposed herein is a scalable high-radix (i.e., <inline-formula><tex-math notation="LaTeX">$2^m$</tex-math><alternatives><mml:math><mml:msup><mml:mn>2</mml:mn><mml:mi>m</mml:mi></mml:msup></mml:math><inline-graphic xlink:href="zhang-ieq1-3052999.gif"/></alternatives></inline-formula>) Montgomery Modular (MM) Multiplication circuit replacing the integer multiplications in each iteration of the Montgomery MM algorithm (related to the product of <inline-formula><tex-math notation="LaTeX">$m$</tex-math><alternatives><mml:math><mml:mi>m</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq2-3052999.gif"/></alternatives></inline-formula> bits of the multiplier and the multiplicand) with carry-save compressions and completely eliminating costly multiplications. Furthermore, the proposed Montgomery MM decomposes the multiplicand itself using a radix of <inline-formula><tex-math notation="LaTeX">$2^w$</tex-math><alternatives><mml:math><mml:msup><mml:mn>2</mml:mn><mml:mi>w</mml:mi></mml:msup></mml:math><inline-graphic xlink:href="zhang-ieq3-3052999.gif"/></alternatives></inline-formula> with <inline-formula><tex-math notation="LaTeX">$w\geq 2m$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>w</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn><mml:mi>m</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="zhang-ieq4-3052999.gif"/></alternatives></inline-formula>, thereby achieving a scalable design, which can deliver an issue latency of one cycle and a cycle (count) latency of <inline-formula><tex-math notation="LaTeX">$O(N^2/(wmp))$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:msup><mml:mi>N</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>/</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mi>w</mml:mi><mml:mi>m</mml:mi><mml:mi>p</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="zhang-ieq5-3052999.gif"/></alternatives></inline-formula> where <inline-formula><tex-math notation="LaTeX">$p$</tex-math><alternatives><mml:math><mml:mi>p</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq6-3052999.gif"/></alternatives></inline-formula> denotes the number of available processing elements, each of which is designed to complete the above iteration by computing in part the product of <inline-formula><tex-math notation="LaTeX">$w$</tex-math><alternatives><mml:math><mml:mi>w</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq7-3052999.gif"/></alternatives></inline-formula> bits of the multiplicand and <inline-formula><tex-math notation="LaTeX">$m$</tex-math><alternatives><mml:math><mml:mi>m</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq8-3052999.gif"/></alternatives></inline-formula> bits of the multiplier. The area complexity of the proposed Montgomery MM is <inline-formula><tex-math notation="LaTeX">$O(wmp)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mi>w</mml:mi><mml:mi>m</mml:mi><mml:mi>p</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="zhang-ieq9-3052999.gif"/></alternatives></inline-formula>, and thus, the Area-Latency-Product complexity is <inline-formula><tex-math notation="LaTeX">$O(N^{2})$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:msup><mml:mi>N</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="zhang-ieq10-3052999.gif"/></alternatives></inline-formula>.