Probably every real programmer absorbed this decades ago in CS101. I learned it from an episode of NOVA I watched with my son last night, “The Rise of the Hackers“: The basis for most public/private key encryption, which we use for practically all internet data privacy these days, is a simple mathematical fact discovered (I think) by the RSA mathematicians:
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.
This fact seemed so irresistible and elegant to me (a teachable moment for my son! Something I could dust the old Python off for) that I got my laptop out and, as we watched the segment on quantum cryptography, created a little test program:
import time
def factor(sp):
start = time.time()
for p1 in range(1,sp):
for p2 in range(1, sp):
if p1 * p2 == sp:
print "factors:", p1, p2
print "time:", time.time() - start, '\n'
factor(15)
factor(15*71)
factor(229*101)
factor(307*89)
# factor(487*691)
# factor(997*991)
factor(900*200)
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.
""" factors: 3 5 factors: 5 3 time: 0.0390000343323 factors: 3 355 factors: 5 213 factors: 15 71 factors: 71 15 factors: 213 5 factors: 355 3 time: 0.213999986649 factors: 101 229 factors: 229 101 time: 65.7490000725 factors: 89 307 factors: 307 89 time: 81.3059999943 factors: 2 90000 factors: 3 60000 factors: 4 45000 factors: 5 36000 factors: 6 30000 factors: 8 22500 factors: 9 20000 factors: 10 18000 factors: 12 15000 factors: 15 etc etc """