Intractability of Learning the Discrete Logarithm with Gradient-Based
  Methods
Rustem Takhanov Maxat Tezekbayev Artur Pak Arman Bolatov Zhibek Kadyrsizova Zhenisbek Assylbekov
The discrete logarithm problem is a fundamental challenge in number theory
with significant implications for cryptographic protocols. In this paper, we
investigate the limitations of gradient-based methods for learning the parity
bit of the discrete logarithm in finite cyclic groups of prime order. Our main
result, supported by theoretical analysis and empirical verification, reveals
the concentration of the gradient of the loss function around a fixed point,
independent of the logarithm's base used. This concentration property leads to
a restricted ability to learn the parity bit efficiently using gradient-based
methods, irrespective of the complexity of the network architecture being
trained.
  Our proof relies on Boas-Bellman inequality in inner product spaces and it
involves establishing approximate orthogonality of discrete logarithm's parity
bit functions through the spectral norm of certain matrices. Empirical
experiments using a neural network-based approach further verify the
limitations of gradient-based learning, demonstrating the decreasing success
rate in predicting the parity bit as the group order increases.