mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2019-01-31, 23:38   #1
mathPuzzles
 
Mar 2017

2×3×5 Posts
Default 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
mathPuzzles is offline   Reply With Quote
Old 2019-01-31, 23:46   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

24·83 Posts
Default

Quote:
Originally Posted by mathPuzzles View Post
We have a composite number N on the order of \(2^{4096}\) bits.
And how do you store it?
R. Gerbicz is offline   Reply With Quote
Old 2019-01-31, 23:54   #3
mathPuzzles
 
Mar 2017

2·3·5 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
And how do you store it?
Ha! My mistake, N is 4096 bits, not \(2^{4096}\). Big difference!
mathPuzzles is offline   Reply With Quote
Old 2019-01-31, 23:59   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

100011000110112 Posts
Default

"Lasciate ogne speranza, voi ch'intrate"
Batalov is offline   Reply With Quote
Old 2019-02-01, 02:35   #5
axn
 
axn's Avatar
 
Jun 2003

2×3×757 Posts
Default

Quote:
Originally Posted by mathPuzzles View Post
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.
axn is offline   Reply With Quote
Old 2019-02-01, 02:44   #6
mathPuzzles
 
Mar 2017

2×3×5 Posts
Default

Quote:
Originally Posted by axn View Post
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.
mathPuzzles is offline   Reply With Quote
Old 2019-02-01, 03:54   #7
axn
 
axn's Avatar
 
Jun 2003

2×3×757 Posts
Default

Quote:
Originally Posted by mathPuzzles View Post
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.
axn is offline   Reply With Quote
Old 2019-02-01, 05:22   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·29·101 Posts
Default

Quote:
Originally Posted by mathPuzzles View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2019-02-01, 16:49   #9
chris2be8
 
chris2be8's Avatar
 
Sep 2009

33×5×13 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2019-02-01, 23:43   #10
mathPuzzles
 
Mar 2017

368 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
mathPuzzles is offline   Reply With Quote
Old 2019-02-01, 23:47   #11
mathPuzzles
 
Mar 2017

2×3×5 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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".
mathPuzzles is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
OpenCL GPU P-1 Factoring and ECM Factoring xx005fs GPU Computing 3 2018-10-27 14:49
Magnitude 5.6 Earthquake in Silicon Valley ewmayer Science & Technology 66 2008-07-31 15:30
P-1 factoring != "Mersenne numbers to factor"? James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38
Factoring from the factor-1 jocelynl Math 12 2003-06-27 01:24

All times are UTC. The time now is 21:57.

Thu Apr 9 21:57:59 UTC 2020 up 15 days, 19:31, 1 user, load averages: 1.91, 1.69, 1.72

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.