48-bit large primes! - Page 2

jasonp · 2009-09-22, 16:00

Was that the complete input file? I can't get any relations produced even when I fill in alim, lpb[ra], etc.

(I'm using the latest GGNFS source; can you tell I don't do lattice sieving often?)

fivemack · 2009-09-22, 16:32

Sorry: cut-and-paste error on my part. Omitting mfba and mfbr makes gnfs-lasieve4I1?e use defaults which cause no relations to be found ...

Code:

n: 1248763129719355523107879850580906737073652359373784929661233741389327470271436463810348813
skew: 269019.30
Y0: -4938227649481593747717
Y1: 517398632491
c0: -871341534477377379017980
c1: 69959334784958737916
c2: 186442429493209
c3: -1091661800
c4: 2100
alim: 1000000
rlim: 1000000
lpba: 33
lpbr: 33
mfba: 66
mfbr: 66
alambda: 2.6
rlambda: 2.6

Raman · 2009-09-22, 19:46

Is this number 2,877- that is giving error on the square root phase with msieve upon using 33 bit large primes? Why does this number use up only an algebraic factor base limit of 1 million, and then that degree 4 polynomial only, within the file? If it is not so, what number it is so?

fivemack · 2009-09-22, 21:13

This is a random C91 (index 1056 of aliquot sequence starting 560328); I have my own script for chasing aliquot sequences, it does GNFS when that's the right thing to do, and this means I have a load of GNFS polynomials for small numbers lying around.

jasonp · 2009-09-23, 20:05

Tom, we were both right; problem fixed in SVN 60.

Note that only about 10% of the relations in the dataset had a large prime > 2^32, and each dependency only had 100-200 of those relations out of ~85000. It's possible you have to tweak mfb[ra] to be more than 2*lpb[ra] if you want lots of large primes near the specified bound.

jrk · 2010-06-01, 05:11

Quote:

Originally Posted by fivemack

Code:

n: 1248763129719355523107879850580906737073652359373784929661233741389327470271436463810348813
skew: 269019.30
Y0: -4938227649481593747717
Y1: 517398632491
c0: -871341534477377379017980
c1: 69959334784958737916
c2: 186442429493209
c3: -1091661800
c4: 2100
alim: 1000000
rlim: 1000000
lpba: 33
lpbr: 33
mfba: 66
mfbr: 66
alambda: 2.6
rlambda: 2.6

Quote:

Originally Posted by jasonp

Note that only about 10% of the relations in the dataset had a large prime > 2^32, and each dependency only had 100-200 of those relations out of ~85000. It's possible you have to tweak mfb[ra] to be more than 2*lpb[ra] if you want lots of large primes near the specified bound.

I think that's because the lambda values are too low for finishing the large composites. If I understand correctly, the ggnfs siever will start rejecting composites larger than about fblim^lambda after sieving, which in this case is much smaller than the mfba,mfbr bits requested, so raising mfba,mfbr will probably do nothing. Using lambda values of about 3.2 or 3.4 with the other parameters unchanged will find many more relations and a bigger proportion of them will have factors >2^32, but it will of course be a lot slower too.

fivemack · 2010-06-01, 11:27

That's interesting. I hadn't tried making lambda that big because I'd done experiments that showed that 2.8 gave the same answer as 2.6, and I _thought_ that the restriction to two large primes meant that very large lambda values didn't make sense.

I had thought that the cutoff was 2^(lpba*lambda), not alim^lambda !

So in this case going from lambda=2.6 to lambda=3.5 is giving me three times as many relations per Q (admittedly at the price of slowing time-per-relation by a factor eight). I'm still seeing only two large primes per side, but many more relations with very large large-primes on both sides.

Andi47 · 2010-06-01, 11:55

Quote:

Originally Posted by fivemack

That's interesting. I hadn't tried making lambda that big because I'd done experiments that showed that 2.8 gave the same answer as 2.6, and I _thought_ that the restriction to two large primes meant that very large lambda values didn't make sense.

I had thought that the cutoff was 2^(lpba*lambda), not alim^lambda !

