Using p=2 for sieving (Quadratic sieve algorithm)

[jasonp]

Originally Posted by bsquared

That's the value my KS algorithm also kicks out. And I note that it's also what msieve (v1.25) uses for this input. Sometimes its worth a little larger k for the impact to the factor base...

It doesn't happen too often, but it does happen. The Knuth-Schroeppel 'score' reflects the sum of contributions in the factor base, reduced by the log of the multiplier size. If all the smaller multipliers generate significantly worse factor bases, a large multiplier can still be a win.

In fact, choosing an even multiplier is sometimes a win too, despite the fact that it reduces the frequency of powers of two in relations. My test C60 has an optimal multiplier of 6, and msieve runs twice as fast compared to the best odd multiplier.

@smoking81: it's more intuitive to build your matrix so that the columns represent relations and the rows represent primes. This way the solution vector has one bit for every relation (0 = don't use, 1 = use) instead of one bit for every prime.

Also, if you do not use the large prime variation, it's possible for the small prime variation to make things slower. Skipping small primes means you do a lot more trial division, especially if you're only looking for full relations. If trial division is slow compared to sieving, it could result in a net slowdown when you do more of it.

[akruppa]

I couldn't reproduce k=71 as the optimal multiplier... I wrote a quick-and-dirty implementation in Pari/GP of KS as found in TAOCP, 4.5.4:

f(p, d) = {if(d%(p^2)==0,return(2./(p+1)+f(p,d/p^2)/p)); if(d%p==0,return(1/(p+1))); if(p==2&&d%4==3,return(1./3.)); if(p==2&&d%8==5,return(2./3.)); if(p==2&&d%8==1,return(4./3.)); if(kronecker(d,p)==1,return(2*p/(p^2-1))); return(0);}

ks(N, k, n) = {local(s, p); s=0.;forprime(p=2,n,s+=(f(p,k*N)-1/(p-1))*log(p));return(s-log(k)/2);}

I added the -1/(p-1) in ks() to make it converge for n -> ∞.

Now I get

? N=732197471686198597184965476425281169401188191;
? ks(N, 1, 100)
%110 = -0.13205054122432296662436801768407422559
? ks(N, 71, 100)
%111 = -0.86459414391670106086722847847597662319

so a multiplier of 1 seems like the better choice to me, and in fact like the best multiplier < 1000. Other values of n in the ks() call don't change the conclusion (see attached graph).

Something's wrong here (I just hope there's not some dumb bug in my code)

Alex

[smoking81]

Originally Posted by akruppa

I couldn't reproduce k=71 as the optimal multiplier... I wrote a quick-and-dirty implementation in Pari/GP of KS as found in TAOCP, 4.5.4:

f(p, d) = {if(d%(p^2)==0,return(2./(p+1)+f(p,d/p^2)/p)); if(d%p==0,return(1/(p+1))); if(p==2&&d%4==3,return(1./3.)); if(p==2&&d%8==5,return(2./3.)); if(p==2&&d%8==1,return(4./3.)); if(kronecker(d,p)==1,return(2*p/(p^2-1))); return(0);}

ks(N, k, n) = {local(s, p); s=0.;forprime(p=2,n,s+=(f(p,k*N)-1/(p-1))*log(p));return(s-log(k)/2);}

I added the -1/(p-1) in ks() to make it converge for n -> ∞.

Now I get

? N=732197471686198597184965476425281169401188191;
? ks(N, 1, 100)
%110 = -0.13205054122432296662436801768407422559
? ks(N, 71, 100)
%111 = -0.86459414391670106086722847847597662319

so a multiplier of 1 seems like the better choice to me, and in fact like the best multiplier < 1000. Other values of n in the ks() call don't change the conclusion (see attached graph).

Something's wrong here (I just hope there's not some dumb bug in my code)

Alex

Silverman wrote in this same topic that the values of KS should be strictly positive. In fact when I got negative ones I had a bug in my code..
With k=71 my FB begins like this:
-1 2 3 5 7 11 13 19 23 29 59 67 73 83 89 97
with k=1 indeed:
-1 2 5 7 11 17 23 29 41 43 53 59 61 67 73 79 89

