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

 2007-06-12, 15:54 #12 alpertron     Aug 2002 Buenos Aires, Argentina 22·373 Posts 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. Last fiddled with by alpertron on 2007-06-12 at 15:59
2007-06-12, 18:41   #13
smh

"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts

Quote:
 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?

2007-06-12, 19:23   #14
Andi47

Oct 2004
Austria

2×17×73 Posts

Quote:
 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.

2007-06-12, 19:33   #15
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

101101011111012 Posts

Quote:
 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

2007-06-12, 22:39   #16
akruppa

"Nancy"
Aug 2002
Alexandria

9A316 Posts

Quote:
 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.

Quote:
 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

 2007-06-12, 23:19 #17 alpertron     Aug 2002 Buenos Aires, Argentina 22×373 Posts 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. Last fiddled with by alpertron on 2007-06-12 at 23:21
 2007-06-17, 09:19 #18 Capone   Jun 2007 Rotterdam, Holland 5 Posts Well, I've implemented the trial division factoring along with ECM, and it works like a charm! No more problems now... (yet :P)

 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 10:28.

Sat Jan 28 10:28:35 UTC 2023 up 163 days, 7:57, 0 users, load averages: 1.03, 0.93, 0.97