This study investigates how to automatically choose the fastest algorithm for solving a given instance of the Discrete Logarithm Problem (DLP). The DLP underlies many public-key cryptographic systems, yet no single algorithm is optimal for every instance: Pohlig–Hellman is highly effective when the group order is smooth, Pollard’s Rho and the Kangaroo method are suitable for prime-order and interval-restricted cases, and Index Calculus dominates over large prime fields. In this study, algorithm selection is formulated as a supervised classification task. For each instance, a compact set of number-theoretic features—bit length, largest prime factor, smoothness ratio, interval width, and simplified cost estimates—is computed, and three tree-based models, namely Decision Tree, Random Forest, and XGBoost, are trained on a balanced synthetic dataset of 24,000 instances. XGBoost achieved 94.6% accuracy and a 94.3% macro F1-score. Feature-importance analysis showed that the smoothness ratio and the largest prime factor are the most decisive predictors for algorithm choice. The findings confirm that a lightweight machine learning model can serve as a reliable and interpretable tool both for selecting DLP solvers and for assessing the real hardness of group parameters.
Adaptive Ai-Based Algorithm Selection Framework for The Discrete Logarithm Problem
DOI:
Abstract
References
W. Diffie and M. E. Hellman. “New Directions in Cryptography.” IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.
T. ElGamal. “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.” IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 469–472, 1985.
S. C. Pohlig and M. E. Hellman. “An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance.” IEEE Transactions on Information Theory, vol. 24, no. 1, pp. 106–110, 1978.
J. M. Pollard. “Monte Carlo Methods for Index Computation (mod p).” Mathematics of Computation, vol. 32, no. 143, pp. 918–924, 1978.
J. M. Pollard. “Kangaroos, Monopoly and Discrete Logarithms.” Journal of Cryptology, vol. 13, no. 4, pp. 437–447, 2000.
D. Coppersmith, A. M. Odlyzko and R. Schroeppel. “Discrete Logarithms in GF(p).” Algorithmica, vol. 1, pp. 1–15, 1986.
J. R. Rice. “The Algorithm Selection Problem.” Advances in Computers, vol. 15, pp. 65–118, 1976.
P. C. van Oorschot and M. J. Wiener. “Parallel Collision Search with Cryptanalytic Applications.” Journal of Cryptology, vol. 12, no. 1, pp. 1–28, 1999.
L. Breiman. “Random Forests.” Machine Learning, vol. 45, no. 1, pp. 5–32, 2001. DOI: 10.1023/A:1010933404324.
T. Chen and C. Guestrin. “XGBoost: A Scalable Tree Boosting System.” Proceedings of ACM SIGKDD, 2016, pp. 785–794. DOI: 10.1145/2939672.2939785.
K. A. Smith-Miles. “Cross-Disciplinary Perspectives on Meta-Learning for Algorithm Selection.” ACM Computing Surveys, vol. 41, no. 1, pp. 1–25, 2008.
D. Hankerson, A. Menezes and S. Vanstone. Guide to Elliptic Curve Cryptography. Springer, 2004.
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.
F. Pedregosa et al. “Scikit-learn: Machine Learning in Python.” Journal of Machine Learning Research, vol. 12, pp. 2825–2830, 2011.