2005-04-30, 11:08 | #1 |
Jul 2004
Potsdam, Germany
831_{10} 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 | ||
Mar 2003
New Zealand
13×89 Posts |
Quote:
Quote:
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 |
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 |
"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 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Factorization of Ideals in Number Field, Looking for Reference | jinydu | Abstract Algebra & Algebraic Number Theory | 5 | 2014-07-30 11:24 |
Number 59649589127497217 is a factor of Fermat number F7 | literka | Miscellaneous Math | 73 | 2013-11-17 10:33 |
PFGW can't find a small factor. | Arkadiusz | Software | 7 | 2013-02-18 12:43 |
Large small factor | Zeta-Flux | Factoring | 96 | 2007-05-14 16:59 |
Factorization attempt to a c163 - a new Odd Perfect Number roadblock | jchein1 | Factoring | 30 | 2005-05-30 14:43 |