Factoring

[wesley]

Hey everyone,

I've been looking through the project on discovering the private keys for the calculators, but I'm a little confused as to how to get something going on my computer.

I have a pretty cruddy CPU (1 GHz and 1GB ram), but I also have access to some computers on campus (of course I can't install anything on them though).

I am just wondering what the best thing would be for me to do in factoring some large numbers. Could I get on the BOINC project somehow and put up some CPUs to do some factoring on some of my numbers?

Here are some examples:

R[1] := 856635008816114236287228889862706211601023274703568825790281732493598811489183201347792967433515761143227907320020567329633259067977601308187753;
R[2] := 262503444433443202297590751101961074929610529338524795169358249999355359738922201372169082275693161097217696397422937901342947981249;

EDIT: my platform is Windows XP/Fedora 10.

[Graphmastur]

Try GNFS. I think that's what boinc uses. If you can program java, I would suggest a simple client/server system.

[wesley]

Hm... I can program Java, but I'm not sure how to set up a client/server system with Java. If I had the time, I would look into that route.

As of now, I am looking for something already implemented. I am in a cryptology class right now and when we take an exam, we have a 7 day period where we have a chance to crack classmates' keys. The exam starts in a little over a week, so I was wondering if I could get my hands on something pretty soon.

The keys will be smaller than 528 bits, and probably considerably smaller, so it won't be too terribly difficult if I could use something with other systems attached. My computer won't be sufficient unless my classmates make weak keys, in which case I could exploit attacks such as the following: Fermat, Pollard's Rho, P-1, ISA, and a couple of others we have learned. But since we are learning how to also defend against such attacks, and our class has 11 students, I doubt there will be very many mistakes. I just think it would be pretty fun to crack all the keys, but I guess I would need help for that :/.

[wesley]

Okay, I think I will go with the GGNFS route. I'm just struggling on what to put in the text file, as shown in k0A.txt at http://www.unitedti.org/forum/index.php?showtopic=8899.

What values do I need to edit inside of that file?

[wesley]

Okay, I see how the .poly files are created and they are similar to the k0A.txt one, but how do I modify it to set limits on the q size?

[Lionel Debroux]

All lines (but "type: gnfs", of course ) need to be modified for optimal operation on your numbers.
I suggest you to use the factMsieve.pl or factmsieve.py scripts, under Fedora 10 (since on your Windows XP boxes, you won't be able to install Perl or Python), to see what invocations of ggnfs they run, and run that on your most powerful computers. See http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html for setting them up.


FYI, three things:
* msieve has a much more state-of-the-art polynomial selector than the pol5sel in ggnfs is. If you've got a CUDA-capable nVidia GPU (GeForce 8000 series and newer), by all means, use msieve-gpu, it's much faster for polynomial selection than msieve(-cpu);
* it will be hard to crack the C132 and C144 you posted in 7 days, unless you've got two or three appropriate computers doing the sieving: 1) factoring a C124 by GNFS takes between two and three days on a Core 2 Duo @ 2 GHz, both cores being used for the sieving and 2) in that range, GNFS factorization gets twice as hard every 5 or 6 digits.
* before running GNFS on a number, it's good to run it for 10 minutes or so in http://www.alpertron.com.ar/ECM.HTM . Besides ECM (which may weed out fishy keys quickly, as you've learnt), this applet uses a deterministic primality test (APRT-CLE).


Hope this helps

[wesley]

Lionel, thanks for the reply!

I've been looking through this, before you posted -- it's a great tutorial!

factmsieve.py was easy to get running on my Windows XP machine, but when I did, the thing went from start to go to the finish (finding the factors). The .poly file produced for the example shown in the tutorial you posted, is what I got below:

[wesley]

Here's what my file doesn't have that the k0A file does have:

[Lionel Debroux]

I have edited my previous post.

Polys that work, found in a couple hours with the pol5sel in ggnfs (while IIRC, factmsieve.py nowadays uses msieve's polsel):
(not very good)

[wesley]

Right, so how do I account for the differences in my .poly file as in the k0A file? How do I get the m, rlim, etc. for example? Could it be the way I setup the program to run, as shown in the tutorial?

[wesley]

Oh, and what's the difference between factMsieve.pl and factmsieve.py? Does one run the other? The first is Perl while the second is Python, but I've only used the Python one.

[Lionel Debroux]

[wesley]

Hmph... I can't seem to get GGNFS compiled on Fedora. Any suggestions? My machine has an Intel processor.

The tutorial we mentioned earlier doesn't note anything about libgmp, but Floppus mentions it here. First of all, do I need it? If so, how do I install it? I don't think yum has anything, and I can't find it in a search.

EDIT: What are the exact numbers for the ranges Floppus specified?

[wesley]

Sorry for asking so many questions, but do I absolutely need a Debian version of Linux to use factMsieve.pl?

[Lionel Debroux]

[wesley]

Well, for some reason, after installing all of the required libraries (e.g., Perl, Python, GMP), ggnfs and msieve still don't want to compile. I simply get tons of errors. How do I tell what Intel processor I have (difference between Pentium 2, Pentium 3, etc.). But even then, I've tried it with every option for the processor.

[Lionel Debroux]

Are you the "Romulas" who posted http://www.mersenneforum.org/showthread.php?t=13367 ?
Whether you are or you aren't, it's a good idea to post there, since you'll certainly get more help there with multiple persons than here with one person.

[wesley]