View Single Post
Old 2009-12-19, 21:14   #4
ThiloHarich's Avatar
Nov 2005

101 Posts

I think the question akruppa raised is valid.

I analyzed the smooth values and found out that the probability of a factor p being part of the smooth value is much higher then for a random number (which should be clear).
For the SIQS (without large primes) I estimated a value of:

2.2 / (p - 1)^.72

for the expected length of a factor (of the factor base, different from 2) in a smooth decomposition.

So I used this approximation for determining the multiplier. If it differs it always causes a better runtime then the approximation log (p)/p or log (p)/(p-1).
Here are some examples:

N = 25249581771989830594180551024377089571(38)

my multiplier: 59 time : 0.24417041800000003
knuth-schroeppel: 3 time : 0.520334009

N = 24339015700034049398642312663507799431(38)

my multiplier: 11 time: 0.283217839
knuth-schroeppel: 7 time: 0.45216473

N = 15028821219978351294914980921150425953(38)
my multiplier: 2 time: 0.241755027
knuth-schroeppel: 1 time: 0.6213507580000001

From my point of view the p-1 approximation is better then the p since the following facts:

A random number is dividable by a factor p with probability 1/p. With probability 1/p^2 it is dividable by p^2.
So the resulting length of the exponent of a factor p is
log (p)/p + 2*log (p)/p^2 + 3*log (p)/p^3 + ... =
log (p)/p * (1 + 1/p + 1/p^2 + ..) =
log (p)/p * (1/(1-1/p)) = log (p) * (1/(p-p/p)) = log (p) /(p-1)

I will try running the sieve with different multipliers lets say k_1, k_2, k_3 with polynomials including the factors k_2*k_3, k_1*k_3, k_1*k_2. So the conguences are all mod k_1*k_2*k_3. Will this work?
ThiloHarich is offline   Reply With Quote