mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2017-02-01, 19:36   #1
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

2×32 Posts
Default Low CPU/GPU usage?

Hi, just started learning to use msieve, trying to run on a 170 digit number, but I notice CPU and GPU usage are both quite low. Is this normal?
GeoffreyY is offline   Reply With Quote
Old 2017-02-01, 21:45   #2
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

2×32 Posts
Default

Sorry, apparently I forgot the attachment or something:

https://imgur.com/a/g3xFM

I am in fact running factmsieve.py, after following instructions from that guide. I should be using the CUDA version if I did it correctly.I just started the process, so I'm still in the poly selecting stage.

Here's the log file, if it's of any use:

http://pastebin.com/0jitawas
GeoffreyY is offline   Reply With Quote
Old 2017-02-01, 21:53   #3
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5×347 Posts
Default

The GPU is used only for part of the -np step (-np1, if you look at the msieve -h), so it's not being used 100% of the time. Not sure about the CPU since I think the other parts of -np1 (-nps and -npr) are multithreaded. Maybe -npr is not.

Also, based on your filename, are you trying to crack an RSA number? Might want to explain what you're doing...
wombatman is offline   Reply With Quote
Old 2017-02-01, 22:10   #4
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

2×32 Posts
Default

As you mentioned them, can you explain the flags / process in a bit more depth? I'm still reading up on NFS very slowly...

As for the "RSA", we're learning cryptography in our computing class, and the 170 digit number is the example modulus used. I take this chance to try and crack it while reading up on some extra maths.

I believe the standard for RSA nowadays is (or rather should be) 2048 bit anyway, and probably not this unusual 170 digit.
GeoffreyY is offline   Reply With Quote
Old 2017-02-01, 22:17   #5
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5×347 Posts
Default

