mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2016-05-27, 03:33   #1
siegert81
 
Dec 2010

2×37 Posts
Default 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
siegert81 is offline   Reply With Quote
Old 2016-05-27, 04:13   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2016-05-27, 07:32   #3
siegert81
 
Dec 2010

2×37 Posts
Default

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
siegert81 is offline   Reply With Quote
Old 2016-05-27, 14:01   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101011011102 Posts
Default

Quote:
Originally Posted by siegert81 View Post
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.)
bsquared is offline   Reply With Quote
Old 2016-05-27, 18:25   #5
siegert81
 
Dec 2010

2·37 Posts
Default

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).
siegert81 is offline   Reply With Quote
Old 2016-05-27, 19:36   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by siegert81 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2016-05-27, 20:15   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×32×191 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
bsquared is offline   Reply With Quote
Old 2016-05-28, 02:00   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100100111011002 Posts
Default

Quote:
Originally Posted by bsquared View Post
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/
LaurV is offline   Reply With Quote
Old 2016-05-28, 07:48   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

29BE16 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
xilman is offline   Reply With Quote
Old 2016-05-28, 08:00   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·17·139 Posts
Default

Quote:
Originally Posted by xilman View Post
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
LaurV is offline   Reply With Quote
Old 2016-05-28, 16:29   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×13×137 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A simple idea for factoring numbers ThiloHarich Factoring 15 2017-03-06 11:23
Simple Script to get Trial Factoring Work jfamestad PrimeNet 3 2016-11-06 20:32
2014 Challenge Questions sean Puzzles 1 2014-07-20 20:24
Factoring Challenge in TAOCP Random Poster Factoring 74 2012-09-18 22:56
Regards RSA factoring challenge 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

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