so I have more small primes in the FB when k=71... if the aim of evaluating ks is to achieve this result, then k=71 would be better than 1, isn't it?

[R.D. Silverman]

Originally Posted by akruppa

I couldn't reproduce k=71 as the optimal multiplier...



Alex

Something is wrong. I get 15 as the best multiplier......

We try to factor: 732197471686198597184965476425281169401188191
i, test = 1 3
factors = 1 3 11 19 23 31 59 61 73
count = 9
Knuth value = 1.620993
i, test = 3 7
factors = 1 2 7 13 29 53 59 71 97
count = 9
Knuth value = 1.996679
i, test = 4 11
factors = 1 3 5 7 11 13 31 43 47 53 71 79 89
count = 13
Knuth value = 2.176029
i, test = 6 15
factors = 1 2 3 5 7 11 13 17 19 31 37 43 47 53 59 61 67 83 97
count = 19
Knuth value = 3.166916
i, test = 8 19
factors = 1 5 13 17 19 37 47 59 61 67 73 79 83 97
count = 14
Knuth value = 0.929538
i, test = 10 23
factors = 1 2 3 7 11 23 29 31 37 41 43 47 67 71 73 79 97
count = 17
Knuth value = 2.684286
i, test = 12 31
factors = 1 2 5 11 13 19 23 31 37 41 43 47 71 79
count = 14
Knuth value = 2.388305
i, test = 14 35
factors = 1 3 5 7 17 23 29 37 43 47 59 67 71 73 83
count = 15
Knuth value = 1.064989
i, test = 16 39
factors = 1 2 3 5 7 13 23 37 41 47 61 67 71 83 89 97
count = 16
Knuth value = 2.265376
i, test = 18 43
factors = 1 7 17 31 37 41 43 47 53 83
count = 10
Knuth value = 0.205570
i, test = 19 47
factors = 1 2 3 11 13 17 23 43 47 53 61 67 71 83 89
count = 15
Knuth value = 2.171651
i, test = 20 51
factors = 1 3 5 7 17 19 29 37 41 59 71 79 97
count = 13
Knuth value = 0.943500
i, test = 22 55
factors = 1 2 5 11 17 23 31 37 67 71 73 79 83 89 97
count = 15
Knuth value = 1.308345
i, test = 24 59
factors = 1 3 5 11 13 17 19 23 29 37 41 43 53 59 67 71 97
count = 17
Knuth value = 1.692477
i, test = 27 67
factors = 1 7 11 13 17 19 29 43 47 67 71 73 79 83 89 97
count = 16
Knuth value = 0.681312
i, test = 29 71
factors = 1 2 3 5 7 11 13 19 23 29 59 67 71 73 83 89 97
count = 17
Knuth value = 2.970742
i, test = 31 79
factors = 1 2 5 7 19 31 37 43 59 73 79 83 89
count = 13
Knuth value = 1.614011
i, test = 32 83
factors = 1 3 13 17 29 31 41 43 61 67 79 83 97
count = 13
Knuth value = 0.431694
i, test = 35 91
factors = 1 5 7 11 13 19 29 31 37 41 47 53 67 73 83 89
count = 16
Knuth value = 0.603504
i, test = 37 95
factors = 1 2 3 5 7 19 23 43 53 59 61 79
count = 12
Knuth value = 1.745014
i, test = 40 103
factors = 1 2 11 17 19 29 37 41 43 61 67 83
count = 12
Knuth value = 1.191968
Selected multiplier = 15
pmax = 58481


Note that my values of the KS function are all positive........
The output shows the factors in the factor base less than 100 for
each multiplier. I am only using k so that kN = 1 mod 4.

I use a slightly modified version of KS. It ignores the higher powers
of the primes, so the probability is 2/p not 2/(p-1).

The value of the KS function should be positive.

[smoking81]

Originally Posted by bsquared

To optimize the trial division cutoff, manually add or subtract single bits to the result of your formula rather than try to tweak the formula. Then you can quickly see if a higher or lower value helps or not.

