Slashdot Mirror

The trouble isn't making an arbitrary number in the hopes that it's prime, it's in proving that it's prime. There are relatively simple methods to look for Mersenne primes, they just take constant time for crunch. For non-Mersenne primes, you'd have to crunch out every possible factor to prove that it's prime, a tedious process.

This is not even close to correct. Testing primality this way becomes impractical around 30-40 digits or so (depending a bit on how patient you are) and there are methods that are faster even with substantially smaller numbers than that.

First of all, there are probabalistic methods of testing primality that don't involve factoring. While probabalistic, these can be carried to an arbitrary level of accuracy quite quickly and easily. This is a typically done as a preliminary before more difficult methods are attempted at all.

Once you're convinced that a number is almost certain to be prime, there are quite a few methods of proving it's prime that are faster than brute force -- probably the oldest and best known is based on Fermat's Little Theorem. There's also something known as Wilson't theorem that can prove the same thing, but TTBOMK, this rarely has much practical application. If you're interested in more, you can find a fairly reasonable introduction a number of the better-known factoring methods and such here. You can find more links about factoring here.

I think your conclusion is correct. Big-Oh notation is not useful for direct conversion to raw performance numbers.

For a concrete example, consider my two functions A(N) and B(N). If I tell you that A(N) is O(N) and B(N) is O(logN), you'll probably eagerly pick B over A without even thinking, because it's faster in the limit. If I define A(N) is N and B(N) is 4096 * (logN/log2), then it's easy to verify that A(N) < B(N) for all numbers in the interval N = [2, 65535]. This is just a simple example. It gets even messier when we add multiple levels of exponentiation.

I'll also advise caution in selecting the base for your logarithms. Most papers I've found on GNFS quote base-e, while most computer scientists use base-2 exclusively for calculations. This raises the question of whether they really mean ln or whether they mean lg (the base-2 logarithm), which makes an enormous difference in the calculation, and it also makes most "back of the envelope" calcuations highly suspect. When we use hard numbers like those found on http://www.crypto-world.com/FactorRecords.html, we see that going from RSA-160 to RSA-200 (a 25% increase in input size) results in a change from 2.7 CPU years to 121 CPU years just for the GNFS step. That's a change of about 44.8x, yet the formula we're given for GNFS only predicts a change of 28.4x using base-e or about 19.3x using base-2. Clearly we're missing some information about the GNFS, and we need more data points to draw any kind of meaningful conclusion about its actual growth rate on real-world problems.

Anyway, for me the key takeaway is that GNFS is still "state of the art", and it's only approximately 2^cuberoot(N), which is still exponential in N. Although that's fast enough to scare some people about the security of RSA encryption, it's nowhere near tractable for large N. Wake me up when someone comes out with a factoring algorithm that runs in 2^polylog(N), or better yet: Poly(N). :-)

/me starts building an RSA-1000000 "just to be safe"

echo "3532461934402770121272604978198464368671197400197 6\
25023649303468776121253679423200058547956528088349 *\
79258699544783330333470858414800596877379758573642 \
19960734330341455767872818152135381409304740185467 " | bc

Btw: Not 11^281+1 itself (which has obviously >281 decimal digits) was the previous world record, but a 176-digit factor of 11^281+1 called "c176":

echo "8428398995380842661984668205419427509438600\
88703946121840940131686719691460399191375953 *\
11981208699381274324213719517435209389491006\
236671100986363096780488054684807819312870741" | bc

And, using perl and Math::BigInt, I did, and it checked out. Also useful is to verify that the number really was RSA200, as other anonymous Wiki-troll-edits were changing the number like a flickering flame.

And the source of the original Anon-Wiki edit was an email from the academic ring-leader, available on FactorRecords on FactorWorld.

IAAAM,

Bill N1VUX
I Am An Apostate Mathematician
I prostitute my math degree sorting ones from zeroes

And, using perl and Math::BigInt, I did, and it checked out. Also useful is to verify that the number really was RSA200, as other anonymous Wiki-troll-edits were changing the number like a flickering flame.

And the source of the original Anon-Wiki edit was an email from the academic ring-leader, available on FactorRecords on FactorWorld.

IAAAM,

Bill N1VUX
I Am An Apostate Mathematician
I prostitute my math degree sorting ones from zeroes

Many comments here assume that the time to factor a composite integer N is proprotional to N, which is, happily, quite incorrect. Even by trial division, you only have to test prime divisors <=sqrt(N), and there are many far more efficient factoring methods.

RSA Security Inc. has quite informative FAQs on this subject, for example The RSA Factoring Challenge FAQ or What are the best factoring methods in use today?

A good paper, "A Survey of Modern Integer Factorization Algorithms" by P.L.Montgomery, can be found at Crypto World. It is slightly math-inclined but definitvely a worthwhile read for anyone interested in the topic.

Now for the bad news: 2048 bits can't be done today. Even GNFS, the best algo in town, has only managed to factor a 512 bits RSA key (and a 158 decimal digit number, with a 576 bits RSA coming soon, though) but 2048 bits will be million times harder. Right now there's no way to factor that, if Microsoft has chosen the primes for the key even remotely securely. I'm sorry to say that but with present technology, this project is a waste of time.

Alex