mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2017-02-02, 10:48   #12
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

2·32 Posts
Default

I stand corrected, after running for an hour, I have the following output in RSA.ms:

http://pastebin.com/Avj6B01B

Still, this is different from what I saw previously. How can I check if this is valid?

Edit: good news, with invoking msieve from command line, my GPU is currently on full load. Thanks guys

Last fiddled with by GeoffreyY on 2017-02-02 at 10:51
GeoffreyY is offline   Reply With Quote
Old 2017-02-02, 17:12   #13
chris2be8
 
chris2be8's Avatar
 
Sep 2009

5·389 Posts
Default

GNFS has several stages:
1: Searching for small factors with ECM. If you know it doesn't have any small factors you can skip this (RSA numbers usually don't).
2: Searching for a polynomial. This can be aided by your GPU. And split over several systems.
3: Sieving for relations. This can be split over several systems, each core on each system sieving a separate range. Be careful to ensure you don't sieve the same range more than once, this produces duplicate relations which are useless.
4: Building a matrix (by running msieve -nc1). It may fail saying it needs more relations, if so sieve some more. But don't take the message saying how many more it needs seriously. This is single threaded.
5: Solving the matrix (msieve -nc2). This may take several days for RSA170. It can use multiple cores on 1 system.
6: The square root stage (msieve -nc3) which finds the factors. This is single threaded.

You might do better to start by factoring RSA100 first (In a different directory to the one you are working in). That should not take long and seeing it all the way through will tell you what to expect in larger runs.

Then RSA110, RSA120, etc. Each will take about 4 times as long as the last.

Also look at the NFS@Home forum thread http://mersenneforum.org/showthread....20023&page=162 on linear algebra. You can read the msieve logs for similar sized jobs which might be helpful.

HTH

Chris
chris2be8 is offline   Reply With Quote
Old 2017-02-02, 17:19   #14
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

106048 Posts
Default

Sorry I forgot the worktodo.ini part- glad you solved that one!

My settings do not create much output into .ms; I think four GPU-hours found ~90 lines in the .ms file, something on the order of one every 4-5 minutes.

The -npr command works on the raw data in the .ms file, outputting actual usable polynomials into RSA.p. The best-scoring poly found will be saved to msieve.fb; in order to begin another run, you'll have to rename that file (I use filenames like RSA{scoreofthispoly} so I can see from the directory which poly had the best score, so the one I found for you is saved as RSA346).

I don't know why the script wasn't using your GPU fully, but I can tell you the script predates msieve-GPU code. I also can tell you that the -npr step takes a lot of time on each hit, and the default settings in msieve generate a LOT of hits into .ms! Perhaps the script tries to do -npr on all of them, pausing the GPU as it processes all of the GPU's output. My custom norm settings reduce the output from the GPU to just the very best candidates in the raw data, so that -npr takes perhaps an hour or two per day of GPU output.

If you have a fast GPU, say 900 series or newer, you may wish to add -t 2 after the -np1 -nps flags; this sends two sets of data to the GPU to process at the same time (two threaded, so to speak). This helps with smaller input numbers, say C150s, but is likely only slightly useful at this size.

As for running from 0 to 400, the default behavior is to start with coefficient 0 and work up, and really small coeffs take a while to churn through. I often start my search at 5000 or 10000; I only selected 5 million for mine to avoid overlapping any work you had already done. Smaller coeffs have a history of producing good scores with slightly less search time than large ones; if you run 10000 to 500000 with my norm settings, I bet you'll find a few polys above 3.2e-13.

Yes, your pastebin output is exactly what should be in .ms; if you ran ./msieve -npr -s RSA msieve would process that raw polynomial into one that the script can run sieving on (a list is saved to RSA.p). Not every raw poly line will produce a good-enough poly to save into RSA.p; I'd wait for 50 or more lines in RSA.ms to bother stopping the GPU search to run -npr. Note that once you run -npr, you should rename RSA.ms into something else, so that you don't re-process those hits the next time you run -npr. Also, change the input coefficient to start where the GPU left off; if your search got from 6000000 to 6150328, I'd start the next run at 6150400. But, start at 10000 sometime.
VBCurtis is offline   Reply With Quote
Old 2017-02-02, 21:52   #15
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

