7
$\begingroup$

Given a RSA modulus $n$, which is the product of two safe primes: \begin{align*} P &= 2p + 1 \quad\quad\quad Q = 2q + 1 \\ n &= P \cdot Q = 4p q + 2 p + 2 q + 1 \end{align*} The hidden group order is then \begin{align*} \Phi(n) &= (P-1)(Q-1) = 4p q \end{align*} Choosing some random element $z \in \mathbb{F}_n^*$, then most likely $z^4 \in C_{p q}$ (the subgroup of $\mathbb{F}_n^*$ that has order $pq$). Let's call $z^4$ now $g$. For every $g \in C_{pq}$ it holds that $g^x = g^{x \bmod p q}$. We have $\frac{n-1}{2} = 2p q + p + q $, so it follows that \begin{align*} g^\frac{n-1}{2} &\equiv g^{p + q} \pmod{n} \end{align*} We define $p>q$. Computing the discrete logarithm $\text{dlog}_g(g^{p+q})=p+q$ takes $\mathcal{O}(\sqrt{p})$ time, which suffices to compute the group order $\Phi(n)$, and thus factor $n$. Note that the running time of the baby-step giant-step algorithm depends only on the size of $p$ here and not on the group size $\Phi(n)$.

Question: Is there an algorithm to compute this discrete logarithm faster than factoring $n$? Would the running time of index calculus depend on the group size here or would it depend on the size of $p$?

$\endgroup$
1
  • $\begingroup$ Note that if you can compute a discrete log modulo a composite, then you can factor the composite; this holds true even if the composite is not a product of two safe primes. This implies that there is no algorithm to computing the discrete log that is faster than factoring... $\endgroup$
    – poncho
    Commented Nov 15, 2022 at 11:58

1 Answer 1

5
$\begingroup$

Classically speaking, it will be hard to do better than Pollard's kangaroo method (essentially equivalent to baby-step-giant-step, but with better memory usage), which, as you note, will take time $O(\sqrt{p+q})$.

Index calculus algorithms need to know the order of the subgroup being solved during the linear algebra phase (and if we knew the order of the subgroup, we would be able to factor without the discrete logarithm). In any event, the runtime would depend on the group size rather than the exponent size.

The quantum Fourier transform (i.e. Shor's algorithm) can take advantage of this by requiring $O(\log(p+q))$ qubits for the transform rather than $O(\log(pq))$. This approach has been noted by Ekerå and Håstad in their paper Quantum algorithms for computing short discrete logarithms and factoring RSA integers.

$\endgroup$
1
  • $\begingroup$ Since ibm is now letting to rent 131 qbits quantum computers in the cloud, is there working algorithms that can work on unstable qbits requiring less than nbits(pq)? $\endgroup$ Commented Apr 13 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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