5
$\begingroup$

I'm trying to compute $g^m$ mod $n$ where $m,n$ are 1024-bit numbers. The method I want to use is fixed base exponentiation with precomputations, also known as fixed-base windowing.The paper I'm following is Brickell et. al. "Fast Exponentiation with Precomputation: Algorithms and Lower Bounds" which can be found here.

Basically the idea is to precompute $g^{b^i}$ where $b$ is a radix. Now if we write $m$ in the radix base: $m=\sum_{i=0}^k e_i b^i$ then $g^m=\prod (g^{b^i})^{e_i}$. For example: say we want to compute $g^{142}$ and we have chosen as radix $b=3$ (I'm aware of the more natural example of radix 2, but I'm experimenting with different radices to see if there is any speed-up). I write $m=(12021)_3$ and compute $g^{142}=g^{3^4}\times(g^{3^3})^2\times (g^3)^2 \times g^3$.

The pseudo code given in the paper is:

b ← 1
a ← 1
for d = h to 1 by −1
    for each i such that a_i = d
        b ← b ∗ g^{x_i}
    a ← a ∗ b.
return a.

where $h$ is the range of $e_i$, and $a_i=e_i$ and $x_i=g^{b^i}$.

My question is: instead of going through $e_i$ by tier as the pseudo code suggested, why don't we go through the base $b$ representation of $m$ one digit at a time and multiply as we go?

When I looked up fixed-base exponentiation in Henk and Tilborg "Encyclopedia of Cryptography and Security," they say that "there is time saved by multiplying together powers with identical coefficients, and then raising the intermediate products to powers step by step." I believe this is hinting at the answer to my question, but I don't understand the reasoning.

$\endgroup$
3
$\begingroup$

Your question hits at the main part of the faster algorithm presented in the paper. Many people know the usual (base-2) "repeated squaring" algorithm to compute $g^n$ is to write $n$ in binary: $$ n=\sum_{i=0}^m e_i2^i\qquad e_i\in\{0,1\} $$ so $$ g^n=g^{e_02^0+e_12^1+e_22^2+\dotsm}=(g^{2^0})^{e_0}(g^{2^1})^{e_1}(g^{2^2})^{e_2}\dotsm $$ and observe that $g^{2^k}=(g^{2^{k-1}})^2$ so computation of the $g$ terms can be accomplished by repeated squaring, either in the body of the loop or by precomputation. The paper simply generalizes this using a base, $b$, other than $2$. If we keep with your example of $b=3$, then we're doing the same thing as the usual algorithm, only using repeated cubing, rather than repeated squaring, so if we have, in general $$ n=\sum_{i=0}^m e_ib^i\qquad e_i\in\{0,1,\dotsc,b-1\} $$ then we can write $$ g^n=(g^{b^0})^{e_0}(g^{b^1})^{e_1}(g^{b^2})^{e_2}\dotsm $$ and do the usual algorithm, forming the product seriatim, from $0$ up to the limit $m$, using repeated exponentiation of the terms, since $g^{b^k}=(g^{b^{k-1}})^b$ as above. This is your proposal and it will work just fine.

The key idea in the paper relies on the observation that the $e_i$ are now not just $0$ or $1$, so we often have another exponentiation step for each term. Rather than do several of those, the paper just does it once, for each possible value of $e_i$.

Here's your example, with $n=142$ and $b=3$. Since $142_{10}=12021_3$ we'll have $e_4=1$, $e_3=2$, $e_2=0$, $e_1=2$, $e_0=1$. Looping from $i=0$ to $4$ you could successively form the product $$ g^{142}=(g^{3^0})^1(g^{3^1})^{2}(g^{3^2})^{0}(g^{3^3})^{2}(g^{3^4})^{1} $$ The paper instead loops first by the nonzero values of the $e_i$, effectively grouping several exponentiations into one, doing this: $$ g^{142}=\left [(g^{3^1})(g^{3^3})\right ]^2\left [(g^{3^0})(g^{3^4})\right ]^1 $$ obviously saving some multiplications.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.