MHB Fast Exponentiation: Time Complexity and Number of Bit Operations

[evinda]

Hello! (Wave)

It is stated in my notes that the calculation of $a^{n-1} \pmod{n}$ by fast exponentiation takes $O(\log{n})$ arithmetic operations and $O((\log{n})^3)$ bit operations.By using fast exponentiation, in order to calculate $a^{n-1} \pmod{n}$ we write $n-1$ as $n-1=n_0+2 n_1+ \dots+ 2^k n_k$.

We calculate $a^2, (a^2)^2, \dots, (a^{2^{k-1}})^2$.

Does each calculation $b^2$, where $b=a^{2^{j}}$, require time $\log^2n$ and since we make $k \leq \log{(n-1)}\leq \log{n}$ operations, we need totally $O(\log^3 n)$ time?

Is the time complexity needed equal to the number of bit operations?

 

[Evgeny.Makarov]

Does each calculation $b^2$, where $b=a^{2^{j}}$, require time $\log^2n$ and since we make $k \leq \log{(n-1)}\leq \log{n}$ operations, we need totally $O(\log^3 n)$ time?

Yes. Each multiplication takes time proportional to the square of the number of bits. Since computation is done modulo $n$, it requires approximately $\log n$ bits. There is also about $\log n$ additions, but each takes only time proportional to the number of bits.

Is the time complexity needed equal to the number of bit operations?

Yes.

 

[evinda]

There is also about $\log n$ additions, but each takes only time proportional to the number of bits.

You mean the additions we make to write this: $n-1=n_0+ 2n_1+ \dots+ 2^k n_k$ ? If so, don't we also need to make $k$ divisions by $2$ in order to find the $n_i$s for $i=0$ to $k$?

 

[Evgeny.Makarov]

You mean the additions we make to write this: $n-1=n_0+ 2n_1+ \dots+ 2^k n_k$ ?

I should have said we need up to $k$ additional multiplications. This is what we do with $a^2,\ldots,a^{2^k}$.

If so, don't we also need to make $k$ divisions by $2$ in order to find the $n_i$s for $i=0$ to $k$?

This too. Though if $n$ is considered constant, then the binary representation of $n-1$ can be computed in advance and can be considered known.

 

[evinda]

I should have said we need up to $k$ additional multiplications. This is what we do with $a^2,\ldots,a^{2^k}$.

Ah I see...

This too. Though if $n$ is considered constant, then the binary representation of $n-1$ can be computed in advance and can be considered known.

Ok, but if we would want to find the time complexity in order to find the binary representation of $n-1$ then we would need to make $k$ divisions by $2$. So the time complexity would be $k \cdot (\log{n} \cdot \log{2} )=O(\log^2{n})$, right?

 

[Evgeny.Makarov]

The problem statement probably says that we are given binary representations of $a$ and $n$ and have to compute the binary representation of $a^{n-1}\pmod{n}$. In this case computing the binary representation of $n-1$ takes time proportional to the number of bits in $n$, i.e., $\log n$.

 

[evinda]

The problem statement probably says that we are given binary representations of $a$ and $n$ and have to compute the binary representation of $a^{n-1}\pmod{n}$. In this case computing the binary representation of $n-1$ takes time proportional to the number of bits in $n$, i.e., $\log n$.

How do we compute the binary representation of $n-1$ in time proportional to $\log{n}$ ?
I am looking at the algorithm of the Fermat test where the binary representation of $n$ is given , we choose a random $a \in \{2, \dots, n-2\}$ and we want to calculate $a^{n-1} \pmod{n}$, in order to deduce whether $n$ is prime or composite.

 

[Evgeny.Makarov]

How do we compute the binary representation of $n-1$ in time proportional to $\log{n}$ ?
I am looking at the algorithm of the Fermat test where the binary representation of $n$ is given

There is such operation as subtracting one. (Smile) It can be done on numbers in binary.

 

[evinda]

There is such operation as subtracting one. (Smile) It can be done on numbers in binary.

Ah, so we just subtract 0001 from the number $n$ given?
I see... Thank you very much! (Smirk)

 

[evinda]

I have a question. When we have the binary representation of $n-1$, how can we find the $u,k$ such that $n-1=u \cdot 2^k$ ?

 

[Evgeny.Makarov]

When we have the binary representation of $n-1$, how can we find the $u,k$ such that $n-1=u \cdot 2^k$ ?

You can always take $k=0$ and $u=n-1$...

 

[evinda]

You can always take $k=0$ and $u=n-1$...

Oh sorry, I forgot to mention that $u$ has to be odd.

 

[Evgeny.Makarov]

And if you have a decimal representation of $n-1$, are you able to find $u$ and $k$ such that $u$ is not a multiple of $10$ and $n-1=u10^k$?

 

[I like Serena]

Oh sorry, I forgot to mention that $u$ has to be odd.

How about something like:
$$
\left|\begin{array}{l} u\leftarrow n-1 \\ k\leftarrow 0 \\ \text{while } u \text{ even} \\
\left| \begin{array}{l} u \leftarrow u / 2 \\ k \leftarrow k+1\end{array}\right.\end{array}\right.
$$

 

[Evgeny.Makarov]

But we have the binary representation of the number...

 

[evinda]

I think that we count the number of successive zeros from the right to the left till we find one nonzero element.
The number of $0$s that we find will be equal to $k$.
We delete these $0$s and $u$ will be equal to the number that corresponds to the binary representation of the remaining elements.

 

[Evgeny.Makarov]

I agree.

 

[evinda]

I agree.

Nice. (Smile)
And if we are given the binary representation of some number $b$ and want to divide it by $2$ or $4$, we get the result by deleting the last, or the last two elements of $b$, respetively, right?
Also the remainder of $b$ modulo $4$ or modulo $8$ will be equal to the last two or the last three elements of $b$ respectively, right?

 

[Evgeny.Makarov]

And if we are given the binary representation of some number $b$ and want to divide it by $2$ or $4$, we get the result by deleting the last, or the last two elements of $b$, respetively, right?

Yes, if you through away the remainder and take only the quotient.

Also the remainder of $b$ modulo $4$ or modulo $8$ will be equal to the last two or the last three elements of $b$ respectively, right?

Yes.

 

[evinda]

Yes, if you through away the remainder and take only the quotient.

Yes.

Nice. Thanks a lot! (Happy)