20190131, 23:38  #1 
Mar 2017
36_{8} 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 P1 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 20190201 at 05:24 Reason: correct N as clarified below 
20190131, 23:46  #2 
"Robert Gerbicz"
Oct 2005
Hungary
2^{3}·3·59 Posts 

20190131, 23:54  #3 
Mar 2017
2·3·5 Posts 

20190131, 23:59  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
21703_{8} Posts 
"Lasciate ogne speranza, voi ch'intrate"

20190201, 02:35  #5 
Jun 2003
2^{3}×3×199 Posts 

20190201, 02:44  #6 
Mar 2017
1E_{16} Posts 

20190201, 03:54  #7 
Jun 2003
2^{3}·3·199 Posts 

20190201, 05:22  #8 
Aug 2006
2·2,969 Posts 
Definitely some form of ECM. Too big, sadly, for Chelli's trick.

20190201, 16:49  #9 
Sep 2009
3625_{8} Posts 
P1 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 F1 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 
20190201, 23:43  #10  
Mar 2017
36_{8} Posts 
Quote:
Edit: it's probably this deterministic ECM algorithm? Last fiddled with by mathPuzzles on 20190201 at 23:49 Reason: Added reference link 

20190201, 23:47  #11  
Mar 2017
2×3×5 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
OpenCL GPU P1 Factoring and ECM Factoring  xx005fs  GPU Computing  3  20181027 14:49 
Magnitude 5.6 Earthquake in Silicon Valley  ewmayer  Science & Technology  66  20080731 15:30 
P1 factoring != "Mersenne numbers to factor"?  James Heinrich  Marin's Mersennearies  8  20040517 11:09 
Shortest time to complete a 2^67 trial factor (no factor)  dsouza123  Software  12  20030821 18:38 
Factoring from the factor1  jocelynl  Math  12  20030627 01:24 