20090921, 21:51  #1 
Tribal Bullet
Oct 2004
DD1_{16} Posts 
48bit 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 :) 
20090921, 22:05  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
13×491 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 postfactoring stage and at that point you've evaluated f(x,y) as an mpz_t.
The yields from using 33bit 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 20090921 at 22:44 
20090921, 22:07  #3 
"Ben"
Feb 2007
6514_{8} 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 20090921 at 22:09 
20090922, 01:24  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
13·491 Posts 
Actually, this doesn't seem quite to be working with the 33bit large primes; starting with 21.8M relations, it makes a matrix of reasonablelooking 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! 
20090922, 03:06  #5 
Tribal Bullet
Oct 2004
3^{3}·131 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 20090922 at 04:09 
20090922, 06:19  #6 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×29×101 Posts 

20090922, 08:56  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×3×5×313 Posts 
The new msieve will be able to reap what that new siever* (lasieve5 branch) may sometime soon sieve.
lasieve4 is limited at 32bit, 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... 
20090922, 09:18  #8 
(loop (#_fork))
Feb 2006
Cambridge, England
13·491 Posts 
I left the siever running and an endless loop calling postprocessing 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 svn56 I get the same problem.
Anything more I can do to debug? Last fiddled with by fivemack on 20090922 at 09:18 
20090922, 09:20  #9 
(loop (#_fork))
Feb 2006
Cambridge, England
13·491 Posts 
As far as I remember, the 32bit to which lasieve4 is limited is the smallprime bound; I'm not sure even RSA768 needs 32bit small primes.

20090922, 11:54  #10 
Tribal Bullet
Oct 2004
3^{3}·131 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. 
20090922, 13:30  #11 
(loop (#_fork))
Feb 2006
Cambridge, England
13×491 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 I did mv msieve.dat msieve.dat.0 egrep v ":.*1[09af]{8}" msieve.dat.0 > msieve.dat which I think removes the 33bit 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][09af]{7}" msieve.dat.1 > msieve.dat Last fiddled with by fivemack on 20090922 at 15:05 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Where do I send my PRP primes with large k?  Trilo  Riesel Prime Search  3  20130820 00:32 
lots of large primes  Peter Hackman  Factoring  2  20080815 14:26 
NFS with 5 and 6 large primes  jasonp  Factoring  4  20071204 18:32 
Why only three large primes  fivemack  Factoring  18  20070510 12:14 
What is the use of these large primes  Prime Monster  Lounge  34  20040610 18:12 