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 = \frac{\ln(p)}{\ln(B)}$, and that $\pi(B) \approx \frac{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$.
