48-bit large primes!
 

SVN 55 and up now include support throughout the NFS postprocessing for prime factors up to 48 bits in size for relations. The changes were fairly straightforward, but it took a great deal of time to rearrange the code to be modular enough for the changes to just drop in.

Runtime should not be affected adversely (most of the filtering uses an intermediate representation of relations that doesn't care how many bits the primes have) although memory use at the start of singleton removal will increase somewhat.

I've done some basic tests for large primes < 2^32, so who wants to be brave and use wildly inappropriate large prime sizes on a small job to test large primes > 2^32 ? Can the GGNFS siever even handle large primes that large?

These changes should hopefully be enough so that the only bottleneck to doing huge jobs is the linear algebra. I don't know when I'll be able to focus my attention on that, but hopefully these changes buy me some time to stay ahead of mersenneforum and NFS@Home :)

The GGNFS siever has a check that its large primes are no more than 33 bits, but as far as I can tell there's no underlying reason for this; the large primes come out at the post-factoring stage and at that point you've evaluated f(x,y) as an mpz_t.

The yields from using 33-bit large primes to sieve a C91 are somewhat impressive; about 600,000 relations per kiloQ and 3k relations per second. Of course, the winnowing from singleton removal is equally impressive; sieving overnight and will try to see if I get a matrix in the morning :)

(for example, it is not until 4.9 million unique input relations and 9.7 million unique input ideals that I first get an ideal surviving singleton reduction)

Hooray! Very cool.

I think the GGNFS siever can go to 33 bit large primes... don't know how hard of a stop that is.

fivemack beat me to it... seeing similar sieving/filtering results with a slightly larger number which I'm now killing.

Actually, this doesn't seem quite to be working with the 33-bit large primes; starting with 21.8M relations, it makes a matrix of reasonable-looking size, but then at least the first ten dependencies give an error that I've not seen before:

[code]
Tue Sep 22 02:14:23 2009 reading relations for dependency 8
Tue Sep 22 02:14:23 2009 read 123377 cycles
Tue Sep 22 02:14:23 2009 cycles contain 496240 unique relations
Tue Sep 22 02:14:32 2009 read 496240 relations
Tue Sep 22 02:14:35 2009 multiplying 496240 relations
Tue Sep 22 02:15:33 2009 multiply complete, coefficients have about 20.44 million bits
Tue Sep 22 02:15:33 2009 initial square root is modulo 740671
Tue Sep 22 02:17:51 2009 dependency does not form a congruence of squares!
[/code]

Rats. The error comes about because squaring the rational and algebraic square roots does not result in the same residue mod N. The algebraic square root doesn't care if relations have large factors, and the code for the rational square root is really simple, so my guess is that it's something to do with the formation of ideals when the underlying prime exceeds 2^32. The internal checks in the square root (powers of primes, powers of ideals, product of relations, Newton iteration) all pass, so all of the postprocessing produces internally consistent answers. I'll check a few more things.

PS: does SVN 56 change anything?

[quote=akruppa;169889]I emailed Thorsten and asked for the latest version of the lattice siever. Here it is. It has 64 bit code and supports special-q > 2^32.

Alex[/quote]

does this help with the siever limitation?

[quote=henryzz;190630]does this help with the siever limitation?[/quote]
The new msieve will be able to reap what that new siever* (lasieve5 branch) may sometime soon sieve.

lasieve4 is limited at 32-bit, lasieve5 is not.

[SIZE=1]*reminds me (or anyone else!) to take some time to merge the recent patches into that code. While it is new(-er) and undoubtedly bett...(-er), the redu2.c looked exactly the same as in the old code (therefore it may infinitely loop) and some other places looked untouched...[/SIZE]

I left the siever running and an endless loop calling post-processing overnight, and got the log file attached, which shows quite a nice case of making too sparse a matrix, but no factors. Rerunning with the top 25M relations and svn-56 I get the same problem.

Anything more I can do to debug?

[QUOTE=Batalov;190642]The new msieve will be able to reap what that new siever* (lasieve5 branch) may sometime soon sieve.

lasieve4 is limited at 32-bit, lasieve5 is not.
[/QUOTE]

As far as I remember, the 32-bit to which lasieve4 is limited is the small-prime bound; I'm not sure even RSA768 needs 32-bit small primes.

Can you remove relations with large primes above 2^32 and check if the filtering still works? Otherwise the only thing I can suggest is to upload a block of relations somewhere for me to go through manually...

Alternately, which siever and input file did you use? For a tiny problem like this I can generate the relations myself.

Input file was

[code]
n: 1248763129719355523107879850580906737073652359373784929661233741389327470271436463810348813
skew: 269019.30
Y0: -4938227649481593747717
Y1: 517398632491
c0: -871341534477377379017980
c1: 69959334784958737916
c2: 186442429493209
c3: -1091661800
c4: 2100
alim: 1000000
[/code]

and it looks as if gnfs-lasieve4I13e -a input.file -f 1000000 -c 45000 will generate in about four hours enough relations to show the problem. Which is probably logistically easier than uploading 1.8GB through the straws I have ...

I did

mv msieve.dat msieve.dat.0
egrep -v ":.*1[0-9a-f]{8}" msieve.dat.0 > msieve.dat

which I think removes the 33-bit primes, but am still getting the 'dependency does not form a congruence of squares!' errors.

I'm wondering if there might be a signed/unsigned int32 issue somewhere;

[code]
mv msieve.dat msieve.dat.1
egrep -v ":.*[89abcdef][0-9a-f]{7}" msieve.dat.1 > msieve.dat
[/code]

so I'm only working with 31-bit large primes gives no errors, and indeed gives factors on the fourth dependency