Factoring the "0A" key

[FloppusMaximus]

OK, guys, here we go. If you're just tuning in: factoring the "0A" key will enable us to load third-party OSes on the TI-84+ (BE/SE), without the use of additional (potentially risky) software.

Here's how it works:

- First of all, you will need to have libgmp (including devel files: libgmp3-dev on Debian/Ubuntu) installed. You will also need Perl. In addition, you will need some disk space (a few gigabytes at minimum) and a bit of spare RAM (maybe 100-150 megabytes per thread.)

- Next, download and compile GGNFS. There are some Windows binaries available, but I have not tested them. For other platforms, download the latest code, and compile it by running 'make <your-cpu-model>' (run simply 'make' for a list of supported targets.)

For x86-64 systems, I recommend using the "experimental" siever, which can be found in the src/experimental/lasieve4_64 subdirectory (instructions for compiling are in the INSTALL file.)

- Download [attachment=2730:factMsieveQ.pl.txt]
(Rename it to factMsieveQ.pl because the forum is silly.) Open it in your favorite text editor. Change the 'GGNFS_BIN_PATH' to the name of the directory containing your GGNFS executables, and change the 'NUM_CPUS' to the number of CPU cores you have.

- Choose a range of q values to work on. (See below.) Post in this thread, or email me privately, to reserve a range.

- Download [attachment=2729:k0A.txt]
Open it in your favorite text editor, and replace <STARTING VALUE HERE> and <ENDING VALUE HERE> with the values you chose. Save the result as k0A.poly.

- Run './factMsieveQ.pl k0A.poly'. This will take a long time. I suggest running it inside a 'screen' session, so you can run it in the background without keeping the terminal window open.

