The Brickell, Gordon, McCurley and Wilson (BGMW) Method for Fast Exponentiation with Precomputed…

The Brickell, Gordon, McCurley and Wilson (BGMW) Method for Fast Exponentiation with Precomputed Values

I love reading classic patents, and [here] is a classic that was submitted by Brickwell, Gordon, and McCurley. It was patent number 5,299,262 and was assigned to the United States of America:

As is common, the authors published the work later as a research paper [1]:

Square and multiply method

The standard way to produce an exponent is to use the square and multiply method (SMQ), and where we take a maximum of (log_2 N)-2 operations, and where N is the largest value we can have for our power value. So for a 256-bit exponentation value we would have up to 254 operations.

So 5⁴ (where 4 is the exponent) becomes:

5² = 25
25²= 625

If we can to multiply 5⁸ that is 5² squared to give 5⁴, and then if we square again we get 5⁸. It has thus taken us three operations to find a power of 8. For 5⁶⁴, we will need six operations:

5²→5⁴→5⁸→5¹⁶→5³²→5⁶⁴

But lets say we want 5⁹. For this we square as we did before to give us 5⁸, and then just multiply by 5 to give 5⁹.

The basic method involves converting the exponent into bits, and then multiplying and squaring if the bit is a ‘1’ (or a power of two), or square if it is a ‘0’. In Python this becomes:

def exp_func(x, y):
    exp = bin(y)
    value = x
 
    for i in range(3, len(exp)):
        value = value * value
        print i,":\t",value
        if(exp[i:i+1]=='1'):
            value = value*x
	    print i,"*:\t",value
    return value

So, with an exponent is 12 we have a binary value of 1100. We ignore the first bit, and start on the ‘1’ (1100) , where we multiply and square. Next we have a ‘0’ (1100), so we just square, and finally a ‘0’ (1100), so we again just square. If we want to raise 5¹², we square(5²) and multiply (5³), next square (5⁶), next square (5¹²) [demo]:

Binary value of b is: 0b1100
Bit Result
2 : 25 (square)
2 : 125 (multiply)
3 : 15625 (square)
4 : 244140625 (square)
Result: 244140625

If we try 5¹²⁸ we get:

We will calculate a^b
a= 5
b= 128
==== Calculation ====
Binary value of b is: 0b10000000
Bit Result
2 : 25 (square)
3 : 625 (square)
4 : 390625 (square)
5 : 152587890625 (square)
6 : 23283064365386962890625 (square)
7 : 542101086242752217003726400434970855712890625 (square)
8 : 293873587705571876992184134305561419454666389193021880377187926569604314863681793212890625 (square)
Result: 293873587705571876992184134305561419454666389193021880377187926569604314863681793212890625

BGMW Method

With the Brickell, Gordon, McCurley and Wilson (BGMW) method we can set up fast exponentiation using precomputed values. With this, we have the form of g^n and where we store the pre-computed values of g^{x0}, g^{x1} … g^{xm−1}. We find the decomposition of n with:

and where 0≤a_i≤h, for 0≤i≤m. It is then possible to compute:

and where:

The core application of this is where we have a fixed value of g, and can thus build up pre-computed values for g^n. Overall this will save time in computing the value. The coding is here:

import sys

x = [1,3,5,9]

ai=[4,0,4,1]
h=4
g=3
p=2**255-19

if (len(sys.argv)>1):
  g=int(sys.argv[1])
if (len(sys.argv)>2):
  ai=eval("["+sys.argv[2]+"]")

if (len(sys.argv)>3):
  x=eval("["+sys.argv[3]+"]")

h=max(ai)

xi =[0]*len(x)
for i in range(len(x)):
  xi[i]=pow(g,x[i])

print (f"g={g}")
print (f"a_i={ai}")
print (f"x_i={x}")

print (f"\nh={h}")
print(f"p={p}")

n=0
b=1
a=1
for i in range(len(x)):
  n=n+ai[i]*x[i]

for d in range(h,0,-1):
  for i in range(len(ai)):
    if (ai[i]==d):
      b=b*pow(g,x[i],p)
  a=(a*b) % p

print (f"\n{g}^{n} mod p={a}")

print ("\nLet's check with pow(g,n,p)")
res=pow(g,n,p)

print (f"{g}^{n} mod p={res}")

A sample run is:

g=3
a_i=[4, 0, 4, 1]
x_i=[1, 3, 5, 9]

h=4
p=57896044618658097711785492504343953926634992332820282019728792003956564819949

3^33 mod p=5559060566555523

Let's check with pow(g,n,p)
3^33 mod p=5559060566555523

In this case we have:

n=4×1+0×3+4×5+1×9=33

We then get 3^{33}. The coding is here:

and a demo:

Conclusions

If you are interested in other patents, please try here:

and:

References

[1] Brickell, E. F., Gordon, D. M., McCurley, K. S., & Wilson, D. B. (1992, May). Fast exponentiation with precomputation. In Workshop on the Theory and Application of of Cryptographic Techniques (pp. 200–207). Springer, Berlin, Heidelberg.[here].