Optimizing the Miller-Rabin Primality Test Using Supervised Machine Learning for Intelligent Witness Selection
Location
Golden Eagles
Start Date
2-5-2025 12:50 PM
Department
Computer Science
Abstract
Primality testing is the foremost process in ascertaining whether a number is prime. These exams form the foundations of security within cryptographic schemes such as RSA. A widely utilized algorithm for this purpose is the Miller-Rabin primality test. This is a probabilistic algorithm that efficiently detects compositeness for a number but needs multiple rounds for confident results when checking for primes. This research aims to optimize the Miller-Rabin test through supervised machine learning techniques for intelligent witness selection. The witness, a number used to verify primality, plays the most critical role in deciding the accuracy and efficiency of the test. By training supervised machine-learning models to identify good witnesses for candidate numbers based on detected patterns in their performance, we aim to reduce the number of test iterations without affecting accuracy. This approach combines insights from traditional number theory with more modern data-driven techniques, providing a unique solution to a classically difficult problem. We anticipate improvements in computational efficiency within cryptographic systems and forwarding interdisciplinary studies in the domain of number theory, and machine learning, as a result of this research.
Faculty Sponsor
Peter Kimmel
Optimizing the Miller-Rabin Primality Test Using Supervised Machine Learning for Intelligent Witness Selection
Golden Eagles
Primality testing is the foremost process in ascertaining whether a number is prime. These exams form the foundations of security within cryptographic schemes such as RSA. A widely utilized algorithm for this purpose is the Miller-Rabin primality test. This is a probabilistic algorithm that efficiently detects compositeness for a number but needs multiple rounds for confident results when checking for primes. This research aims to optimize the Miller-Rabin test through supervised machine learning techniques for intelligent witness selection. The witness, a number used to verify primality, plays the most critical role in deciding the accuracy and efficiency of the test. By training supervised machine-learning models to identify good witnesses for candidate numbers based on detected patterns in their performance, we aim to reduce the number of test iterations without affecting accuracy. This approach combines insights from traditional number theory with more modern data-driven techniques, providing a unique solution to a classically difficult problem. We anticipate improvements in computational efficiency within cryptographic systems and forwarding interdisciplinary studies in the domain of number theory, and machine learning, as a result of this research.