mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-01-25, 03:44   #1
FactorEyes
 
FactorEyes's Avatar
 
Oct 2006
vomit_frame_pointer

23·32·5 Posts
Default Brent-Montgomery-te Riele numbers

I'm curious how much ECM CPU time has gone into the Brent-Montgomery-te Riele extensions of the Cunningham tables (see the link at Zimmerman's page). They aren't mentioned much around here.

Bound to be some factors less than 50 digits among those composites, assuming no huge university clusters have ground away at them for months.

Last fiddled with by FactorEyes on 2008-01-25 at 03:45
FactorEyes is offline   Reply With Quote
Old 2008-01-25, 05:09   #2
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by FactorEyes View Post
I'm curious how much ECM CPU time has gone into the Brent-Montgomery-te Riele extensions of the Cunningham tables (see the link at Zimmerman's page). They aren't mentioned much around here.

Bound to be some factors less than 50 digits among those composites, assuming no huge university clusters have ground away at them for months.
Kruppa/Montgomery (aka, Alex/Peter) recently completed a record
p-1/p+1 pass (check Paul's records page). CWI's been grinding
through them for years; two of the top10 from 2007 were from
B&P's large run with epfl's machines, including the largest, p65. We
think that they're less tested than the Cunningham list; but I wouldn't
rule out factors under 50 digits there either. [Ooops, looks like Alex's
p4x's have gotten bumped out of the top10 p-1's; check Richard's
list.] -Bruce

(Ah, Richard's factors.txt reports that there was an ECMNET server
running during 2003-2006; then further factors up to Feb 2007, a
whole lot of CWI reports. There are surely easier targets.)
bdodson is offline   Reply With Quote
Old 2008-01-25, 15:30   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000110011102 Posts
Default

Quote:
Originally Posted by FactorEyes View Post
I'm curious how much ECM CPU time has gone into the Brent-Montgomery-te Riele extensions of the Cunningham tables (see the link at Zimmerman's page). They aren't mentioned much around here.

Bound to be some factors less than 50 digits among those composites, assuming no huge university clusters have ground away at them for months.
The tables are at http://wwwmaths.anu.edu.au/~brent/factors.html

I believe huge university clusters have precisely ground away at these for months. The lowest-hanging fruit on the first-holes list, which are reasonable personal-SNFS targets - an S190 is probably no more than a week on a dual-core - are the 133=7x19 and 121=11x11 powers, and then there are some small prime or {2^kp,+} ones:

Code:
24 139 + 191.85
62 107 + 191.79
15 163 - 191.70 (NB bdodson found a P47 factor on 2/2/08, this is now a C136)
* 13 172 + 191.60 (finished by bdodson with a P43, 4 Feb 08)
42 118 + 191.54
* 55 121 - 191.44 (finished by bdodson with a P52, 14 Feb 08)
46 133 + 189.55
37 133 - 178.77
There are a few C13x which would likely be easier by GNFS; the bottom of the first-holes list sorted by 'digits / snfs_difficulty' are

Code:
* 60 113 - 143 200.93 1.405  finished by bdodson 08 Feb with a P49
* 90 101 - 139 197.38 1.420  finished by FactorEyes 25 Apr with a P58
28 137 - 139 198.26 1.426
69 106 + 136 194.92 1.433
* 10 232 + 160 232.00 1.450 <- Cunningham number done by Irvine with a P61
* 57 113 + 136 198.41 1.459 finished by bdodson 21 Feb with a P49
97 119 - 138 202.65 1.468
67 127 - 154 231.91 1.506
88 118 + 147 229.45 1.561
57 139 - 154 244.07 1.585

Last fiddled with by fivemack on 2008-05-18 at 10:52 Reason: added list of gnfs-first targets
fivemack is offline   Reply With Quote
Old 2008-01-25, 17:19   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

Arjen Lenstra's students Aniruddha Bhargava and Sylvain Pelissier have run a lot of ECM on the BMteR tables lately. Peter and I did P-1 with B1=10^11 and B2=10^16 on a lot of these numbers. Some time ago I did a lot of the easiest SNFS numbers, difficulty <150 or so. Running the remaining numbers in comps.gz through phi finds 2 of difficulty < 160 and and bunch more of difficulty <170:
Code:
*15 204+ 86477846399689043464683717029156090048861048967246028346542762082353766287850823568159598684691797717310021500567119657051941720885202081
*19 186+ 22064611336630037993441645496728842220556437573639879717180732956862218596945115207666437591234151129886605991653966248694423179304531921

