Go Back > Factoring Projects > GMP-ECM

Thread Tools
Old 2005-04-30, 11:08   #1
Mystwalker's Avatar
Jul 2004
Potsdam, Germany

83110 Posts
Question 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!
Mystwalker is offline   Reply With Quote
Old 2005-04-30, 12:09   #2
geoff's Avatar
Mar 2003
New Zealand

13×89 Posts

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.

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.
geoff is offline   Reply With Quote
Old 2005-05-02, 08:04   #3
Mystwalker's Avatar
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!
Mystwalker is offline   Reply With Quote
Old 2005-05-02, 08:31   #4
akruppa's Avatar
Aug 2002

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.


Last fiddled with by akruppa on 2005-05-02 at 08:34
akruppa is offline   Reply With Quote

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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.