mersenneforum.org 48-bit large primes!
 Register FAQ Search Today's Posts Mark Forums Read

 2009-09-21, 21:51 #1 jasonp Tribal Bullet     Oct 2004 23·5·89 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 72458 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, 01:24 #4 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 645410 Posts 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!
 2009-09-22, 03:06 #5 jasonp Tribal Bullet     Oct 2004 23×5×89 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, 06:19   #6
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

5×7×173 Posts

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?

2009-09-22, 08:56   #7
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·439 Posts

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

2009-09-22, 09:18   #8
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2·7·461 Posts

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?
Attached Files
 msieve-svn55.repeatedly.txt.gz (28.9 KB, 248 views)

Last fiddled with by fivemack on 2009-09-22 at 09:18

2009-09-22, 09:20   #9
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

11001001101102 Posts

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.

 2009-09-22, 11:54 #10 jasonp Tribal Bullet     Oct 2004 1101111010002 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.
 2009-09-22, 13:30 #11 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 11001001101102 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Riesel Prime Search 3 2013-08-20 00:32 Peter Hackman Factoring 2 2008-08-15 14:26 jasonp Factoring 4 2007-12-04 18:32 fivemack Factoring 18 2007-05-10 12:14 Prime Monster Lounge 34 2004-06-10 18:12

All times are UTC. The time now is 18:40.

Tue Mar 28 18:40:46 UTC 2023 up 222 days, 16:09, 0 users, load averages: 1.09, 0.96, 0.89