Talk:Two hundred digit number factored

"The number is the largest integer yet factored..."

The number is the largest integer yet factored with a general purpose algorithm.

I disagree. Since most numbers are not the product of two primes, lots of general purpose algorithms (like trial division) will work on lots of larger numbers (eg, powers of two). No doubt, someone has done this in the past, and if not, I would be happy to do so right now. Also, we often test the primality of much larger numbers through probabilistic means, which amounts to factoring, since by discovering a number's primality we trivially learn its prime factorization. I don't know what else to say here; perhaps "largest challenge number"? Brighterorange 21:01, 10 May 2005 (UTC)

Good point, Orange. Maybe we could say "the largest semiprime integer"? (Semiprime means product of two primes.) "Largest challenge number" is safe, but maybe not the broadest claim we can make. I'll go with that for now. Feel free to improve it if you think of something better. Pingswept 21:09, 10 May 2005 (UTC)

Yep, thanks for spotting that (my only excuse is that I just lazily lifted the "The number is the largest integer yet factored with a general purpose algorithm" statement from here without engaging my brain at all...) Matt Crypto 21:43, 10 May 2005 (UTC)

Just say something like "the largest integer with no special form" in cases like this...

Frequently changed numbers

How many times have the numbers been changed on the article page? I think that number could be larger than the primes.

Factoring correct; Source Reference

The desired source-references are http://www.loria.fr/~zimmerma/records/rsa200 and http://www.loria.fr/~zimmerma/records/factor.html now linked from http://www.crypto-world.com/FactorRecords.html as http://www.crypto-world.com/announcements/rsa200.txt

A simple Perl script (using Math::BigInt) confirms that the product of the two factors exhibited is indeed RSA200 as shown. I can not at this time confirm the two factors are prime, but I would trust RSA to have verified that before the original challenge.

You can cite http://mathworld.wolfram.com/Semiprime.html for "SemiPrime", but that neologism does not please me, it should be reserved for http://mathworld.wolfram.com/SemiprimeIdeal.html .

The announcement claims "the largest integer factored with a general-purpose algorithm". The special cases where small factors are found quickly are excluded from this claim by the terminology "general-purpose algorithm".

If one does not like that, rather than say "semiprime", perhaps one could say "largest hard factorization" to avoid technical terminology that one does not understand or fears the reader will not understand.

IAAAM,

Bill / N1VUX I am an Apostate mathematician ... I work went over to the darkside of *Software*

Hi Bill,

Thanks for the double check. I think you're right about "general-purpose algorithm" excluding checking for small factors first, but perhaps "largest hard factorization" is better. Feel free to update the article with whatever you prefer. Pingswept 21:27, 10 May 2005 (UTC)

Pingswept, I'll leave to you regular editors to update the article.

FYI, I've posted the Perl confirm and reference at

http://use.perl.org/~n1vux/journal/24616

-- Bill / N1VUX 2005-05-10-2136Z ISO Standard Time

I still disagree that "general-purpose algorithm" excludes trial division. Trial division is correct for all numbers, and it's even fast for most numbers—it just has bad worst-case performance. I think that qualifies as "general-purpose". "Hard" is good with me. Brighterorange 21:50, 10 May 2005 (UTC)

BO, we're talking General Purpose Algorithm as a technical term, not as English. Yes, Trial Division is the *classical* algorithm. That may make it "general-purpose" solution to you, but that does NOT make it a "General Purpose Algorithm" in the technical sense. General-Purpose Algorithm as a technical term means suitable for ALL cases, not just some subset of cases where it works better than luck, and not that it's suitable for the case generally found by school children. It works fine in schoolrooms. However, it is hopeless in the general case, where factor size is bounded by the square-root of the product and the size of the product is in the range of interest to people who do this sort of thing. In the technical jargon of Factoring and Cryptography, an algorithm that only works with numbers that fit on your pocket caclulator is not considered General Purpose. If you don't Grok the difference between "hard" and "NP-Hard", please do not re-express an opinion on what CompSci/Math majors mean by "General Purpose Algorithm". -- Bill N1VUX 2005-05-10-2215Z ISO Time

Bill, take it easy. We're a news site, not Cryptologia. Orange is trying to help out, not deal out injustice to mathematics. Pingswept 22:24, 10 May 2005 (UTC)

Indeed, this is the Wiki News not the Wikipedia, where technical accuracy would be paramount. Unlike straight News or straight Science, Science News writing must walk a knife edge between technical accurarcy and readibility. For the record, "Trial Division" aka "Direct Search Factorization" is a "Special Purpose Algorithm", see for example http://www.absoluteastronomy.com/encyclopedia/i/in/integer_factorization.htm . -- Bill N1VUX 2005-05-11-1539Z ISO Time

Bill, thanks. I hope you'll excuse the cheesy "holy war" shot, but I felt compelled to give the equivalent Python code ;-) ...

a = 532461934402770121272604978198464368671197400197625023649303468776121253679423200058547956528088349
b = 7925869954478333033347085841480059687737975857364279258699544783330333470858414800596877379758573642
print a * b

Matt Crypto 21:48, 10 May 2005 (UTC)

Matt - Duplicate Verifications are good. But Wiki will wreck Guido's indents ! -- Bill N1VUX 2005-05-10-2215Z ISO Time

Why RSA-200, not RSA-640?

Why did the team not attempt to factor RSA-640, rather than RSA-200? After navigating the confusing shift of naming conventions, one can see that RSA-200 is actually 23 bits longer than RSA-640: it should be easier to factor. Moreover, RSA-640 carries a US$20,000 bounty for its factorisation, whereas RSA-200 has no reward associated with it (other than prestige). Matt Crypto 01:37, 11 May 2005 (UTC)

Yeah, I found that strange too... At first I thought thay maybe they had started factoring this before the rsa challenge numbers were available (which would be kind of strange since they were the ones who factored RSA-576), but I have now confirmed that that's not the case. RSA-576 was factored in December 3 2003 (according to the RSA page), and I found this in their announcement of the factorization of RSA-200: "We started sieving shortly before Christmas 2003....". A possibility would be that this number was easier to factor than RSA-640 would be, despite being bigger? I don't know much about GNFS, I know that one of the first phases is finding a polynomial which depends on the number and which quality determines how fast the factorization will be. What I don't know is if it's easier to find a good polynomial for some numbers than others (excluding numbers of a special form such as a*k^b+c, for which SNFS is applied with an easily derived polynomial).

Google Calculator result

I think it's pretty retarded that I don't have the ability to add this to the article. link --Alterego 17:57, 18 October 2005 (UTC)