I was watching a video by the excellent YouTube channel 3Blue1Brown and they claimed calculating all possibilities of 2^256 would take many, many, many times the age of the universe even with many galaxies filled with computers to calculate.
Yet we can know primes up to 2^136,279,841 -1?
How can we calculate such monstrously big primes yet be unable to do 2^256?
I am missing something here.
You’re confusing two different things. Verifying the property of a single number that’s extremely large vs checking every single number up to a large number. I can tell you confidently that 555[1 googol more 5s]555 is both odd and divisible by 5 without having to check any of the numbers in between.
But don’t they need to check every number to see if it is a prime? I guess they can cut half out for being even but that still leaves a lot of numbers to check.
Put another way, it is one thing to verify a number is prime and a much harder task to find the next biggest prime.
Nope:
Also, the primes found are a special form known as Mersennes Primes. We don’t know every prime below that number, just that this number is a prime.
This is true, but as mentioned, but finding 2^{136279841} - 1 wasn’t finding the next prime, but the next Mersenne prime, which are 2^p - 1 where p is prime. Determining if these are prime is easier (the above mentioned Lucas - Lehmer test)
Brian
A bit more about primality tests: There are two types, probabilistic tests and definite tests. The probabilistic tests aren’t completely certain to be accurate, but the chance of them being inaccurate is so ludicrously low that you could spend the entire lifetime of the Universe testing numbers and never once get a false positive. There are also tests that don’t rely on probability at all, and which are still a lot more efficient than testing every possible divisor, but much less efficient than the probabilistic ones, so in practice, they’re hardly ever used.
Also, even for very large numbers like the ones used for cryptography, primes are common enough that the method for generating primes is usually just to generate a random number, test to see if it’s prime, and if not, try another number and repeat.
As noted, knowing that a particular number is prime is not the same thing as knowing all the primes up to that number. I think you would be correct to be incredulous of a claim that we know all the primes up to 2^136,279,841 -1.
So now I’m wondering if there’s a largest number n such that we know all the primes up to n.
One nice thing about the Lucas–Lehmer primality test is that your are doing a ton of mods 2^(huge number) - 1. This is really easy on good old binary computers. There are tests for primality that require mods that aren’t so fast. (One of them even produced a record prime decades ago.) Now the numbers are so large that LL is the champion method.
But the multiplications are the big time chewers.
BTW, there might be other Mersenne primes smaller than the largest known one. The distributed testing doesn’t ensure all candidates are tested in order. A while ago, some people were making guesses as to more likely candidates and tested just those leaving big gaps of untested candidates.
I’m not sure “know” is exactly the right word. This site Home claims that there are 50,847,534 primes of nine digits, so presumably a count was made at some point; whether it’s maintained as a standing database I don’t know. The site offers to calculate the first two hundred primes following any twelve-digit number; at some point it becomes a question of whether keeping a list or recalculating a given example on the fly requires more resources.
Tomás Oliveira e Silva has calculated all primes up to 4*10^18 (or, rather, prime gaps but that means knowing one prime and the next prime after it so…all prime numbers below some limit). I am not sure how long ago that claim was made though and it may be more today.
Our prime gap computations are a by-product of our Goldbach conjecture verification effort [5]. We have computed the gaps between all prime numbers smaller than 4·10^18, and, so far, double-checked our results up to 4·10^17 - SOURCE
I am not sure is meant that we cannot calculate 2^{256}. It is only about 78 digits long and I’m sure it can be calculated readily. It would take a while, but I believe I could do it by hand. I really have no idea what that statement means. Back in 1984, I saw a display of the actual decimal expansion of what was then the largest known Mersenne prime.
There have been roughly 10^60 planck times since the start of the universe and 2^256 is roughly 10^77 so even if you started counting at 1 and counted up 1 every planck time, you wouldn’t reach 10^77 before the heat death of the universe.
Wolfram Alpha computed it out pretty much instantaneously.
Apparently, the result is 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936
According to this page no such list of consecutive primes exists. The reason is that (relatively) small primes are easy to find. Any such list would be simple to augment.
I worded the title/OP poorly. It is in the video I linked which is about running through all combinations of something that has 2^{256} possibilities and not just calculating that one number. As @Shalmanese noted, there has not been enough time in the universe to do this.
I assumed (incorrectly it seems) that mathematicians were finding one prime number, and then the next after that one, and the next one after that and so on. So, I wondered how they ever found one so big but it seems there are loads of smaller primes they have not found yet.
Ever wondered which is the smallest prime number we don’t know yet, and which one is the smallest we will never know?
I have not but the link @Petek gave just above says it has been considered:
It is often wondered what is the longest list of consecutive primes, starting at two, that has ever been found? Sometimes it is asked in a different manner: “what is the smallest number n such that it is not known whether or not n is prime?” (Of course there are infinitely many primes, so there is no theoretical limit to the length of such a list.)
Not sure how to answer the second bit of your question. I assume that is a moving target.
It was tongue in cheek, sorry I did not make it clear.
That’s factorial 2^{256}, or 2^{256}!, which is an entirely different proposition.