"Largest Known Prime Number Discovered; Has 17,425,170 Digits" http://www.sciencedaily.com/releases/2013/02/130213225424.htm
If we can find prime numbers larger than 17 milion digits, why can't we find all 1024bit (just 309 decimal digits) primes?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Generally when you see stuff about largest primes, it's all Mersenne Primes, which don't really have anything to do with general purpose primality testing. And neither has anything to do with cracking RSA. $\endgroup$– AntimonyCommented Jun 24, 2013 at 3:44
-
22$\begingroup$ You are able to tell me a 100 digit number. So why can't you tell me all 9 digit numbers? $\endgroup$– CodesInChaosCommented Jun 24, 2013 at 6:22
-
$\begingroup$ There are specific methods to prove the primality of x if all prime factors of x-1 or x+1 are known. That condition is very important. For example we know all prime factors of 2^k even if k is huge, and that helps to check if 2^k +/- 1 are prime. There is no way on earth to find just the prime numbers from x-1,000,000 to x+1,000,000 for your large prime above. All 1024 bit primes - that's impossible because there are just too many! $\endgroup$– gnasher729Commented Sep 19, 2022 at 13:40
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
Due to the prime number theorem the number of primes with length $2^{1024}$ is approximately
$$\pi(2^{1024}) - \pi(2^{1023})\approx \frac{2^{1024}}{\ln(2^{1024})}- \frac{2^{1023}}{\ln(2^{1023})} \approx \frac{2^{{1024}}}{709.8} - \frac{2^{1023}}{709.1}\approx 2^{1013.5}$$
The number of atoms in the universe is approximately $10^{80} \approx 2^{265.75}$, which means...
Edit, fixing math:
... you would have to fit just around $2^{748} (\approx 2^{1013.5 - 265.75})$ prime numbers in every single atom in the universe in order to store this list.
To further break this down: Assume you could program atoms to output 1 prime at a time for 1 attosecond (shortest measured time, $2^{-18}s$), you would still need $2^{663.1}$ years, and it's been "only" $2^{33.7}$ years since the Big Bang.
Short: It's far, far beyond the anything ever achievable. And this is not due to our technical limitations, it's just not possible in existence.
-
$\begingroup$ How about subatomic particles from CERN? And dark matter?' It turns out that roughly 68% of the Universe is dark energy. Dark matter makes up about 27%. The rest - everything on Earth, everything ever observed with all of our instruments, all normal matter - adds up to less than 5% of the Universe. ' $\endgroup$ Commented Jun 24, 2013 at 10:20
-
7$\begingroup$ @user129789 Those numbers are so huge that no amount of optimization can make this approach feasible. Literally, you would need to store around $2^{750}$ primes into a single atom, which is an unimaginably large number, and for all intents and purposes infinite. Tylo, your calculation is wrong, by the way, that should be $2^{1013.5 - 265.75}$ (just about 744 orders of magnitude off :p) $\endgroup$– ThomasCommented Jun 24, 2013 at 10:46
-
2$\begingroup$ @user129789 If you find some way to store prime number information in dark matter, we can start recalculating. $\endgroup$ Commented Jun 24, 2013 at 11:25
-
1$\begingroup$ Thanks Thomas, I corrected the math and added a tiny bit more. $\endgroup$– tyloCommented Jun 24, 2013 at 12:31
-
1$\begingroup$ That is because there are more efficient algorithms for factoring than trying out every possible prime as factor. But that was not the point in this question. $\endgroup$– tyloCommented Aug 30, 2013 at 13:27
$\begingroup$
$\endgroup$
12
The Prime Number Theorem is a way to estimate the number of primes less than or equal to a given number. It basically says that for a given $x$, the number of primes $\le x$ is bounded by $$\frac{x}{\ln{x}}$$ For $2^{1024}$ this is a very large number. It's also worth noting that this would be essentially useless for cracking RSA because RSA moduli are semiprimes, not primes. They're products of two large prime numbers, so really you'd have to compute the products of all pairs of primes $\le x$, which is $$\frac{(2^{1024})(2^{1024} - 1)}{2}$$ Also a very large number.
Even if some crazy billionaire or the NSA did this, all you'd have to do is use 4096-bit keys. Public-key crypto would get a bit slower but generating all those numbers again would take exponentially more effort.
-
$\begingroup$ 'RSA moduli are pseudoprimes, not primes.' <-- so??? You still need to compute 2 2^1024 primes? $\endgroup$ Commented Jun 24, 2013 at 1:36
-
$\begingroup$ @user129789 Even if we assumed that you could calculate all those $2^{1024}$ primes - never mind all their products pairwise, to make a huge lookup table - instantly (that is ludicrous but let us imagine). How much space would you need to store them all (1024 bits per prime)? $\endgroup$– ThomasCommented Jun 24, 2013 at 1:44
-
3$\begingroup$ This is a nonstandard use of the term "pseudoprime". The standard meaning is "a composite number that satisfies some relation that is true of all prime numbers, and false for most composites", the most common one being $2^{p-1} \equiv 1 \mod p$ $\endgroup$– ponchoCommented Jun 24, 2013 at 2:51
-
1
-
$\begingroup$ Ah yeah, sorry folks. I knew it was either pseudoprime or semiprime, and I chose the wrong one >.< Editing it now. $\endgroup$– pg1989Commented Jun 24, 2013 at 4:52