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.

研究了梯度法在有限循环群中学习离散对数奇偶位的局限性，理论和经验证实发现梯度函数集中在一个固定点附近，不管所使用的对数的基。通过使用内积空间中的 Boas-Bellman 不等式以及建立离散对数奇偶位函数的近似正交性，对于基于梯度的学习的限制性能进行了证明。使用基于神经网络的方法的实证实验证明了梯度法学习的局限性，随着群的阶数的增加，在预测奇偶位上的成功率逐渐降低。