The heaviest part of QS is to search for bSmooth numbers.
So far I thought about two algorithms for solving this.
- 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