Factors Found in 200-Digit RSA Challenge

diodesign writes "The two unique prime factors of a 200-digit number have been discovered by researchers at Bonn University (Germany) and the CWI (Netherlands). The number is the largest integer yet factored with a general purpose algorithm and was one of a series of such numbers issued as a challenge by security company RSA security in March 1991 in order to track the real-world difficulty of factoring such numbers, used in the public-key encryption algorithm RSA. RSA-200 beats the previous record number 11281+1 (176 digits, factored on May 2nd, 2005), and RSA-576 (174 digits, factored on December 3rd, 2003)."

Re:so?

[CodeBuster]

It means that an incrementally more efficient algorithm has been discovered which allows a slightly larger prime to be factored in a reasonable amount of time. However, this does not represent the sort of breakthrough algorithm that blows the problem wide open and allows factoring of arbitrarily large primes in time polynomial to the size of the input (the length of the prime number to be factored in this case). Thus, this new algorithm does not scale elegantly as one increases the size of the inputs and therefore it does not represent the general solution to the prime number factorization problem. Your public key crypto systems are safe if the prime numbers are large enough...for now.

Re:Notation?

[iMaple]

Does anyone know what the notation "11281+1" means?

It means 11282 :) .
There seems to be a typo in the article post (A typo on slashdaot .. thats news ..I mean just one typo thats cool). Its probably due to some filter. It should say 11^281 +1

it's 11^281+1

[Anonymous Coward]

Here's the factorization [loria.fr]

Re:55 CPU years

[TedCheshireAcad]

Another victory for the General Number Field Sieve (I think). The article was a little light on the details, but it mentioned they used a "general algorithm", which I'm assuming is the GNFS. The original paper [acm.org] may shed some light on the algorithm, for the algebraically inclined Slashdotter. (Link courtesty of Google Scholar [google.com])

Re:Algorithmic difficulty

[SlashThat]

At first glance, it looks like adding digits makes the factoring problem exponentially harder. The question is: what is the base of the exponent.

This is an interesting analysis, but unfortunately completely wrong. The thing is that the Number Field Sieve algorithm's complexity is sub- exponential in number length. (To be precise, it's O(exp(c*log(n)^(1/3)*loglog(n)^(2/3)+o(1))) ).

A naive analysis suggests that adding one binary digit makes the number twice as big and thus makes the factoring problem twice as hard.

Well ... no. No one ever claimed that, at least nobody familiar with the subject. It is easily seen not to be the case both from basic complexity analysis and experimental data. Again, the algorithm's complexity is not exponential.

That said, it doesn't seem that the factoring problem will become any easier, at least not before Quantum computers are built. The factoring problem is considered "the holy grail" of cryptography for 3 decades now, and there were hardly any advances in the last 15 years, despite the huge interest in the problem.

Verify yourself!

[graf0z]

To verify the factorization [crypto-world.com] just type

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

After deleting the spaces slashcode mysteriously puts in, you should get RSA-200 [wikipedia.org].

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

/graf0z.

Re:Infinite Improbability...

[VoidWraith]

Just the flowers. The whale was coming to terms with its newfound existence.