Neural Network Configuration of the r-Adding Walk in Pollard’s Rho Method Using the Spectral Gap for the Elliptic Curve Discrete Logarithm Problem

Abstract

This paper investigates two neural-network formulations for configuring the r-adding walk in Pollard’s Rho method for the elliptic curve discrete logarithm problem on short Weierstrass curves over prime fields. The first formulation uses an NM-r classifier to predict the increment-table size r and an NM-inc regression network to generate the normalized increment coefficients (α_i, β_i) directly from the curve and subgroup context. An approximate spectral-gap dataset with context-grouped training, validation, and test partitions was constructed for this formulation. Its evaluation revealed severe target-class imbalance for NM-r and instability of the single-target increment labels under higher-precision transition sampling, which limited reliable end-to-end generalization. These findings motivated a second formulation in which a neural model scores a finite pool of candidate increment tables and selects the candidate with the highest predicted spectral quality for a fixed r. To evaluate the second formulation without sampling uncertainty in the target, an exact dataset containing 5,000 curve contexts and 480,000 candidate configurations was generated for r ∈ {8, 16, 32}, with the prime field modulus p and subgroup order N satisfying 2¹⁵ < p, N < 2²⁰. Each target was computed from an exact r × r tag-transition matrix obtained by enumerating every subgroup state. Candidate-scoring models were trained using context-grouped 80/10/10 splitting, evaluated across multiple input representations and random seeds, and frozen before integration into a C# implementation of Pollard’s Rho method. The benchmark compared neural selection, deterministic random selection, an L = 512 sampled-gap oracle, and an exact-gap oracle on 500 held-out contexts using 30 paired trials for each context and r, producing 180,000 successful measurements. Across r ∈ {8, 16, 32}, neural selection reduced the mean number of iterations normalized by √N by 2.52% relative to random selection, with a context-bootstrap 95% confidence interval of [0.24%, 4.79%] and a paired sign-flip value of p = 0.0325. For r = 8, the reduction was 5.25% with a 95% confidence interval of [1.40%, 9.00%] and a Holm-adjusted value of p = 0.0237 across the three neural-versus-random tests. No conclusive improvement was obtained for r = 16 or r = 32. Moreover, improvements in the exact spectral gap showed only a weak association with reductions in the number of iterations of Pollard’s Rho method, and the exact-gap oracle did not provide a consistent advantage. The results demonstrate a modest empirical benefit of neural candidate selection in the evaluated research-scale setting while showing that the spectral gap alone is not a universal predictor of the performance of Pollard’s Rho method.