mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-03-09, 19:43   #1
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

3×11×223 Posts
Default Curve Counts

According to http://www.loria.fr/~zimmerma/records/ecm/params.html the curve counts listed for the 2- and 2+ pages is too high. The values I use came from ECMNet's pages several years ago.

I suspect I should convert my pages to use these new values. Opinions anyone?
Prime95 is online now   Reply With Quote
Old 2005-03-09, 19:56   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

I wanted to post something about curve counts for a while but I'm still running tests on how often gmp-ecm finds factors vs. computed values (looking very good so far) and also haven't had the time to write something up yet. I'm pretty sure that the expected curve numbers computed by GMP-ECM 6 are pretty close to the truth, and that the old figures were too high. I also think the effect of curves with smaller bounds on larger factor sizes should be considered and the bound level should be increased when the probability of missing a factor of the target size with *all* curves done so far is <exp(-1). This will further reduce the number of curves to do at each level.

I'll try to write something more coherent when the latest batch of test curves finish and I have a moment to put together the results.

Alex
akruppa is offline   Reply With Quote
Old 2005-03-09, 21:36   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

3·11·223 Posts
Default

Quote:
Originally Posted by akruppa
I also think the effect of curves with smaller bounds on larger factor sizes should be considered and the bound level should be increased when the probability of missing a factor of the target size with *all* curves done so far is <exp(-1). This will further reduce the number of curves to do at each level.
So you are saying that the new table on ECMNet's page does not take into account curves done with smaller B1. That is, to find a 30-digit factor if no ECM has been done requires 648 curves at B1=250,000. But if you've already done 262 curves at B1=50,000, then we only need to do (roughly) 648 - (262 / (250000 / 50000)) = 596 more curves at 250,000.
Prime95 is online now   Reply With Quote
Old 2005-03-09, 22:15   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

Yes.

The expected number of curves to find a p30 with B1=50k, B2=100*B1 is 5268. Doing 262 curves does 262/5268 = .0497 of the required work, so only 616 additional curves at B1=250k should be needed to get the probability of a miss <exp(-1). The effect from curves with smaller bounds, say B1=11k, is very small and can be ignored.

Similarly, if someone does curves at a high bound before the expected number of curves at lower levels are done, the effect of the "large" curves on smaller factor sizes should be considered. This will also avoid people waste cpu time on small bounds to "fill in gaps" when a lot of curves at high bounds have been done already. There are no actual gaps, they are merely an artifact of the bookkeeping method.

I think it might be better to not count curves but a fraction or percent, where "p45 nn% done" means that the probability of missing a p45 with the curves that have been done so far is exp(-nn/100). If people do curves with varying B2 parameters, for example by fine-tuning gmp-ecm, the "standard curve" with B2=100*B1 become a rather arbitrary unit that everyone need to convert to. Normalizing the unit to "100% = all finished" is probably easier in the long run.

Comments cordially invited!

Alex
akruppa is offline   Reply With Quote
Old 2005-03-10, 02:14   #5
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

735910 Posts
Default

Quote:
Originally Posted by akruppa
I think it might be better to not count curves but a fraction or percent, where "p45 nn% done" means that the probability of missing a p45 with the curves that have been done so far is exp(-nn/100). If people do curves with varying B2 parameters, for example by fine-tuning gmp-ecm, the "standard curve" with B2=100*B1 become a rather arbitrary unit that everyone need to convert to. Normalizing the unit to "100% = all finished" is probably easier in the long run.
Technically, I agree. But from a human-factors (and historical) point of view maybe not. Prime95 ECM users are oft-times beginners. It is simpler for them to say: "I did a hundred curves on Mxxx with B1=yyy". They may have difficulty converting that to a percentage. By and large, GMP-ECM users are a much more seasoned breed.

BTW, I have to plead guilty to some sloppy bookkeeping. In my tables, GMP-ECM curve counts emailed to me are simply doubled no matter what B2 is chosen. I do appreciate the forum threads here which aggregate GMP-ECM curves and compute the multiplier properly.
Prime95 is online now   Reply With Quote
Old 2005-03-10, 10:20   #6
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

32×307 Posts
Default

Alex,
I think I'll take your suggestion for updating the Cunningham tables in the forum here. I'm also leaning towards removing the 2- and 2+ tables altogether (with the exception of 2LM) since having these tables on both George's pages and the forum is just confusing and adds work and the probability of an error.
garo is offline   Reply With Quote
Old 2005-03-10, 12:06   #7
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Quote:
Originally Posted by garo
I'm also leaning towards removing the 2- and 2+ tables altogether (with the exception of 2LM) since having these tables on both George's pages and the forum is just confusing ...
If you do so, I suggest that you leave a deep link to George's corresponding pages along with the explanation as to why you have omittted them.
Wacky is offline   Reply With Quote
Old 2005-03-10, 13:23   #8
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

624710 Posts
Default

Quote:
Originally Posted by garo
Alex,
I think I'll take your suggestion for updating the Cunningham tables in the forum here. I'm also leaning towards removing the 2- and 2+ tables altogether (with the exception of 2LM) since having these tables on both George's pages and the forum is just confusing and adds work and the probability of an error.
Here is my 2 cents.

Since George's pages only have 2+/2-, maybe he could redirect his links to the thread in this forum. The format of the tables in this forum, plus all of the other information available, such as which are reserved, make this forum a better resource.

Also, maybe Paul Zimmerman can point his Cunningham project to that thread in this forum. Again, the format is far easier to understand than those on his website.

I like one-stop shopping and to have only 1 place to coordinate all Cunningham work is a good thing.
rogue is offline   Reply With Quote
Old 2005-03-10, 13:43   #9
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

1CBF16 Posts
Default

I have no problem with letting someone else maintain the 2- and 2+ tables in the forums. I'll do whatever everyone thinks is best.
Prime95 is online now   Reply With Quote
Old 2005-03-10, 13:49   #10
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

33F16 Posts
Default

My short answer would be:

A lot of people can maintain those tables, but only few (or maybe only one?) can improve prime95/mprime.
Mystwalker is offline   Reply With Quote
Old 2005-03-10, 14:13   #11
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

32×307 Posts
Default

For historical reasons, I'm inclined to let George handle the 2+ and 2- tables. Plus, believe me, updating all the tables is a pain and very time-consuming and if I have two less tables to handle I'll be a lot happier :)

Regardless, it is always possible to give other people - including George - mod privileges on the forum so if we do decide to host everything on the forum, we should be able to divide the work. I did an update on the the tables last week but I'm still waiting for an email response or two before I finish the job and upload the tables that are now residing on my HD.

BTW, I wanted to ask Xyzzy if it is possible to enable HTML on the forum. Maybe I have asked before and he has said no already but I don't remember.
garo is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
post counts Raman Forum Feedback 67 2016-01-07 18:35
Why different shift counts are important Madpoo Data 6 2015-10-11 03:55
I don't understand these relation counts fivemack Msieve 4 2012-10-29 11:26
Dedidicated rig; What counts in Prime Crunching? kaffikanne Hardware 10 2009-12-12 23:46
Case of the disappearing post counts... PrimeCruncher Lounge 7 2004-10-31 22:07

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

Sun Mar 7 00:02:23 UTC 2021 up 93 days, 20:13, 0 users, load averages: 2.41, 2.42, 2.03

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.