Bernoulli(200) c204

[akruppa]

Hi all,

Barry Mazur and William Stein have inquired whether it were possible to obtain the factorization of the numerator of the 200th Bernoulli number. The factors 389, 691, and 5370056528687 are known, leaving a c204:

N = 345269032939215803146410928173696740406844815684239672101299206421451944591925694154456527606766236010874972724155570842527652727868776362959519620872735612200601036506871681124610986596878180738901486527

Mazur once incorrectly stated in an article that the cofactor were prime; Mazur and Stein are currently in the process of writing a book in which they would like to include the factorization of this not-quite-prime number.

A c204 is a factorization with chest hair, but I think RSALS could handle it. Would you be interested in this? Can someone take on the matrix?

[fivemack]

I don't believe RSALS can handle it, they're only geared up to use the 14e siever. This sounds like a good candidate for nfs@home, and they have the right sievers for it, but I think they're busy.

Order of a CPU-century to sieve and therefore a CPU-decade to do the polynomial selection (so a season on my 48-Opteron machine). I could do the matrix, it would take me about a season on 24 Opteron cores, but I suspect frmky has grids that could do it faster. How much ECM has been done on the cofactor?

I think this may well be too hairy a problem to be reasonable with what we've got here now; I'm not really prepared to commit two seasons (so the thick end of a thousand dollars in depreciation and electricity) for an aside even in a book by Mazur and Stein

[akruppa]

Yoyo is just about to finish a p65 test, see http://www.rechenkraft.net/yoyo/y_status_ecm.php

[fivemack]

I make that about a CPU-decade of ECM, so enough to want to proceed to polynomial selection. But msieve isn't quite plug-and-play for polynomial selection at this level yet (see the fuss that I'm going to in the http://www.mersenneforum.org/showthread.php?t=16369 and the fact that I haven't devoted more time to carrying on with the selection)

Maybe I'm just being pessimistic - I'm moving house and job in the upcoming season and probably shouldn't volunteer for a six-month committment. Though it's probably more valuable than extending yet more aliquot sequences, and it has less-interesting intermediate results so I might end up wasting less time watching numbers factor in the mornings than I do at the moment.

[Dubslow]

Interestingly enough, in this paper on the RH, the 7th endnote is a page and a half about B200 (though about half of that is an explanation of the Fermat 2-PRP test).

But then, given that it is so \easy" to see that N is not prime, a natu-
ral question to ask is: what, in fact, is its prime factorization? This--it turns out--isn't so easy to determined, and--to date--has not been deter-
mined (at least by us). Naskrecki devoted 24 hours of computer time setting
standard factorization algorithms on the task, and that was not sucient
time to resolve the issue. The factorization of the numerators of general
Bernoulli numbers is the subject of a very interesting web site of Samuel
Wagsta (http://homes.cerias.purdue.edu/~ssw/bernoulli). Linked
to this web page one nds (http://homes.cerias.purdue.edu/~ssw/
bernoulli/composite) which gives a list of composite numbers whose fac-
torizations have resisted all attempts to date. The two-hundredth Bernoulli
number is 12th on the list.
Finally, we note that there with sucient motivation we believe it would
be possible to factor N. The page http://en.wikipedia.org/wiki/
Integer_factorization_records lists record challenge factorization, and
one challenge that was completed in 2009 involves a difficult-to-factor num-
ber with 232 digits; its factorization was completed by a large team of
researchers and took around 2000 years of CPU time.

Even though it is an aside, they appear to desire its factorization quite a bit.

Fittingly enough, the 8th footnote is a two-liner stating that factorization has never been proven to be hard, and the 9th endnote is a one line link to GIMPS.

FWIW (not much) I'd be willing to donate one core of an i7-2600K indefinitely.

[debrouxl]

SNFS 204 is a piece of cake for RSALS (with a sextic or a quintic, a bit less so for a quartic)... but IIUC akruppa's and fivemack's posts, we're talking about a GNFS 204 here, and that is way out of reach for the poor little 14e, indeed

With a good poly, GNFS 175 could probably be done with 14e, as RSALS has already sieved a GNFS 169 task with 30-bit LPs. But in the Aliquot 4788 team sievings, IIRC, 15e was used instead of 14e above 162-163 digits.

[xilman]

Originally Posted by debrouxl

SNFS 204 is a piece of cake for RSALS (with a sextic or a quintic, a bit less so for a quartic).

IMAO, it's a piece of cake for anyone. I'm churning out SNFS-201 once every two to three days on a single machine as part of my GCW efforts. By the time I reach 204 digits the rate will probably have fallen to two a week.

If anyone else would like to join in, please contact me.


Paul

[jasonp]

Originally Posted by pinhodecarlos

Those 7% less unique relations give an increase of 48% on LA time processing, is this the only reason?!

Did the first job have (relations minus unique ideals) larger when the filtering started? I suspect the first job just had more oversieving; 7% extra relations actually is enough to make a big difference in matrix size.

[akruppa]

I don't know how to make useful SNFS polynomials for Bernoulli numbers. Since there are composites with less than 200 digits left on Wagstaff's list, it appears that no one else does, either.

[R.D. Silverman]

Originally Posted by akruppa

I don't know how to make useful SNFS polynomials for Bernoulli numbers. Since there are composites with less than 200 digits left on Wagstaff's list, it appears that no one else does, either.

There are recursion formulae for the Bernouilli's, but I seriously doubt that there is an algebraic closed form amenable to SNFS. Ask Sam.

[LaurV]

Originally Posted by akruppa

Can someone take on the matrix?

Stupid question: What (minimal/recommended) hardware does one need for such a huge job? (cores, gigs of memory). Maybe some people will want to, but they are not sure if the hardware they have is enough. Can one do it with his hardware at home, or he need all the university's lab for it? Estimation for completion?