mersenneforum.org ecm_factor returning the same number as input
 Register FAQ Search Today's Posts Mark Forums Read

 2007-06-11, 09:19 #1 Capone   Jun 2007 Rotterdam, Holland 5 Posts ecm_factor returning the same number as input Hi, I am trying to use the GMP-ECM factoring library to create a sort of general purpose factoring algorithm. At the moment I just call the ecm_factor method for the number to be factorized, divide the number by the factor found by ecm_factor, and repeat the process until the remainder is a prime or 1. For the B1 value I use some standard values found in the GMP-ECM documentation, and for the ecm_params I use the default values (I only call ecm_init(p) for the ecm_params). Sometimes though I encounter a problem with some integers I want to factor. Instead of returning a factor of the number, it returns the number itself, or a composite factor. If I try to factor that number again, the ecm_factor method returns 1 (factor found in stage 1), and the factor found is the same number as the input. This occurs for example with the numbers 27, and 14877. At the moment, this naturally causes an infinite loop in my program, since it keeps trying to factor that number and keeps getting the same result. I have tried several B1 values, from very small to very large, but each B1 value returns the same outcome. What can be causing this? Should I adjust any of the ecm_params values? (I am not a math genius by the way...) Thanks in advance!
 2007-06-11, 11:12 #2 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 Posts ECM finds any prime factor (or prime power) where the order of the group defined by the curve is smooth. It is perfectly possible to find several prime factors at once this way, or even all primes of the input numer, which means the input number is reported as the "factor." This happens mostly if there are several small prime factors present, with larger prime factors pi is quite improbable that given curve parameters lead to several smooth curves reduced to the individual pi. The easiest way of avoiding the problem is getting rid of small primes with trial division first. Once you know that there are no primes <10^6 or so left, you can start ECM. Alex
 2007-06-11, 11:36 #3 Capone   Jun 2007 Rotterdam, Holland 516 Posts That sounds logical... I think I'll just do that then... Thanks!
 2007-06-11, 15:19 #4 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Note: the bound 10^6 is much on the small side. At that point, you can expect that ECM with small B1,B2 parameters will more often spit out prime factors than composite factors but it is hardly the optimal threshold for switching to ECM. If your trial division code is reasonably efficient, higher bounds will make sense - just experiment a little and see how long it takes the trial division code to find an n digit prime, and how long it typically takes the ECM code to find it. Alex
 2007-06-11, 18:11 #5 alpertron     Aug 2002 Buenos Aires, Argentina 5AC16 Posts The bound B1 = 1000000 is very high for small numbers, so you will not be able to "crack" them. I would start with B1 = 2000, then I'd continue with B1 = 11000, B1 = 50000 and so on. See the table of optimal parameters in order to know how many curves you have to run for each value of B1.
 2007-06-12, 03:07 #6 jasonp Tribal Bullet     Oct 2004 5·709 Posts It's a very interesting problem to build a general find-all-factors program, that uses a combination of algorithms in a way that minimizes the expected runtime. A complete implementation should do trial division, then pollard rho, then p+1 / p-1 with small bounds, then put the remaining cofactor and any prime factors found into a structure that remembers each factor and whether it is prime or not. Then you should iterate through the composite factors, test for whether each is a prime power and then try ECM / p-1 / p+1 with increasing bounds, then QS. When new factors are found, previously found prime factors are divided out and anything left gets added to the structure, then the process repeats. Composite cofactors that are small should be handled with dedicated SQUFOF or QS routines, as these can dependably split the cofactors. For such a simple-sounding job, it's a very large amount of code to do right.
2007-06-12, 07:36   #7
Capone

Jun 2007
Rotterdam, Holland

58 Posts

Quote:
 Originally Posted by akruppa Note: the bound 10^6 is much on the small side. At that point, you can expect that ECM with small B1,B2 parameters will more often spit out prime factors than composite factors but it is hardly the optimal threshold for switching to ECM. If your trial division code is reasonably efficient, higher bounds will make sense - just experiment a little and see how long it takes the trial division code to find an n digit prime, and how long it typically takes the ECM code to find it. Alex
What if I would turn this around? I mean: first start using ECM, and when it returns a composite factor instead of a prime factor, use trial division to factor only that composite part. It would be easy to implement, but may not be the fastest way...

@alpertron:
Alex was talking about the bound for trial division, not the B1 bound for ECM. I am indeed using those optimal parameters list for my B1 values, and kind of extrapolated the list for smaller digit factors, which meant my lowest B1 has a value of 400 (may be kind of small, but it works (most of the time :P)).

@jasonp:
I think that would indeed be a good general factorization method. But because of my limited knowledge of the factorization algorithms, I'll just settle with a simpler, but less efficient way. Speed is not a very big issue here (although only using trial division would be too slow... :P)

 2007-06-12, 09:52 #8 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts It depends on what numbers you expect to be factoring. "Random" numbers usually have a few very small prime factors, so running ECM first and then trial division will almost always be a waste as you'll have to trial divide after all. Trial division is still the best way of recovering very small factors and should always be done first. Alex
2007-06-12, 10:20   #9
Capone

Jun 2007
Rotterdam, Holland

516 Posts

Quote:
 Originally Posted by akruppa It depends on what numbers you expect to be factoring. "Random" numbers usually have a few very small prime factors, so running ECM first and then trial division will almost always be a waste as you'll have to trial divide after all. Trial division is still the best way of recovering very small factors and should always be done first. Alex
Thanks, I will do it that way then (first trial division, then possibly ECM)...

2007-06-12, 13:15   #10
wblipp

"William"
May 2003
New Haven

1001010000112 Posts

Quote:
 Originally Posted by jasonp It's a very interesting problem to build a general find-all-factors program, that uses a combination of algorithms in a way that minimizes the expected runtime. A complete implementation should do trial division, then ...
You forgot about detecting and removing algebraic factors.

2007-06-12, 14:54   #11
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 Originally Posted by wblipp You forgot about detecting and removing algebraic factors.
This assumes that the algebraic form of the number is given, or can be detected efficiently. The latter part is decidedly non-trivial for a lot of numbers where algebraic factorisation are possible.

Alex

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Msieve 1 2017-12-12 17:22 UBR47K GPU Computing 2 2016-06-11 22:38 wombatman Factoring 5 2014-06-14 04:44 opyrt Prime Sierpinski Project 6 2009-12-28 17:42 M0CZY GMP-ECM 10 2006-12-21 14:13

All times are UTC. The time now is 07:33.

Wed Jun 29 07:33:41 UTC 2022 up 76 days, 5:35, 1 user, load averages: 1.61, 1.28, 1.08