A large project for the new year

[fivemack]

I am interested, in 2008, in performing a GNFS factorisation of size noticeably greater than 512 bits.

I think all the pieces for this exist: RSA-200 proved that polynomial selection by Kleinjung's code is reasonable up to 200 digits and sieving with the Franke siever demonstrably works that far; msieve is likely to filter and run in reasonable (a quad-core month or so) time provided that the matrix fits in 8GB or so.

Aoki's team has produced matrices of that sort of size for even 176-digit numbers, though I suspect they have at least one filtering technique better than msieve currently offers - their matrices are much smaller and denser than I get by extrapolating from the medium GNFS jobs I've run with msieve. They used parallel linear algebra, but didn't have access to 8GB machines at the time. They also used parallel filtering; filtering takes a bit more memory than the matrix step, but is apparently local enough that it can be allowed to run on fast swap disc.

To get the sieving done in reasonable time will require a few dozen cores, which means I will have to get several people to help, which means it makes sense to ask around for an appropriate number rather than pick one.

I don't see anything obvious on the more-wanted list or the first-five-holes tables: anything with few enough digits is also of small enough SNFS difficulty that you'd use that instead, though the decision is perhaps not absolutely clear for 10^232+1.

My preferred candidate is the cofactor of 6^383+1. It's 165 digits, so would be a second-champion; it has a prime exponent; it has the largest ratio of SNFS difficulty to digit count of any number in the tables.

If that's too far to stretch, there is clearly already interest in 3^527-1 C160/S252, though I'd not want to set up to shoot that fox if akruppa is already ready to hunt it.

If people are not interested in this, I'll return to picking off Cunningham-table entries in order by SNFS difficulty ...

[em99010pepe]

I'm willing to donate my 2.4 GHz quad-core but it only has 2GB of memory. Of course I can easily add more memory but the main issue here is my lack of knowledge on how to run msieve and the rest of the software. I have to study them...the offer stands...

Carlos

[bsquared]

It's not much, but I can offer one core of an Athlon X2 4400+ for lattice sieving. I already have GGNFS up and running via Msys.

[R.D. Silverman]

Originally Posted by fivemack

I am interested, in 2008, in performing a GNFS factorisation of size noticeably greater than 512 bits.

...

How big is "noticeably greater"? 160 digits? 170? 180?

Perhaps you might try one of the following:

12,253+ C169. (via SNFS it is C249)
2,1105- C158 (SNFS is bad via 4th degree)
11,266+ C165
2,1598M C160 (slightly easier than with SNFS)
10,232+ C160
2,832+ C175
2,980+ C162 (definitely easier than SNFS)
2,1012+ C163 ditto.
M827 C172


or really ambitious,

2,1157- c182 etc.

I can suggest some others.

[R.D. Silverman]

Originally Posted by fivemack

I am interested, in 2008, in performing a GNFS factorisation of size noticeably greater than 512 bits.


Aoki's team has produced matrices of that sort of size for even 176-digit numbers, though I suspect they have at least one filtering technique better than msieve currently offers ...

I have my own (very old) filter code; It is witten in Fortran, dates from
1990, and uses intelligent Gaussian elimination. It produces very poor
matrices.

For this reason, I use the CWI filter code. It seems to produce much
better matrices than what I have seen reported by others.

[jasonp]

@fivemack: I suspect Aoki's team uses lattice sieving with composite special-q, in order to avoid a proliferation of large primes that must be dealt with during filtering. Franke has a presentation somewhere that shows the technique produces smaller but denser matrices.

@Bob: comparing the CWI filtering with msieve's filtering is something I'm always interested in. The only head-to-head comparison using the same set of relations, that I've been able to find (for 5,323-), puts the two packages on the same curve of size-vs-density. The CWI matrix was about 10% smaller and about 10% more dense than the msieve version. Do you have additional figures?

Such a large GNFS job is going to be a severe test of msieve's square root. I need to do some work to flush intermediate numbers to disk, in order to allow bigger FFTs, but that's not very involved and it would certainly be done by the time it was needed.

[xilman]

Originally Posted by fivemack

I am interested, in 2008, in performing a GNFS factorisation of size noticeably greater than 512 bits.

I can (very probably) persuade the CWI filtering code to do a good job on a collection of relaions iff:

1) no large prime is > 1e9
2) routines to convert into and out of CWI format are available.

I can possibly provide 2) if they are not already written.

I've about 10 years experience with the CWI code and can generally get a reasonable matrix from some relations. Doing so is much more an art, or possibly a craft, than a science.