*13 219- 29789227638967279719753452653419330616492652498969823472736616044408900214492708666729753560650062601082073419281423838835993023775830992450981
*13 185+ 19198075398143282986521312292007210339867204517090997717056197733310096986428557713704819474579995542784067972998805981880984450916235431
*13 228+ 2727364713570059220279875144576079475403851873457637202751779519533254755818120824963764148419498582454672890891627002684180842305689354915715330067231473
*15 207- 200605994644287593361720414946755526335253616754462308696719693457589547560338042130862594677649676700840237084637053616237004264766403
*15 213- 2066957912511937223486278091004702307738903999738040895327891708741440460352478870799960031807639552756444103266055920366399429995356491667232049271148228943
21 183+ 840495924180053889480828320466090761213441850805869573117086685493441247366283840934405600405893270865405558261915109754194721889173519532934835841
21 186+ 129448909920304924867760651957761342407632280139510993404590115590731227274229350321955442652859842734192467044448256320420026040449
22 183- 33729278874243768066840544721250443222501196317530015698928363277010534626968965932075117893701136762671962220930452920558918235076223828303
22 183+ 351010416794463810326290140143660929903016348764190934847996908678342762573046606988781625855854022779076505615077186221687482877124053812941707255710443993153
23 155- 1292173230767983005217310792141279567315609093128659129811853603939453351326699352608650846291286206367038097373538248391276807239103602200053634786305032277311
24 183- 230223670658996925410197108966943754873294412852520219733667714294040308902808805182130471548678423014030764227959005924733050709589604158581136447396195437843529
24 145+ 311441749661125508779820860518393021783979989185535491637993981358479318102572173944478467494082073940288514845644498147791776561021
26 177- 2757741899316066474467784735435019764295890940462946536735922314883399017882238830573494413902454692484010569377381856131203764553973815504158711464979910875761
28 145- 4170520752643080302572797397982189273322959084449683008329127991951508969382319811864004350667257313721289791997219726648505628447871
31 159+ 8609758383766875992363295671475401342328692516921317342527073312610917766014707705872645275542074221651105886525040933678985711470145517798716401841
33 159+ 86776601947035139102955966706432585170964953534415262702221079534253696018529937121075589336461240895008116430976702815560542378049790290790661512428751068801
BTW, afaik Paul does not maintain a list of reservations for these numbers. Our P-1 pass is finished so afaik the only Lenstra's students are doing large scale work on the BMteR tables at the moment. If anyone wants to coordinate with them, let me know and I'll forward a message to them.

Alex

Last fiddled with by fivemack on 2008-05-18 at 10:50 Reason: Added stars by completed numbers
akruppa is offline   Reply With Quote
Old 2008-01-28, 16:08   #5
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by fivemack View Post
If Paul is not maintaining reservations for these numbers, and there aren't that many people working on them, why not do reservations for sieving here on this very forum? Obviously for truly-enormous sieving effort it's worth checking that the ECMers won't trump you, but for anything less than several month's work the risk is pretty small.

