ecm_factor returning the same number as input

[Capone]

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!

[akruppa]

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 p_i is quite improbable that given curve parameters lead to several smooth curves reduced to the individual p_i.

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

[Capone]

That sounds logical...

I think I'll just do that then...

Thanks!

[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

[alpertron]

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.

[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 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.

[Capone]

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)

[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

[Capone]

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)...

[wblipp]

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.

[akruppa]

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