0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Dec 26, 2016 at 23:38

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.