Reservations
Code:
Number   who?      when?
19,186+  fivemack  26/01/2008
I'm (very!) puzzled here. The notion that Paul was the person to check
with on the Brent-Montgomery-teRiele numbers was first introduced two
or three posts above (in your post). Paul has never kept these factors,
so far as I know. But that doesn't make this forum the next most likely
place to check. The tables have been maintained for many years by
Richard Brent (that would be as in OPN's Brent), and it appears to me that
CWI (including Montgomery and Herman teR.) were sending monthly
updates. The Feb 2007 update includes

>> 22 148 12595083615719740205913831870057576586969
CWI 20070222

which seems to be a p41. While it is true that Bhargava and Pelissier
have gotten large ecm factors, many/most seemed to have come from
the smaller numbers on the tables. If someone has tested the complete
list up to p45 (to probability .62), I haven't heard. I'm not saying that
it hasn't; and I'd be interested to hear if it has. Back in October,
Alex was reporting a p42 and a p44; and then a p44 and a p46; but
only by p-1/p+1; which will certainly not get all [p42..p46]'s.

Seems to me that one wouldn't start a 3 week sieving project without
more info and/or more ecm; much less two months or so. -Bruce

PS - well, are we discussing difficulty < 170? Then you may not
mind finding a p45. the "3 months" and checking Paul rather than
Richard Brent was the part that had me puzzled.

Last fiddled with by bdodson on 2008-01-28 at 16:21 Reason: ps from re-checking Alex's post, above
bdodson is offline   Reply With Quote
Old 2008-01-28, 16:30   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

143168 Posts
Default

Sorry, I clearly need to rewrite this at some point. Paul Zimmermann is clearly not the right contact point. Brent's list of holes has some of them marked up with people/organisation names, which I presume are reservations.

I'm vaguely tempted to set up another copy of my homogenous-Cunningham reservation server with the 1037 comps.gz numbers in it, though I'd want to check that that didn't step on Brent's toes.

http://wwwmaths.anu.edu.au/~brent/ft...ors/ecmnet.txt was last updated in February 2007 since ecmnet moved on to other projects; the first-holes file was updated much more recently (20080121), so seemed a safer source for numbers not yet done.

A p45 on a single number is 5000 curves at 11e7, which I think of as taking five CPU-days, or around enough time for a C120 GNFS or difficulty-170 SNFS; I can see that it'd be worth doing more ECM on the GNFS-numbers, and perhaps on my sublist of SNFSable first holes, but akruppa's list of SNFS candidates look adequately pre-sieved.

Last fiddled with by fivemack on 2008-01-28 at 16:30
fivemack is offline   Reply With Quote
Old 2008-01-28, 20:00   #7
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

102410 Posts
Default

Quote:
Originally Posted by fivemack View Post
... Brent's list of holes has some of them marked up with people/organisation names, which I presume are reservations.

I'm vaguely tempted to set up another copy of my homogenous-Cunningham reservation server with the 1037 comps.gz numbers in it, though I'd want to check that that didn't step on Brent's toes.
I'm sure Richard would be happy to have more ecm run on the
B-M-teR tables, but reports and reservations(?) perhaps ought
to include a copy to him --- if for no other reason than that other
people (not necessarily on this forum) would check with him. The
reservations on the 1st holes file are taken from Sam's "who's doing
what" --- only Cunninghams, base < 13, are listed as reserved.
Doesn't appear that there's an online place for reserving 19,186+,
and perhaps you'd be done with it before it'd be updated anyway?

If I'm reconstructing things correctly, the ecmnet from 2003-2006
was Xilman's. Then CWI decided that I'd ruined the Cunningham
list (according to a lecture of Peter's in Berlin, just before the ANTS;
at a conference in Brent's honor, organized by Paul Zimmermann,
among others), and switched to B-M-teR. Not sure which came first,
but Xilman seems to have decided that the BMteR tables had gotten
too hard, and switched to homog Cunninghams (or was that you?).

Quote:
http://wwwmaths.anu.edu.au/~brent/ft...ors/ecmnet.txt was last updated in February 2007 since ecmnet moved on to other projects; the first-holes file was updated much more recently (20080121), so seemed a safer source for numbers not yet done.

A p45 on a single number is 5000 curves at 11e7, which I think of as taking five CPU-days, or around enough time for a C120 GNFS or difficulty-170 SNFS; I can see that it'd be worth doing more ECM on the GNFS-numbers, and perhaps on my sublist of SNFSable first holes, but akruppa's list of SNFS candidates look adequately pre-sieved.
A mess. Looks like CWI sent in it's first bunch of factors in March 2006,
before xilman's server was taken down? sixteen in the first report. Then
a whole bunch in April; another chunk in May, then a bunch in June. Then
nothing until October; the mess, a bunch of duplicates submitted more
than once, from more than one person; nothing from CWI in Nov, then 3
monthly reports, Dec 06, Jan 07 and Feb 07; at which point the ecmnet
server has been gone for a while, and Richard discontinues the online file.
Again, "ecmnet" is Xilman's server (perhap it doesn't help that there's more
than one Paul involved?); Paul Zimmermann's never run/listed the
B-M-teR's.

So looks like there's another 17-or-so on Alex's list; I could probably run
the t45's with B1=110M (p55-optimal limits) without much distraction if
there's interest in cleaning these ones up. Richard would likely be glad
to have them done/removed. -Bruce
bdodson is offline   Reply With Quote
Old 2008-01-28, 20:33   #8
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

17·593 Posts
Default

Quote:
Originally Posted by bdodson View Post
Not sure which came first,
but Xilman seems to have decided that the BMteR tables had gotten
too hard, and switched to homog Cunninghams.
To be precise, and this is really just rephrasing your statement, the arrival rates of new factors had fallen so low that I was worried that participants would a) lose interest and b) find the memory demands of the ecmnet client too high.

Paul
xilman is offline   Reply With Quote
Old 2008-01-29, 03:11   #9
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by fivemack View Post
A p45 on a single number is 5000 curves at 11e7, which I think of as taking five CPU-days, ...
Uhm, you want 11e6 for 5000 curves. That's p45-optimal. My inclination
would be to use 110e6 = 11e7, p55-optimal. Not so efficient for finding
p45's, but we expect p52-or-so to be a more likely factor size. Using
250Mb P4's, k=20 seems to work here, and Alex's -v gives

Code:
GMP-ECM 6.1.1 [powered by GMP 4.2.1] [ECM]
Input number is 1022589...5200558598087 (237 digits)
Using MODMULN
Using B1=110000000, B2=961969548556, polynomial Dickson(30), sigma=634450470
dF=65536, k=20, d=690690, d2=17, i0=143
Expected number of curves to find a factor of n digits:
20      25      30      35       40      45      50      55       60      65
 2       4      10      33      131     594     3028    17145   107134  723404
