mersenneforum.org Number with small factor: Further factorization?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2005-04-30, 11:08 #1 Mystwalker     Jul 2004 Potsdam, Germany 83110 Posts Number with small factor: Further factorization? Hi there! First: Sorry for the confusing title, I can't think of a way to concentrate the problem into a few words... Ok, here it goes: I want to factor 5^349-1 and 19^193-1. Both numbers have small factors (e.g. 2). The gmp-ecm approach would be to use the remaining composite. The prime95 approach is to factor the whole number, because of the special form. Now, I want to do stage1 with Prime95, but stage2 with gmp-ecm for optimal performance. Is there a way to a) simply convert the ECM residue after stage1 s.t. it fits as an input file for the smaller composite b) tell gmp-ecm that it does not have to look for the small factors (maybe something like lowm/lowp) c) get to a solution differently? Thanks in advance!
2005-04-30, 12:09   #2
geoff

Mar 2003
New Zealand

13×89 Posts

Quote:
 I want to factor 5^349-1 and 19^193-1
Are these numbers really faster with Prime95? I tried stage one for 5^349-1 with B1=3e6 on a 2.66GHz P4, Prime95 24.11 took 172 sec. but gmp-ecm 6.0 took only 149 sec. I would have thought that any other machine would be even better off with gmp-ecm than a P4.

Quote:
 Is there a way to a) simply convert the ECM residue after stage1 s.t. it fits as an input file for the smaller composite
Once Prime95 finds the small factor, all stage one residues output from then on will be with respect to the remaining cofactor, just as if the new factor had been in a lowm.txt file from the beginning.

Even so, gmp-ecm will reduce the residue modulo the number being factored automatically. This means that if you find a factor in the stage two step and still have some stage one residues to process, you can just replace the input number (N= field) with the new cofactor, no change to the residue field is necessary.

It would be nice if Prime95 had a k*b^n+c version of the low[mp].txt files though, at the moment you waste one curve each time a trivial factor is found because no residue is output.

 2005-05-02, 08:04 #3 Mystwalker     Jul 2004 Potsdam, Germany 3×277 Posts You're right! A P3/800 takes ~8 hours to do a stage1 with B1=11e7, but only ("only"?) ~6 hours with gmp-ecm. Still a lot worse than M1061, which only needs 1.5 hours despite it's 25% larger... Anyways: Thanks for that tip!
 2005-05-02, 08:31 #4 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts George mentioned that he plans to look into the DWT for non-base 2 numbers, but it will be several months off yet. When ready, it will speed up stage 1 for numbers like these rather drastically. I don't mean to stop anyone doing what they want to do, but I'll mention that personally I'll focus on base 2 numbers (where the DWT already works) and numbers not of the form a*b^n+c (say, Fibonacci/Lucas numbers) and SNFS for a while, and keep the others for when the much faster stage 1 is available. Alex Last fiddled with by akruppa on 2005-05-02 at 08:34

 Similar Threads Thread Thread Starter Forum Replies Last Post jinydu Abstract Algebra & Algebraic Number Theory 5 2014-07-30 11:24 literka Miscellaneous Math 73 2013-11-17 10:33 Arkadiusz Software 7 2013-02-18 12:43 Zeta-Flux Factoring 96 2007-05-14 16:59 jchein1 Factoring 30 2005-05-30 14:43

All times are UTC. The time now is 12:51.

Sun May 9 12:51:44 UTC 2021 up 31 days, 7:32, 0 users, load averages: 1.43, 1.59, 1.73