Local GNFS (breaking RSA keys)

Lattice Siever, C137 cofactor (2^688)+1

Dear Lattice Siever,

This is a project that breaks a 137-digit number, by the same method used to break an RSA-key of the same size. The program claims to want 64Mb of RAM, but runs well with smaller amounts. If you have under 96Mb of RAM, you may be able to get the program to run reasonably well using 36 Mb. For W95/W98/NT users, Arjen's binary s137.exe is available here. You'll also need to build the factor bases using the binaries ratbase and algbase. As described below, ratbase is to be run with input c137.dat , and algbase with alat15 .

For unix users (and anyone else wishing to see the code), the present c-code is s137.c, which requires aklpar.h. We expect the present code to run on pcs and SUNs (32-bit mode); and if you still have your copies of lip.o, ratbase and algbase you can skip to paragraph (**) below, or to paragraph (*) to use your copy of lip.o to recompile ratbase and algbase. So far as we know the present code compiles on Alpha's, but you'll need to update all binaries using a new lip.o, from the new code (see below). All users of the new lip.c _Must_ use the new lip.o for compiling (or recompiling) all of the subsequent programs ratbase, algbase and s137, since the new lip.o is binary incompatible with the old version.

NOTE: All programs and initialization files are copyright Arjen K. Lenstra, as indicated. The -Alpha compile option is due to Scott Contini.

Once you have a running binary, email me at bruce.dodson@lehigh.edu telling me how many cpus you expect to run, and I'll send you back a range for sieving. (This is a temporary measure. Still.) A partial revision of the instructions for running 2,773+, which apply with minor changes, follows.

Dear cabalist,

If you expect to need (new) copies of all of the files, you may ignore the step-by-step instructions below and click files . There are 14 program files and a single unified instruction file. In fact, this time's tarfile has a working Makefile, so the step-by-step instructions below are for people that want to see the steps or need/want to do their own custom compiling.

Long Integer Package [no changes, but we're using revised code]:

If you don't already have a copy of lip.o, click on lip. There are 3 program files and a compile instruction. This output file is needed for all of the following, so if you're having trouble at this step you should consider picking up a compiled binary of s137, above, or consulting a cabalist with experience using your compiler. As long as you're here, you might like Scott's 32-bit Makefile which is also available in an Alpha version Makefile-ALPHA, (rename Makefile-ALPHA to Makefile, unless you need both "makes", in which case you might use separate directories; whatever fits how you run at your site).

(*) Factor Base Programs [no changes]:

If you don't already have a copy of ratbase and algbase, click bases. There are 3 new program files and two compile instructions. (If your copy of lip.o is OK, this step should be easy.)

(**) Siever and Factor Bases:

Now that you have lip.o, ratbase and algbase, click s137. There's a new program file (the siever!) and three instructions.

Test File(s) [in preparation]:

Here's a copy of my mem=64 output mem64. The corresponding text is txt64. There's also a program to check your timings. [Caution: Large memory machines should use one of 52Mb, 54Mb, 56Mb, ..., 64Mb. Lehigh's SGI's run better using 62Mb than 64Mb, and you should take the setting that gives the best rate (seconds/relation) for your machine. Typically, larger memory give more relation/q, but the extra relations are obtained at a low rate: you might try 64Mb, 62Mb and one of the low 50's, 54Mb, say. I'm running 54Mb on my pc; Arjen's running 64Mb on his 600Mhz laptop. The small memory setting is 36Mb; which is what I run on Lehigh's public SGIs.]

Check out a sieving range (and decide how you'll send in your data):

TBA ...

B. Dodson, bad0@lehigh.edu. September 29, 2000. (Revised Oct. 9.)