On the Complexity of Constant Multiplication Problem

ABSTRACT In this paper, we present a method that serves as a binary version of the traditional width‐ r nonadjacent form ( r ‐NAF) algorithm, originally proposed by Solinas. Unlike r ‐NAF, it avoids arithmetic operations and relies solely on digit substitutions, making it significantly faster, especially for large numbers. Despite its simplicity, the method retains key properties such as minimality and canonicity. Its exact average Hamming weight ( ω ) formula aligns with the asymptotic complexity of r ‐NAF. The new method achieves an average reduction of 21.79% in ω for 32‐bit numbers compared with our previously published binary method, known as Radix‐2 r . Guided by an optimum formula, it produces a highly sparse representation of the numbers, which is crucial for various numerical applications. Applied to the single/multiple constant multiplication (S/MCM) problem, we got limits with an exact number of additions for the average, adder cost, and adder depth. These limits are the lowest analytic bounds known so far for S/MCM. We achieved an average saving of 12.96% and 17.16% in adder cost over Radix‐2 r for 32‐bit constants in SCM and MCM, respectively. Leveraging its sublinear runtime complexity, our recoding technique is also applied to the elliptic‐curve scalar multiplication (ECSM) problem, achieving substantial reductions in execution time compared with state‐of‐the‐art ECSM methods.