Something that always bothered me:

3.14159 · 2010-05-28, 00:23

How a prime square will be factored instantly, but a semiprime won't.

Ex: 438190746132064523680359691464734744483214502885929539054808778130318905370682196955192091850205041234129084385881 = 661959776823384128858607768192010463436677049149657043109² Would be found in under half a second

246090902435728443147794225059123680177312909574781907744990390550902712459821618259887515603771941862490471935777 = 609730809803503522343684492396608771943181991097776558309 * 403605818303712690533169288723930453642200445195683040653

Would take days to factor.

I find this very disturbing.
Very disturbing.

Wacky · 2010-05-28, 00:45

Consider factoring by Fermat's Method.

For N = cd, let c be the largest subroot factor.
If N has a factor close to its square-root, the method works quickly. More precisely, if c differs less than (4N)^1/4 from (N)^1/2 the method requires only one step. Note, that this is independent of the size of N.

In the former case, the difference is zero.
In the latter case, it is large. Either more steps would be required, or a different method is needed. By either approach, the computation is longer.

philmoore · 2010-05-28, 03:15

Several factoring methods only work if the number to be factored is known not to be a prime power, i.e., it is known to have at least two distinct prime factors. Therefore, before trying one of these methods, a check is made that the number is not a perfect square, cube, etc. This can be done quickly compared to the time it will take to actually factor it.

Mini-Geek · 2010-05-28, 03:33

I know the chances of actually running into a large prime power is astronomically low when dealing with large numbers as encountered in aliquot sequences of Cunningham tables (or the like), but do any of the normal automated tools do any check of this at all? Or, for the factoring tables, has a check been done? Considering the low cost, (if I understand correctly, it's pretty quick for checking a narrow range of factors, just like TF is, but for the opposite end of size: where TF looks for very small factors, Fermat's method looks for ones near sqrt(N)) would it be worthwhile?

Wacky · 2010-05-28, 03:50

Since we have a polynomial description of each Cunningham number, algebraic methods eliminate any such possibility.

Further, the "simpler" factoring methods, have all been attempted to eliminate any "low-hanging fruit".

The only remaining holes in the Cunningham tables are composed of only factors that are more difficult to find.

philmoore · 2010-05-28, 04:25

But suppose a 225 digit Cunningham number suddenly has a 60 digit factor discovered by ECM. Nothing says that the 165 or so digit cofactor could not be a square of a prime. My understanding is that this is tested before trying GNFS with the current programs. Anyone able to clarify?

10metreh · 2010-05-28, 07:08

I know that msieve checks for prime powers. I don't think the GGNFS sievers do, though.

Mini-Geek · 2010-05-28, 11:46

(all of these are msieve being told, by factmsieve.py, to run polynomial selection:
Where p is 661959776823384128858607768192010463436677049149657043109 (the prime in the example in the first post), and q is the next prime after that (same digits but ending in 81)
the first is p^2,
the second is p*q
the third is p^3,
the fourth is p^2*q)

Code:

Msieve v. 1.44
Fri May 28 06:25:20 2010
random seeds: db891914 67fd9bc5
factoring 438190746132064523680359691464734744483214502885929539054808778130318905370682196955192091
850205041234129084385881 (114 digits)
searching for 15-digit factors
prp57 factor: 661959776823384128858607768192010463436677049149657043109
prp57 factor: 661959776823384128858607768192010463436677049149657043109
elapsed time 00:00:01

Msieve v. 1.44
Fri May 28 06:28:30 2010
random seeds: 586bb268 c9f15c95
factoring 438190746132064523680359691464734744483214502885929539102469882061602562648501956265016845
217645788772904391489729 (114 digits)
searching for 15-digit factors
commencing number field sieve (114-digit input)
commencing number field sieve polynomial selection
time limit set to 1.72 hours
...

Msieve v. 1.44
Fri May 28 06:50:53 2010
random seeds: a84fa7fc 3deedde0
factoring 290064648515653604290850896210557000788223358877016965219834376481563501426743334123375488
518677419822009003459489974639850922949258651900751911554066671289177491607944029 (171 digits)
searching for 15-digit factors
prp57 factor: 661959776823384128858607768192010463436677049149657043109
prp57 factor: 661959776823384128858607768192010463436677049149657043109
prp57 factor: 661959776823384128858607768192010463436677049149657043109
elapsed time 00:00:03

Msieve v. 1.44
Fri May 28 06:53:58 2010
random seeds: 46972700 d092cfad
factoring 290064648515653604290850896210557000788223358877016965251384110203072147131729231908836390
121468864029795930271436206665233884135947770081525742167281434258034785683727461 (171 digits)
searching for 15-digit factors
commencing number field sieve (171-digit input)
commencing number field sieve polynomial selection
time limit set to 300.00 hours
...

