ecm_factor returning the same number as input

[alpertron]

All the steps noted by jasonp (except for rho, p-1 and p+1), including finding algebraic / Aurifeuillian factors of numbers of the form a^b +/- 1 are already done in my applet.

The applet also uses the Lehman factorization code in order to crack some easy composite numbers whose ratio of factors are near a rational number.

[smh]

Originally Posted by Capone

Thanks, I will do it that way then (first trial division, then possibly ECM)...

You do know that GMP-ECM is able to do the trailfactoring don't you?

[Andi47]

Originally Posted by akruppa

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

If the input is given as algebraic term (for example 2^1701-1 or 3^115-2^115, not just the number) this should be no big problem to split off the algebraic factors after parsing the input.

[xilman]

Originally Posted by akruppa

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

Further, even if you can detect the form of the number relatively easily, it may not be easy to find an algebraic factorization where one is possible.

For instance, it's easy to detect an N which is a (factor of) a generalized Cullen & Woodall number but I am far from certain that http://www.leyland.vispa.com/numth/f.../algebraic.txt contains all the algebraic factorizations that may exist for numbers of this form.


Paul

[akruppa]

Originally Posted by smh

You do know that GMP-ECM is able to do the trailfactoring don't you?

This is part of the application, but it's not in the library.

If the input is given as algebraic term (for example 2^1701-1 or 3^115-2^115, not just the number) this should be no big problem to split off the algebraic factors after parsing the input.

Even for the standard cyclotomic numbers, getting the algebraic factorisation is not trivial anymore when Aurifeullian factorisations are involved.

Alex

[alpertron]

They are not completely trivial but they are easy. Just read Richard Brent's publication 127 about Aurifeuillian factorizations. I used this information for my applet.

[Capone]

Well, I've implemented the trial division factoring along with ECM, and it works like a charm! No more problems now... (yet :P)