Discussion about this post

User's avatar
Martini Glambassador's avatar

I’m grateful all you crazy, lovely mofos are here, commenting and posting and sometimes writing advice columns and being my online friends. The absolute absurdity of the world is easier to contemplate with your rainbow coloring lighting up the corners.

Expand full comment
Crip Dyke's avatar

Okay, now let's talk about factoring to identify prime numbers. Let's use the numbers 121 and 137 for our test cases. If you have just a few prime numbers memorized, we can do this easily, but even if you don't, we can quickly find those first few numbers that allow us to get started.

0 and 1 are by definition not prime numbers. A prime number has exactly 2 factors: 1 and itself.

If you divide 2 by 2 you get 2, and if you divide it by 1 you get 2 and there are no other numbers as small as 2 or smaller to test, so ... VOILA, 2 is a prime number. Let's check 3.

If you divide 3 by 3 you get 1 if you divide it by 2 you get 1.5 which is not a whole number so it doesn't count at all, and then if you divide it by 1 you get 3. VOILA, 3 is a prime number.

If you divide 4 by 4 you get 1 and by 1 you get 4, and this is obviously true for every number so in the future we can skip that part. So now we just need to check the numbers between 1 and 4 to see if any of them are factors. Unfortunately for 4, you can divide it by 2 and get a whole number (another 2) which. means that 4 is not prime. In fact, no even number is prime except for 2 itself, because all the higher even numbers are divisible by 2.

While easily checking the rest of the odd numbers between 1 and 20 we find the primes are 2, 3, 5, 7, 11, 13, 17, and 19.

So to determine whether 121 and 137 are primes, we ONLY have to divide them by previously established prime numbers. Why? Well because if they're divisible by a number that's not prime they are ALSO divisible by at least one prime number (The number 16 is divisible by 4, which is not prime, but also by 2, which is a prime factor of 4).

121/2 = something.5, because 117 is odd, so 2 is not a factor. We'll skip 2 in the future when we're dealing with odd numbers, though computers won't, since they don't glance at a number and determine it is even. They have to do the math to see that it's even.

121/3 = 40.3333... Okay, not divisible by 3

121/5 = 6.2 ... not a prime factor

121/7 = 15.8something

121/11 = 11 Oh, hey! Eleven is a prime factor of 121. In fact it's the only prime factor, because 121 = 11 squared! So 121 is not prime.

So that's the basic process, but it's all so brute force b/c you have to continue until you find a prime factor or until you reach the number you're factoring, right?

Well... not exactly.

137/2 doesn't work, and 2 is not a factor. But **because** 2 is not a factor, that tells us something. That tells us that the largest number that could be a factor of 137 has to be less than 1/2 of 137. Think about it. Is 130 going to divide evenly into 137? Nope. Nothing less than itself but more than 1/2 of itself can be a prime factor specifically because there's no other prime to multiple it by that is more than 1 but less than 2.

So okay, but not generalize this --

137/3 = 45.66666 so 3 is not a factor, but that also means that the highest thing that could be a factor must be less than 1/3rd of 137, which we just figured out was 45.66...

Since only whole numbers can be factors, we've already limited not just 2 and 3, but also every number above 45.

keep going.

137/5 = 27.4

So 5 is not a prime factor, and also no number higher than 27 is a prime factor.

137/7 = 19.57ish

So 7 is not a prime factor, nor is any number over 19.

You can see now how the upper bound drops radically, right?

137/11 = 12.44ish

So now we've eliminated 11, but we've also eliminated every number larger than 12. This is easily verified by multiplying the next prime (which is 13) by itself. The product is 169, which is more than 137. So there's nothing we could multiple 13 by to get 137 that isn't smaller than 13, and we've already checked everything smaller.

Since there are no numbers greater than 11 that are prime unless they are also greater than 12, we're done.

So it started out looking like we were going to have to check every number from 1 to 137, but in the end we did some quicker calculations to find the early primes under 20, and then checked some of those, not even all of them, to determine that 137 has no prime factors that are not itself. Therefore it only has the factors 137 and itself. Therefore 137 is prime.

Cool beans, huh? So now you know that when checking a number to see if it's prime, you can stop as soon as you hit a prime that, when squared, produces a number higher than the one you're checking for primeness.

Since 20 squared is 400, for numbers below 400 you'll never have to check them against more prime factors than just the ones below 20, so our 2, 3, 5, 7, 11, 13, 17, and 19 which we started out with.

You can use other winnowing tricks to find primes more quickly than most people expect, but the work of finding primes still quickly becomes pretty huge.

Remember after all that if you divide a 24 digit number in 2, you still have a 23 or 24 digit number. And if you want to find the smallest number that, when squared, is larger than your 24 digit number, you're still looking for a 12 digit number.

And sure looking for 1 in 10 ^ 12 is a lot less work than looking for 1 in 10 ^ 24, but it's still a TON of work.

And this is why, to this day, you've got computers working every second on nothing but finding the next prime, so that codebreakers at the NSA and other places can use a database of only-primes in their decrypt attempts. (And also so that banks can use the highest valued prime numbers we know to multiply together to get new decrypt-keys.)

Expand full comment
575 more comments...

No posts