As you can see, msieve finds prime powers during its 15-digit factors check, but must not run Fermat's factorization method at all. It also doesn't find p^2*q (not sure if there'd be an easy way for it to). It should be noted that factmsieve.py doesn't handle msieve finding factors correctly, as it doesn't expect msieve to find factors when it tells it to run poly selection.

jasonp · 2010-05-28, 12:23

Msieve uses a very complex recursive factoring framework; after ECM, factors are dropped into a list but first have any factors in common with other factors in the list removed. Then for every composite in the list it checks whether the composite is a power and if not then runs QS or NFS. If given a number of the form p*p*q, QS or NFS will first find factors of p*p and q, then the recursive framework will split p*p. Unfortunately there is no known way to use the fact that an input contains a factor which is a power, in order to make the factorization faster.

Mini-geek is correct, Fermat's method is not implemented (nor Lehman's; maybe someday I should fix that; alpertron's applet uses it though, and for inputs where Lehman's method works it's much faster than any of the heavy artillery that msieve uses).

3.14159 · 2010-05-29, 01:14

Factoring the following: c(80, 82, 84, 86, 88, 90, 94, 98, 102, 106, 110, 116, 122, 128, 134, 140)

c80 = 45261371639976440147856072490845590811635113169755543286071538119010508358468757.
/used QS:

Code:

SIQS parameters: 18617 primes, sieve limit: 76968
Multiplier: 2, factor base: 441937

Factors: 4545628859816454389520488213755833214847 and 9957119913613894514260462174988378455531

3.14159 · 2010-05-29, 12:39

"I know the chances of actually running into a large prime power is astronomically low when dealing with large numbers"

Self-explanatory.

2010-05-28, 00:23	#1
3.14159 May 2010 Prime hunting commission. 1680₁₀ Posts	Something that always bothered me: How a prime square will be factored instantly, but a semiprime won't. Ex: 438190746132064523680359691464734744483214502885929539054808778130318905370682196955192091850205041234129084385881 = 661959776823384128858607768192010463436677049149657043109² Would be found in under half a second 246090902435728443147794225059123680177312909574781907744990390550902712459821618259887515603771941862490471935777 = 609730809803503522343684492396608771943181991097776558309 * 403605818303712690533169288723930453642200445195683040653 Would take days to factor. I find this very disturbing. Very disturbing.

2010-05-28, 12:23	#9
jasonp Tribal Bullet Oct 2004 3·1,181 Posts	Msieve uses a very complex recursive factoring framework; after ECM, factors are dropped into a list but first have any factors in common with other factors in the list removed. Then for every composite in the list it checks whether the composite is a power and if not then runs QS or NFS. If given a number of the form ppq, QS or NFS will first find factors of pp and q, then the recursive framework will split pp. Unfortunately there is no known way to use the fact that an input contains a factor which is a power, in order to make the factorization faster. Mini-geek is correct, Fermat's method is not implemented (nor Lehman's; maybe someday I should fix that; alpertron's applet uses it though, and for inputs where Lehman's method works it's much faster than any of the heavy artillery that msieve uses). Last fiddled with by jasonp on 2010-05-28 at 12:27

2010-05-29, 01:14	#10
3.14159 May 2010 Prime hunting commission. 2⁴·3·5·7 Posts	Factoring the following: c(80, 82, 84, 86, 88, 90, 94, 98, 102, 106, 110, 116, 122, 128, 134, 140) c80 = 45261371639976440147856072490845590811635113169755543286071538119010508358468757. /used QS: Code: SIQS parameters: 18617 primes, sieve limit: 76968 Multiplier: 2, factor base: 441937 Factors: 4545628859816454389520488213755833214847 and 9957119913613894514260462174988378455531 Last fiddled with by 3.14159 on 2010-05-29 at 01:25

2010-05-28, 00:45	#2
Wacky Jun 2003 The Texas Hill Country 441₁₆ Posts	Consider factoring by Fermat's Method. For N = cd, let c be the largest subroot factor. If N has a factor close to its square-root, the method works quickly. More precisely, if c differs less than (4N)^1/4 from (N)^1/2 the method requires only one step. Note, that this is independent of the size of N. In the former case, the difference is zero. In the latter case, it is large. Either more steps would be required, or a different method is needed. By either approach, the computation is longer.

2010-05-28, 03:15	#3
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 10001011111₂ Posts	Several factoring methods only work if the number to be factored is known not to be a prime power, i.e., it is known to have at least two distinct prime factors. Therefore, before trying one of these methods, a check is made that the number is not a perfect square, cube, etc. This can be done quickly compared to the time it will take to actually factor it.

2010-05-28, 03:33	#4
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 17×251 Posts	I know the chances of actually running into a large prime power is astronomically low when dealing with large numbers as encountered in aliquot sequences of Cunningham tables (or the like), but do any of the normal automated tools do any check of this at all? Or, for the factoring tables, has a check been done? Considering the low cost, (if I understand correctly, it's pretty quick for checking a narrow range of factors, just like TF is, but for the opposite end of size: where TF looks for very small factors, Fermat's method looks for ones near sqrt(N)) would it be worthwhile?

2010-05-28, 03:50	#5
Wacky Jun 2003 The Texas Hill Country 10001000001₂ Posts	Since we have a polynomial description of each Cunningham number, algebraic methods eliminate any such possibility. Further, the "simpler" factoring methods, have all been attempted to eliminate any "low-hanging fruit". The only remaining holes in the Cunningham tables are composed of only factors that are more difficult to find.

2010-05-28, 04:25	#6
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3·373 Posts	But suppose a 225 digit Cunningham number suddenly has a 60 digit factor discovered by ECM. Nothing says that the 165 or so digit cofactor could not be a square of a prime. My understanding is that this is tested before trying GNFS with the current programs. Anyone able to clarify?

2010-05-28, 07:08	#7
10metreh Nov 2008 912₁₆ Posts	I know that msieve checks for prime powers. I don't think the GGNFS sievers do, though.

2010-05-29, 12:39	#11
3.14159 May 2010 Prime hunting commission. 1680₁₀ Posts	"I know the chances of actually running into a large prime power is astronomically low when dealing with large numbers" Self-explanatory.