# Hardness of finding mutual discrete logarithms of small generators in $\mathbb{Z}_p$

Suppose you want to select a prime $p$ such that finding e.g. $log_2(3)$ in $\mathbb{Z}_p$ is expected to be either at least as hard as the general Discrete Logarithm Problem in $\mathbb{Z}_p$, or at least both problems infeasible, e.g. because you want to use $g=2,h=3,p$ as domain parameters for some scheme. How large would $p$ have to be?

Intuitively, the problem of finding $log_2(3)$ seems similar to the problem of doing the precomputations of Index Calculus, i.e. to find a sequence of exponents ${(k_i)}_{i=0}^n$ such that, for all $i=0..n$, the integer $FE2I(g^{k_i} \pmod p)$ is $B$-smooth (and has prime power factors with exponents that form a vector $v_i$ that cannot be expressed as a linear combination of any other $v_j$, etc).

To make Index Calculus in $\mathbb{Z}_p$ hard, requires choosing a prime $p$, such that, for any smaller prime $B$, there would either be too few $B$-smooth integers, or the number $\pi(B)$ of primes less than $B$ would have to be too great. Given the approximation that the probability of a number less than $p$ being $B$-smooth is approximately $u^{-u}$ where $u = ln(p)/ln(B)$, and that $\pi(B) \approx B/ln(B)$, you e.g. get either a probability of at most $2^{-128}$ that a random element in $\mathbb{Z}_p$ is $B$-smooth, or you have to choose a $B$ that is greater than the $2^ {128}$:th prime, if $p \approx 2^{3645}$.

Consequently, presuming that a 3072-bit prime is generally (more than) sufficient for schemes that require a 128-bit strong DLP scheme, would a 4096-bit prime be sufficient for a scheme that relies on the hardness of computing $log_g(h)$ for small deterministically selected generators $g$ and $h$?

Edit: Considering that e.g. $p = 2^{4096} - 3^{2225}$ is a prime (implying $log_2(3) = 4096(2225)^{-1} \bmod (p-1)$) and the main argument in my question only applies to verifiably randomly generated primes, do primes for which $log_2(3)$ is easily solvable have anything in common? Are all such primes on the form $p = 2^n-3^m$ or some other easily detected form, or is it possible to doctor such a prime in such way that knowledge of $log_2(3)$ may be kept secret?

Edit 2: Considering that the equation $kp = 2^n - 3^m$ has at least one solution $k \in \mathbb{Z}, n,m \in \mathbb{Z}_{p-1}$ for all primes $p > 3$, could the question regarding doctoring these primes be expressed as: Is there a way to calculate $(2^n - 3^m)/k$ as efficiently in $\mathbb{Z}$, as $2^n - 3^m$ might be calculated in $\mathbb{Z}_p$, for arbitrary $k,n,m$ in a suitable range?.

For instance, would checking $2^i3^{-j} \bmod p \neq 1$ for $0 \lt i,j \le 2^{48}$ be sufficient, or is it possible to calculate $(2^n - 3^m)/k$ for huge $n,m$ e.g. if $k$ is a huge power of another small prime? Are there other short cuts?

Edit 3: Because $kp = 2^n - 3^m$ is equivalent to $1 + kp3^{-m} = 2^n3^{-m}$, we have $n\ln(2) - m\ln(3) = \ln(1 + kp3^{-m})$. If $kp$ is significantly smaller than $3^m$, we would have $|n\ln(2) - m\ln(3)| \lt \epsilon$. This would however require that $\frac{\ln(3)}{\ln(2)} = \frac{n}m + \delta$ with $|\delta| \lt \epsilon$, which is not the case (because $\epsilon$ can be approximated by an exponential function in $-m$ and the fractional expansion of $\frac{\ln(3)}{\ln(2)}$ is not periodic with period dividing $\phi(m)$ in the $\approx m$ most significant positions).

Hence, if $2^{255} \lt n \lt 2^{256}$, there is no solution in the natural numbers to $kp = 2^n - 3^m$ in which $k$ is small enough for $kp$ to be several magnitudes smaller than $2^{2^{255}}$.

Next, suppose $C$ is the greatest number you are able to represent in arithmetic operations. If $k = \prod_{i=0}^{l}p_i^{e_i}$ with each $p_i^{e_i} \le \frac{C}{p_i}$, there is a non-negligible probability that $kp$ might be factored by performing a CRT reconstruction from $\frac{(2^n-3^m)\prod_{j=0,j\neq i}^{l}p_j^{-e_j} \pmod {p_i^{e_i+1}}}{p_i^{e_i}}$. This would however still entail a bound $k \lt C^{\pi(C)}$, which would still be too small to guarantee that $n$ and $m$ might not be calculated given $p$.

-
Isn't it the same than trying to find a value of p for which Tonnelli-Shanks algorithm (and its generalization en.wikipedia.org/wiki/…) would require a large number of iterations ? The proof seems to indicate that the square-root algorithm converges in polynomial time. –  Pierre May 21 at 23:01
@Pierre: (Generalized) Tonelli-Shanks is an algorithm for finding (arbitrary) roots in cyclic groups. It's not the same thing, far from it, but if you see a connection, please feel free to demonstrate it. –  Henrick Hellström Jul 10 at 1:58
The entire argument of "what if $p=2^n-3^m$" is pointless. A random prime has a negligible chance to fulfill this requirement. Similar arguments can be made for RSA numbers having a specific format: E.g. if $p$ and $q$ are close together, Fermat factoring works. The knowledge of a fixed element to a fixed base does not help solving arbitrary logarithms. For example: $\log_2(8)=3$ is known to be true in any $\mathbb{Z}_p$ with $p>8$. –  tylo Aug 17 at 9:56
@tylo: This questiion isn't about solving DLP in arbitrary $\mathbb{Z}_p^*$ groups, but specifically about the security of system parameters $g,h,p$ where $g=2$ and $h=3$. Should I read your comment as implying that I should clarify the reason for the question? –  Henrick Hellström Aug 17 at 11:13
@tylo: Furthermore, I believe I am able to prove that $kp=2^n−3^m$ for bounded values of k, only has a limited number of solutions $n,m,p$ that can all be found. This means we don't have to worry too much about such possibilities regardless if we generate p ourselves or if someone else generates the prime. –  Henrick Hellström Aug 19 at 8:53