Remember that in the small prime variation, you need to abort the trial division if you find that a candidate in fact does not have a lot of small divisors. Two cutoff levels is one way to handle this. Although I suspect that for a number this 'small', the extra overhead may negate the benefit of not sieving by smaller primes.

Over-determined sets of equations always have a solution. Google might have more to say about it.

good luck,
- ben.

I'll try to do as you advise later and report the results.

Originally Posted by bsquared

Depends on what you mean by interesting, but if you have a probable primalty test routine coded up (rabin-miller or equivalent), then you could just find random large primes and multiply them together. Are you using GMP? Maybe it has a prime test routine in there...

thanks a lot for this suggestion! OF course I didn't think of this! ehehe!

[akruppa]

The negative values of my ks() are due to the fact that I subtract 1/(p-1), i.e. the average exponent of p in "random integers" (chosen uniformly at random in [1, x] with x->∞, yadda yadda). I did it that way to be able to see the fluctuation of the result as n varies a bit better. Without that term, the result is indeed positive, and the extra term does not affect the optimal multiplier (for a given n) as it is just an additive term in the result that depends on n but not on N or k.

Alex

PS: I get

? ks(N,1,100)
%124 = -0.13205054122432296662436801768407422559
? ks(N,15,100)
%125 = -0.44704900313343378302569624353501420840
? ks(N,71,100)
%126 = -0.86459414391670106086722847847597662319

so 15 isn't all bad but not as good as 1, according to my ks(). Without the -1/(p-1), my KS value for k=15 is 3.6678, a bit higher than that listed by Bob's code.

[alpertron]

My factorization applet also uses KS multiplier = 1 in this case.

[R.D. Silverman]

Originally Posted by akruppa

The negative values of my ks() are due to the fact that I subtract 1/(p-1), i.e. the average exponent of p in "random integers" (chosen uniformly at random in [1, x] with x->∞, yadda yadda). I did it that way to be able to see the fluctuation of the result as n varies a bit better. Without that term, the result is indeed positive, and the extra term does not affect the optimal multiplier (for a given n) as it is just an additive term in the result that depends on n but not on N or k.

Alex

PS: I get

? ks(N,1,100)
%124 = -0.13205054122432296662436801768407422559
? ks(N,15,100)
%125 = -0.44704900313343378302569624353501420840
? ks(N,71,100)
%126 = -0.86459414391670106086722847847597662319

so 15 isn't all bad but not as good as 1, according to my ks(). Without the -1/(p-1), my KS value for k=15 is 3.6678, a bit higher than that listed by Bob's code.

You are using 1/(p-1), while I used 1/p.

[jasonp]

Originally Posted by smoking81

Silverman wrote in this same topic that the values of KS should be strictly positive. In fact when I got negative ones I had a bug in my code..

so I have more small primes in the FB when k=71... if the aim of evaluating ks is to achieve this result, then k=71 would be better than 1, isn't it?

The KS value corresponding to a given multiplier can be positive or negative, depending on the convention you choose. I find it more convenient to minimize a negative KS value, since this convention can be interpreted as the number of bits added to a random sieve value because of small primes. In that case you add log(sqrt(multiplier)) and subtract 2*log(prime p)/(p-1). You can also flip the signs of everything and maximize a positive KS value.

Remember to account for the multiplier: your factor base can have more small primes but the multiplier could be too large, and sieve values could therefore grow on average, reducing the yield of relations.

[bsquared]

71 seems to work best in practice. Here are some timings for the 3 different multipliers mentioned so far:

no small prime variation:
k = 71, total time = 0.73sec
k = 1, total time = 0.8sec
k = 15, total time = 1sec

I use a KS method similar to jason's, except i test slightly more primes and multipliers, and maximize instead of minimize.

[Peter Hackman]

Originally Posted by jasonp

The factor base should have more than 3000 entries; this is sufficient for self-initializing QS but not ordinary MPQS. Also, your input has 14 digits worth of small factors which you should find via other methods.

Unless my programs are completely wrong,
this number yields completely to Pollard rho; the largest prime factor (38 digits) can be certified by elementary means (Pratt)!