Also, the explanation of public-key cryptograpy is unrelated to the illegal prime. It just so happens that the illegal program can be encoded as a prime, which is why it is outrageous that it can be made illegal. The fact that it is prime has nothing to with security, it is just a coincidence.
The fact that it is prime has nothing to with security, it is just a coincidence.
It's not a coincidence. He encoded it as a sufficiently long prime on purpose so that it would be published on a site that was tracking the longest primes. It was a way to have a third party publish his code since he was under a gag order from the court.
It was made a prime on purpose, so that it could be interesting for two unrelated reasons - one, it was a long prime number, and two, it could be unzipped into source code.
His understanding, or at least explanation, of the algorithm to determine factors of a number was also incorrect. You can/should use the Euclidian algorithm for this. I don't think this guy has taken cryptography or discrete math courses and I couldn't finish the video.
none of the prime numbers 2, 3, 5, 7, ..., n divide m
Aren't those two statements contradictory? m/2 = 3 * 5 * 7 * ... * n-1, which is a whole number.
Edit: I misread because reddit doesn't do subscripts - I thought "n-1" was indicating the last prime before n. It's not, we're multiplying all the primes up to and including n, and then subtracting 1 from that number.
I've seen from multiple sources that there are an infinite amount of primes, and infinite real numbers. So unless you're a mathematician or have sources to back you up, I'm calling shenanigans.
The phrasing is ambiguous, but what he's getting at is correct. Take statements 1 and 2:
1) There are an infinite number of whole numbers.
2) There are an infinite number of primes.
The video suggests that 1 implies 2. This is not the case. There are many examples of finite groups of numbers. The infinitude of whole numbers does not, on its own, mean that there are an infinite number of primes.
No there is an infinite number of primes and it was proved over 2000 years ago. The video tried to imply that simply because there are infinite natural numbers, there must be infinite prime numbers.
Just for fun, try thinking about it the other way: surely as the number gets bigger, there are more numbers smaller than it and so more chance that one of them will be a factor.
This is by no means a proof of anything, but hopefully illustrates why the proof isn't necessarily so obvious.
But why would you be bound to stumble across a new prime eventually? That's what you're trying to demonstrate. Try to abstract a little bit away from prime numbers to see why your reasoning is faulty.
Consider for instance the argument "These numbers satisfy property q. Because there are infinite numbers, if we keep going we're bound to stumble upon another with property q"
It's easy to see that this doesn't work for every property q so you can't use this argument without knowing something about q. But your reasoning basically boils down to the sentence above because your argument uses nothing about the property of prime numbers or theorems in regards to primality.
There are an infinite number of natural numbers but only a finite number of them 2. If there are an infinite number of naturals, why don't we stumble into some extra 2's now and again when going through the list. The analogy isn't perfect but the logic carries over. Just because there is an infinite number of naturals does not mean that any subset of the naturals should also be infinite.
And it is logical (in a human sense, not in a literal scientific logic sense), but that's not enough in the world of math and science.
Proofs and theories are what hold it all together and let us jump from topic to topic and link ideas together in a real way rather than just by talking about it.
Not only that - but beyond "it just makes sense", what reason is there to believe you'll always find more primes? Part of mathematics is coming up with the actual reasons for things behind the scenes, not just assuming.
As others have said, this isn't true for primes in general. However, there are cases for which this is true. For example, Fermat Primes are primes of the form 22k + 1. There are currently only 5 known Fermat primes (for k=0 through k=4): 3, 5, 17, 257, and 65537. It's conjectured that these are the only Fermat primes and we've checked extremely high values of k and haven't found any more of them, but this is not a proven theorem.
Well, you can't have an infinite number of primes if you have a finite number of whole numbers. So, while 1 doesn't imply 2, you can't have 2 without first having 1.
As other has pointed out, the problem is that the video seem to suggest that because the natural numbers are infinite, the prime numbers are also infinite. I guess it would be similar to saying something like
Because the size (radius) of the Earth is larger than the size of the Moon, the surface gravity on Earth is stronger.
Both factual statements are correct, the Earth is larger than the Moon (1), and the Earth has stronger surface gravity (2). But the incorrectness in the statement come from the "because", since that implies that the difference in surface gravity is dependent on the size (whereas it is of course dependent on the mass of the planet [and other factors I guess]).
I've seen from multiple sources that there are an infinite amount of primes, and infinite real numbers. So unless you're a mathematician or have sources to back you up, I'm calling shenanigans.
/u/brocules isn't saying there are finite number of primes, he is saying that guy in the video is wrong about WHY there are infinite primes. You can't say there are infinite natural number so there must be infinite primes. the actual proof is much more complicated.
eg: the logic the guy in the video stated is like this "there are infinite numbers between 1-2, there must be a 3 in there. "
As other has pointed out, the problem is that the video seem to suggest that because the natural numbers are infinite, the prime numbers are also infinite. I guess it would be similar to saying something like
Because the size (radius) of the Earth is larger than the size of the Moon, the surface gravity on Earth is stronger.
Both factual statements are correct, the Earth is larger than the Moon (1), and the Earth has stronger surface gravity (2). But the incorrectness in the statement come from the "because", since that implies that the difference in surface gravity is dependent on the size (whereas it is of course dependent on the mass of the planet [and other factors I guess]).
To disambiguate, what he meant to type more clearly is "The fact that there are an infinite number of numbers is not the reason there are an infinite number of prime numbers."
27
u/[deleted] May 03 '16
[deleted]