mersenneforum.org B1 and # curves for ECM
 Register FAQ Search Today's Posts Mark Forums Read

 2014-02-15, 10:46 #34 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2×29×109 Posts I think the confusion here is in the way that GMP-ECM interprets B2. The available B2 are very quantised - they're roughly k * 4^n * magic-constant-depending-on-the-input-number, for small integer k and n, and what you specify is a value that the B2 used must exceed. The magic constant is about 2.85 billion for numbers of up to 1920 bits. For example, Code: echo "2^1061-1" | ecm -v -k 1 -c 1 1e5 192e9 uses an actual B2 of about 194 billion. Replacing '-k 1' with '-k 16' uses a B2 of about 769 billion, and takes about four times as long. Replacing '-k 1' with '-k 4' uses a B2 of about 192.3 billion, and is slightly faster. If you leave out the explicit '-k', then the actual B2 you get are Code:  97..144 k=3; B2=144.26G 145..192 k=4; B2=192.35G 193..240 k=5; B2=240.44G 241..288 k=6; B2=288.54G 289..388 k=2; B2=388.07G 389..582 k=3; B2=582.12G Basically, look at the B2 that gmp-ecm is actually using, rather than the one you specified on the command line. Last fiddled with by fivemack on 2014-02-15 at 10:52
2014-02-15, 17:01   #35
chris2be8

Sep 2009

5·383 Posts

Quote:
 Originally Posted by R.D. Silverman What is 'k'? It too is undefined.
From the man page for ecm:
-k k
[ECM, P-1, P+1] Perform k blocks in step 2. For a given B2 value, increasing k decreases the memory usage of step 2, at the expense of more cpu time.

Chris

2014-02-15, 20:29   #36
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2·3·733 Posts

Quote:
 Originally Posted by chris2be8 From the man page for ecm: -k k [ECM, P-1, P+1] Perform k blocks in step 2. For a given B2 value, increasing k decreases the memory usage of step 2, at the expense of more cpu time. Chris
Mr Silverman-
See post #24 for Henry's definition of k. Since it had already been defined in this thread, I felt no need to provide context.
Post #20 and 21 refer to using the -I option in GMP-ECM to slowly increase B1 after each failed curve. I was referring to this software option with my "iterating B1 up slowly", as a reply to Walter's curiosity whether using the -I option would be more efficient than the traditional method of running a set number of curves at a fixed B1 and then increasing B1 to a level optimal for a larger desired factor.

You state the procedure for changing B1, B2 does not depend on implementation. But GMP-ECM is rather coarse in available B2 choices- what if the method from your paper suggests, say, B2 = 450e9 but GMP-ECM only offers 388e9 and 582e9? Is it possible that a different choice of B1 with one of those available B2 values would be more efficient than your method's calculation suggests as optimal?

Chris-
k is used by GMP-ECM whether you invoke the command-line option or not. We can force GMP-ECM to use a certain number of blocks with the -k option, or allow it to choose k on its own. GMP-ECM only uses B2 values multiples of {list of small values I haven't studied}, 12e9, 48e9, 192e9, 768e9, etc; so a B2 choice of, say, 144e9 causes the program to use k=3 blocks of 48e9 each. You can see this parameter choice in the verbose output of GMP-ECM.

2014-02-16, 00:20   #37
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by VBCurtis You state the procedure for changing B1, B2 does not depend on implementation. But GMP-ECM is rather coarse in available B2 choices- what if the method from your paper suggests, say, B2 = 450e9 but GMP-ECM only offers 388e9 and 582e9?
Good question.

The response curve is VERY flat in the neighborhood of the optimum.
Modest changes in B1 or B2 from the optimum won't make a lot of
difference. I also doubt whether the difference could ever be observed
by actual trials. One would have to collect very large amounts of data
to see the difference.

One can also compensate for a smaller/larger than optimum B2 by

But it isn't going to matter in practice........

 Similar Threads Thread Thread Starter Forum Replies Last Post James Heinrich PrimeNet 3 2017-11-14 13:59 CRGreathouse Software 1 2017-09-06 15:39 WraithX Math 12 2010-09-29 09:34 henryzz GMP-ECM 3 2007-12-21 16:13 otkachalka Factoring 5 2005-11-20 12:22

All times are UTC. The time now is 05:38.

Wed Oct 28 05:38:00 UTC 2020 up 48 days, 2:48, 2 users, load averages: 2.11, 1.91, 1.75