Effective Hybrid Algorithm For Generating Large Prime Numbers
Keywords:
Prime number, primality test, Miller–Rabin,, random number generation, cryptographyAbstract
This article addresses the problem of generating large prime numbers. Due to the high computational complexity of traditional methods, their efficiency remains low. Therefore, the paper analyzes existing approaches and proposes a new hybrid algorithm, based on algebraic and probabilistic tests. The proposed method demonstrates the ability to generate prime numbers quickly and reliably. The results are compared across different bit lengths (256, 512, 1024, 2048 bits) using experimental data, and the efficiency of the algorithm is presented. The research outcomes have practical significance for generating secure keys in public-key cryptosystems (e.g., RSA).
References
1. Marc Joye, Pascal Paillier and Serge Vaudenay, Efficient Generation of Prime Numbers, Springer-Verlag Berlin Heidelberg 2000, pp. 340–354, 2000.
2. C. Couvreur and J.-J. Quisquater. An introduction to fast generation of large prime numbers. Philips Journal of Research, vol. 37, pp. 231–264, 1982.
3. R. Solovay and V. Strassen. A fast Monte-Carlo test for primality. SIAM Journal on Computing, vol. 6, pp. 84–85, 1977.
4. H.C. Pocklington. The determination of the prime or composite nature of large numbers by Fermat’s theorem. Proc. of the Cambridge Philosophical Society, vol. 18, pp. 29–30, 1914.
5. A.O.L. Atkin and F. Morain. Elliptic curves and primality proving. Mathematics of Computation, vol. 61, pp. 29–68, 1993.
6. W. Bosma and M.-P. van der Hulst. Faster primality testing. In Advances in Cryptology – CRYPTO ’89, vol. 435 of Lecture Notes in Computer Science, pp. 652–656, Springer-Verlag, 1990.
7. J. Brandt and I. Damg˚ard. On generation of probable primes by incremental search. In Advances in Cryptology – CRYPTO ’92, vol. 740 of Lecture Notes in Computer Science, pp. 358–370, Springer-Verlag, 1993.
8. J. Menezes, P.C. van Oorschot, and S.A. Vanstone. Handbook of Applied Cryptography, CRC Press, 1997.
9. Bruce Shnier, Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C Publislirc John Wiley & Sons, Inc.
10. A.V. Bajandin, To distribution of simple numbers to set of natural integers. - Novosibirsk 1999.27 p.
11. I M. Vinogradov, Bases of the theory of numbers. - M 1981.
12. Bruce Shnier, Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C Publislirc John Wiley & Sons, Inc.
13. Vladislav S. Igumnov, Generation of the Large Random Prime Numbers, 5th International siberian workshop and tutorial edm' 2004, session II, july 1-5.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Xudoykulov Z. T., Jabbarov N. A., Jabborov A. A.
This work is licensed under a Creative Commons Attribution 4.0 International License.