FWIW, I just started a 516-bit GNFS (of 2,1574L) on my home machines. It should be finished by April, and possibly earlier if I can persuade a lattice siever to run on my wife's Vista machine at rather more than 1% of the performance of my Linux box.


Paul

[R.D. Silverman]

[QUOTE=jasonp;120359@Bob: comparing the CWI filtering with msieve's filtering is something I'm always interested in. The only head-to-head comparison using the same set of relations, that I've been able to find ([url="http://mersenneforum.org/showpost.php?p=115343&postcount=12"]for 5,323-[/url]), puts the two packages on the same curve of size-vs-density. The CWI matrix was about 10% smaller and about 10% more dense than the msieve version. Do you have additional figures?

QUOTE]

I have my own code, so I have not installed msieve. If you like,
I can gather together all my relations for my current project (6,299-)
and send them to you (on CD; via snail mail). Then we can compare
results. 6,299- should finish sieving in 2-3 days. [it would be done
already if a server hadn't gone down last weekend].

[jasonp]

Originally Posted by R.D. Silverman

I have my own code, so I have not installed msieve. If you like,
I can gather together all my relations for my current project (6,299-)
and send them to you (on CD; via snail mail). Then we can compare
results. 6,299- should finish sieving in 2-3 days.

That would be a good idea; I'll send my snail-mail address via email.

PS: In my previous post I meant 5,317-

[fivemack]

Originally Posted by R.D. Silverman

How big is "noticeably greater"? 160 digits? 170? 180?

I was thinking somewhere around 165 - big enough to be second-champion for Cunningham GNFS, but small enough that I can reasonably extrapolate the runtime, that the polynomial search doesn't itself require substantial multi-contributor logistics, and hopefully that people can use the ggnfs Windows builds of gnfs-lasieve4I14e rather than having to fiddle around with cross-compilers to get a gnfs-lasieve4I15e Windows binary: I have no Windows machine at the moment.

My prejudice is to have a prime exponent and a large SNFS-to-GNFS ratio, which makes 6^383+1 perfect, though I realise it's a long way beyond the smallest holes, and that six isn't prime so I can't claim to be contributing to knowledge about the structure of finite fields.

Perhaps you might try one of the following:

12,253+ C169. (via SNFS it is C249)
2,1105- C158 (SNFS is bad via 4th degree)
11,266+ C165
2,1598M C160 (slightly easier than with SNFS)
10,232+ C160
2,832+ C175
2,980+ C162 (definitely easier than SNFS)
2,1012+ C163 ditto.
M827 C172

That's quite a long list, and I don't quite see the rationale behind its entries; there's one more-wanted, a few early holes, but I'm wondering why something like 2,1012+ is on the list when something like 5,391- (C161, S273) isn't. I presume a factor of 17 in the exponent is useless, and even if you could multiply the difficulty by 16/17 somehow it would still be S258 and easier by GNFS.

[fivemack]

Originally Posted by jasonp

@fivemack: I suspect Aoki's team uses lattice sieving with composite special-q, in order to avoid a proliferation of large primes that must be dealt with during filtering. Franke has a presentation somewhere that shows the technique produces smaller but denser matrices.

I'm not sure that's compatible with (from the Aoki report http://www.loria.fr/~zimmerma/records/11_281+ )

special-Q: only for algebraic side.
 100% of 30.5M-221.2M except 111.5M-113.4M (about 10.2M ideals)
  83% of 28.8M-30.5M, 221.2M-227.0M (about 0.3M)

where pi(221M) - pi(30.5M) is about ten million.

My suspicion is that this is simply significant over-sieving; they use 576M relations where, for LP=2^32, I would have expected to need about 350M to make a barely-adequate matrix.

I don't know what the asymptotics of over-sieving are like: I did one, accidental experiment (http://www.mersenneforum.org/showthread.php?t=9381) in which 26M relations gave no matrix, 27M relations gave a matrix with side 2746454 and cycle-entries 178617306, and 34M gave side 2261961, cycle-entries 147036684, so the weight per row stayed absolutely constant and the side is going down. But I don't know if the conclusion to draw is '7 million relations reduce the side by 20%' or '25% more relations than needed for a minimal matrix reduce the side by 20%', and I don't know whether going further would make the weight per row start to go up.

I suppose I could deliberately grotesquely over-sieve some number, but I don't understand the underlying process enough to know whether results for lp=2^26 will scale to a run with lp=2^31 or whether results for SNFS will be transferrable to GNFS, and I don't particularly want to spend the CPU time to sieve a complete-after-1000-hours problem for a thousand more hours.