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…