Question

Using the Fermat primality test, calculate how many Fermat witnesses AND how many Fermat liars there are for 341 using computer programming.

Answer 1

}

Copyable Code

//Include the needed headers
#include <cstring>
#include <iostream>
#include <cstdlib>
#define longlong long long
using namespace std;

//Method modulo()
longlong modulo(longlong base, longlong expo, longlong mod)
{
   // Declare and initialize variables
   longlong c = 1;
   longlong d = base;

   //Loop till the condition satisfies
   while (expo > 0)
   {
       //Check condition
       if (expo % 2 == 1)

           //Compute c
           c = (c * d) % mod;

       //Compute d
       d = (d * d) % mod;

       //Compute exponent
       expo = expo / 2;
   }

   //Return value
   return c % mod;
}

//Method Fermat()
bool Fermat(longlong p, int noOfIterations)
{
   // Declare and initialize variables
   int fLiars = 0;
   int fWitness = 0;

   //Check condition
   if (p == 1)
   {
       //Return
       return false;
   }

   //Loop through noOfIterations
   for (int i = 0; i < noOfIterations; i++)
   {
       //Declare and initialize a
       longlong a = rand() % (p - 1) + 1;

       //Check condition
       if (modulo(a, p - 1, p) != 1)
       {
           //Increment fermat liars
           fLiars++;

           //Display fermat liar
           cout << " Number of Fermat lairs: " << fLiars;
          
           //Return
           return false;
       }
   }

   //Increment fermat witness
   fWitness++;

   //Display fermat witness
   cout << " Number of Fermat witness: " << fLiars;

   //Return
   return true;
}

//Method main()
int main()
{
   //Declare and initialize iteration
   int iteration = 50;

   //Declare a variable for input
   longlong input;

   //Prompt for input
   cout << " Enter an input to test primality: ";

   //Read input
   cin >> input;

   //Check condition
   if (Fermat(input, iteration))

       //Display result
       cout << " " << input << " is prime" << endl;

   //Otherwise
   else
       //Display result
       cout << " " << input << " is not prime" << endl;

   //Pause
   getchar(); getchar();

   //Return
   return 0;
}