48-bit large primes!

jasonp · 2009-09-21, 21:51

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 :)

fivemack · 2009-09-21, 22:05

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)

bsquared · 2009-09-21, 22:07

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.

fivemack · 2009-09-22, 01:24

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!

jasonp · 2009-09-22, 03:06

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?

henryzz · 2009-09-22, 06:19

Quote:

Originally Posted by akruppa

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

does this help with the siever limitation?

Batalov · 2009-09-22, 08:56

Quote:

Originally Posted by henryzz

does this help with the siever limitation?

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.

*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...

fivemack · 2009-09-22, 09:18

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?

fivemack · 2009-09-22, 09:20

Quote:

Originally Posted by Batalov

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.

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.

jasonp · 2009-09-22, 11:54

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.

fivemack · 2009-09-22, 13:30

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

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

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

2009-09-21, 21:51	#1
jasonp Tribal Bullet Oct 2004 5·23·31 Posts	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 :)

2009-09-21, 22:05	#2
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	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) Last fiddled with by fivemack on 2009-09-21 at 22:44

2009-09-21, 22:07	#3
bsquared "Ben" Feb 2007 7264₈ Posts	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. Last fiddled with by bsquared on 2009-09-21 at 22:09

2009-09-22, 03:06	#5
jasonp Tribal Bullet Oct 2004 5×23×31 Posts	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? Last fiddled with by jasonp on 2009-09-22 at 04:09

2009-09-22, 13:30	#11
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	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 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 so I'm only working with 31-bit large primes gives no errors, and indeed gives factors on the fourth dependency Last fiddled with by fivemack on 2009-09-22 at 15:05

2009-09-22, 11:54	#10
jasonp Tribal Bullet Oct 2004 DED₁₆ Posts	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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Where do I send my PRP primes with large k?	Trilo	Riesel Prime Search	3	2013-08-20 00:32
lots of large primes	Peter Hackman	Factoring	2	2008-08-15 14:26
NFS with 5 and 6 large primes	jasonp	Factoring	4	2007-12-04 18:32
Why only three large primes	fivemack	Factoring	18	2007-05-10 12:14
What is the use of these large primes	Prime Monster	Lounge	34	2004-06-10 18:12