# 2^256 possibilities is impossible to calculate but we can calculate prime numbers to 2^136,279,841 -1? **URL:** \ **Category:** Factual Questions\ **Created:** [February 15, 2025, 10:13am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348 "2025-02-15T10:13:41Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\ **Post date:** [February 15, 2025, 10:13am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/1 "2025-02-15T10:13:41Z")
I was [watching a video by the excellent YouTube channel 3Blue1Brown](https://youtu.be/S9JGmA5_unY) 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?](https://boards.straightdope.com/t/new-largest-prime-number/1009144) How can we calculate such monstrously big primes yet be unable to do 2^256? I am missing something here. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [February 15, 2025, 10:23am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/2 "2025-02-15T10:23:09Z")
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. ---
**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\ **Post date:** [February 15, 2025, 10:26am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/3 "2025-02-15T10:26:55Z")
> [@Shalmanese](#): > > Verifying the property of a single number that’s extremely large vs checking every single number up to a large number. 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. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [February 15, 2025, 10:55am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/4 "2025-02-15T10:55:32Z")
> [@Whack-a-Mole](#): > > But don’t they need to check every number to see if it is a prime? Nope: > **[Primality test](https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests)** > > A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number ... > **[Lucas–Lehmer primality test](https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test)** > > In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930. > The Lucas–Lehmer test works as follows. Let Mp = 2p − 1 be the Mersenne number to test with p an odd prime. The primality of p can be efficiently checked with a simple algorithm like trial division since p is exponentially smaller than Mp. Define a sequence > > > > { > > ... 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. ---
**Author:** ![N9IWP](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/n9iwp/32/3154_2.png) [@N9IWP](https://boards.straightdope.com/u/N9IWP)\ **Post date:** [February 15, 2025, 12:51pm UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/5 "2025-02-15T12:51:20Z")
> [@Whack-a-Mole](#): > > (snip) > Put another way, it is one thing to verify a number is prime and a much harder task to find the next biggest 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 ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [February 15, 2025, 2:26pm UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/6 "2025-02-15T14:26:04Z")
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. ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [February 15, 2025, 2:51pm UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/7 "2025-02-15T14:51:15Z")
> [@Whack-a-Mole](#): > > Yet we can know primes [up to 2^136,279,841 -1?](https://boards.straightdope.com/t/new-largest-prime-number/1009144) 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. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [February 15, 2025, 4:14pm UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/8 "2025-02-15T16:14:18Z")
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. ---
**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\ **Post date:** [February 15, 2025, 4:41pm UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/9 "2025-02-15T16:41:59Z")
> [@Thudlow\_Boink](#): > > So now I’m wondering if there’s a largest number _n_ such that we know _all_ the primes up to n. I’m not sure “know” is exactly the right word. This site [Home](http://compoasso.free.fr/primelistweb/page/prime/accueil_en.php) 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. ---
**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\ **Post date:** [February 15, 2025, 7:15pm UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/10 "2025-02-15T19:15:39Z")
> [@Thudlow\_Boink](#): > > So now I’m wondering if there’s a largest number _n_ such that we know _all_ the primes up to n. 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](https://sweet.ua.pt/tos/goldbach.html) effort [[5]](https://sweet.ua.pt/tos/gaps.html#r5). 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](https://sweet.ua.pt/tos/gaps.html) ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [February 16, 2025, 12:03am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/11 "2025-02-16T00:03:19Z")
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. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [February 16, 2025, 12:39am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/12 "2025-02-16T00:39:53Z")
> [@Hari\_Seldon](#): > > I really have no idea what that statement means. 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. ---
**Author:** ![gnoitall](https://avatars.discourse-cdn.com/v4/letter/g/bb73d2/32.png) [@gnoitall](https://boards.straightdope.com/u/gnoitall)\ **Post date:** [February 16, 2025, 4:02am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/13 "2025-02-16T04:02:19Z")
> [@Hari\_Seldon](#): > > 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. Wolfram Alpha computed it out pretty much instantaneously. > **[Power\[2,256\] - Wolfram|Alpha](https://www.wolframalpha.com/input?i2d=true&i=Power%5B2%2C256%5D)** > > Wolfram|Alpha brings expert-level knowledge and capabilities to the broadest possible range of people—spanning all professions and education levels. 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 ---
**Author:** ![Nars\_Glinley](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/nars_glinley/32/8177_2.png) [@Nars\_Glinley](https://boards.straightdope.com/u/Nars_Glinley)\ **Post date:** [February 16, 2025, 4:55am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/14 "2025-02-16T04:55:53Z")
[Recent thread involving cryptography and selection of prime numbers.](https://boards.straightdope.com/t/how-do-encryption-algorithms-pick-prime-numbers/1007315) ---
**Author:** ![Petek](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/petek/32/1590_2.png) [@Petek](https://boards.straightdope.com/u/Petek)\ **Post date:** [February 16, 2025, 8:59am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/15 "2025-02-16T08:59:50Z")
> [@](#): > > So now I’m wondering if there’s a largest number _n_ such that we know _all_ the primes up to n. According to [this page](https://t5k.org/notes/faq/LongestList.html) 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. ---
**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\ **Post date:** [February 16, 2025, 9:06am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/16 "2025-02-16T09:06:41Z")
> [@Hari\_Seldon](#): > > I am not sure is meant that we cannot calculate 2^{256}. 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. ---
**Author:** ![Pardel-Lux](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pardel-lux/32/20182_2.png) [@Pardel-Lux](https://boards.straightdope.com/u/Pardel-Lux)\ **Post date:** [February 16, 2025, 9:22am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/17 "2025-02-16T09:22:40Z")
> [@Whack-a-Mole](#): > > 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? ---
**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\ **Post date:** [February 16, 2025, 9:37am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/18 "2025-02-16T09:37:16Z")
> [@Pardel-Lux](#): > > Ever wondered which is the smallest prime number we don’t know yet… 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. ---
**Author:** ![Pardel-Lux](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pardel-lux/32/20182_2.png) [@Pardel-Lux](https://boards.straightdope.com/u/Pardel-Lux)\ **Post date:** [February 16, 2025, 10:56am UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/19 "2025-02-16T10:56:04Z")
> [@Whack-a-Mole](#): > > Not sure how to answer the second bit of your question. It was tongue in cheek, sorry I did not make it clear. ---
**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\ **Post date:** [February 16, 2025, 3:31pm UTC](https://boards.straightdope.com/t/2-256-possibilities-is-impossible-to-calculate-but-we-can-calculate-prime-numbers-to-2-136-279-841-1/1014348/20 "2025-02-16T15:31:45Z")
> [@Whack-a-Mole](#): > > all combinations of something that has 2^{256} possibilities and not just calculating that one number. That’s **factorial** 2^{256}, or 2^{256}!, which is an entirely different proposition.