# complexity of iterative squaring in relation to factorization

I've run into a question dealing with the number of
modular multiplications of O(n) bit numbers in the following situation:

Given two n bit primes p,q define m=pq. ​ ​ ​ Choose some 'a' so that ​ $2<a<m\hspace{-0.04 in}-\hspace{-0.04 in}2$
and look at a^(2^t) for some integer t. ​ ​ ​ This is done using iterated squaring.

The question asks about the number of modular multiplications needed for the
case of not knowing the factorization of m and the case of knowing the factorization.
The question hints at using t and n to quantify things.

Me question is, what does the factorization of m have to do with this?

The trick in integrated squaring is using the 'on bits' of a b (call them bi for i: 0 -> n) to calculate a^b by multiplying all (a^(2^i))^bi. I don't quite understand where this question is headed.

Could anyone shed a little light on things?

• Assuming the question really asks: "and look at $a^{(2^t)}\bmod m$ for some integer $t$ " , hint for the "knowing the factorization" case: look at $a^{(2^t)}\bmod p$ and $a^{(2^t)}\bmod q$ using Fermat's little theorem, then apply the CRT.
– fgrieu
Dec 26, 2016 at 23:38

Let $m = pq$. Computing $A := a^{2^t} \pmod m$ requires $t$ $2n$-bit modular multiplications.
Now if you know the factorization of $m$ (i.e., $p$ and $q$) then you can evaluate $A = a^{2^t} \pmod m$ from $A_p := a^{2^t} \pmod p$ and $A_q := a^{2^t} \pmod q$ using Chinese remaindering: $$A = A_p + p\bigl[i_p (A_q-A_p) \bmod q\bigr]\quad\text{where i_p = p^{-1} \bmod q}$$
The computation of $A_p$ (resp. of $A_q$) requires $t$ $n$-bit modular multiplications. Assuming that $i_p$ is pre-computed, the computation of $A$ thus requires $(2t+1)$ $n$-bit modular multiplications.
The key here is that knowing the factorization of $m=pq$ greatly speeds up the computation of $a^{2^t} \pmod{m}$ when $t$ is large. As noted before, it suffices to compute $a^{2^t} \pmod{p}$ and $a^{2^t} \pmod{q}$ and to apply the CRT.
However, thanks to Fermat's little theorem, $a^{2^t} \pmod{p}$ (and similarly $a^{2^t} \pmod{q}$) can be computed more efficiently than by applying $t$ successive squarings. Instead, we can first compute $e=2^t \pmod{p-1},$ a $\log_2(p)$-bit number and then use: $$a^{2^t}=a^e\pmod{p},$$ to compute $a^{2^t} \pmod{p}$ using only $\log_2(p)$ squarings and multiplications. When $t$ is large, this is much more efficient than repeatedly squaring $t$ consecutive times.