By: Cyril Rikh
In fifth grade, many students were taught how to calculate the greatest common divisor (GCD) using prime factorization. This method involves factoring a number until only prime numbers remain.
For example, twenty can be factored into four times five. Four is not prime, so we factor the four into two times two (two is a prime number). So, the prime factorization of twenty is two times two times five. To find the GCD, we do this for two numbers and then make pairs of common factors. Then, we multiply those common factors together, and the result is the GCD. For example, if we took ten, the prime factorization is two times five. The numbers common with twenty are two and five. Two times five is ten, meaning the greatest common divisor of twenty and ten is ten.
Tedious, right? You probably skimmed or even skipped over the previous paragraph entirely. While valid, the math many learned back in fifth grade is not up to par with what students could do using more advanced techniques—namely, the Euclidean algorithm.
This paragraph goes into the technicalities of the algorithm. While it’s not necessary to read it word-for-word, try to see if you can notice any apparent differences between this method and prime factorization just by visually skimming. The algorithm takes the GCD of A and B as follows. First, if A = 0 or B = 0, the value of the non-zero letter is the GCD, and the user can stop. If the user doesn’t have the GCD, then set A = B * Q + R. Q is how many times B goes into A, and R is the remainder. Then, find the GCD of B and R, making A now equal to B and B now equal to R. The user would continue until a number in the pair they’re trying to take the GCD of is zero. For a concrete example, suppose A = 270 and B = 192. The first question is simple: how many times does B go into A? It’s 1. And the remainder is 78. From this, we can write 270 = 192 * 1 + 78. Then we set 192 as A and 78 as B. We can repeat this, finding 78 goes into 192 twice. So, we get 192 = 78 * 2 + 36. We continue this until A = 6 and B = 0. When B equals 0, that means the GCD is A, which in this case is 6.
You might have skipped the last paragraph, but that’s okay. Visually, the previous paragraph has many more equations and mathematical operations than the second paragraph. That fact makes it easy to implement the technique in the real world.
One way it’s implemented relates to RSA, an encryption algorithm used to transmit messages securely over the internet. Hackers can use the Euclidean algorithm to break the encryption as a result of the RSA architecture.
The RSA architecture involves public keys and private keys. A public key is like a lock that you put on a package and send. Only the receiver has the key (referred to as the private key) to open that lock and, therefore, the package. The public key is created by two random large prime numbers, p and q, and is equal to p times q, and the private key is created in a different process also involving p and q.
The security of RSA encryption comes from the fact that it’s hard, even for a computer, to factor a large number (such as 414863) into the product of two large primes. But, with the Euclidean algorithm, hackers don’t need to factor the number, like they would need to with prime factorization, to find the GCD, which can be used to break the lock. To break a public key, hackers might pick two random public keys online and then run a computer algorithm to find the GCD. If they find a GCD that’s not equal to one, they now have p for both public keys. Since the public key equals p times q, having p also gives them q. With p and q, hackers can re-create the private key and break the RSA encryption, successfully cracking both keys at once.
The Euclidean algorithm demonstrates that math builds on itself. More advanced methods of doing things are more efficient because they have the foundations baked in. While computers weren’t invented until 2100 years after Euclid’s findings, his—and those of other prominent mathematicians—still hold relevance in the world of computer science.
By taking math classes, you will be more equipped to turn ideas in your head into effective code on a computer. Let’s say you wanted your computer to identify a handwritten number. Your brain does it easily, so you may want to replicate how your brain does it. The commonly used technique for this is a neural network. The neural network relies on math. It turns the image into a matrix and uses various techniques from linear algebra and calculus to train its accuracy.
Math classes are tough. They’ll take a lot of staring at numbers. But they’ll increase your analytical skills and ability to make a computer do what you want. Many people fear we may lose control of technologies like AI, which could become dangerous. With math, maybe you could help solve the problem of controllable AI, helping society harness the technology safely. Maybe you’ll work at a research university or maybe as an AI engineer at Google. But wherever you go, your math background will stay with you and help you ensure technology works exactly how you want it to.