# What is the most efficient way to find bSmooth values in QS?

The heaviest part of QS is to search for bSmooth numbers.

So far I thought about two algorithms for solving this.

1. Trial division
• calculate $$X$$ as a product of all the values in the factor base
• speed up the trial division with $$gcd(X,Y)$$ where $$Y$$ is a potential bSmooth value

## 1 Answer

The most efficient method is to use a sieve; this is why the method is called the quadratic sieve. It should be mentioned, though, that the sieve is just an optimization over Dixon's method, and doesn't affect the asymptotic running time apart from some (multiplicative) lower order terms. For a description of the sieve, you can start with Wikipedia.

• Can you explain a little bit more what they describe in wiki. I understand how they contracted the v vectors out of the prime base in the range of 100. But I don't understand how it's been used latter. Commented Jan 31, 2016 at 10:10
• There are many resources on the quadratic sieve other than Wikipedia. Perhaps some of them contain better descriptions. Commented Jan 31, 2016 at 10:16
• I been reading more about this, and I understand now that by thieving you don't need to ask the question if a number is factor of $Y(x)$. By using your chosen bound you can find all the values that some prime $p$ is their factor. So unless I yet not understanding it all, you answer does not answering the question. Because even if I know that $p$ is a factor of some value $a$ I also need to check if $p^k$ is also a factor, if so I need to keep dividing, but this brings me to ground zero and back to the original question. Commented Feb 1, 2016 at 8:14