mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2013-09-04, 08:40   #1
mohamed
 
Jul 2013

3·5 Posts
Exclamation 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
mohamed is offline   Reply With Quote
Old 2013-09-04, 11:37   #2
prgamma10
 
prgamma10's Avatar
 
Jan 2013

10910 Posts
Default

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
prgamma10 is offline   Reply With Quote
Old 2013-09-04, 13:15   #3
jcrombie
 
jcrombie's Avatar
 
"Jonathan"
Jul 2010
In a tangled web...

D616 Posts
Default

I found this site quite useful when I was first starting out factoring > 100 digits numbers.
jcrombie is offline   Reply With Quote
Old 2013-09-04, 13:32   #4
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5·349 Posts
Default

Seconding Jeff Gilchrist's site as a fantastic starting point. Once you understand that stuff, you can start playing around with other options.
wombatman is offline   Reply With Quote
Old 2013-09-04, 16:29   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·29·61 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2013-09-05, 09:52   #6
mohamed
 
Jul 2013

1510 Posts
Default

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..
mohamed is offline   Reply With Quote
Old 2013-09-05, 10:57   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by mohamed View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2013-09-05, 11:58   #8
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101010112 Posts
Default

Quote:
Originally Posted by mohamed View Post
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).
Mini-Geek is offline   Reply With Quote
Old 2013-09-05, 19:00   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·29·61 Posts
Default

See also the Readme files here. If you downloaded one of the binary releases from sourceforge.net then you should have them already.
jasonp is offline   Reply With Quote
Old 2013-09-07, 09:47   #10
mohamed
 
Jul 2013

F16 Posts
Default

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
mohamed is offline   Reply With Quote
Old 2013-09-08, 06:28   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×2,393 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime95 - hours per day question Przem Information & Answers 3 2015-10-06 15:16
100M digits, how much trial factoring will it do? xorbe LMH > 100M 189 2010-12-09 08:30
Factoring 132-digits Number abc_temp Factoring 14 2007-12-23 20:25
10.000.000 digits prime factoring Damian Lounge 8 2005-06-02 18:36
No progress indication for the last 12 hours. 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.