Image for post
Image for post
Photo by ThisisEngineering RAEng on Unsplash

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:

Image for post
Image for post

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

Image for post
Image for post

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

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:

Image for post
Image for post

and where 0≤a_ih, for 0≤im. It is then possible to compute:

Image for post
Image for post

and where:

Image for post
Image for post

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

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store