Factoring when one factor's magnitude is known

[mathPuzzles]

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?

[R. Gerbicz]

Originally Posted by mathPuzzles

We have a composite number N on the order of \(2^{4096}\) bits.

And how do you store it?

[mathPuzzles]

Originally Posted by R. Gerbicz

And how do you store it?

Ha! My mistake, N is 4096 bits, not \(2^{4096}\). Big difference!

[Batalov]

"Lasciate ogne speranza, voi ch'intrate"

[axn]

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.

[mathPuzzles]

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.

[axn]

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.

[CRGreathouse]

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.

[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).

Chris

[mathPuzzles]

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?

[mathPuzzles]

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".