Processing math: 100%

Oct 08, 2025

Wiki

Python

Aide

edit SideBar

Search

Rapid exponentiation


Objectives

Various operations in cryptography require the calculation of a multiple or a power: for example, as we will see, the way to encrypt and decrypt for the RSA, and a cryptographically secure pseudo-random number generator such as the BBS boils down to iterating a power calculation modulo p. These operations must therefore be able to be done efficiently, especially since the objects considered here (wireless sensors) are low-powered and battery-powered.

Also, given an exponent e, we want to calculate here as efficiently as possible xe,x, i.e. by minimizing the number of multiplications, to save execution time.

Indeed, to calculate X8, we can :

  • Calculate X×X×...×X, which makes 7 multiplications. The list of calculated exponents is: 1, 2, 3, 4, 5, 6, 7, 8.
  • Calculate :
    • Y=X×X, which corresponds to X2,
    • then Z=Y×Y, which corresponds to X4,
    • finally T=Z×Z, which gives the result.
We thus obtain the result T=X8 in only three multiplications. The list of exponents is: 1, 2, 4, 8.

The gap widens very quickly, between the naive method and the more advanced methods. Thus, to compute X1024, one needs to

  • 1023 multiplications, for the naive method,
  • 10 multiplications for the fast exponentiation method.

When we know that in the RSA method, in order to encrypt the plain text, we must raise our message (a number) to the power "a large prime number" (including: an exponent of several hundred digits), we understand the interest of shortening the calculation time of a power.

Fast exponentiation

Presentation

Fast exponentiation is a classical technique, used in practice, to obtain the power of a given number.

This fast exponentiation iterates, for the calculation of Xe, the following operations:

  • the square elevation,
  • multiplication by X,

in an order depending on the base 2 entry of e.

It is well understood in its recursive version :

  • if e is even, we calculate (recursively) Xe/2, which we multiply by itself,
  • otherwise, we calculate (recursively) Xe1, which we multiply by X.

The algorithm

As the above technique is recursive, its implementation in a sensor may be problematic. But as the operations to be done are determined by the parity of the number following a division by 2, or has a division by 2 after a deletion of 1, we deduce that the binary writing of the number contains exactly the operations to be done.

More precisely...

  • We write e in base 2,
  • We remove the first 1 of this writing,
  • One replaces then, in this writing,
    • the 0 by S,
    • the 1 by SX,
we thus obtain a word made up of the letters S and X.
  • We start from the number X.
    • if the first letter is S, we raise to the square
    • otherwise, multiply by X.
  • Start again with the following letters, until the end of the word.

Examples

First example

15 is written 1111 in base 2.

The previous algorithm results in the word SXSX. The steps of the calculation are then :

 res = XX
Sres = res * resX2
Xres = res * XX3
Sres = res * resX6
Xres = res * XX7
Sres = res * resX14
Xres = res * XX15

The last result (res) thus contains the power sought, in only 6 operations (compared to 14 in the naive method).

The list of exponents is here: 1, 2, 3, 6, 7, 14, 15.

Second example

19 is written 10011 in base 2, which provides the word SSSXSX.

After work, the list of exponents is here: 1, 2, 4, 8, 9, 18, 19.

We could therefore calculate X19 in 6 multiplications.

Practical work

Make a function that performs fast exponentiation in a pyboard.

The best exponentiation ?

Finally, let's note that fast exponentiation doesn't always give the fastest method. For example, to compute X15, we could have proceeded like this :

a1=XX
a2=a1a1X2
a3=a2a1X3
a4=a3a3X6
a5=a4a3X9
a6=a4a4X15

Then 5 multiplications for X15, instead of 6 by the method called fast exponentiation. A better exponentiation list for X15 is: 1, 2, 3, 6, 9, 15. More efficient techniques exist, such as the addition strings detailed on another page of this wiki.

Page Actions

Recent Changes

Group & Page

Back Links