Score:5

How fast is Factorization reduced to a Discrete Logarithm?

cn flag

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$?

poncho avatar
my flag
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...
Score:4
ru flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.