mersenneforum.org Factoring 110 digits in 38 hours !
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2013-09-04, 08:40 #1 mohamed   Jul 2013 3·5 Posts Factoring 110 digits in 38 hours ! I have been running msieve151 (last version) and trying to factor a 110-digits number, it managed to find the 2 factors but the problem is it took too much time (about 40 hours ) ,, which means i will wait forever to solve a 170-digit number.My Questions are: -Is this normal ? my computer is i7 with 8 gigabytes Ram ,, running windows 7 64-bit -How can i optimize this tool to get it more efficient,, i quote this from another thread : ******************************************************************************************************************* firejuggler to give you an idea: A modern CPU and working on 3 core-one computer-. a C110-C115 is a matter of 2 or 3 hours, a C115-C120 half a day; C120-C125 a day, C125-C130 two to three day, C130-C135 a week... roughly doubling the time for 5 or 6 digits. prgamma10 With both cores of my Core i5 (64-bit ASM siever), a GNFS 125 job takes a day, and a GNFS 135 job takes 3 days (poly selection time included). ******************************************************************************************************************* I dont know why did it take all this time although it solved the 100-digit number in about 4 hours only!also 4 hours is much time but even doubling it twice doesn't reach this 40 hours range.. Last fiddled with by mohamed on 2013-09-04 at 08:41
 2013-09-04, 11:37 #2 prgamma10     Jan 2013 10910 Posts You should not use the siever in Msieve anyway. People use the factmsieve.py script (and a combination of GGNFS and Msieve) for small numbers (95-140 digits). Last fiddled with by prgamma10 on 2013-09-04 at 11:41
 2013-09-04, 13:15 #3 jcrombie     "Jonathan" Jul 2010 In a tangled web... D616 Posts I found this site quite useful when I was first starting out factoring > 100 digits numbers.
 2013-09-04, 13:32 #4 wombatman I moo ablest echo power!     May 2013 5·349 Posts Seconding Jeff Gilchrist's site as a fantastic starting point. Once you understand that stuff, you can start playing around with other options.
 2013-09-04, 16:29 #5 jasonp Tribal Bullet     Oct 2004 2·29·61 Posts Actually if you just use Msieve with no options, you would be using the quadratic sieve to factor a 110-digit input. The line sieve in Msieve doesn't even work anymore. Last fiddled with by jasonp on 2013-09-04 at 16:29 Reason: speeling
 2013-09-05, 09:52 #6 mohamed   Jul 2013 1510 Posts Could you please tell me how to use options ? or where to start reading about how to control this tool because i found many stuff but i got stuck and couldn't reach what is the starting point to fully understand this fantastic tool..
2013-09-05, 10:57   #7
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by mohamed Could you please tell me how to use options ? or where to start reading about how to control this tool because i found many stuff but i got stuck and couldn't reach what is the starting point to fully understand this fantastic tool..
Learn how the underlying algorithms work. You can't understand
what the options and parameters mean without understanding
the algorithm.

Do you know how to use command line driven software? e.g. how to
list the options by invoking the help option?

2013-09-05, 11:58   #8
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101010112 Posts

Quote:
 Originally Posted by mohamed I have been running msieve151 (last version) and trying to factor a 110-digits number, it managed to find the 2 factors but the problem is it took too much time (about 40 hours ) ,, which means i will wait forever to solve a 170-digit number.My Questions are:
A 170-digit number is extremely difficult. See http://www.mersenneforum.org/showthread.php?t=14026 (take note of the log in the attachment at http://www.mersenneforum.org/showthr...111#post236111, it should have some memory usage figures that you'll want to take note of) for a team effort to GNFS (General Number Field Sieve) a c170 (170-digit composite number). You can rerun a small portion of the test to get an idea of how long such a thing would take on your single CPU (and remember that you can run one instance of the siever on each core).

 2013-09-05, 19:00 #9 jasonp Tribal Bullet     Oct 2004 2·29·61 Posts See also the Readme files here. If you downloaded one of the binary releases from sourceforge.net then you should have them already.
 2013-09-07, 09:47 #10 mohamed   Jul 2013 F16 Posts Good news(for me actually) is that when I used cuda the time needed decreased to 2.5 hours only ! (what a significant performance increase),, using GPU 0 (GeForce GTX 560) Here is some info Number: example Code: N = 33319100065905904618088073943717337775739127140720065000985127089174658538966168614190493840451006968337649739 (110 digits) Divisors found: r1=2425967623052370772757633156976982469681 (pp40) r2=4384165182867240584805930970951575013697 (pp40) r3=53542885039615245271174355315623704334284773568199 (pp50) r4=622288097498926496141095869268883999563096063592498055290461 (pp60) Version: Msieve v. 1.51 (SVN unknown) Total time: 2.28 hours. Factorization parameters were as follows: n: 33319100065905904618088073943717337775739127140720065000985127089174658538966168614190493840451006968337649739 Y0: -836927139885417757727 Y1: 104390864471 c0: -2609428838573120977025316 c1: 6455109638585727585738 c2: 605367217999925363 c3: -73299778283069 c4: -2107091359 c5: 81144 skew: 15521.55 type: gnfs Factor base limits: 3200000/3200000 Large primes per side: 3 Large prime bits: 27/27 Sieved algebraic special-q in [0, 0) Total raw relations: 8256248 Relations: 537820 relations Pruned matrix : 330082 x 330307 Polynomial selection time: 0.10 hours. Total sieving time: 2.07 hours. Total relation processing time: 0.03 hours. Matrix solve time: 0.05 hours. time per square root: 0.02 hours. Prototype def-par.txt line would be: gnfs,109,5,61,2000,0.00015,0.3,250,15,50000,2400,3200000,3200000,27,27,50,50,2.6,2.6,100000 total time: 2.28 hours. Intel64 Family 6 Model 45 Stepping 7, GenuineIntel Windows-7-6.1.7600 processors: 8, speed: 3.60GHz actually I have 2 cuda cards,, is it available to use both of them during the same run ? how ? I am reading now more about msieve and the algorithms it uses ,, i am a fresh graduate from faculty of engineering so i have a lot to read (a lot really!) Thanks all for your help and if anyone told me how to enable using both card it would be great really.. Last fiddled with by wblipp on 2013-09-10 at 17:21 Reason: Added code box
 2013-09-08, 06:28 #11 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2×2,393 Posts CUDA only helps with polynomial selection. Yes, in principle you could use two CUDA cards with two separate copies of msieve running- but look at the amount of time you spent on poly select in this example; it's not worth the effort to manually run poly select on two cards until perhaps C145 or bigger.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Przem Information & Answers 3 2015-10-06 15:16 xorbe LMH > 100M 189 2010-12-09 08:30 abc_temp Factoring 14 2007-12-23 20:25 Damian Lounge 8 2005-06-02 18:36 Kimmy Hardware 4 2004-12-29 01:48

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

Sat May 15 14:21:33 UTC 2021 up 37 days, 9:02, 0 users, load averages: 1.19, 1.52, 1.69

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.