2×32 Posts
Default

Thank you very much for all the info! I don't think I'll have any more problems from here going forwards.

I sieved through 5.5 to 6.2 mil this afternoon, but I didn't find any poly above 3.2e-13. I only have a laptop with a 950m, which's the only machine I've been sieving on. There are some technical difficulties with uni's machine.

One more question, is the polynomial searching non-deterministic? I think I got different results passing through the same range twice.

Also, are there any particular aspect / coefficient of the polynomial I should be looking for, besides the Murphy E-score? Or are they simply data points that don't carry much weight?
GeoffreyY is offline   Reply With Quote
Old 2017-02-02, 23:12   #16
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22·19·59 Posts
Default

Quote:
Originally Posted by GeoffreyY View Post
One more question, is the polynomial searching non-deterministic? I think I got different results passing through the same range twice.

Also, are there any particular aspect / coefficient of the polynomial I should be looking for, besides the Murphy E-score? Or are they simply data points that don't carry much weight?
1. msieve searches a subset of the search space for each leading coefficient, randomizing which piece each run to minimize repeated work if multiple people run the same range. It was my impression that my tight stage1-norm reduced the search space so much that msieve didn't do this, but your results suggest otherwise. So, sort-of deterministic? :)

2. Score is an estimate of poly effectiveness; it is imperfect but within 3-5% of accurate; that is, two polys of the same score can differ by up to 5% speed in use. For jobs this size, folks usually test any poly that scores within 3-4% of the best poly (say, within 0.15 in your case) in case the best one happens to run poorly and 2nd or 3rd place runs well. If you find nothing better than 3.30, I wouldn't bother with test sieving; just use the 3.4699 poly I posted.

