msieve parallel poly selection with MPI

[drone84]

Hello

I would like some advice/precision about msieve.

I'm trying to factor a 155-digit number (yes it's an RSA key) with msieve. To speed-up the process, I setup MPI to lunch msieve on all core of several computer, NFS to spread the data on all the computer and openSSH for the connection between the master node and the slave.

This is the tutorial I’ve used to setup MPI:
http://mpitutorial.com/tutorials/running-an-mpi-cluster-within-a-lan/


I'm able to run the polynomial stage in parallel (-np argument). To make it work, I have modified the demo.c file to look after the MPI ID

if 0 => master node

1. Wait for a message "ready to work" from any slave.
2. When the message is received, the master read the log and compare the e value with the best e found from the previous slave work, save it if needed.
3. Erase all the temp file generated by the slave node.
4. Compute a range to process and sent it back to the slave.
5. Go back to 1.

If != 0 => slave node

1. Waiting for a range to search.
2. Run the msieve lib.
3. Send the signal "ready to work" to the master.
4. Go back to 1.

(before the master loop there is a loop to lunch the first work on all the slave node)

Like this the load is distributed regardless of the speed of the computer ass soon a node completed his task it work on another one.

/**********************/
For the sieving step, it the same, but I don’t erase the temp file. Like that all the data generated by the node are all saves in the xxx_node_number.dat file (I use a script to read all the log end add all the relation generated at each msieve lib lunch)

/**********************/
when eanof relation is found, I just lunch the normal demo code like this ./msieve -npc and if I'm luky I ends up with my two number.

I only manage to facto un 100-digit number

My questions are:

• - The polynomial selection is done the right way for e 155-digit number?
  I read some ware that is better to run -np1 (sort the result) then run the other -npx step on the best result. What is a best result from -np1 output?
  message 9
  http://www.mersenneforum.org/showthread.php?t=19312
• Should I to start the polynomial search from 0 or 1000000 (or higher value )?
  
  
• -When I run the sieving I setup I setup a range of 1000 for each work (the b value), it means that I can see how much relation I get for each range on all the node (info stored in the log file) and I end up with value of 1000 relation for each core after 10h, 8 min pear job (100-digit number) and near 100 or 50, 20 min pear job for a 120-digit number.
  is it normal? (I'm not shure someone have the answer).
  Have you some example of factoring time for different digit number (100,110,120...), let’s say on a quad core 3Ghz
• - When the polynomial is selected, I create several xxx.fb one for each node then run msieve -ns. at the end when I have enough data, I put all the data from the .dat file in one file than run the last step, is it right?
• - A lot of big number use ggnfs for the sieving instead of msieve, should I do the same or msieve on a lot of pc work?

Modification to do on the polynomial step

• instead of saving only the best polynomial (and the last best found) try to save them and test witch one is the best.

Hard:

• 4/5 laptop with i7-6700HQ 2.6GHz
• 1 VM on a serer 12 xenon core
• 8/12 several other laptops with 2/4 core

Sorry for the wired writing, English is not my mother tongue.
Thanks.

[VBCurtis]

Do *not* use msieve for the NFS sieving step. You *must* use GGNFS or CADO.
CADO automates all of the sharing-across-platforms steps without MPI, and for your purposes is likely your best choice. You merely need SSH connections among the nodes to the host.

An RSA-512 key takes 10-11 days on a quad-3ghz using Msieve & GGNFS; CADO is a bit slower, perhaps 12-13 days, but it parallelizes across machines so easily that it's worth the slower speed for your use case. Difficulty for GNFS tasks such as yours doubles every 5 decimal digits, so a 150 digit factorization would take 60-80 ghz-days, 140 would take 15-20 ghz-days, 130 would take a quad-core less than a day, etc. Those numbers assume hyperthreading, which adds perhaps 20% to NFS efficiency; they also assume ideal parameter choice, which may not happen automatically. So, perhaps rather than expecting 150 ghz-days for your RSA key, if you expect 180 you are unlikely to be disappointed.

CADO is linux-only, though the client can run on windows with some fussing. It's not worth the effort to try to run the host software on windows, and the authors do not intend to support windows.

[Dubslow]

Yes, if you are trying to automate the task over the network, then CADO is definitely recommended from an ease of use standpoint (if not necessarily an absolute performance standpoint, but as above, the performance gap is minimal and certainly worth the human effort saved).

And again, just to emphasize, DO NOT use Msieve for sieving. It's excellent for poly select and post processing, but it's terrible for sieving.

[drone84]

"DO NOT use Msieve for sieving" => I was not sure, but now I am...

I tried ggnfs but I gave-up due to compile error ( xxx.a missing,I have to compile myself that lead me to other error... the explication to build the 64 version is not clear)

CADO-NFS is crassly fast to use : 20 min between the download to a 80-digit number factorised.

Now I just have to make it work on several PC I already have a poly for the RSA key.
I have some error about "service not known" and I think reading the doc will help me.

Tanks-you.

[drone84]

I Setup CADO-NFS to run on 128 Xenon core at 2.66Ghz ( 4 rack of dual 8 core Xenon dual thread, 8*2*4*2= 128).

and it took about 27h

The best result I've got is with:

• 2 thread for the sieving,
• 32 thread for the filtering (work only on the server side so only 32 core available)
• 1 thread for the filtering but with 2x8 instance op MPI (CADO-NFS need to be compiled with MPI, "MPI=1 make" instead of "make")
• for all the other step I put tasks.threads = 16 (I don't try higher value because the step time spend with this setting is about 1 or 2 h maximum)

To prevent the server node to resubmit the current job we need to increase the timeout value (the value is a lite bit crays for maxtimedout , but work )

tasks.wutimeout = 1600
tasks.maxtimedout = 10000

you can play also with

tasks.sieve.qrange = 1000

To high value wile take forever to send back the result.
I attached my params.155 file