Question

Problem 1: Implement an algorithm to generate prime numbers. You will need to implement the following ingredients (some of them you developed for earlier assignments):

1. A method to generate random binary numbers with n-digits (hint: for the most significant digit, you have no choice, it will be 1; similarly, for the least significant digit there is no choice, it will have to be 1; for all other position, generate 0 or 1 at random)

2. A method to compute modular exponentiation. It will require that you also implement the algorithm for modular addition and multiplication.

3. A method to test primality. Since the numbers you will be testing are randomly generated, use the first algorithm we discussed with a single test 3 N−1 ≡ 1(mod N)

Test your algorithm with randomly generated 16-bit numbers. Specifically, use it to generate 100 numbers (presumably prime), and check how many of them are primes by a brute-force approach of trying all divisors up to the square root of the number; you will be able to use regular integer arithmetic to do it). How many times did your algorithm come back with a wrong answer? Should that surprise you or is it consistent with what we discussed in class?

Use your algorithm to generate prime numbers with 16, 32, 64 and 128 bits. In each case, report the number of randomly generated numbers before the prime was found. What should it be in theory? Are your results consistent with the theory?

Answer 1

#include<iostream>

using namespace std;

bool isPrime(int n){
   for (int i=2; i< n; i++)
   {
       if (n % i == 0)
       {
           return false;
       }
   }
   return true;
}

int main(){
   int n;
   cout<<"Enter number:"<<endl;
   cin>>n;
   int i = 0;
   while( !isPrime(n+i)){
       i++;
   }
   cout<<n+i;
}