20160527, 03:33  #1 
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 20100 digits long? (Assume the smallest prime factor is greater than 1,000,000) Last fiddled with by siegert81 on 20160527 at 03:36 
20160527, 07:32  #3 
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 20160527 at 07:32 
20160527, 14:01  #4 
"Ben"
Feb 2007
110101101110_{2} Posts 

20160527, 18:25  #5 
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). 
20160527, 19:36  #6 
Aug 2006
3^{2}×5×7×19 Posts 

20160527, 20:15  #7 
"Ben"
Feb 2007
2×3^{2}×191 Posts 
The crossover point is of course dependent on implementation and platform. I've seen numbers anywhere from 90ish 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 rebenchmarked since then.

20160528, 02:00  #8  
Romulan Interpreter
Jun 2011
Thailand
10010011101100_{2} Posts 
Quote:
Yes, we benchmarked it in all situations . We love yafu! Last fiddled with by LaurV on 20160528 at 02:05 Reason: s/nor/not/ 

20160528, 07:48  #9  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
29BE_{16} Posts 
Quote:
Fifteen years ago a bunch of us factored 2,166L.c135 with QS. Most of us used my tripleprime variation of the venerable MPQS which had been used for RSA129 but Sam Wagstaff used his own implementation of SIQS modified to find triple large prime relations. Paul 

20160528, 08:00  #10  
Romulan Interpreter
Jun 2011
Thailand
2^{2}·17·139 Posts 
Quote:


20160528, 16:29  #11 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2×3×13×137 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A simple idea for factoring numbers  ThiloHarich  Factoring  15  20170306 11:23 
Simple Script to get Trial Factoring Work  jfamestad  PrimeNet  3  20161106 20:32 
2014 Challenge Questions  sean  Puzzles  1  20140720 20:24 
Factoring Challenge in TAOCP  Random Poster  Factoring  74  20120918 22:56 
Regards RSA factoring challenge  koders333  Factoring  5  20060328 13:50 