MSieve 1.45 Polyselection question (154 Digit Num)

Carlo · 2010-07-15, 20:30

Hi Jeff,

I read your article at http://gilchrist.ca/jeff/factoring/nfs_msieve_poly_guide.html
and I'm trying to use the factmsieve.py script with a 154 digit number. I'm using
a CUDA enable nVidia GPU for the poly selection.

It has been running a few days longer than the 287.50hr time limit that was displayed
by the script/msieve. Is this to be expected?

I've attached some of the output, so you can see what I mean:

Tue Jun 29 16:32:05 2010 -> factmsieve.py (v0.72)
Tue Jun 29 16:32:05 2010 -> This is client 1 of 1
Tue Jun 29 16:32:05 2010 -> Using 4 threads
Tue Jun 29 16:32:05 2010 -> Working with NAME = bmw_mode_85
Tue Jun 29 16:32:05 2010 -> Running polynomial selection ...
Tue Jun 29 16:32:05 2010
Tue Jun 29 16:32:05 2010
Tue Jun 29 16:32:05 2010 Msieve v. 1.45
Tue Jun 29 16:32:05 2010 random seeds: 5d81c030 bbab83df
Tue Jun 29 16:32:05 2010 factoring 8224973201493734039216932833462996815932154044113673505636726252834676063695616729466358005376619469264571014058650019804568205019013693877262015651491183 (154 digits)
Tue Jun 29 16:32:06 2010 searching for 15-digit factors
Tue Jun 29 16:32:06 2010 commencing number field sieve (154-digit input)
Tue Jun 29 16:32:06 2010 commencing number field sieve polynomial selection
Tue Jun 29 16:32:06 2010 time limit set to 287.50 hours
Tue Jun 29 16:32:06 2010 searching leading coefficients from 1 to 1654380
Tue Jun 29 16:32:07 2010 using GPU 0 (GeForce GTX 470)
Tue Jun 29 17:01:51 2010 -> factmsieve.py (v0.72)
Tue Jun 29 17:01:51 2010 -> This is client 1 of 1
Tue Jun 29 17:01:51 2010 -> Using 4 threads
Tue Jun 29 17:01:51 2010 -> Working with NAME = bmw_mode_85
Tue Jun 29 17:01:51 2010 -> Running polynomial selection ...
Tue Jun 29 17:01:52 2010
Tue Jun 29 17:01:52 2010
Tue Jun 29 17:01:52 2010 Msieve v. 1.45
Tue Jun 29 17:01:52 2010 random seeds: c12175f0 f37de101
Tue Jun 29 17:01:52 2010 factoring 8224973201493734039216932833462996815932154044113673505636726252834676063695616729466358005376619469264571014058650019804568205019013693877262015651491183 (154 digits)
Tue Jun 29 17:01:53 2010 searching for 15-digit factors
Tue Jun 29 17:01:54 2010 commencing number field sieve (154-digit input)
Tue Jun 29 17:01:54 2010 commencing number field sieve polynomial selection
Tue Jun 29 17:01:54 2010 time limit set to 287.50 hours
Tue Jun 29 17:01:54 2010 searching leading coefficients from 1 to 1654380
Tue Jun 29 17:01:54 2010 using GPU 0 (GeForce 9800 GX2)

Regards,
-Carlo

firejuggler · 2010-07-15, 21:00

did it display things like this ?

Code:

poly  0 p 750137 q 1050389 coeff 787935653293
poly  0 p 693317 q 1068389 coeff 740732256313
poly  0 p 675449 q 1079003 coeff 728811497347
poly  0 p 796813 q 1092469 coeff 870493501297
poly  0 p 841933 q 1107239 coeff 932221052987
poly  0 p 837293 q 1121117 coeff 938703416281
poly  0 p 747493 q 1129303 coeff 844146087379

Carlo · 2010-07-15, 21:04

It is, it's even writing to the .dat.p file. (Contents below), but it's definitely past the 287.5hr time limit it says it is using (or is that just a rough time limit) ?

The contents of the .p file sofar:

# norm 4.652487e-015 alpha -7.613601 e 2.642e-012
skew: 18058251.88
c0: -654529522189169930540488032966516308151
c1: 61184160880916365847724420771954
c2: 66570932299197610231474221
c3: -53841309728436708176
c4: -105098038628
c5: 9120
Y0: -979553472347178183831585863588
Y1: 213121598011759487
# norm 4.605008e-015 alpha -7.841830 e 2.663e-012
skew: 27107508.52
c0: 11253826979093893808956434377659443684489
c1: 7228468033831610925259126332937574
c2: 206693977832425853550581301
c3: -53406046989987932976
c4: -144808798628
c5: 9120
Y0: -979553657944121812372335117538
Y1: 213121598011759487
# norm 4.659914e-015 alpha -7.702207 e 2.634e-012
skew: 24851565.51
c0: 17580575098092917730496834796705939313665
c1: 6635411622317837728500779130020386
c2: 370264566107818533949030965
c3: -52714778782229282608
c4: -191652037028
c5: 9120
Y0: -979553876876267072324432771106
Y1: 213121598011759487