Best wishes on your effort- post if you have further questions, such as what parameters to select. The choices are made around line 520 in factmsieve.py, and formulas are easily edited to nudge the script to pick a different siever or large-prime bound. Hopefully, it picks 15e rather than 14e (part of the name of the lasieve executable), and chooses 2^31 as large prime bound (in a .job file created by the running script, you'll see lbpr and lpba; those should be 31 for a job this size, with 32 acceptable but 30 probly bad).

Last fiddled with by VBCurtis on 2017-02-02 at 23:17
VBCurtis is offline   Reply With Quote
Old 2017-02-03, 10:35   #17
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

100102 Posts
Default

I still haven't found any better poly, so I've moved on to finding relations using your poly. I think this RSA.poly file should be alright: http://pastebin.com/w15j4PDx

I'm able to use uni's computer for this step, but I have to manually create the .job files so that there's no overlap, because I'm not sure how to do otherwise. (example: http://pastebin.com/jKdcRigw) I guess I can make my own .resume files?

One problem though, sometimes after invoking the command, the uni computer reports the .exe is not responding. I think it took a bit too long to create the .afb.0 file. They all have the same size (14,951,800 bytes), are they all identical? If I simply copy, paste and rename the files, I no longer have the occasional crash at start-up, but I'm not sure if I should do that.

Another thing, do I simply transfer all the spairs.out.t_ files from my multiple computers and truncate them? I'm just zipping them up for now.

Sorry if my questions are getting bothersome. I'm partly recording the process for myself for when I come back in the future. Thanks!
GeoffreyY is offline   Reply With Quote
Old 2017-02-03, 13:34   #18
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

2×32 Posts
Default

quick update: currently I have the following files in \gfns\RSA: http://pastebin.com/sWYD4t5Q

And from there using "..\factmsieve.py RSA" seems to be working.

I think I have a total of 100 relations/sec utilizing uni's computers. This easy setup means I can easily set up more computers if I want to / if I can.
GeoffreyY is offline   Reply With Quote
Old 2017-02-03, 14:47   #19
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DA116 Posts
Default

Your error is an FAQ; if you only run poly selection in stages then unless you run the stage 2 root sieve you will not assemble a complete polynomial. By default the NFS driver in Msieve assumes you want to do the whole factorization, so not having a complete polynomial is treated as an error. It actually is silly to do that, since even if you did have a complete polynomial the sieve code in Msieve is probably an order of magnitude slower than the high-performance lattice sieve that a script calls an external binary to perform.

In the past we have had students complete big factorizations (i.e. 160 digits) in a remarkably short time, by taking over idle computer labs. On modern machines a 170-digit factorization starts to get into the range where the linear algebra is a major headache to perform in a reasonable time, i.e. it will take weeks unless you use MPI and have a few machines with a high-speed interconnect (gigabit ethernet isn't enough).
jasonp is offline   Reply With Quote
Old 2017-02-03, 16:48   #20
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22×19×59 Posts
Default

Quote:
Originally Posted by GeoffreyY View Post
One problem though, sometimes after invoking the command, the uni computer reports the .exe is not responding. I think it took a bit too long to create the .afb.0 file. They all have the same size (14,951,800 bytes), are they all identical? If I simply copy, paste and rename the files, I no longer have the occasional crash at start-up, but I'm not sure if I should do that.

Sorry if my questions are getting bothersome. I'm partly recording the process for myself for when I come back in the future. Thanks!
No, the .afb files do change from range to range, and it's not wise to move/rename them.

Threads like this become reference material when the next person comes along, so your idea of recording the process for yourself is wise.

(I don't know the answer to spairs.add, so I didn't address that question)
VBCurtis is offline   Reply With Quote
Old 2017-02-03, 21:34   #21
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

1101011110012 Posts
Default

Quote:
Originally Posted by GeoffreyY View Post
...
Another thing, do I simply transfer all the spairs.out.t_ files from my multiple computers and truncate them? I'm just zipping them up for now.
...
You should not truncate the files. You should concatenate all of the unzipped spairs.out.t_ files into spairs.add:
Code:
cat spairs.out.t_* >> spairs.add
From there, factmsieve.py will concatenate spairs.add to the RSA.dat file. By using the spairs.add file, you allow factmsieve to modify the RSA.dat file instead of risking a manual modification causing a crash.
EdH is offline   Reply With Quote
Old 2017-02-17, 11:47   #22
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

2×32 Posts
Default

I have successfully factorized: C170 = P85 * P85. For various reasons I won't post the exact result until 27th Feb. (deadline for this bonus challenge) Thank you everyone for helping.

Quote:
In the past we have had students complete big factorizations (i.e. 160 digits) in a remarkably short time, by taking over idle computer labs.


To be safe, I got up to ~120% of minimum relations needed, and got 30 nontrivial dependencies at the end. Dependency number 1 worked anyway. Oh well.

Apparently I had to convert my .poly into .fb to start the linear algebra phase with factmsieve.py.

During the -nc2 phase my windows crashed (BSOD), and the .mat file became 0 bytes for some reason. The .dat file was also re-written. but luckily we have .gz backup. I think it's a RAM issue, as I had chrome with multiple tabs opened.

I'll try and see if I can reproduce the low CPU/GPU usage issue that started this thread.

Besides that, I'm probably going to grab an aliquot sequence to work on. I was looking into helping factordb too, but it doesn't seem 100% stable at the moment.
GeoffreyY is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GPU Usage Brain GPU Computing 9 2011-04-12 22:25
GMP-ECM resource usage lavalamp Software 0 2010-10-11 20:46
High CPU usage Primix Hardware 2 2008-07-20 23:44
Usage of GMP-ECM ECMFreak Factoring 13 2007-07-20 17:34
CPU usage Unregistered Software 6 2003-11-19 07:05

All times are UTC. The time now is 08:34.

Sat Nov 28 08:34:31 UTC 2020 up 79 days, 5:45, 3 users, load averages: 1.57, 1.68, 1.65

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