Multilevel Variable Length Shifter Design for an Iterated Shift-and-Add Product Operation

We investigate various designs for a variable length left-shifter component for implementing a proposed iterated shift-and-add product operation Pi^n-1 _i=1(b_i2ⁱ+1)x where b_n-1b_n-2...b₀ and x are n-bit arguments. This iterated product operation has application in a new fast integer exponentiation algorithm replacing a sequence of O(n) dependent square-and-multiply operations. This paper presents the resulting area and time requirements realized by synthesizing alternative variable length shifter designs.