Probabilistic Primality Tests and RSA Algorithm

Year 2024, Volume: 1 Issue: 1, 8 - 18, 01.01.2025

Fatma Çetin , Ahmet Sınak

Abstract

The security of the RSA algorithm is based on the difficulty of the integer factorisation problem. To construct an RSA algorithm for one user, two sufficiently large prime numbers are needed. This leads to the issue of generating large prime numbers. In the literature, there are two main primality test methods: probabilistic and deterministic primality tests. This paper reviews the main probabilistic primality tests such as the Fermat, Lehmann, Slovay-Strassen and Miller-Rabin tests. Then we evaluate and compare their performance based on their execution times for different sizes of inputs. We present performance analyses based on their execution times. We finally review the RSA algorithm that uses two sufficiently large prime numbers.

Keywords

Cryptology, Prime numbers, Probabilistic Primality tests, RSA algorithm

Thanks

This work is the output of the Master's thesis in [3] supervised by the second author. We extend our gratitude to Ebru SINAK for her continuous support and contribution to the realization of this work. The first author offers her endless respect and gratitude to her parents, who have always supported her throughout her studies, giving her strength with their presence.

References

• [1] M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P, Annals of Mathematics, 160(2), 781-793, 2004.