Answer 5
> Can you really? How thick a stack of paper would it take to print it out?
Using a reasonable font size, and estimates of 80 columns and 56 rows, and two-sided printing, 1449 pages.
> It's much easier to verify whether a given number is prime, than it is to find a prime in the first place.
Actually, finding primes isn't too hard.
The probability of a number around 10^1000 (~= 2^3322, so a very realistic size) being prime is around 1 / ln(10^1000) == 1 / (1000 * ln(10)) == 1 / 2302.585... (see
http://en.wikipedia.org/wiki/Prime_number_theorem ) and that's counting numbers with tiny divisors like 2, 3, 5. It gets better, because it takes only one failed probabilistic primality test to
exclude a number from consideration (see
http://en.wikipedia.org/wiki/Primality_test ). After narrowing down the candidates, then you can throw a bunch of probabilistic primality tests at a survivor (this is "good enough" for encryption), or a deterministic test if you want that (the probabilistic
tests beforehand are cheap in comparison).
> That's why people concentrate on numbers of a special form, which are analytically
> shown to be much more likely to be prime than a number of comparable magnitude just picked at random.
Actually, Mersenne numbers are special because they have an exceedingly fast deterministic primality test (the fastest one known).
I don't know if Mersenne numbers can be said to be "much more likely" to be prime than ordinary numbers (this is beyond my amateur mathematical ability). Let's play around with C++:
C:\Temp>type primes.cpp
#include <math.h>
#include <iostream>
#include <ostream>
usingnamespace std;
bool prime(constint n) {
if (n < 2) {
returnfalse;
}
for (int i = 2; i <= n / i; ++i) {
if (n % i == 0) {
returnfalse;
}
}
returntrue;
};
int main() {
double total_prime_exponents = 0.0;
double total_all_exponents = 0.0;
for (int i = 2; i <= 43112609; ++i) {
constdouble d = i < 31 ? log((1 << i) - 1.0) : i * log(2.0);
if (prime(i)) {
total_prime_exponents += 1 / d;
}
total_all_exponents += 1 / d;
}
cout << "total_prime_exponents: " << total_prime_exponents << endl;
cout << " total_all_exponents: " << total_all_exponents << endl;
}
C:\Temp>cl /EHsc /nologo /W4 /MT /O2 /GL primes.cpp
primes.cpp
Generating code
Finished generating code
C:\Temp>primes
total_prime_exponents: 4.73798
total_all_exponents: 24.9863
Looking at only those Mersenne numbers with prime exponents, the Prime Number Theorem says we should expect about 5 of them to be prime, when in fact 47 of them in this range are known to be prime (there may be more). It certainly appears that by exploiting
an easy-to-prove fact about Mersenne numbers (for 2^N - 1 to be prime, N must be prime) and by performing a tiny amount of work (testing N for primality), the remaining Mersenne numbers with prime exponents are about 10 times more likely to be prime than numbers
chosen at random.
Without exploiting that fact, Mersenne numbers in general don't appear to be "especially prime". The ultra-trivial fact about them is that they're all odd, and the chance of a random odd number being prime is double the chance of any random number being
prime, so the Prime Number Theorem tells us to expect about 50 primes in this range, and we've found 47.
(Ooh, conjecture! It would be awesome if there were exactly 3 currently-unknown Mersenne primes with exponents between 20,996,011 and 43,112,609.)
That was fun.
> Sieve of Eratosthenes is an algorithm for finding primes,
> and is largely a toy, impractical beyond some, rather low, threshold.
Of course.