....

firejuggler · 2010-07-15, 21:09

Maybe it is because it has not found a good enough poly.
Wait for someone more competent than me to answer .
I'm pretty useless here beside basic.

ET_ · 2010-07-15, 22:07

Hi Carlo (can I guess from your name you are from Italy? I am too),

If memory serves, the time shown for polynomial selection (especially when a GPU is used) is just a rough estimate of the time needed; the process is not software timed (consider about 10% of the whole factoring time for polynomial selection). Usually there are 2 methods to check when stopping polyselect: the first is letting the program stop by itself when it terminates its iterations, regardless of the estimate, while the second is stopping it manually after it has written some data on the .p file.

If you skim through the forum you'll be able to find some good values for polynomial selection on C154 values: compare them to the ones written into your file and take your action.

Luigi

jasonp · 2010-07-15, 22:34

It looks like it's running okay. Do I read the output correctly that you are using a new Tesla card? If so, it's nice to know that the code runs on the latest and greatest cards.

The time limit is approximate, it may run a lot longer (I've seen reports of up to 20% longer). It only measures wall-clock time, not the quality of the polynomials found, and the time limit for one value of A5 can get exceeded if it does more work on that A5.

I also ran my much less powerful card on a 512-bit input (RSA512), and in two weeks it found maybe 5 polynomials. The best E-value found was around 3e-12, and this is not all that great considering the amount of work expended.

Carlo · 2010-07-15, 22:45

Well, I tried a GTX470 but that didn't seem to work, I'm using a 9800 GX2 now.

It found about 45 polys in just over two weeks, most of them
all have e values of 2.6e-012.

You figure, I may just as well stop with the poly selection now and
just pick one?

# norm 4.587349e-015 alpha -8.309035 e 2.652e-012
skew: 14306415.97
c0: -15852531439144025442733972847810232310525
c1: 3684988207254928439957337995876115
c2: -27332675829115566654228907
c3: -35792316957219381147
c4: 3280647151364
c5: 78540
Y0: -636805373599577378143689299658
Y1: 350947796784182687

jasonp · 2010-07-16, 02:33

If you've already spent the full two weeks looking for a good polynomial then it would be better to stop now and begin the sieving. Especially if you have more than one machine waiting for the sieving, the savings you will get from a better polynomial will not justify additional time spent with polynomial selection.

Karl M Johnson · 2010-07-16, 05:16

The fact that Msieve's CUDA-enabled poly selection isnt working with Fermi is expected.
All CUDA apps, that were compiler prior to release of Fermis, worked on all future cards.
However, for a certain CUDA app to work on Fermi, it needs to be recompiled with 3.0/3.1 SDK.
What's odd, this doesnt affect OpenCL apps.

asp · 2010-07-16, 16:09

I've used msieve145_gpu with Fermi based cards without issues. There are issues with the NVIDIA drivers though and they do crash. Usually I need to split the range into smaller parts and run multiple instances of msieve145_gpu in parallel in order to load a single card 100%. This is usually because it will stall in the CPU intensive stages for a while which causes about 30 - 40% utilization of the GPU. A single Fermi card generally finds 10 - 14 polys per 24 hours for a 154+ digit semiprime number for me during testing. It's been my experience that you can kill the poly selection with a Murphy score of 2.9e-12 or better and start sieving when dealing with semiprimes around 154 digits.

jrk · 2010-07-16, 22:30

Quote:

Originally Posted by asp

Usually I need to split the range into smaller parts and run multiple instances of msieve145_gpu in parallel in order to load a single card 100%. This is usually because it will stall in the CPU intensive stages for a while which causes about 30 - 40% utilization of the GPU.

The CPU intensive stage might be the stage2 code which optimizes the stage1 hits found by the GPU. Only one stage runs at a time, so the GPU will stall while stage2 is running.

The next version of msieve will have -np1 and -np2 options for running stage1 and stage2 separately. Do you want to try? It is in the latest SVN. When running -np1, msieve will write stage1 results to a file msieve.dat.m, and when running -np2 msieve will read from this file for stage2.

If you still get high CPU utilization (more than 10%) when running with -np1, then you have a really fast GPU and the CPU code simply isn't feeding it fast enough.

Quote:

Originally Posted by asp

A single Fermi card generally finds 10 - 14 polys per 24 hours for a 154+ digit semiprime number for me during testing. It's been my experience that you can kill the poly selection with a Murphy score of 2.9e-12 or better and start sieving when dealing with semiprimes around 154 digits.

For a 512bit number, a 2.9e-12 score is great.

2010-07-15, 20:30	#1
Carlo Jul 2010 8₁₀ Posts	MSieve 1.45 Polyselection question (154 Digit Num) Hi Jeff, I read your article at http://gilchrist.ca/jeff/factoring/nfs_msieve_poly_guide.html and I'm trying to use the factmsieve.py script with a 154 digit number. I'm using a CUDA enable nVidia GPU for the poly selection. It has been running a few days longer than the 287.50hr time limit that was displayed by the script/msieve. Is this to be expected? I've attached some of the output, so you can see what I mean: Tue Jun 29 16:32:05 2010 -> factmsieve.py (v0.72) Tue Jun 29 16:32:05 2010 -> This is client 1 of 1 Tue Jun 29 16:32:05 2010 -> Using 4 threads Tue Jun 29 16:32:05 2010 -> Working with NAME = bmw_mode_85 Tue Jun 29 16:32:05 2010 -> Running polynomial selection ... Tue Jun 29 16:32:05 2010 Tue Jun 29 16:32:05 2010 Tue Jun 29 16:32:05 2010 Msieve v. 1.45 Tue Jun 29 16:32:05 2010 random seeds: 5d81c030 bbab83df Tue Jun 29 16:32:05 2010 factoring 8224973201493734039216932833462996815932154044113673505636726252834676063695616729466358005376619469264571014058650019804568205019013693877262015651491183 (154 digits) Tue Jun 29 16:32:06 2010 searching for 15-digit factors Tue Jun 29 16:32:06 2010 commencing number field sieve (154-digit input) Tue Jun 29 16:32:06 2010 commencing number field sieve polynomial selection Tue Jun 29 16:32:06 2010 time limit set to 287.50 hours Tue Jun 29 16:32:06 2010 searching leading coefficients from 1 to 1654380 Tue Jun 29 16:32:07 2010 using GPU 0 (GeForce GTX 470) Tue Jun 29 17:01:51 2010 -> factmsieve.py (v0.72) Tue Jun 29 17:01:51 2010 -> This is client 1 of 1 Tue Jun 29 17:01:51 2010 -> Using 4 threads Tue Jun 29 17:01:51 2010 -> Working with NAME = bmw_mode_85 Tue Jun 29 17:01:51 2010 -> Running polynomial selection ... Tue Jun 29 17:01:52 2010 Tue Jun 29 17:01:52 2010 Tue Jun 29 17:01:52 2010 Msieve v. 1.45 Tue Jun 29 17:01:52 2010 random seeds: c12175f0 f37de101 Tue Jun 29 17:01:52 2010 factoring 8224973201493734039216932833462996815932154044113673505636726252834676063695616729466358005376619469264571014058650019804568205019013693877262015651491183 (154 digits) Tue Jun 29 17:01:53 2010 searching for 15-digit factors Tue Jun 29 17:01:54 2010 commencing number field sieve (154-digit input) Tue Jun 29 17:01:54 2010 commencing number field sieve polynomial selection Tue Jun 29 17:01:54 2010 time limit set to 287.50 hours Tue Jun 29 17:01:54 2010 searching leading coefficients from 1 to 1654380 Tue Jun 29 17:01:54 2010 using GPU 0 (GeForce 9800 GX2) Regards, -Carlo

2010-07-15, 22:34	#6
jasonp Tribal Bullet Oct 2004 3×1,181 Posts	It looks like it's running okay. Do I read the output correctly that you are using a new Tesla card? If so, it's nice to know that the code runs on the latest and greatest cards. The time limit is approximate, it may run a lot longer (I've seen reports of up to 20% longer). It only measures wall-clock time, not the quality of the polynomials found, and the time limit for one value of A5 can get exceeded if it does more work on that A5. I also ran my much less powerful card on a 512-bit input (RSA512), and in two weeks it found maybe 5 polynomials. The best E-value found was around 3e-12, and this is not all that great considering the amount of work expended. Last fiddled with by jasonp on 2010-07-15 at 22:39

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve v. 1.47 and 148 digit composite	Unregistered	Information & Answers	8	2010-10-04 07:31
Quick msieve question	alkirah	Msieve	2	2009-12-30 14:00
222-digit SNFS completed with msieve	frmky	Factoring	2	2007-10-01 18:23
Question about cycle counting in MSieve	schickel	Msieve	3	2006-11-25 07:14
MSieve - problem with 106-digit effort	schickel	Msieve	5	2006-08-31 03:19

2010-07-15, 21:04	#3
Carlo Jul 2010 1000₂ Posts	It is, it's even writing to the .dat.p file. (Contents below), but it's definitely past the 287.5hr time limit it says it is using (or is that just a rough time limit) ? The contents of the .p file sofar: # norm 4.652487e-015 alpha -7.613601 e 2.642e-012 skew: 18058251.88 c0: -654529522189169930540488032966516308151 c1: 61184160880916365847724420771954 c2: 66570932299197610231474221 c3: -53841309728436708176 c4: -105098038628 c5: 9120 Y0: -979553472347178183831585863588 Y1: 213121598011759487 # norm 4.605008e-015 alpha -7.841830 e 2.663e-012 skew: 27107508.52 c0: 11253826979093893808956434377659443684489 c1: 7228468033831610925259126332937574 c2: 206693977832425853550581301 c3: -53406046989987932976 c4: -144808798628 c5: 9120 Y0: -979553657944121812372335117538 Y1: 213121598011759487 # norm 4.659914e-015 alpha -7.702207 e 2.634e-012 skew: 24851565.51 c0: 17580575098092917730496834796705939313665 c1: 6635411622317837728500779130020386 c2: 370264566107818533949030965 c3: -52714778782229282608 c4: -191652037028 c5: 9120 Y0: -979553876876267072324432771106 Y1: 213121598011759487 ....

2010-07-15, 21:09	#4
firejuggler Apr 2010 Over the rainbow 2·1,303 Posts	Maybe it is because it has not found a good enough poly. Wait for someone more competent than me to answer . I'm pretty useless here beside basic.

2010-07-15, 22:07	#5
ET_ Banned "Luigi" Aug 2002 Team Italia 61×79 Posts	Hi Carlo (can I guess from your name you are from Italy? I am too), If memory serves, the time shown for polynomial selection (especially when a GPU is used) is just a rough estimate of the time needed; the process is not software timed (consider about 10% of the whole factoring time for polynomial selection). Usually there are 2 methods to check when stopping polyselect: the first is letting the program stop by itself when it terminates its iterations, regardless of the estimate, while the second is stopping it manually after it has written some data on the .p file. If you skim through the forum you'll be able to find some good values for polynomial selection on C154 values: compare them to the ones written into your file and take your action. Luigi

2010-07-15, 22:45	#7
Carlo Jul 2010 2³ Posts	Well, I tried a GTX470 but that didn't seem to work, I'm using a 9800 GX2 now. It found about 45 polys in just over two weeks, most of them all have e values of 2.6e-012. You figure, I may just as well stop with the poly selection now and just pick one? # norm 4.587349e-015 alpha -8.309035 e 2.652e-012 skew: 14306415.97 c0: -15852531439144025442733972847810232310525 c1: 3684988207254928439957337995876115 c2: -27332675829115566654228907 c3: -35792316957219381147 c4: 3280647151364 c5: 78540 Y0: -636805373599577378143689299658 Y1: 350947796784182687

2010-07-16, 02:33	#8
jasonp Tribal Bullet Oct 2004 DD7₁₆ Posts	If you've already spent the full two weeks looking for a good polynomial then it would be better to stop now and begin the sieving. Especially if you have more than one machine waiting for the sieving, the savings you will get from a better polynomial will not justify additional time spent with polynomial selection.

2010-07-16, 05:16	#9
Karl M Johnson Mar 2010 3×137 Posts	The fact that Msieve's CUDA-enabled poly selection isnt working with Fermi is expected. All CUDA apps, that were compiler prior to release of Fermis, worked on all future cards. However, for a certain CUDA app to work on Fermi, it needs to be recompiled with 3.0/3.1 SDK. What's odd, this doesnt affect OpenCL apps.

2010-07-16, 16:09	#10
asp Jul 2010 2 Posts	I've used msieve145_gpu with Fermi based cards without issues. There are issues with the NVIDIA drivers though and they do crash. Usually I need to split the range into smaller parts and run multiple instances of msieve145_gpu in parallel in order to load a single card 100%. This is usually because it will stall in the CPU intensive stages for a while which causes about 30 - 40% utilization of the GPU. A single Fermi card generally finds 10 - 14 polys per 24 hours for a 154+ digit semiprime number for me during testing. It's been my experience that you can kill the poly selection with a Murphy score of 2.9e-12 or better and start sieving when dealing with semiprimes around 154 digits.