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&lt;a&lt;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?
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.