As a computer programmer, you will need to know how to use algorithms and be able to come up with your own. Last week, we learned about public key cryptography and the RSA algorithm, and this week we are considering how fast algorithms can complete. These topics are combined in this discussion. In addition, you research and discuss Millennium Problems, specifically the P vs NP Problem which looks at the ability of algorithms to solve every problem quickly.

 

Respond to the following:

• The RSA algorithm hinges on the fact that factoring a very large integer into the product of two primes is an extremely time-consuming task. Why is factoring large integers a difficult action to perform?
• What happens to the RSA algorithm if someone comes up with a separate algorithm to factor large numbers quickly?
• In mathematics and computer science, there is an unsolved problem called the "P vs NP Problem" which essentially tries to determine if every problem has an algorithm to solve it in a small amount of time. Right now, we do not know of any algorithm that factors integers in a small amount of time, but that doesn't mean one doesn't exist! There are many other problems that fall into this category (i.e., that do not currently have an algorithm to solve them quickly). Researchers are trying to determine if there is such an algorithm or if one will never exist, and the P vs NP Problem is trying to determine if there are some problems that cannot be solved quickly or if every problem can. The P vs NP Problem is one of the prized Millennium Problems, each of which has a $1,000,000 prize to be awarded to the first solver by the Clay Mathematics Institute. These next questions will require you to do some digging.
• How many Millennium Problems are there?
• How many Millennium Problems have been solved since their inception in 2000?
• What would a solution to the P vs NP Problem mean for society?