20061130, 12:01  #1  
Einyen
Dec 2003
Denmark
19·181 Posts 
Quote:


20061130, 12:29  #2  
Aug 2002
Buenos Aires, Argentina
1497_{10} Posts 
Quote:
Quote:
Last fiddled with by alpertron on 20061130 at 12:30 

20061130, 12:34  #3 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
For a given prime p, you can construct a curve of any order in the Hasse interval around p by a technique called Complex Multiplication. That is, I think to construct any valid order you may need to define the curve over an algebraic closure of GF(p), I'm not sure. Afaik, "usually" it works over GP(p) as well. This will give you the curve parameters, i.e. for a curve in Weierstraß form, the a and b parameters. Curves in Montgomery parameterisation are a subset of the curves in Weierstraß form, so not every curve generated by Complex Multiplicaion may be suitable for converting to Montgomery form. Furthermore, generating a curve in Montgomery form from the sigma value is not a bijective function either, so even for a valid curve in Montgomery form there may not be a suitable sigma value. If there is, the sigma value will be very large, more or less a random value (mod p).
I think David Broadhurst did some experimenting with producing "fake" ECM sucesses by constructing curves with Complex Multiplication. Iirc, he managed to make ECM "find" factors >1000 digits that way, but usually the size of the sigma value gave them away, as the random number generator we use in GMPECM chooses sigma <2^32. Alex 
20061130, 12:50  #4  
"Nancy"
Aug 2002
Alexandria
4643_{8} Posts 
Here is a posting of David Broadhurst to the NMBRTHRY mailing list on the subject:
Quote:
Last fiddled with by akruppa on 20061130 at 12:53 Reason: Moved to separate thread, CM isn't a beginners question at all! 

20061130, 23:10  #5 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6686_{10} Posts 
I see no reason why this can't also be a challenge for people to "make" the largest factors using a small sigma. As long a people don't try to misrepresent the result as "real" factors then it could be fun to try generating huge factors. We might even learn something of mathematically interesting in the process.

20061201, 15:44  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
I don't see much of a challenge here... David showed that it is possible to fake record ECM factors that are indistinguishable from the real thing. What would even larger fakes prove? CM is greatly refined and studied in detail for Elliptic Curve Primality Proving, and imho that's where it makes sense to invest the effort.
Alex 
20061201, 16:02  #7  
"Bob Silverman"
Nov 2003
North of Boston
16524_{8} Posts 
Quote:
Be the first to find a 70 digit factor of a Cunningham number via ECM. 

20061201, 19:58  #8 
Aug 2002
Buenos Aires, Argentina
2731_{8} Posts 

20061201, 20:11  #9 
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 

20061201, 20:15  #10 
Aug 2002
Buenos Aires, Argentina
10111011001_{2} Posts 
If I instruct one thousand computers with multiple cores to run random curves in all remaining Cunningham numbers, one of them will eventually find the 70digit or larger factor. Where is the merit?

20061202, 06:33  #11  
Jun 2005
lehigh.edu
2^{10} Posts 
wondering, too
Quote:
950, but that's including dual cpus, counted as 2; 50 short and no multiple cores. Not counting 30 xeons and macs running NFSNET. For one thing, the scheduling software running the xps  U Wisc's condor  clearly isn't quite up to the task yet; we're hoping the new core due over the semester break is more robust. I can assure you that it isn't a case of submitting the number of expected curves and waiting! For one, the gmpecm6.1 README doesn't even go up to 70; stops at 65digits. Same for Alex's v. The old gmpecm5.0 gives the optimal b1 = 2,700,000,000 for p70 (with 850M for p65), and (with a smaller default b2 than 6.1 would use), 120,000 curves. So the first problem you'll have is that these type of commodity chips don't come with enough memory to run even 850M, much less 2700M. I have 250Mb on the P3s and c. 300 of the xps; 500Mb on the other 450 xp; 1Gb/cpu on the Opterons. That gets me to 250digits with b1 = 260M (p60optimal) on the Opterons; and b1=43M on the xps and P3s. Our expensive machine has 128Gb for 32 Itanium2's, so just 4Gb/cpu  I tried 850M there for a while, with step1 on the (faster) Opterons, to best use the expensive memory in step 2's. Just on c175c185 to get more curves. Too labor intensive. Looks like 15K curves, all told. So that's probably a second point; you'd do better dropping the c251c366's anyway, something like 1/3 of the 850 on the current list. If you're going to find a p70, you'd want to have it meet Brent's restriction, so that means droping numbers under c150, or so (hardly any of them anyway, headed towards 2*t50 soon). But it's worse than that, if you found a p70 in a c170, someone would likely point out that you'd have done better using gnfs; so probably you'd do better staying in the range c200c250. Uhm, well, I'm just finishing a run on c195c233, something like 230 numbers out of the 850. No p7x's yet. Looks like 300K curves with b1=260M (p60 optimal). Supposed to be enough for a p65; found a p67. Next problem is that  if you're spending this amount of cputime  you most likely would want to make sure to get something for the effort. Grinding on the above 230numbers might make best sense for an ecm p7x, but there are still p4x's left in c250c366  Brent's claim was/is that one might justify at most 10% of an ecm effort on looking for champion factors (viz his p40 from F10). I found myself rather annoyed that people were running snfs and finding p47; and am somewhat happier that small factors these days have been p52p54, instead of p4x's. So that argues for time on numbers that aren't in what I'd consider best p7x range. bdodson (ecm records: p57, p59, p66 and p67, so far) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
the unit circle, tangens and the complex plane  bhelmes  Math  0  20180304 18:50 
Basic Number Theory 10: complex numbers and Gaussian integers  Nick  Number Theory Discussion Group  8  20161207 01:16 
radius of convergence of a complex power series  wildrabbitt  Math  3  20160816 08:38 
Complex, but deceptively simple question about Prime95 failures?  halcion  Software  6  20041216 20:10 
Complex number problem  dave_0273  Math  3  20041108 17:15 