# 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^{x*0}, *g^{x*1} … *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 sysx = [1,3,5,9]ai=[4,0,4,1]

h=4

g=3

p=2**255-19if (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) % pprint (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=578960446186580977117854925043439539266349923328202820197287920039565648199493^33 mod p=5559060566555523Let'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].