mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-01-29, 19:49   #1
swishzzz
 
Jan 2012
Toronto, Canada

1378 Posts
Default ecm anomaly?

When factoring a C155 from 2^577+5 using gmp-ecm 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?
swishzzz is offline   Reply With Quote
Old 2012-01-29, 20:15   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

24·5·137 Posts
Default

Quote:
Originally Posted by swishzzz View Post
However, the last factor (1682659283) is larger than the B2 bound used to find this factor. How is this possible?
Typing the words "Brent Suyama extension" into Google should enlighten you.

Paul
xilman is offline   Reply With Quote
Old 2012-01-29, 20:37   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Default

factordb parser hadn't read it either :-)

Link

Quote:
Originally Posted by factordb.com parser
More information
Err: Calculated grouporder 6924574727318477523234391935036<31> is not within B1/B2 bounds (B1=1000000, B2=1045563762). Please check your result!
Batalov is offline   Reply With Quote
Old 2012-01-29, 22:34   #4
swishzzz
 
Jan 2012
Toronto, Canada

5·19 Posts
Default

Quote:
Originally Posted by xilman View Post
Typing the words "Brent Suyama extension" into Google should enlighten you.

Paul
All I could find on google is the Brent-Suyama extension for P-1. Or is there a trivial generalization of this that applies to ECM?
swishzzz is offline   Reply With Quote
Old 2012-01-30, 08:45   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2AD016 Posts
Default

Quote:
Originally Posted by swishzzz View Post
All I could find on google is the Brent-Suyama extension for P-1. Or is there a trivial generalization of this that applies to ECM?
It could be argued that P-1, P+1 and ECM are all exactly the same algorithm. Their only difference is the ring in which the arithmetic operations are performed.

Perhaps you should start researching the chronological development of these three. You will find the experience worthwhile and should find it relatively straightforward.

Paul
xilman is offline   Reply With Quote
Old 2012-01-30, 13:16   #6
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by xilman View Post
It could be argued that P-1, P+1 and ECM are all exactly the same algorithm. Their only difference is the ring in which the arithmetic operations are performed.
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 almost-group in which the almost-group operation is performed; for P-1 it's the multiplicative almost-group of that ring, for P+1 it's a simple quadratic extension of that almost-group, and for ECM it's something much more complicated. (I use the word "almost-group" because the whole point of these algorithms is to find a noninvertible element which couldn't exist in a true group.)
Random Poster is offline   Reply With Quote
Old 2012-01-30, 14:27   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1096010 Posts
Default

Quote:
Originally Posted by Random Poster View Post
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 almost-group in which the almost-group operation is performed; for P-1 it's the multiplicative almost-group of that ring, for P+1 it's a simple quadratic extension of that almost-group, and for ECM it's something much more complicated. (I use the word "almost-group" because the whole point of these algorithms is to find a noninvertible element which couldn't exist in a true group.)
Thanks for adding some additional information to my statement. However, I stand by my claim, absent further comment.

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
xilman is offline   Reply With Quote
Old 2012-01-31, 10:46   #8
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
Rings have two distinct associative binary operations, but elliptic curves only have one; there is no possible way to define a ring structure on an elliptic curve. P-1 and P+1 certainly do operate on elements of rings, but since you insisted that they are the same abstract algorithm as ECM, you must forget about addition and pretend that P+-1 only use multiplication.
Random Poster is offline   Reply With Quote
Old 2012-01-31, 11:59   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

24·5·137 Posts
Default

Quote:
Originally Posted by Random Poster View Post
Rings have two distinct associative binary operations, but elliptic curves only have one; there is no possible way to define a ring structure on an elliptic curve. P-1 and P+1 certainly do operate on elements of rings, but since you insisted that they are the same abstract algorithm as ECM, you must forget about addition and pretend that P+-1 only use multiplication.
Thank you. It was brain rot, as I suspected.
xilman is offline   Reply With Quote
Old 2012-01-31, 17:18   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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.
akruppa is offline   Reply With Quote
Old 2012-01-31, 17:34   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

24×5×137 Posts
Default

Quote:
Originally Posted by Random Poster View Post
Rings have two distinct associative binary operations, but elliptic curves only have one; there is no possible way to define a ring structure on an elliptic curve. P-1 and P+1 certainly do operate on elements of rings, but since you insisted that they are the same abstract algorithm as ECM, you must forget about addition and pretend that P+-1 only use multiplication.
IMO, the P+-1 algorithms only use multiplication. Each algorithm raises a base element to a highly composite power and attempts to compute a result which has no inverse.

The algebraic object is, BTW, a monoid --- the conventional name for what you call an "almost group".


Again, further evidence for brain-rot on my part is welcomed. It won't get better unless I treat it.

Paul
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Annoying Ambient Air Anomaly Analyzed and Answered! Xyzzy Miscellaneous Math 3 2015-09-06 06:47
Anomaly after ECM report; possible ECM data base integrity problem cheesehead PrimeNet 8 2013-09-01 04:27
v4_computer vs. Machine Name anomaly ADBjester PrimeNet 5 2008-11-12 17:07

All times are UTC. The time now is 15:25.


Wed Oct 27 15:25:56 UTC 2021 up 96 days, 9:54, 0 users, load averages: 0.79, 0.85, 1.00

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.