A Few Questions

[wombatman]

Hi everyone,

I recently came across the MSieve/GGNFS project courtesy of Jeff Gilchrist's page. I've gotten everything set up and running reasonably well--I can factor the 100 digit example number on Jeff's tutorial with the factMsieve.py script. However, I have a few questions that I haven't been able to find an answer to searching on these forums that I hope will further my understanding of this process.

1) On my laptop, I have a GTX 560M graphics card (2GB RAM, 128 bit). I'd like to use the CUDA-based msieve to do some factoring while I'm working. When I start it, however, it basically brings my computer to a crawl--the CPU is not pegged out at all (highest is ~13%), but there's an approximately 1 or 2 second delay on anything that happens on the screen. Is there a way to combat this? I tried limiting the amount of memory used with the appropriate flag, and I also tried cutting down the number of threads used with its flag, but neither of these helped.

2) On my desktop at home, I'm also trying to do some factoring on a GTX 570. Again, the program works fine (and, oddly, doesn't cause any slowdown), but when I stopped the polynomial selection step and tried to start the 2nd step, I get the following:

C:\GGNFS\RSA1024>..\factMsieve.py rsa1024
-> ________________________________________________________________
-> | Running factmsieve.py, a Python driver for MSIEVE with GGNFS |
-> | sieving support. It is Copyright, 2010, Brian Gladman and is |
-> | a conversion of factmsieve.pl that is Copyright, 2004, Chris |
-> | Monico.    Version 0.76 (Python 2.6 or later) 10th Nov 2010. |
-> |______________________________________________________________|
-> This is client 1 of 1
-> Running on 1 Core with 1 hyper-thread per Core
-> Working with NAME = rsa1024
-> Selected default factorization parameters for 309 digit level.
-> Selected lattice siever: gnfs-lasieve4I16e
-> Creating param file to detect parameter changes...
-> Running setup ...
-> Estimated minimum relations needed: 3.44021e+11
-> resuming a block for q from 49756050000 to 49756150000
-> Running lattice siever ...
-> entering sieving loop
-> making sieve job for q = 49756050000 in 49756050000 .. 49756150000 as file rs
a1024.job.T0
-> Lattice sieving algebraic q from 49756050000 to 49756150000.
-> gnfs-lasieve4I16e -k -o spairs.out.T0 -v -n0 -a rsa1024.job.T0
gnfs-lasieve4I16e: L1_BITS=15, SVN $Revision: 406 $
Cannot handle special q >= 1073741823
-> Return value 1. Updating job file and terminating...
Terminating...

What does this mean, and is there anything I can do to fix it?

3) Is there any good, relatively easily digested reading on how to help guide the polynomial selection depending on the number? Obviously the program does some of that itself, but I'd like to understand how/why it makes the choices it does and what I can do to tweak it more.

If I've left off any important information, please let me know, and I'll reply as soon as I can. Thanks!

[pinhodecarlos]

Before you start...

Originally Posted by jasonp

This was written just after RSA768 was factored. I bring it up because there's a reason nobody has started thinking seriously about RSA1024.

Selecting a polynomial is something we can do now. Doing the sieving is something we cannot do now with current tools; think something like lasieve5e20 with three to five 40-bit large primes. Just storing a factor base up to 2^34 would probably take 16GB.

The public tools could not begin to handle postprocessing with 10^12 relations. Estimates for the size of the matrix range from 5x to 50x the size of the RSA768 matrix.

If we had specialized software that squeezed down the sieving to a size that would fit commodity machines today at a significant performance cost, and got all the usual suspects to help, for years, then Moore's law combined with a fairly serious cluster could factor RSA1024. But make no mistake that it would be an extremely difficult, sustained worldwide effort.

[wombatman]

Hahaha, so in short....no chance in hell of factoring the RSA1024 number in anything resembling a reasonable amount of time on a personal computer. I'll play around with other ones. Any ideas for the questions?

[chris2be8]

2) probably means you are trying to factor a number too large for the siever to process. Try something more reasonable such as rsa512 and see if the error goes away.

A reasonable way to learn more after factoring rsa100 would be to factor rsa110, rsa120, rsa130, etc and see how it goes. Each will take about 4 times as long as the previous number. Or go to http://oddperfect.org/composites.html for some numbers of slightly more mathematical interest (although most of them are SNFS targets).

Chris

[wombatman]

Thanks Chris. I think you're right about the number being too large. I've been playing around with smaller numbers and don't hit that issue.

[VBCurtis]

This week's poly adventure for Greg's c212 has shown me that my video response slows to a crawl while running -np1 poly select for a 212-digit number, but not for anything smaller than 150 digits. Seems that even using 4 threads for the smaller job doesn't fully tax the GPU (temps support this idea too- 75C on the c212, 56-60C on the previous smaller jobs using the -np flag).

I don't think there is a way to throttle msieve to maintain system responsiveness, but not using the 'threads' option may allow some jobs to run without slowing system responsiveness. It's not a memory or CPU issue- we're taxing the GPU so much it doesn't have cycles available to refresh the screen.

-Curtis

[chris2be8]

Hello,

What does the -e option do? The help says "perform 'deep' ECM, seek factors > 15 digits" but does that mean do the optimum amount of ECM curves before starting QS? And what happens if the ECM finds a factor? I've read the Readme files and searched the web, but not found answers.

Chris

[wombatman]

I don't know how high it goes, but it does ECM seeking at least 45 digit factors. I've never waited longer than that.

[jasonp]

I call it 'deep ECM' because the library runs ECM to the 15 digit level on anything you give it automatically, since that takes less than 1 second. But it can't guess whether you want to spend more time on ECM or just skip over to something else, so you have to ask for ECM that has higher bounds.

The library does have a complete ECM driver, which will scale up the amount of work smoothly and will cut over to another method when any remaining composites drop below an ECM-level-specific threshold in size. Likewise the driver will give up ECM if continuing will take so much time that it's worthwhile to switch to some other method. Curves stop after the 45-digit level, because one such run of curves will take many hours already and it's not nice to silently skip to NFS in those circumstances.

Regarding the GPU problems above, which I just saw now, using a GPU for small problems will make the library give small chunks of work to the card, which finish very quickly and do not impact the responsiveness of the system if the GPU is connected to a display. Large problems (maybe 180+ digits) use big chunks of work unavoidably, and that does slow things to a crawl. Poly selection on RSA896 was excruciating.

[chris2be8]

Thanks, that will be useful for numbers where QS is faster than GNFS.

Chris

[chris2be8]

It proved a bit disappointing. I tried it on two 85 digit numbers, it ran ECM for about 20 seconds then started QS which took about 20 minutes. Which is nowhere near enough ECM. So I'm back to my scripts to run ECM before calling msieve.

Chris