ANALYSIS OF PROBABILISTIC PRIME NUMBER GENERATION METHODS AND THEIR EFFICIENCY

Abstract

Probabilistic primality tests are fundamental tools in cryptography, enabling the efficient generation of large prime numbers for secure keys. This paper presents a comprehensive examination of two key algorithms – the Miller–Rabin and Solovay–Strassen tests – highlighting both their theoretical foundations and practical performance in cryptographic prime generation. We detail the operational principles of each algorithm and analyze their computational efficiency and error probabilities. A comparative evaluation of Miller–Rabin and Solovay–Strassen in practice highlights Miller–Rabin’s superior speed and reliability. In particular, the Miller–Rabin test offers faster execution (owing to simpler modular operations) and a stricter error bound (with error probability decreasing roughly as 4^(-k) per round, versus 2^(-k) for Solovay–Strassen), making it the preferred choice in modern cryptographic libraries. Additionally, we briefly examine hybrid techniques such as the Baillie–PSW test – a combination of Miller–Rabin and Lucas sequence tests – which has no known pseudoprimes, illustrating an alternative high-confidence approach. Overall, these findings underscore the importance of robust probabilistic testing, exemplified by Miller–Rabin, for secure key generation in cryptosystems, ensuring that primes used in cryptographic keys are reliable without significant performance trade-offs.