Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.