complexity of iterative squaring in relation to factorization

Question

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?

Answer 1

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.

Answer 2

There is more to this question than meets the eye at first glance. In fact, it was used in a paper of Rivest, Shamir and Wagner called Time-lock puzzles and timed-release Crypto (see https://people.csail.mit.edu/rivest/pubs/RSW96.pdf).

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.