What is the time complexity of modular exponentiation?

 

The incorporation of cryptographic methods increased dramatically and is said to continue until   significant improvements in data privacy are enforced tremendously. 

Certain top confidential messages are sent as encrypted information since only those required to read them will access them, not third parties. 

Cryptographic methods use secret keys that will be known only to the receiver and the sender. The encrypted message will never be understood forever if the key gets lost. 

To encrypt these confidential data, it uses the concept of exponentiation, and the most used one is modular exponentiation.

Speaking of this method, it gets run over a modulus. While this is the commonly used method, it takes a lot of time during the process.

 Let us read more about this interesting concept, its severe time complexity, and the reason behind it. 

What is modular exponentiation?

As we know, modular exponentiation is a type of exponentiation that gets run over a modulus. It is a very important method in cryptography. 

When you divide a positive number m (modulus) by a positive number b (base) raised to the e-th power, you get the remainder (e stands for exponent). In other words, given a b, e, and m, one desires to compute c in a way that:

c = b^e (mod m)

For example, let’s assume these values. 

b = 4

e = 3

m = 12

The solution would be the remainder of dividing 4 power 3 by 12.

c = 4^3 (12)

c = 64 (12)

c = 5

Even when the actual figures are huge, modular exponentiation problems like the one illustrated above are regarded as simple. Calculating the derivative (finding e given b, c, and m) is considered to be complicated. 

Given its one-way function structure, modular exponentiation is an excellent option for cryptographic uses.

What is the time complexity of modular exponentiation?

Since we know modular exponentiation uses a lot of time, let’s first check the approaches to know the precise time complexities. 

Usually there are only two approaches that get used and they are,

• Naive approach

• Binary exponentiation

Naive approach

In the naive approach, we will find the exponentiation value by multiplying the value x by the n count of times. 

When we do this, the program would be like

int naiveExponentiationIterative(int x, int n)

{

    int result = 1;

    for(int i=0; i<n; i++)

    {

        result = result * n;

    }

    return result;

}

Under this method, the time taken would be simply O(n) and the space would be O (1). While the time taken seems lesser, this approach is not efficient. The binary exponentiation method alone works perfectly for finding modular exponentiation and they’re often used by coders. 

Hence, let’s take a thorough look at the second approach and know the time complexity under that.

Note: Naive approach is a common method used to solve various problems like bridges in graph since they’re time and space consuming. 

Binary exponentiation 

If the n is large then binary exponentiation will be the best method to employ compared to the naive approach. 

Suppose you divide the given problem into halves, that is if you want to find X^n then, one should initially figure out x^(n/2) and square it. This helps in effectively figuring X power n. 

However what if n is not even? 

In such a case, we will not figure out x^(n/2) rather determine what x power ((n-1)/2) is and then square it then with x, we multiply it. 

Since we’re reducing the exponent every time by 2, the time complexity would be O(logN). The program would be, 

int binaryExponentiationIterative(int x, int n)

{

    int result = 1;

    while( n > 0)

    {

        if( n&1 ) // check whether n is odd or not

        {

            result = result * x;

        }

        x = x*x;

        n = n/2;

    }

    return result

}

Now that we saw the iterative code and the procedure, let’s understand it better with numbers, shall we?

Let’s say we need to find 2 power 21. In this, x denotes 2 and n would be 21. When we code 21 in binary format the result will be 10101. Now, we can also write  2²¹ = (2¹⁶) * (2⁴) * (2¹). We are now supposed to find exponents that have a set bit of 21 written in its binary format. 

For that, we initially make the output as 1. Then in the binary format we start from the left side and move to the right. In each move, we square the base (b) and multiply it with the output everytime we meet the number 1 in the exponent’s binary format. 

That is n’s binary format which is 10101. We technically do, x = x² and n = n/2 and multiply it with x. As the step gets completed within 5 times (the count of characters in the binary format equals to 5), the time complexity becomes O(logN) and space would be O(1).

To produce the result in a recursive manner (the above-mentioned steps are done in an iterative manner) the same steps must be followed and also the usage of stacks. 

Since stacks get used the space complexity changes to O(logN) and the time complexity remains the same. 

Note that if the n value is too big, we can figure out X power n output however sometimes large values will become trouble when it comes to storing the result. And so, most of the problems will make use of the modulo to determine the result. 

Since modulo has a principle that any result under modulo that is M will be lesser than M, the storing of the result becomes easier. 

Hence, the exponentiation found in a modulo is simply called modular exponentiation. The syntax would be: xⁿ % M = (x * x * x * ….. n times) % M

Final thoughts

Modular exponentiations indeed take time but they’re one of the important features of cryptography. Be it any texting apps or so, encryptions prevent our messages or data from being accessed by illegal users. 

We hope our article helped you with the answers you were seeking. For further reading materials related to questions like target sum, coin change, bridges in graph and such, visit our website and enrich yourself.