Prof Bill Buchanan OBE

Oct 24, 2021

4 min read

A Bit of Miller and Rabin

Before 1976, we struggled to quickly and effectively test if a number was a prime number. Up to that point, we used Euler and Solovay-Strassen tests, and which struggled to effectively find some prime numbers. For example, both Euler and Solovay-Strassen often identify Carmichael numbers as prime numbers [here]. An example of a Carmichael number is 561, and it will pass the Euler and Solovay-Strassen tests, and be identified as a prime number…