Truthfully, there are others on here (including MSieve's creator) who can explain it better than I can, so I'll leave that to them.

I only asked about the RSA name because there have previously been others on here trying to crack keys. As you might imagine, people are less inclined to help them.

Also, that C170 is going to take a while to factor using GNFS. I'm working on a C150 (with 6 threads), and that's going to take me a week or so. I believe the general rule of thumb is that time to factor via GNFS roughly doubles for each 5 digit increase, so you're looking at something like 4 months or so?
wombatman is offline   Reply With Quote
Old 2017-02-01, 22:30   #6
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

100102 Posts
Default

Thanks for the info, I'll keep looking around!

I wasn't sure how long will it take; your 4 months estimate is a bit high for me. My spring term ends at the end of March, and if I don't expect to finish cracking by then, I'll probably stop the project and go back to finding primes.

I may be able to use my uni's computers to speed up the process a bit, but I'm not sure how effective can that be.
GeoffreyY is offline   Reply With Quote
Old 2017-02-01, 22:43   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×7×11×29 Posts
Default

Expanding on Wombatman's info:

Poly select can be run for as long as you like; I suggest about a GPU-week as a reasonable balance (that is, if you spent only 3 days on poly search you might spend 4 extra days on the other longer steps, compared to a better poly that the extra 4 days *might* find- it's guesswork and expectations).

Once that step is done,and you can run that step on different ranges of leading coefficients on multiple machines (say, 1 day each on 7 machines with each one assigned a range on the command line), then you'd invoke factmsieve.py with the proper number of threads for your machine's hardware. For best speed, DO take advantage of hyperthreading; a quad-core HT should have 8 threads running.

Speed: I've finished a GNFS-156 on a 6-core i7 in nearly exactly 7 days. So, using the "double every 5 digits" rule of thumb, you can expect 7-8 weeks if you have 6 cores available, or 10-12 weeks if you have just a single quad-core. You can definitely split the task over two or more machines; just make each machine do its own region of q-values.

If you look at the command that factmsieve issues to the command line as it runs, you can figure out how to manually invoke lasieve4i15e on any number of machines. It takes a little practice/trial and error; I suggest you try to factor something around 130 digits and mess with command lines and editing q-values and renaming outputs to spairs.add to see how the script adapts to these things.

If you post the number here, I'll give my GPU a few hours of poly select on it, and can explain what score means for your expected sieving time.

Note the stage after sieving, when you solve the matrix, will be done on one machine only. Expect a few days for that last step (unless you have a really fast machine like a Xeon or 6-core, which might reduce that to 50-65 hr).

Good luck!
VBCurtis is offline   Reply With Quote
Old 2017-02-01, 23:04   #8
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

1216 Posts
Default

If you're interested, here's the information for our given RSA encryption: http://pastebin.com/QTC4LpvJ

I'll mess around a bit more with the code on uni's computer tomorrow.

I got so far as to figured out the e-score(?) is the 10^-13 one in .dat.p file; "rroots" is probably the number of real roots of the polynomial, and that smallest integer param is a good indication of progress.

I'm progressing but struggling quite a bit understanding the ggnfs-doc.pdf, as I barely know any group theory. On the bright side, I'll have a quite a head start next year

Again, thank you everybody for the information!
GeoffreyY is offline   Reply With Quote
Old 2017-02-02, 04:06   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×7×11×29 Posts
Default

I admit I don't grok the NFS algorithm as well as I'd like, but for your purposes it's quite useful to understand the stages and what progress looks like.

I'm running poly select on two GPUs this evening on your number; I'll let them each run a couple hours and post the best poly I find here (so you can compare what you find, which will surely be better).

In this subforum, you'll find a thread "best msieve poly scores". Post #7 notes a C170 has best score 3.91e-13. If you break that score, I'd end poly select and proceed right to the sieving step (and post the poly you found so I can note the new record!)

A C171 has score of 3.13e-13, so you should expect to beat that score with your search. Score is, roughly, a measure of the rate at which you can expect to find relations, so a larger score is better (and project length scales roughly with inverse of score- a 3e-13 project is *about* 10 times harder than a 3e-12 project).

Your search will produce quite a few okay polys, with occasional good ones. In some sense, we wait for a really good one to pop out of the search- but how long to wait, as well as what "good" is, isn't quite clear. That's why I track best scores- if you break someone else's best for a size, you've likely found a really good poly and can skip the rest of poly select. If you find a few around 3.2e-13, and then one batch has one or two like 10% better, you've probably found your poly. It's worth holding out a few days of poly select for a hit 8-10% better than the typical best results from a run (I check twice a day, and consider each half-day a "run"), because 8% shorter project length for an 8-week effort is ~5 days of saved sieving time.

The factmsieve script has been tested and refined for inputs up to about 150-155 digits; the automatically generated settings aren't the fastest for 150+ digits, simply because so few projects are done at those sizes the author lacked data to create a set of best parameters (so he guessed a little, and figured anyone serious enough to do C170 would already know enough to set parameters himself). The NFS@home BOINC project has recently done a bunch of factorizations in this size category, but they've not always optimized parameters for shortest project length; all the same, their parameters are useful to copy for this project absent better info.

If you decide you wish to do this factorization, I'll explain test-sieving in a future post, so you can test a couple possible parameters choices and hope to discover savings of a day or week in sieving via better-than-script-default choices.

Last fiddled with by VBCurtis on 2017-02-02 at 04:09
VBCurtis is offline   Reply With Quote
Old 2017-02-02, 05:51   #10
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×7×11×29 Posts
Default

2 hrs on each of two GPUs yielded 5 polys between 3e-13 and 3.1e-13, one just over 3.1e-13, and this one:
Code:
# norm 1.664492e-16 alpha -7.157348 e 3.470e-13 rroots 5
skew: 5053398.85
c0: -2786893278589734609571856633574386128995
c1: 4306299542743462566376217981723261
c2: 3783578211791106561032446613
c3: -821977447850264829373
c4: -149300456419050
c5: 5352984
Y0: -387655707969523635036413081890624
Y1: 16516041263376677
I found it using the following invocation for msieve:
./msieve -np1 -nps "5000000,6000000 stage1_norm=4e24 stage2_norm=4e22" -s rsa170test
When I got bored, I stopped it and then ran:
./msieve -npr -s rsa170test
The 5million,6million part is the value of the first coefficient to search over; this is the part you can easily spread over multiple machines. The other settings I set based on personal experience and the speed of my GPUs.
Hope this helps!
VBCurtis is offline   Reply With Quote
Old 2017-02-02, 08:50   #11
GeoffreyY
 
"Geoffrey Yeung"
Feb 2017
London

1216 Posts
Default

Sorry, I think I set up something wrong.

I ran the poly sel overnight (~16 hour total), and the best poly is slightly less than 3e-13, and you have few over 3e-13 in few hours.

The test also only ran from 0 to ~400 for the leading coefficient, instead of your 5 million.

Perhaps because I invoked it through factmsieve.py, instead of using custom parameters?

Again, the CPU / GPU usage is consistently low (~50% at best), is that normal?

Lastly, I tried to run '.\msieve -np1 -nps "6000000,7000000 stage1_norm=4e24 stage2_norm=4e22" -s RSA', it complains "cannot open input file 'worktodo.ini'".

I tried to make a worktodo.ini with the C170 number in it and see what happen. It creates a .ms file, it runs and outputs log on the command prompt, but it has yet to output anything. When I interrupted it, it shows "error generating or reading NFS polynomials". All files remain empty / unchanged

Sorry for the bombard of questions

Last fiddled with by GeoffreyY on 2017-02-02 at 08:50
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 13:18.

Tue Nov 24 13:18:10 UTC 2020 up 75 days, 10:29, 4 users, load averages: 1.31, 1.38, 1.64

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.