So in this case going from lambda=2.6 to lambda=3.5 is giving me three times as many relations per Q (admittedly at the price of slowing time-per-relation by a factor eight). I'm still seeing only two large primes per side, but many more relations with very large large-primes on both sides.

Does it make sense to rise the lambdas for running projects like 2801^79-1 or alq4788.2529?

fivemack · 2010-06-01, 12:45

I don't think it makes a difference for current projects, because for 2801^79-1 we have alim=2^27, and 2.6 * 27 is already greater than mfba; for the aliquot job alim=2^26, and 2.6*26 is also large enough.

Whilst in this case alim=2^20, and 2.6*20 is substantially less than 66.

jasonp · 2010-06-01, 13:46

For future reference, can the existing sievers find large primes larger than 2^33? There is a check to reject them, but is that the only thing stopping them from appearing in relations?

I ask because if I ever add MPI support to the LA then there may be a groundswell of support for doing a large job.

fivemack · 2010-06-01, 13:58

I checked that all the calculations were being done in mpz_t rather than in unsigned long, removed the check, and managed to do some sieving with 36-bit large primes; but this was a while ago, and I don't think I completed the job.

2009-09-23, 20:05	#16
jasonp Tribal Bullet Oct 2004 3²×5×79 Posts	Tom, we were both right; problem fixed in SVN 60. Note that only about 10% of the relations in the dataset had a large prime > 2^32, and each dependency only had 100-200 of those relations out of ~85000. It's possible you have to tweak mfb[ra] to be more than 2lpb[ra] if you want lots of large primes near the specified bound. Last fiddled with by jasonp on 2009-09-23 at 20:09*

2010-06-01, 11:27	#18
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	That's interesting. I hadn't tried making lambda that big because I'd done experiments that showed that 2.8 gave the same answer as 2.6, and I _thought_ that the restriction to two large primes meant that very large lambda values didn't make sense. I had thought that the cutoff was 2^(lpbalambda), not alim^lambda ! So in this case going from lambda=2.6 to lambda=3.5 is giving me three times as many relations per Q (admittedly at the price of slowing time-per-relation by a factor eight). I'm still seeing only two large primes per side, but many more relations with very large large-primes on both sides. Last fiddled with by fivemack on 2010-06-01 at 11:30*

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

2009-09-22, 16:00	#12
jasonp Tribal Bullet Oct 2004 6743₈ Posts	Was that the complete input file? I can't get any relations produced even when I fill in alim, lpb[ra], etc. (I'm using the latest GGNFS source; can you tell I don't do lattice sieving often?)

2009-09-22, 19:46	#14
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 10011101001₂ Posts	Is this number 2,877- that is giving error on the square root phase with msieve upon using 33 bit large primes? Why does this number use up only an algebraic factor base limit of 1 million, and then that degree 4 polynomial only, within the file? If it is not so, what number it is so?

2009-09-22, 21:13	#15
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 14466₈ Posts	This is a random C91 (index 1056 of aliquot sequence starting 560328); I have my own script for chasing aliquot sequences, it does GNFS when that's the right thing to do, and this means I have a load of GNFS polynomials for small numbers lying around.

2010-06-01, 12:45	#20
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1100100110110₂ Posts	I don't think it makes a difference for current projects, because for 2801^79-1 we have alim=2^27, and 2.6 * 27 is already greater than mfba; for the aliquot job alim=2^26, and 2.626 is also large enough. Whilst in this case alim=2^20, and 2.620 is substantially less than 66.

2010-06-01, 13:46	#21
jasonp Tribal Bullet Oct 2004 3²×5×79 Posts	For future reference, can the existing sievers find large primes larger than 2^33? There is a check to reject them, but is that the only thing stopping them from appearing in relations? I ask because if I ever add MPI support to the LA then there may be a groundswell of support for doing a large job.

2010-06-01, 13:58	#22
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	I checked that all the calculations were being done in mpz_t rather than in unsigned long, removed the check, and managed to do some sieving with 36-bit large primes; but this was a while ago, and I don't think I completed the job.