mersenneforum.org > Math Factoring when one factor's magnitude is known
 Register FAQ Search Today's Posts Mark Forums Read

 2019-01-31, 23:38 #1 mathPuzzles   Mar 2017 368 Posts Factoring when one factor's magnitude is known We have a composite number N on the order of $$2^{4096}$$. An oracle tells us that there are no factors smaller than some value L, but there is at least one factor between L and 1.1 * L. What are strategies to find the unknown but range bracketed factor? If L is small, we can use trial division, but let's say L is large enough, say $$L\approx2^{48}$$, to preclude its effectiveness. We can also attempt a round of Pollard P-1 and/or multiple rounds of ECM factoring, but let's say they also fail to find a factor. What else can we try before firing up a general factoring engine like quadratic or general number field sieve? The only algorithm I've discovered that seems applicable is to use simple Fermat factoring with the Lehman multiplier modification. Ie, try to factor the number $$N * L * \lfloor{N\over L}\rfloor$$ since it will likely "split" into two terms of roughly equal magnitude. What else might work? Last fiddled with by CRGreathouse on 2019-02-01 at 05:24 Reason: correct N as clarified below
2019-01-31, 23:46   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

23·3·59 Posts

Quote:
 Originally Posted by mathPuzzles We have a composite number N on the order of $$2^{4096}$$ bits.
And how do you store it?

2019-01-31, 23:54   #3
mathPuzzles

Mar 2017

2·3·5 Posts

Quote:
 Originally Posted by R. Gerbicz And how do you store it?
Ha! My mistake, N is 4096 bits, not $$2^{4096}$$. Big difference!

 2019-01-31, 23:59 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 217038 Posts "Lasciate ogne speranza, voi ch'intrate"
2019-02-01, 02:35   #5
axn

Jun 2003

23×3×199 Posts

Quote:
 Originally Posted by mathPuzzles If L is small, we can use trial division, but let's say L is large enough, say $$L\approx2^{48}$$, to preclude its effectiveness.
Do you mean L~2^2048?

2^48 is trivial to find.

2019-02-01, 02:44   #6
mathPuzzles

Mar 2017

1E16 Posts

Quote:
 Originally Posted by axn 2^48 is trivial to find.
Yes, I mean 2^48. Yes, it's possible, but why is it trivial? My question is what method would work best.

The answer may end up being trial division, which would take on the rough order of a few days on a CPU.

2019-02-01, 03:54   #7
axn

Jun 2003

23·3·199 Posts

Quote:
 Originally Posted by mathPuzzles Yes, I mean 2^48. Yes, it's possible, but why is it trivial? My question is what method would work best. The answer may end up being trial division, which would take on the rough order of a few days on a CPU.
ECM will find 15 digit factors in a few seconds.

2019-02-01, 05:22   #8
CRGreathouse

Aug 2006

2·2,969 Posts

Quote:
 Originally Posted by mathPuzzles Yes, I mean 2^48. Yes, it's possible, but why is it trivial? My question is what method would work best. The answer may end up being trial division, which would take on the rough order of a few days on a CPU.
Definitely some form of ECM. Too big, sadly, for Chelli's trick.

 2019-02-01, 16:49 #9 chris2be8     Sep 2009 36258 Posts P-1 with B1=sqrt(L*1.1) and B2=L*1.1 will almost always work. It only fails if the factor F you are looking for is such that F-1 has a factor f1 to a power p1 such that f1^p1 > sqrt(L*1.1) and p1 >1. There is a way to get round that, but I can't remember the details (it's somewhere in the forum). If L is too large for that to work (eg > 10^20) then running ecm optimized for factors of as many digits as L has will eventually work. But it could take quite a long time if L is large (eg > 60 digits). Chris
2019-02-01, 23:43   #10
mathPuzzles

Mar 2017

368 Posts

Quote:
 Originally Posted by CRGreathouse Definitely some form of ECM. Too big, sadly, for Chelli's trick.
What is Chelli's trick? I was not able to find a reference by searching the forum or Google.

Edit: it's probably this deterministic ECM algorithm?

Last fiddled with by mathPuzzles on 2019-02-01 at 23:49 Reason: Added reference link

2019-02-01, 23:47   #11
mathPuzzles

Mar 2017

2×3×5 Posts

Quote:
 Originally Posted by chris2be8 P-1 with B1=sqrt(L*1.1) and B2=L*1.1 will almost always work. It only fails if the factor F you are looking for is such that F-1 has a factor f1 to a power p1 such that f1^p1 > sqrt(L*1.1) and p1 >1. There is a way to get round that, but I can't remember the details (it's somewhere in the forum). If L is too large for that to work (eg > 10^20) then running ecm optimized for factors of as many digits as L has will eventually work. But it could take quite a long time if L is large (eg > 60 digits).
You're right that this will work. It's not really using the information we have about knowing we have a factor bracketed, but it will work. And as you say, once L is too large then ECM (which also does not use our bracket clue). And when L is too large for ECM... "give up all hope, all ye who enter here".

 Similar Threads Thread Thread Starter Forum Replies Last Post xx005fs GPU Computing 3 2018-10-27 14:49 ewmayer Science & Technology 66 2008-07-31 15:30 James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09 dsouza123 Software 12 2003-08-21 18:38 jocelynl Math 12 2003-06-27 01:24

All times are UTC. The time now is 07:24.

Tue Nov 24 07:24:50 UTC 2020 up 75 days, 4:35, 4 users, load averages: 2.27, 1.90, 1.67