lots of large primes

Peter Hackman · 2008-08-14, 07:02

I going over my QS hobby programs I've been running two versions, one with multipliers, one without.

Typically my runs have been on 50-digit numbers (as I've indicated elsewhere my Python programs are very slow), sieving interval [-10**5, 10**5], factorbase 3000, lowest prime sieved on 37, large prime bound 200*pmax. I've sieved until smooths+0.07*partials exceeds 0.96*length of factor base. This is safe, not to say pessimistic, as I usually get
something like 100-200 relations.

However, in some cases, especially when the multiplier is small, I get an enormous amount of redundance, slowing things down considerably. In other words, in these cases I get many more matches
than expected.
I suppose I could modify my program
to deal with this phenomenon. Just curious whether there is some simple explanation for it.

jasonp · 2008-08-14, 12:34

Hard to say without knowing more about your implementation, but even with SIQS the number of duplicates is not expected to be large. I would suspect a bug, or at least inadvertent selection of the same polynomials multiple times. The other possibility is that your factor base is too small, so that if you only allow one large prime above the factor base bound then that large prime occurs often, in many relations.

Peter Hackman · 2008-08-15, 14:26

Perhaps the example below helps clarify my observations/questions.
I've run it with varying small primes bounds (but always the same tolerance term, 2*int(log(pmax))
and factor base sizes. In my program the ideal seems to be a little above 2000, giving a number of factorizations very close to, sometimes slightly smaller than, the size of the factor base.
Each polynomial gives rise to 10 plus or minus 3 trials and I believe the success rate is something like 85-90% (I've no idea how many candidates I'm missing!). What strikes me is the much larger percentage of matches in the first case, and this is a recurring observation.

N=27656492312230575123821463511979706363619541782727
smoothness bound 45000,
about 2400 primes.
smalles prime sieved on: 37.

multiplier 3:

1793 polynomials
1311 smooths
large prime factorizations 13132
matches 1774
number of relations: 785

multiplier 1:

1575 polynomials
1216 smooths
large prime factorizations: 14943
matches: 1277
number of relations: 170

This is really a different topic, but I don't get duplicate polynomials. I generate the a=q*q coefficients by picking a number at random in a small neighborhood of the ideal size and look for the next larger prime number q
with q&3=3.
I keep a list of the q's and check for duplicates (I've tried hashing, too). For some reason this approach seems to be faster than stepping outwards from the ideal! I'm sure there are better ways, but I haven't seen any discussion of this in the literature.

2008-08-14, 07:02	#1
Peter Hackman Oct 2007 linköping, sweden 2²×5 Posts	lots of large primes I going over my QS hobby programs I've been running two versions, one with multipliers, one without. Typically my runs have been on 50-digit numbers (as I've indicated elsewhere my Python programs are very slow), sieving interval [-105, 105], factorbase 3000, lowest prime sieved on 37, large prime bound 200pmax. I've sieved until smooths+0.07partials exceeds 0.96length of factor base. This is safe, not to say pessimistic, as I usually get something like 100-200 relations. However, in some cases, especially when the multiplier is small, I get an enormous amount of redundance, slowing things down considerably. In other words, in these cases I get many more matches than expected. I suppose I could modify my program to deal with this phenomenon. Just curious whether there is some simple explanation for it. Last fiddled with by Peter Hackman on 2008-08-14 at 07:36*

2008-08-14, 12:34	#2
jasonp Tribal Bullet Oct 2004 3,559 Posts	Hard to say without knowing more about your implementation, but even with SIQS the number of duplicates is not expected to be large. I would suspect a bug, or at least inadvertent selection of the same polynomials multiple times. The other possibility is that your factor base is too small, so that if you only allow one large prime above the factor base bound then that large prime occurs often, in many relations. Last fiddled with by jasonp on 2008-08-14 at 12:36

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Post Lots and Lots of Top-5000 Primes Here	Kosmaj	Riesel Prime Search	1984	2022-07-22 04:12
Inefficient behaviour in yafu when doing large NFS with lots of threads	2147483647	YAFU	3	2016-12-25 21:44
48-bit large primes!	jasonp	Msieve	24	2010-06-01 19:14
POST LOTS AND LOTS AND LOTS OF PRIMES HERE	lsoule	Riesel Prime Search	1999	2010-03-17 22:33
Why only three large primes	fivemack	Factoring	18	2007-05-10 12:14

2008-08-15, 14:26	#3
Peter Hackman Oct 2007 linköping, sweden 24₈ Posts	Perhaps the example below helps clarify my observations/questions. I've run it with varying small primes bounds (but always the same tolerance term, 2int(log(pmax)) and factor base sizes. In my program the ideal seems to be a little above 2000, giving a number of factorizations very close to, sometimes slightly smaller than, the size of the factor base. Each polynomial gives rise to 10 plus or minus 3 trials and I believe the success rate is something like 85-90% (I've no idea how many candidates I'm missing!). What strikes me is the much larger percentage of matches in the first case, and this is a recurring observation. N=27656492312230575123821463511979706363619541782727 smoothness bound 45000, about 2400 primes. smalles prime sieved on: 37. multiplier 3: 1793 polynomials 1311 smooths large prime factorizations 13132 matches 1774 number of relations: 785 multiplier 1: 1575 polynomials 1216 smooths large prime factorizations: 14943 matches: 1277 number of relations: 170 This is really a different topic, but I don't get duplicate polynomials. I generate the a=qq coefficients by picking a number at random in a small neighborhood of the ideal size and look for the next larger prime number q with q&3=3. I keep a list of the q's and check for duplicates (I've tried hashing, too). For some reason this approach seems to be faster than stepping outwards from the ideal! I'm sure there are better ways, but I haven't seen any discussion of this in the literature.