Factoring in the Quadratic Sieve

[ThiloHarich]

I have Implemented the MPQS.
After sieving you have to decomposit the generated values into the primes.
By most algorithms (i read) this is done by trial division (so do I).
This stage uses the same time as the sieving step (i have tested this only on small inputs around 40 Digits).

Which of the known factoring algorithms is recommended for this step?

[R.D. Silverman]

Originally Posted by ThiloHarich

I have Implemented the MPQS.
After sieving you have to decomposit the generated values into the primes.
By most algorithms (i read) this is done by trial division (so do I).
This stage uses the same time as the sieving step (i have tested this only on small inputs around 40 Digits).

Which of the known factoring algorithms is recommended for this step?

Do the factoring by resieving.

Save the locations you believe are smooth.
Resieve. Whenever you hit a location that you think is smooth,
instead of accumulating a scaled logarithm of the prime, save the prime itself.

Split the large cofactors by a 'tiny' QS that does not use the large
prime variation. Although for composites of (say) less than 60 digits,
SQUFOF will be almost as fast.

[xilman]

Originally Posted by R.D. Silverman

Do the factoring by resieving.

Save the locations you believe are smooth.
Resieve. Whenever you hit a location that you think is smooth,
instead of accumulating a scaled logarithm of the prime, save the prime itself.

Split the large cofactors by a 'tiny' QS that does not use the large
prime variation. Although for composites of (say) less than 60 digits,
SQUFOF will be almost as fast.

Good advice.

Arjen Lenstra implemented and I evaluated the use of ECM to split large cofactors. It was better than SQUFOF. We never tried mini-QS.

I even tried using Fermat to split the bicomposites, just for the fun of it. Somewhat to my surprise, it worked remarkably well. It uses such fast primitives that on numbers known to have two factors of similar magnitude it's almost competitive with SQUFOF. I did, of course, employ an early-abort strategy to avoid wasting too much time on any particular cofactor.

Paul

[ThiloHarich]

Resieving is what I actually do.
Is the QS still the best method to find the factors, even if we know that the factors have to be small?
If we have not found many factors, it makes no sense to start at sqrt (n) to find the factors.

An other question.
While sieving we have to determine a^-1 mod p, were a is the factor of the sieving polynomial (ax+b)^2 - n and p is a factor of the factor base.
I compute a^1 mod p by the extended Euclidean algorithm.
Are there faster algorithms? I heard of an unpublished paper of Richard Schroeppel. This algorithm is used in the java class BigInteger.

Back to my idea:
We can compute a^1 mod p via a^(p-2) mod p. This is only a bit slower then the extended Euclidean algorithm.
If a is 2^k then a^1 mod p = 2^k*(p-2) mod p. So we only need a fast algorithm for calculating the modulus.
In practice we need a few a's.

[akruppa]

Is resieving worthwhile for very small primes? It seems to me that those would cause a large number of sieve locations being invesigated while having a low probability of hitting a location marked as smooth (a small prime dividing an integer does not increase the probability of that integer being smooth by much, unlike larger primes). Maybe only resieve by primes between some lower and upper bound?

Alex

[ThiloHarich]

We do not have to inspect all locations for (small) factors p.
If y = (ax+b)^2 - n we just have to look if the value of (ax+b) mod p is the same as one of the roots of n mod p:

For a y= (ax+b)^2 to be factorized and a factor p of the Factor base I calculate (ax+b) mod p.
For the p we have already calculated the (two) values t^2 = n mod p.
If y = t mod p we know that p divides y.
Since a,b,x were longs y mod p can be calculated fast.

This is the way I do it. Instead of calculating y/p.
I think this is what R.D. Silverman mens with resieving.

[R.D. Silverman]

Originally Posted by akruppa

Is resieving worthwhile for very small primes? It seems to me that those would cause a large number of sieve locations being invesigated while having a low probability of hitting a location marked as smooth (a small prime dividing an integer does not increase the probability of that integer being smooth by much, unlike larger primes). Maybe only resieve by primes between some lower and upper bound?

Alex

This is what both my QS and lattice siever do. One of the algorithm
parameters is a TRIAL_DIVISION_CUTOFF. If p is smaller, I trial divide.
If larger, I resieve. This also cuts down on space requirements.

Experimentation is need to determine the best value for this cutoff; it
is implementation dependent and *strongly* depends on the speed of the
integer division hardware on one's machine.

[ThiloHarich]

I start with the small primes as long as the y is bigger the a primitive long value. I check if ax+b is a root of n mod the small prime. If so I divide y by the prime. If y is a long value I switch to trial division.
If the y (reduced by the dividing primes) is lower the the maximal factor of the factor base, the y is a factor of the origianl y itself, and we can stop here.

[jasonp]

Originally Posted by akruppa

Is resieving worthwhile for very small primes? It seems to me that those would cause a large number of sieve locations being invesigated while having a low probability of hitting a location marked as smooth (a small prime dividing an integer does not increase the probability of that integer being smooth by much, unlike larger primes). Maybe only resieve by primes between some lower and upper bound?

When the number to be factored is very small (say under 100 bits) the trial factoring of sieve values takes much longer than the sieving. Resieving is a win as long as the the number of sieve values out of a sieve block needing trial factoring is large. You can skip the smaller factor base primes primes entirely during sieving and manually divide by all of them during trial factoring (after choosing a more generous trial factoring cutoff log value). Bob's QS implementation sieves with the powers of these small primes, mine doesn't sieve with them at all. Each approach has its advantages.

When the input becomes larger and the number of sieve values that need trial factoring per sieve block goes down, I've found it more efficient to skip resieving entirely. Instead you can first fill up a set of hashtables with the locations, log values and primes of every sieve update, then use the hashtable both to compute all the logs of values and to speed up trial factoring. This does mean that your sieve blocks have to be comparatively tiny, and that your siever will use a lot more memory than it has to, but it's a good compromise between sieving fast and trial factoring fast.

Once you try factoring ~60 digit composites you'll start seeing runtime differences from these techniques. Below about 50 digits everything will finish essentially instantly.

jasonp

[ThiloHarich]

I also thought of storing the factors in a Hashmap for each location, to avoid the trial division.

But even storing even one (the highest) factor increases the sieving stage so dramatically (factor 2) that it is slower then the version with the complete trial division stage. In my implementation trial division has the same running time as sieving.
Only storing the highest factor uses just another array. Storing all factors uses much more resources (Hashmap or array) and time.

[ThiloHarich]

At the moment I have only implemented the MPQS, where the sieving interval is larger then the sieving interval in the SIQS. The sieving interval m is a few times bigger then the largest prime. So calculating a * x + b mod p might be faster then resieving.

In SIQS the sieving interval and the larges prime might be in the same area, so resieving will be fast for big factors.

For larger n a ~ sqrt (n)/m and b were no long values. But even if I calculate a * x + b mod p with arbitrary precision this is fast.

My imprecise profiling tool is telling me that sieving takes twice as long as factoring the sieved values. If I eliminate the factoring step the sieving and factoring step decreases only by 1/5.

Forget about my other idea. Calculating the mod is to slow.
Anyway how do you calculate the modular inverse?