Hello everyone i need help with this code , i need it to be written in c++ , also i have attached a sample output on what it is supposed to look like when completeed. please help . and make it clear. Submission format: Submit your code plus 5 output samples into the RSA-key generation folder in Cocalc

To build an RSA crypto system, you first need to find two random primes. Your primes will consist of 7 bits. You will set the first and the last bits to be 1 and randomly choose one-by-one the internal 5 bits. We could have used only 7 bits to store it, but to simplify the program, store it as a standard 32 bit integer, so there will be 25 leading 0 bits. You may use any pseudorandom routine you like to generate random numbers. Very likely, your programming language has one. To generate a random bit, get a (pseudo-)random number, and extract the least significant bit to be your random bit. Print, for one of the random numbers you got, produce a trace showing how the 5 individual bits were obtained, so show your 5 random numbers and the extracted bit for each. You will use the variant of the Miller-Rabin algorithm (and not as it is generally presented) to test if your 7-bit number n is a prime. You will pick some random as, such that 0 < a < n. You can do it either by a process similar to getting a candidate prime above, or to simplify your program, you can just get a pseudorandom number and cut it down to size by computing its remainder modulo n, and discarding it if it is 0. If your number passes the Miller-Rabin test for 20 values of a, you may declare it as prime. For completeness, make sure that one of the ns turned out not to be a prime number. So, if you immediately find the prime numbers you need, pick any number you know not to be prime and perform the test on it. If the test says it is possibly a prime, look for another number that you know not to be a prime. Print, for one that turned out not to be prime and the a for which the answer was not prime, produce a trace. Print, for one n that turned out to be prime and one a for which the answer was perhaps prime, produce a trace. Now, given two primes p and q you found, you will get n = p q. Note that p and q should be different, so you need to check for this. In a real search for large number the probability that p = q is so small that there is no need to check for this, but as you are working with very small numbers, you need to check for that. Pick a small number to be the public key e. It has to be relatively prime with (n). To check if it is relatively prime and to find a multiplicative inverse to serve as the private key d, use the Extended Euclidean Algorithm, which you will code. If e is not relatively prime with (n), then find another small number. Do not do it randomly, start with 3 and go up until you find an appropriate e. In the extremely unlikely case (which would not happen in a real RSA implementation), that all the values of e you try do not work, just pick another pair of random primes and continue from there. And if the smallest e you find is big which here means bigger than (n) that is also fine for your project. Show how you used the algorithm on the various candidates for e until you got the right one. (If you are lucky, the first e you tried, workedthis is fine too.). Produce a trace for each e just as we had in class for the Extended Euclidean algorithm. For the value of e found, find the corresponding value of d and normalize it so that it is positive and smaller than (n). (If it happens that d = e, this will be fine too for your project, though of course not in a real RSA system.) Print, list, the value of d. So, the public key of Alice, is really the pair n, e and the private key of Alice is n, d; only she knows the latter, more precisely only she knows d. but you need to check for it in your implementation Print a line, list the following for Alice, both as integers and as sequences of bits: p,q,n,e,d.

The out put must be in a table showing is prime and etc.

PLEASE PUT IN C++ CODE. SO IT CAN COMPILE AND EXECUTE , THE LAST ONE I PUT UP I GOT THE ANSWER IN JAVA. PLEASE. The output should resemble a sparse table thank you so much.