and looks like 600 curves (that's under 250mb for c190s). The
500Mb P4's are using B1=110000000, B2=769593044236 with
k=16; for which the p45 and p50 columns are 613 and 3133; and
620 curves looks good. For the 250's here's two days of curves:

> -rw-r--r-- 660 2008-01-26 09:35 out613asm56pup.a4.1
> -rw-r--r-- 666 2008-01-26 22:24 out613asm56pup.b4.1
> -rw-r--r-- 668 2008-01-27 07:53 out613asm56pup.c4.1
> -rw-r--r-- 673 2008-01-27 17:08 out613asm56pup.d4.1

two numbers each, 800 curves, so c. 3000 curves/24hrs, for
five p45 tests. For the 500's, two days worth:

> -rw-r--r-- 706 2008-01-26 09:46 outhdk613c7079pd.a1h.1
> -rw-r--r-- 701 2008-01-26 16:50 outhdk613c7079pd.a2h.1
> -rw-r--r-- 730 2008-01-26 23:09 outhdk613c7079pd.a3h.1
> -rw-r--r-- 700 2008-01-27 04:15 outhdk613c7079pd.a4h.1
> -rw-r--r-- 703 2008-01-27 09:32 outhdk613c7079pd.a5h.1
> -rw-r--r-- 754 2008-01-27 16:30 outhdk613c7079pd.a6h.1

two numbers each, 500 curves, so another 3000 curves/24 hrs,
five p45 tests. I could try 2*t45 for five numbers a day, around
four days for all 17 numbers (1 below diff 160, 16 below diff 170).

Suppose 15, 204+ would be next? Care to nominate four more for
the first set of five? -Bruce
bdodson is offline   Reply With Quote
Old 2008-01-31, 19:13   #10
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·52·127 Posts
Default

You're presumably offering to run these curves on the cluster. One curve at 11e7 on 15,204+ is 815+300 seconds on the core2 on which 19+186 took 120 hours, admittedly using around 500M memory, so 600 would be 185 CPU-hours. Though, since the factor is a P52, it might have picked it up.

I'd be happy running with no more ECM on numbers as SNFS-easy as the ones in akruppa's table; if it were my time to allocate, I'd set the cluster off on the five easiest first-holes from my original post (with SNFS difficulties 180-192)

Last fiddled with by fivemack on 2008-01-31 at 19:19
fivemack is offline   Reply With Quote
Old 2008-02-01, 18:12   #11
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

100000000002 Posts
Default

Quote:
Originally Posted by fivemack View Post
You're presumably offering to run these curves on the cluster. One curve at 11e7 on 15,204+ is 815+300 seconds on the core2 on which 19+186 took 120 hours, admittedly using around 500M memory, so 600 would be 185 CPU-hours. Though, since the factor is a P52, it might have picked it up.

I'd be happy running with no more ECM on numbers as SNFS-easy as the ones in akruppa's table; if it were my time to allocate, I'd set the cluster off on the five easiest first-holes from my original post (with SNFS difficulties 180-192)
Uhm, that's 19, 186+? I did 2*t45 on 15,204+. Not having suggestions
on whether/which of the difficulty < 170's were likely to be first, I started
on the smallest. They're _really_ small! In fact, I'd bet that these small
ones were more than adequetly pounded on by previous runs. On the other
hand, t45's aren't hard to come by, so not much (if any) loss running them.
So in addition to the c137 already mentioned, I did 2*t45 on two
c132's from Alex's list; and 1*t45 on four more, c133, c135, c137 and c140.
Hoping not to find a record ecm, since it wouldn't meet Richard (Brent's) ratio
restriction for a Champion factor (c155-or-so, or larger).

So anyway, now that I know that the (current) sieving candidates are
from the first_holes list; rather than running a 2nd t45 on the above, I'm
switching to the ones from your post, eight numbers. Starting with the
smallest first (unless/until I hear otherwise); first two qued. -Bruce
bdodson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Brent tables reservations chris2be8 Factoring 446 2020-04-29 17:08
Brent-Suyama extension of P-1 factoring S485122 Math 1 2009-08-23 15:21
Montgomery method in Prime Numbers: ACP SPWorley Math 5 2009-08-18 17:27
brent suyama extension in P-1 bsquared Factoring 9 2007-05-18 19:24
Brent's p-1 - How to deal with memory problems? jhillenb Factoring 4 2005-01-11 23:50

All times are UTC. The time now is 02:08.

Fri Jul 10 02:08:37 UTC 2020 up 106 days, 23:41, 0 users, load averages: 1.25, 1.57, 1.52

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.