Question

The key operation in encryption and decryption process is the exponentstion. Given an integer x it is easy to write a linear algo O((n)) to find x^n for any integer n. Describe the maths of a fast exponentation algo that can compute x^n in o(log2n) time. Justify

Answer 1

Following are the solution to this question:

Step-by-step explanation:

`x^n` could be approximated by getting a small n loop as well as multiplying x for each incarnation in a linear time. It's very simple. Its key concept is to do it in log2n time.

`x^n = x^{(n)/(2)}\ is \ obvious \ \ x^{(n)/(2)}`

Therefore,
`x^(n), x^{(n)/(2)}` could be determined and divided by itself instead of
`x^n` calculation. It must be done frequently to ensure which half the research is done out with each stage.

Runtime:

Its repetition relationship of the above function is:

`T(n) = T((n)/(2)) + 1`

This can be resolved by master theorem, so it's obvious. The running time of this repeating ration, by master theorem, is
`O ( \log_2n )`.

Pseudocode:

int exponent( int x_1, int y_1 )//defining a method exponent

{

if(y_1==1) //use if to check n value equal to 1

{return x_1;} //return x value

Int t= exponent(x_1,y_1/2);//call method

return t*t;//calculate square

}