mersenneforum.org Simple factoring challenge + questions
 Register FAQ Search Today's Posts Mark Forums Read

 2016-05-27, 03:33 #1 siegert81   Dec 2010 2×37 Posts Simple factoring challenge + questions Can anybody factor this number? 684546173393988695179580947496349194528189263072759549878869521320029 If so, what program(s)/method(s) did you use, and how fast were you able to factor it? What's the quickest way to factor "random" large integers that are 20-100 digits long? (Assume the smallest prime factor is greater than 1,000,000) Last fiddled with by siegert81 on 2016-05-27 at 03:36
 2016-05-27, 04:13 #2 CRGreathouse     Aug 2006 32·5·7·19 Posts yafu is a good tool for plug-and-play factoring. In this case it factors the number in 38 seconds into a P30 times a P40.
 2016-05-27, 07:32 #3 siegert81   Dec 2010 2×37 Posts When I used the siqs command, yafu found the factors in 1.2792 seconds. Last fiddled with by siegert81 on 2016-05-27 at 07:32
2016-05-27, 14:01   #4
bsquared

"Ben"
Feb 2007

1101011011102 Posts

Quote:
 Originally Posted by siegert81 When I used the siqs command, yafu found the factors in 1.2792 seconds.
Likely it reused old sieving data with that timing. (yafu keeps the data file, siqs.dat, until a new number is run, so that if a number is re-factored it can reuse the old data.)

 2016-05-27, 18:25 #5 siegert81   Dec 2010 2·37 Posts Yes, that's what I concluded today after using other numbers as input. It takes about 35 seconds to factor a P30 x P40. It took over 4 minutes to factor a P40 x P40. Still, I'm left wondering which algorithms are the fastest for integers less than 10^100. I don't need any numbers factored. I'm just trying to understand the current state of number theory as it relates to optimally factoring integers of this size. My understanding is that the GNFS is the best for larger numbers (like the RSA challenge numbers).
2016-05-27, 19:36   #6
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by siegert81 Still, I'm left wondering which algorithms are the fastest for integers less than 10^100.
SIQS for most hard numbers in that range. As I understand SIQS implementations have pushed the crossover point to 105+ digits.

2016-05-27, 20:15   #7
bsquared

"Ben"
Feb 2007

2×32×191 Posts

Quote:
 Originally Posted by CRGreathouse SIQS for most hard numbers in that range. As I understand SIQS implementations have pushed the crossover point to 105+ digits.
The crossover point is of course dependent on implementation and platform. I've seen numbers anywhere from 90-ish to 105+. As far as I'm aware, the SIQS implementation in yafu is the fastest available and I've measured it at about 95 digits (linux, 64bit, with SSE4.1). Although that was before I added AVX2 improvements... haven't re-benchmarked since then.

2016-05-28, 02:00   #8
LaurV
Romulan Interpreter

Jun 2011
Thailand

100100111011002 Posts

Quote:
 Originally Posted by bsquared The crossover point is of course dependent on implementation and platform. I've seen numbers anywhere from 90-ish to 105+. As far as I'm aware, the SIQS implementation in yafu is the fastest available and I've measured it at about 95 digits (linux, 64bit, with SSE4.1). Although that was before I added AVX2 improvements... haven't re-benchmarked since then.
We subscribe to this. Yafu's SIQS is bloody fast, we even ran SIQS on numbers of ~115++ digits for fun in the past - there is an old thread here around, about SIQS records, Ben (bsquared) has the one for ~130 digits or so, which is the world record. Currently, in our still surviving 4 computers we have crossovers at 98/99, 99/99, 99/99, 101/102. The 101/102 is a i7-2600k running at 3G8. The two numbers represent Prime95 running or not in background, and/or using the "-p" or not when we run aliqueit.exe (clarification, that is the switch for lowest priority of aliqueit and the tasks launched by it, including yafu). The same computer used to give us in the past, with different configurations and other yafu versions, crossover points like 105/106.

Yes, we benchmarked it in all situations .

We love yafu!

Last fiddled with by LaurV on 2016-05-28 at 02:05 Reason: s/nor/not/

2016-05-28, 07:48   #9
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

29BE16 Posts

Quote:
 Originally Posted by LaurV We subscribe to this. Yafu's SIQS is bloody fast, we even ran SIQS on numbers of ~115++ digits for fun in the past - there is an old thread here around, about SIQS records, Ben (bsquared) has the one for ~130 digits or so, which is the world record.
World record for pure SIQS or world record for QS generally?

Fifteen years ago a bunch of us factored 2,166L.c135 with QS. Most of us used my triple-prime variation of the venerable MPQS which had been used for RSA-129 but Sam Wagstaff used his own implementation of SIQS modified to find triple large prime relations.

Paul

2016-05-28, 08:00   #10
LaurV
Romulan Interpreter

Jun 2011
Thailand

22·17·139 Posts

Quote:
 Originally Posted by xilman World record for pure SIQS or world record for QS generally? Fifteen years ago a bunch of us factored 2,1606L.c135 with QS. Most of us used my triple-prime variation of the venerable MPQS which had been used for RSA-129 but Sam Wagstaff used his own implementation of SIQS modified to find triple large prime relations. Paul
Fixed that for you. The rest, we agree

2016-05-28, 16:29   #11
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×3×13×137 Posts

Quote:
 Originally Posted by LaurV Fixed that for you. The rest, we agree
Thanks. A simple tyop which I failed to pick up before submitting.

 Similar Threads Thread Thread Starter Forum Replies Last Post ThiloHarich Factoring 15 2017-03-06 11:23 jfamestad PrimeNet 3 2016-11-06 20:32 sean Puzzles 1 2014-07-20 20:24 Random Poster Factoring 74 2012-09-18 22:56 koders333 Factoring 5 2006-03-28 13:50

All times are UTC. The time now is 18:18.

Mon May 17 18:18:40 UTC 2021 up 39 days, 12:59, 0 users, load averages: 2.97, 2.62, 2.57