Factoring 110 digits in 38 hours !

mohamed · 2013-09-04, 08:40

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..

prgamma10 · 2013-09-04, 11:37

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).

jcrombie · 2013-09-04, 13:15

I found this site quite useful when I was first starting out factoring > 100 digits numbers.

wombatman · 2013-09-04, 13:32

Seconding Jeff Gilchrist's site as a fantastic starting point. Once you understand that stuff, you can start playing around with other options.

jasonp · 2013-09-04, 16:29

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.

mohamed · 2013-09-05, 09:52

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..

R.D. Silverman · 2013-09-05, 10:57

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?

Mini-Geek · 2013-09-05, 11:58

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).

jasonp · 2013-09-05, 19:00

See also the Readme files here. If you downloaded one of the binary releases from sourceforge.net then you should have them already.

mohamed · 2013-09-07, 09:47

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..

VBCurtis · 2013-09-08, 06:28

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.

2013-09-04, 08:40	#1
mohamed Jul 2013 15₁₀ 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 109 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, 16:29	#5
jasonp Tribal Bullet Oct 2004 3,541 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

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

2013-09-04, 13:15	#3
jcrombie "Jonathan" Jul 2010 In a tangled web... 5×43 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 29×61 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-05, 09:52	#6
mohamed Jul 2013 3·5 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, 19:00	#9
jasonp Tribal Bullet Oct 2004 3,541 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-08, 06:28	#11
VBCurtis "Curtis" Feb 2005 Riverside, CA 1001011111101₂ 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.