mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2014-02-15, 10:46   #34
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×29×109 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2014-02-15, 17:01   #35
chris2be8
 
chris2be8's Avatar
 
Sep 2009

5·383 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
chris2be8 is offline   Reply With Quote
Old 2014-02-15, 20:29   #36
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·3·733 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
VBCurtis is offline   Reply With Quote
Old 2014-02-16, 00:20   #37
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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
a small adjustment in B1.

But it isn't going to matter in practice........
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM - why 3 curves? James Heinrich PrimeNet 3 2017-11-14 13:59
JKL-ECM: ECM using Hessian curves CRGreathouse Software 1 2017-09-06 15:39
Need help with elliptic curves... WraithX Math 12 2010-09-29 09:34
Curves needed henryzz GMP-ECM 3 2007-12-21 16:13
Elliptic curves in NFS 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

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.