20120129, 19:49  #1 
Jan 2012
Toronto, Canada
137_{8} Posts 
ecm anomaly?
When factoring a C155 from 2^577+5 using gmpecm i got:
Using B1=1000000, B2=1045563762, polynomial Dickson(6), sigma=1807440646 Step 1 took 18234ms Step 2 took 8610ms ********** Factor found in step 2: 6924574727318479831777387120007 Found probable prime factor of 31 digits: 6924574727318479831777387120007 Composite cofactor ((2^577+5)/49/41/25127/545543/1194493)/6924574727318479831777387120007 has 124 digits The group order for this factor is: [2, 2] [3, 1] [7, 2] [83, 1] [101, 1] [487, 1] [2179, 1] [5749, 1] [136849, 1] [1682659283, 1] However, the last factor (1682659283) is larger than the B2 bound used to find this factor. How is this possible? P.S. Is the cofactor easier to factor using GNFS or SNFS? 
20120129, 20:15  #2 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{4}·5·137 Posts 

20120129, 20:37  #3  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×4,787 Posts 
factordb parser hadn't read it either :)
Link Quote:


20120129, 22:34  #4 
Jan 2012
Toronto, Canada
5·19 Posts 

20120130, 08:45  #5  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2AD0_{16} Posts 
Quote:
Perhaps you should start researching the chronological development of these three. You will find the experience worthwhile and should find it relatively straightforward. Paul 

20120130, 13:16  #6 
Dec 2008
179 Posts 
Huh? All three algorithms perform their arithmetic operations in exactly the same ring, the ring of integers modulo the number you want to factor. The difference is the almostgroup in which the almostgroup operation is performed; for P1 it's the multiplicative almostgroup of that ring, for P+1 it's a simple quadratic extension of that almostgroup, and for ECM it's something much more complicated. (I use the word "almostgroup" because the whole point of these algorithms is to find a noninvertible element which couldn't exist in a true group.)

20120130, 14:27  #7  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10960_{10} Posts 
Quote:
As you note, the operations are over an "almost group". Unless my brain is rotting even faster than I thought  something which is entirely possible  your "almost groups" are rings. Please take a look at, for instance, http://en.wikipedia.org/wiki/Ring_%2...mal_definition for the definition of a ring with identity and clarify the way in which each of your "almost groups" differ from a ring with identity. We agree that "almost groups" are not groups and that arithmetic over your "almost groups" is itself performed over the ring of integers modulo the composite integer N. Paul 

20120131, 10:46  #8  
Dec 2008
179 Posts 
Quote:


20120131, 11:59  #9  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{4}·5·137 Posts 
Quote:


20120131, 17:18  #10 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Afaik you can embed elliptic curves in rings, fields even. The fact is briefly described here, for example. I know nothing about the details, but I assume you have to know the order of (a cyclic subgroup of) the curve to compute the embedding, and that the embedding degree is usually kinda large  whatever "large" may be in this context  so it is useless for the purpose of ECM.

20120131, 17:34  #11  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{4}×5×137 Posts 
Quote:
The algebraic object is, BTW, a monoid  the conventional name for what you call an "almost group". Again, further evidence for brainrot on my part is welcomed. It won't get better unless I treat it. Paul 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Annoying Ambient Air Anomaly Analyzed and Answered!  Xyzzy  Miscellaneous Math  3  20150906 06:47 
Anomaly after ECM report; possible ECM data base integrity problem  cheesehead  PrimeNet  8  20130901 04:27 
v4_computer vs. Machine Name anomaly  ADBjester  PrimeNet  5  20081112 17:07 