Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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. – fgrieu Nov 12 '12 at 19:09
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. – Sam Kennedy Nov 12 '12 at 19:30
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. – fgrieu Nov 12 '12 at 19:46
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. – Sam Kennedy Nov 12 '12 at 22:55
Try Carl Pomerance's Smooth numbers and the quadratic sieve – fgrieu Nov 14 '12 at 11:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.