# Where is factoring if discrete logarithm is broken?

Assume given $$g^X\equiv h\bmod p$$ where $$g$$ is of order $$\frac{\lambda(p)}2$$ where $$\lambda(p)$$ is Carmichael Lambda function applied to prime $$p$$ (so $$2$$ is invertible in exponent) we can compute $$X$$ in polynomial time on an assumption $$2$$ is invertible in exponent (we can assume we take square roots and make the generator of order $$\frac{\lambda(p)}2$$ and we assume $$2$$ needs to be invertible in exponent).

Consider the scenario where $$N=PQ$$ and $$P$$ and $$Q$$ are equal bit primes and $$e$$ is encryption key and $$d$$ is decryption key satisfying $$ed=1\bmod\varphi(N)$$ where $$\varphi(N)$$ is Euler totient function applied to $$N$$:

Find $$r$$ such that $$g^r\equiv1\bmod N$$ where $$r$$ is period of the multiplicative group modulo $$N$$ and $$g$$ generates it.

In the above two cases since we do not know $$\varphi(N)$$ we cannot assume $$2$$ is invertible in exponent.

Is $$RSA$$ attackable if discrete logarithm is broken using an algorithm which makes essential utilization of $$\lambda(p)$$?

PLEASE DO NOT CONNECT TO Reduction of Integer factorization to Discrete logarithm problem and please see comments on reasons. Bach utilizes blackbox notions which encompasses knowledge of $$\lambda(p)$$.

• Is this a homework question? Dec 14 '20 at 17:56
• Does this answer your question? Reduction of Integer factorization to Discrete logarithm problem
– Mark
Dec 14 '20 at 18:10
• @poncho no. Bach's paper gets discrete logarithm as a black box algorithm. It implicitly assumes all properties of $\lambda(p)$ can be exploited though we don't know it. Dec 14 '20 at 18:15
• @Mark I am aware of Bach's algorithm. Dec 14 '20 at 18:16
• @Mark: actually, for semi-primes, the relation is $\lambda(n) = \phi(n) / \gcd(p-1, q-1)$, and so there are more possibilities (especially if $\gcd(p-1, q-1)$ happens to be large). Dec 14 '20 at 18:36