10.2 Factoring
It is hard to do a web search and find ‘‘practical’’ applications of factoring integers. Many of the results say things like ‘‘factoring integers is a tool in for factoring polynomials,’’ and ‘‘factoring integers is useful for solving some differential equations.’’ These examples are fine, but it seems like math to do more math.
One area where factoring comes into play is cryptography. There are cryptographic protocols that involve not being able to easily factor large numbers, in order to keep your information safe while it travels across the Internet or is stored in databases.
In this section, we examine some of the mathematics of factoring and focus in on one famous algorithm. This is Shor’s algorithm, named after its discoverer, mathematician Peter Shor. It can factor large integers almost exponentially faster than classical methods given a sufficiently large and...
