mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2009-09-21, 21:51   #1
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

352810 Posts
Default 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 :)
jasonp is offline   Reply With Quote
Old 2009-09-21, 22:05   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,353 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2009-09-21, 22:07   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·32·7·13 Posts
Default

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
bsquared is offline   Reply With Quote
Old 2009-09-22, 01:24   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

635310 Posts
Default

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!
fivemack is offline   Reply With Quote
Old 2009-09-22, 03:06   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

23×32×72 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2009-09-22, 06:19   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

10110010000002 Posts
Default

Quote:
Originally Posted by akruppa View Post
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?
henryzz is offline   Reply With Quote
Old 2009-09-22, 08:56   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216008 Posts
Default

Quote:
Originally Posted by henryzz View Post
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...
Batalov is offline   Reply With Quote
Old 2009-09-22, 09:18   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

635310 Posts
Default

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
File Type: gz msieve-svn55.repeatedly.txt.gz (28.9 KB, 91 views)

Last fiddled with by fivemack on 2009-09-22 at 09:18
fivemack is offline   Reply With Quote
Old 2009-09-22, 09:20   #9
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,353 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
fivemack is offline   Reply With Quote
Old 2009-09-22, 11:54   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

23×32×72 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2009-09-22, 13:30   #11
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,353 Posts
Default

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
fivemack is offline   Reply With Quote
Reply

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

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

Sat Aug 15 05:18:04 UTC 2020 up 2 days, 1:53, 0 users, load averages: 2.97, 2.83, 2.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.