mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-04-16, 15:07   #1
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default Bernoulli(200) c204

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:

Code:
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?
akruppa is offline   Reply With Quote
Old 2012-04-16, 15:13   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×52×127 Posts
Default

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

Last fiddled with by fivemack on 2012-04-16 at 15:17
fivemack is offline   Reply With Quote
Old 2012-04-16, 15:15   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Yoyo is just about to finish a p65 test, see http://www.rechenkraft.net/yoyo/y_status_ecm.php
akruppa is offline   Reply With Quote
Old 2012-04-16, 15:23   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×52×127 Posts
Default

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.

Last fiddled with by fivemack on 2012-04-16 at 15:26
fivemack is offline   Reply With Quote
Old 2012-04-16, 17:57   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

1C3516 Posts
Default

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).
Quote:
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.

Last fiddled with by jasonp on 2012-04-16 at 20:02 Reason: fixed markup
Dubslow is offline   Reply With Quote
Old 2012-04-16, 18:17   #6
debrouxl
 
debrouxl's Avatar
 
Sep 2009

977 Posts
Default

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.
debrouxl is offline   Reply With Quote
Old 2012-04-16, 19:21   #7
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

23·13·97 Posts
Default

Quote:
Originally Posted by debrouxl View Post
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
xilman is offline   Reply With Quote
Old 2012-04-16, 20:00   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·52·47 Posts
Default

Quote:
Originally Posted by pinhodecarlos View Post
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.
jasonp is offline   Reply With Quote
Old 2012-04-16, 20:00   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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.
akruppa is offline   Reply With Quote
Old 2012-04-16, 21:13   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

2·3·11·113 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2012-04-17, 05:13   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

218E16 Posts
Default

Quote:
Originally Posted by akruppa View Post
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?
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Does anyone track factors for Bernoulli numbers? VBCurtis And now for something completely different 1 2015-02-08 02:45
Bernoulli(202) C173 bai Factoring 2 2012-10-22 23:16
Bernoulli Number's conjeture? Damian Math 2 2009-09-27 20:37
Bernoulli number Batalov Math 5 2009-06-01 22:10
Bernoulli and Euler numbers (Sam Wagstaff project) fivemack Factoring 4 2008-02-24 00:39

All times are UTC. The time now is 06:40.

Wed Jul 15 06:40:50 UTC 2020 up 112 days, 4:13, 0 users, load averages: 1.68, 1.55, 1.50

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.