A program to factorize a large multiple of two prime numbers
Philip Brunet and Max Ranes
Your final project will be writing code optimized for parallel organizations and architectures. Your team of two will compete against three other teams in a final showdown at the end of the semester. You will also present your code to the class.
Your choice is between writing for OpenMP or MPI. We practiced writing parallelized code in C; if you are more comfortable, you may also write this code in Fortran or Python.
You will do your code development on your iMacs and home computers. However, for the student competition, some of you will be given access to even better hardware.
If you use OpenMP, you will given access to a multicore machine of 12 processors or better for the student competition.
If you use MPI, you will be given access to a cluster of at least 2 nodes of 8 processors or more for the student competition. That is, you will have access to more processors than those using OpenMP, but the memory will not be shared between all processors.
Crack a public/private key pair. After reading this forum answer (https://stackoverflow.com/questions/439870/why-are-primes-important-in-cryptography) describing the importance of prime numbers in cryptography, write a parallel program to factorize a large multiple of two prime numbers. The program should take an large number as input, and output its two prime factors. Your code submission will be graded by me on code clarity through comments, choice of method, and functionality. For the student competition, you will be given several large numbers to factor (all numbers will be < 2^32). First team to accurately factor all of the numbers (or to factor the most prime numbers) wins.