2
$\begingroup$

After my failed attempt at trying to implement the ECM, I started working on the quadratic sieve. It works, but the bottleneck is finding smooth values over the factor base.

The way I implemented it now, it generates 250,000 values of X, then calculates Y as:

Y = (X + ceil(sqrt(n)))^2 - n

Where n is the number to be factored. I then iterate through the 250,000 values for Y, and look for the first divisible by a factor in the factor base (p), then divide every p'th element by p. I repeat this for each factor in the factor base.

Then I search for the values of Y which equal 1, and add them to an array, then repeat the above until I have as many as in the factor base + 1.

This process is really slow, I was hoping for suggestions of ways to speed this up, or an explanation on how to generate polynomials so I can try and implement the MPQS. I've read some explanations, but they focus more on the mathematics rather than the 'mechanics' of generating them.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ This is not a proper implementation of the Quadratic Sieve, and multiple polynomials is not the first thing you want to add. The standard technique for QS uses an array (moreless indexed by your X) where the approximate log of the primes in the factor base is added as appropriate, and thus avoids trial division entirely. The savings are enormous. I think we have a resident expert, I hope he'll be able to give pointers, or/and an answer. $\endgroup$
    – fgrieu ♦
    Commented Nov 12, 2012 at 19:09
  • $\begingroup$ I was trying to avoid using the log function since GMP doesn't have one. I don't understand why, it's like having a formula one car which can only make left turns. If there's a way around this, I will get rid of the trial division. I'll see how hard it would be to code my own log function. $\endgroup$
    – Sam Kennedy
    Commented Nov 12, 2012 at 19:30
  • 1
    $\begingroup$ You need a raw approximation of the log, times some scaling factor. Try the number of bits. And of course compute that outside the inner loop. $\endgroup$
    – fgrieu ♦
    Commented Nov 12, 2012 at 19:46
  • $\begingroup$ Okay let's see if I have understood this correctly. n = number to be factored, pmax = highest prime in factor base, M = number of X/Y pairs collected, T = some fudge factor, p = a prime in the factor base 1) Calculate TARGET = (number of bits in n / 2) + number of bits in M 2) CLOSE = TARGET - T * number of bits in pmax 3) Find the first value of Y that is divisible by p, add the number of bits in p to a zero initialised array 4) Repeat for every p'th element 5) If a value in the array is within CLOSE digits to TARGET, then the corresponding Y value is probably smooth. $\endgroup$
    – Sam Kennedy
    Commented Nov 12, 2012 at 22:55
  • 1
    $\begingroup$ Try Carl Pomerance's Smooth numbers and the quadratic sieve $\endgroup$
    – fgrieu ♦
    Commented Nov 14, 2012 at 11:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.