Factored my first SemiPrime -Some Questions

[tal]

Hey Jason, I didn't want to make a new thread - but I had a followup question. First off, I have to say the msieve code is gorgeous. After reading a lot of code in a lot of different open source projects I have a history of hating "other people's code" - but this is a breath of fresh air; it's downright enjoyable to read.

Since my last post, I kept a lot of logs on sieving times across my various machines, as well as the final combine - comparing results on different computers, results when I have just-barely enough relations compared to oversieving, and so on. I factored RSA100 a few times more, and RSA120 as well - using a job-distribution system I finished the sieving (actually overseiving by 20%) in under an hour. I'm spending a lot of time trying to get a good distribution system set up, so polynomial selection and sieving can be done very quickly on a massive scale. Because sieving is completely parallelizable I envision sieving 512 bit numbers in a day or less, completely automated.

Now I'm spending time looking closely at the polynomial search phase, and how to distribute it - looking closely at the behavior when you specify a range using -np X,Y. Based on a lot of reading and and a few assumptions, it seems the best way to split the polynomial search range is into the ranges generated by msieve in stage1.c:search_coeffs - where you're only going into search_coeffs_core when you have a batch of at least 40 non-trivially divisible numbers. Any other range seems like it will be worse-off at finding a possble polynomial, because the batch won't be full. Is that correct? (I have four paragraphs worth of explanation into how I came up with that... but decided to spare it unless needed.)

[debrouxl]

Because sieving is completely parallelizable I envision sieving 512 bit numbers in a day or less, completely automated.

Given enough dozens of cores, 512-bit RSA keys (a.k.a "GNFS tasks of difficulty 154-155") can definitely be sieved enough in less than 24h per key.

Distributing sieving work across computers can be done by ad-hoc scripts, or by infrastructure such as BOINC. There are two BOINC-based sieving grids:
* RSALS, using the 14e siever, whose original goal was precisely to speed up factorization of a set of 512-bit RSA keys used for signing OS and applications in TI-Z80 and TI-68k calculators;
* NFS@Home, using the 15e/16e/16f/16g sievers for harder factorizations, currently ramping up to the hardest factorizations ever performed using open source software (SNFS difficulty > 300).

[tal]

Originally Posted by debrouxl

using the 15e/16e/16f/16g sievers for harder factorizations

This is the first I've heard of 16f/16g sievers... And a regex across ggnfs source doesn't mention them... Could you elaborate on where they come from?

Based on the factmsieve script, the sievers are (generally) to be used as 11 => <95 digits, 12 => <110 digits, 13 => <140 digits, 14 => <158 digits, 15 => <185 digits, 16 => <999 digits. I'm curious where these come in, since (I thought) RSA-190 was sieved with specialized programs (AFAIK).

[jasonp]

Originally Posted by tal

First off, I have to say the msieve code is gorgeous

Aw shucks :)

Now I'm spending time looking closely at the polynomial search phase, and how to distribute it - looking closely at the behavior when you specify a range using -np X,Y. Based on a lot of reading and and a few assumptions, it seems the best way to split the polynomial search range is into the ranges generated by msieve in stage1.c:search_coeffs - where you're only going into search_coeffs_core when you have a batch of at least 40 non-trivially divisible numbers. Any other range seems like it will be worse-off at finding a possble polynomial, because the batch won't be full.

Larger batches are better but it's not vital to chop the range into optimal-size pieces. If you just make every range larger than a few thousand, you're pretty much guaranteed to have several maximum-size batches.

Also, jrk and I have been working on much better poly selection code, especially for CPUs, and if you're gearing up for bigger jobs then you can play around with the specialq branch. The different algorithm used there doesn't lose efficiency if you give it one leading coefficient at a time.

[Hian]

Hi, if your code is working, may I ask for your favour to factorise this 122-digit-semiprime: 87080933638459254990190759549329249427007327139393378403507376787968543052358925725338774979411611152080797622523844393187

[R.D. Silverman]

Originally Posted by Hian

Hi, if your code is working, may I ask for your favour to factorise this 122-digit-semiprime: 87080933638459254990190759549329249427007327139393378403507376787968543052358925725338774979411611152080797622523844393187

If you have not factored it, how do you know it is a P_2?

What is the source of this number?

[jasonp]

Probably a crackme. Reverse engineers love to give each other little puzzles, but a 512-bit made-up RSA key is a rather large puzzle :)

[Christenson]

Student question, ignoring the obvious ethics issues raised by Jason:
Suppose I know nothing of Hian's number. How, besides feeding it to TF, or otherwise factoring it, would I show that it was indeed a semiprime? (I'm still working on MPQS as an introduction to NFS)

[R.D. Silverman]

Originally Posted by Christenson

Student question, ignoring the obvious ethics issues raised by Jason:
Suppose I know nothing of Hian's number. How, besides feeding it to TF, or otherwise factoring it, would I show that it was indeed a semiprime? (I'm still working on MPQS as an introduction to NFS)

If *he* knows the factors then he can conduct a ZKP with you to convince
you. Otherwise, you are SOL.

[debrouxl]

Well, a GNFS task of difficulty 122 is at most two days of work for a fairly recent dual-core computer, between one and two orders of magnitude easier than a 512-bit RSA key

[RichD]

Originally Posted by Hian

Hi, if your code is working, ...

Why don't you try it and let us know how it works. It is a demo program freely available to anyone that wants to use it.

The author along with several contributors read this forum. If you could report back with parameters selected and timings, it might be helpful for others to see.