It’s really, really hard to find the factors of a semi-prime, the product of two prime numbers. That is, it’s easy to multiply two primes together but hard to reverse engineer, such as you need to do when you hack encryption keys. Computers can start trying to compute the factors of a large semi-prime, but it will take them a long time—”thousands of computers millions of years” for the types of semi-primes we’re talking about. Factorable factors like 20000 x 350400, easy. Primes as factors, like 547 x 953, computationally too intensive for hackers, even with the latest hardware. So the semi-prime becomes the public key and its factors the private keys.
So the factor function uses nested loops to compute the factors of a given number, and it uses the time module to figure out how long each computation takes from start to finish. There are better ways to do this function, like with reduce code or using set to remove x/y y/x dupes, but it works and it’s legible. The bottom part tests the function by supplying semi-primes (via multiplication, so factor(229*101) is equivalent to factor(23129) because of the rules of precedence) and other numbers, and prints the resulting times.
Check it out! (I put the results below.) When you start getting into the semi-primes, it can thousands of times longer to factor, and these are low numbers. I commented out the 487*691 and 997*991 tests because they wouldn’t complete after like 10 minutes!
It’s so great to see mathematical principles applied in this way, to see the simple origins of complex systems like cryptography, and to noodle with code to get how things are working.