On most Unix-like systems, you should be able to pause the job by pressing Ctrl+Z, then resume it by typing 'fg'. If you need to stop the job for a long period of time, or reboot, or whatever, then press Ctrl+C to stop the job completely. You can then pick up where you left off by running './factMsieveQ.pl k0A.poly' again. (Note that when you do this, you may miss a few relations and/or get some duplicates. This isn't anything to worry about too much, it just means we may take a bit longer to finish.)

- Once you've finished your region, report your results here.

Now, about selecting your q values:
- The "best" q-values are going to be between 13 million and 27 million. As we move to smaller and larger q values, the number of relations per q-value will decrease. So let's start out by sieving the 13M-27M region, then move upwards and downwards as necessary. We're going to need somewhere in the neighborhood of 50 million total relations to finish the job.
- Start out by reserving small ranges until you have an idea of how long they'll take. :)

Reserved ranges so far:
(I will update this list as we go, but check the thread as well):
1M-2M limx (done, 847375 relations)
2M-6M BOINC clients
6M-8M Skittle (done, 2582020 relations)
8M-10M Skittle (done, 2606379 relations)
10M-13M fullmetalcoder (done, 4054840 relations)
13M-15M FloppusMaximus (done, 2745936 relations)
15M-17M Taricorp (done, 2764376 relations)
17M-20M fullmetalcoder (done, 4161960 relations)
20M-22M FloppusMaximus (done, 2765854 relations)
22M-25M Skittle (done, 4128280 relations)
25M-34M BOINC clients (done)
34M-35M FloppusMaximus (done, 1255021 relations)
35M-36M FloppusMaximus (done, 1254880 relations)
36M-44M BOINC clients
44M-45M FloppusMaximus (done, 1156504 relations)
45M-46M limx (done, 1153281 relations)
46M-50M BOINC clients

[Taricorp]

I've got two threads working on the 15M-17M range now.

The windows binaries are working just fine with ActivePerl for me, but you'll need to invoke perl explicitly from a command prompt:

[FloppusMaximus]

Cool! And thanks for the tip.

[Graphmastur]

Hey, I have a quick question. The number in the .pub file needs to be factored into to prime numbers, correct?

[fullmetalcoder]

I'll be sieving shortly on the 17M-20M range (it's gonna be a bit of a hassle but even a broken gfx driver won't stop me, actually it'll even make it faster as my laptop won't be doing anything but sieving).

[FloppusMaximus]

Graphmastur: That's correct. The .pub files that are included with Rabbitsign contain the public keys (stored in the same little-endian, length-prefixed form that's used by TI's official key files.) I posted a script over in the other thread, which you can use to convert that into a decimal integer. It is possible that I made a mistake somewhere, so you may want to verify that the key actually does what it claims, before you start trying to factor it.

[Graphmastur]

[FloppusMaximus]

Um... I'm not quite sure what you're saying. By a "brute force attack", are you talking about trial division? Because that will not work. The only way anyone can factor a number of this size is using the GNFS, or possibly (with many CPU-years of work) the quadratic sieve.

With regard to creating a server for assigning GNFS work, it's certainly possible, but realize that it doesn't just involve asking the clients "hey, have you found any factors yet?" Factoring with the GNFS requires collecting a huge amount of data from all of the sievers at once, and combining that together to perform the actual factorization.

Anyway, I created this thread to discuss the factorization of the 0A key in particular, so let's not go too far off topic.

[thornahawk]

Indeed, trial division (dividing a candidate composite with all primes less and equal to the square root of that number) is impractical for numbers that most likely are the product of two huge primes. You'd be better off using the Pollard or CF factorizations, but they too are still slower than GNFS. That's why Floppus and others are using that and not the other algorithms.

Anyway, enough off-topicry.

thornahawk

[fullmetalcoder]

I'm having some trouble. I ran the siever for a couple of hours and everything goes fine until the end of a "step" (100000 by default I think). At that point I get some console output that looks like a summary and a segfault. Anyone knows what might go wrong? My guess is something about threading since I get two similar ouputs (running two threads) and the segfault occurs at the end of the second but it might as well be something else after completion of the two jobs. So far my investigation of the factMsieve script did not lead me anywhere and I have no idea how to debug a perl script...

By the way it looks like the script will restart from the beginning in this case (step finished but not "validated"), anyone knows I may trick it into resuming properly, or "validating" the step by hand?

[FloppusMaximus]

That's bad. At what point exactly does the segfault occur? Is perl crashing, or the siever, or something else?

The factMsieve script determines where to start sieving by reading the 'q0' value from the job file (if there isn't a job file, it will use the q0 value from the poly file, and if that isn't defined I believe it defaults to alim/2.) You can manually update the job file if you want, I guess, but if I were you, I'd try to figure out why it's crashing.

[fullmetalcoder]

Did a bit of debugging and it looks like the segfault occurs in perl, more precisely in the Math::BigInt::GMP module upon exit of a function, apparently because of a double free. So my guess is that each thread is given a reference to the same BigInt and destroys it upon completion instead of letting the caller take care of it. Embarassing but I suppose just disabling GMP would do as none of you have faced a similar issue.

The only question left is : how can I properly resume sieving without loosing the data collected thus far? (or is that data already suitable for sharing?)

edit :
* I disabled GMP in the perl script and the segfault is gone
* I fiddled with the setup and makeJobFile functions to prevent overwriting of some files upon start and it apparently worked so I'm back to sieving.

Side note : I got ~140k relations for a 100k window. Is that an average value to expect (or high, or low) ?

[FloppusMaximus]

140k relations is about what I'm getting for each interval. It's about the same yield as what I got for the 04 key, although it seems to be a bit slower to find them.

If you want to know exactly how far you got with your previous attempt, I believe the current q value is always the last hex number on each line of the output.

[DigiTan]

All this talk of PERL and makefiles makes me wish I knew how to compile instead of just using repositories.

[fullmetalcoder]

about 25% done (went beyond 1M relations). If everything goes well I should be done with my segment within 5 days and be able to pick another 2M segment.

[FloppusMaximus]

13M-15M finished last night, with 2745936 relations. I'm starting on 20M-22M now.

[squalyl]

what about using BOINC for these calculations?

This could allow anyone to join the factorization effort, share the computing power, and manage the whole set of keys at once.

I've set up a project on my server [1], it works, what remains to be done is:

- generating workunits
- writing a cruncher (I believe this will be a recompilation of the lattive siever using the BOINC api)
- result gathering.

The first concept is not yet clear for me, so if anyone has time and experience in this domain this would be appreciated. I'm mistaken in the differences between workunits, workunits names, input files, and database entries, and how to get the whole thing going. I can do this with time, but I'm short on this one.

Writing a cruncher does not seem too difficult. note: it should be statically linked to avoid any gmp/etc dependencies.

What do you think?

[1] http://boinc.unsads.com/rsals/user

[Taricorp]

Results for 15-17M are in. Grab them here. (5528752 relations, best I can tell [grep -o "," k0A.[range].rels | wc -l])

Additional note for Windows users- unless you set COMPRESS_RELATIONS to 0 before running, it'll abort and note it can't find gzip.exe once it finishes the entire set. You can either get a copy of gzip.exe and put it in that directory (meh), or just compress k0A.[range].rels yourself once it finishes.

[FloppusMaximus]

Excellent. Thank you very much! I doubt you got 5.5 million relations, though... and a simple "wc -l" will suffice.

squalyl: Using BOINC is certainly an interesting idea. Adapting the GGNFS siever, though, could be quite challenging. I don't know much of anything about how BOINC works internally, and I don't really have time to work on it right now, but I may be able to help out a little with the mathematical side of things.

[fullmetalcoder]

66% done (2.7M rels so far). Estimated time remaining : 45-50hours