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

Nov 14, 2020 · 4 min read

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]:

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² = 2525²= 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: 0b1100Bit Result2 : 25 (square)2 : 125 (multiply)3 : 15625 (square)4 : 244140625 (square)Result: 244140625`

If we try 5¹²⁸ we get:

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

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_ih, for 0≤im. 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=4g=3p=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=0b=1a=1for 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=3a_i=[4, 0, 4, 1]x_i=[1, 3, 5, 9]h=4p=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:

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].

Written by

Written by