Question

The algorithm for computing ${\mathbf{a}}^{\mathbf{b}}\mathbf{modC}$by repeated squaring does not necessarily lead to the minimum number of multiplications. Give an example of $\mathbf{}\mathbf{b}\mathbf{>}\mathbf{10}$where the exponentiation can be performed using fewer multiplications, by some other method.

Short answer

The new method is performed by using fewer multiplications than the given algorithm.

Step-by-step solution

Introduction 

Example for exponentiation:

Consider the value of b is 15

The repeated squaring algorithm calculates the value ${\mathrm{b}}^{15}$ by following method:

${\mathrm{a}}^{15}=\mathrm{a}*{\mathrm{a}}^2*{\mathrm{a}}^4*{\mathrm{a}}^8$

In the above calculation,

“${\mathrm{a}}^2$” is having one multiplication (i.e.${\mathrm{a}}^2=\mathrm{a}\times \mathrm{a}$ ).

“${\mathrm{a}}^4$” is having one multiplication (i.e.${\mathrm{a}}^4={\mathrm{a}}^2\times {\mathrm{a}}^2$).

“ ${\mathrm{a}}^8$” is having one multiplication (i.e. ${\mathrm{a}}^8={\mathrm{a}}^4\times {\mathrm{a}}^4$).

The expression “$\mathrm{a}\times {\mathrm{a}}^2\times {\mathrm{a}}^4\times {\mathrm{a}}^8$” has three multiplications.

Therefore, the above method takes totally 6 multiplications.

Data step

Other method for exponentiation:

Consider the value “b ” is “15 ”.

Split the value “ 15 ” into “ 3 6 , and 12 ”.

Initially, find “${\mathrm{a}}^3=\mathrm{a}*\mathrm{a}*\mathrm{a}$ ”.

This step contains two multiplications process.

Find “${\mathrm{a}}^6={\mathrm{a}}^3*{\mathrm{a}}^3$ ”.

This step contains one multiplication process.

And find “${\mathrm{a}}^{12}={\mathrm{a}}^6*{\mathrm{a}}^6$ ”.

This step contains one multiplication process.

Then finally, “${\mathrm{a}}^{15}$” can be calculated by the following:

${\mathrm{a}}^{15}={\mathrm{a}}^{12}*{\mathrm{a}}^3$

The above step contains one multiplication process.

Thus, the above method takes a totally5 multiplications.

Therefore, the new method is performed by using fewer multiplications than the given algorithm.