A recent paper by JY Cai and Ben Young entitled, "Quantum Algorithms for Discrete Log Require Precise Rotations" (https://dl.acm.org/doi/full/10.1145/3736421) appears to say that the probability of success of Shors Discrete Log problem gets exponentially smaller as the size of the largest prime factor of the order of the group (for GF(p) that is the largest prime factor of p-1 when p is prime). Is that a correct interpretation of this paper. If it is, then does it then imply that the best primes to use for finite field discrete logarithm are the so called safe primes where the prime minus 1 over 2 is itself prime?
1
-
$\begingroup$ Related question regarding impact of the attack crypto.stackexchange.com/questions/106856/… $\endgroup$kodlu– kodlu2025-07-18 04:08:16 +00:00Commented Jul 18 at 4:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
It is true that if $p-1$ is smooth (has small prime divisors) then certain attacks (e.g., the Pohlig-Hellman algorithm) on the prime field DL are more efficient, so from this point of view choosing a safe prime is good.
However, to the best of my understanding, the most efficient attacks on the prime field DL are still efficient even when $p$ is a safe prime.
For example, the index calculus algorithm uses a factor base made up of small primes and can be optimized to obtain subexponential complexity.
The discussion on pp. 103-113 of Chapter 3 in the Handbook of Applied Crypto is brief and to the point; see under index calculus.
-
$\begingroup$ This answer seems to overlook that the question is about quantum algorithms for dlog, not classical algorithms $\endgroup$Geoffroy Couteau– Geoffroy Couteau2025-07-18 15:38:32 +00:00Commented Jul 18 at 15:38
-
$\begingroup$ I may have misinterpreted it; maybe the OP can clarify. $\endgroup$kodlu– kodlu2025-07-18 16:18:08 +00:00Commented Jul 18 at 16:18