1
$\begingroup$

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
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Ilya Gazman Jan 31 '16 at 10:10
  • $\begingroup$ There are many resources on the quadratic sieve other than Wikipedia. Perhaps some of them contain better descriptions. $\endgroup$ – Yuval Filmus Jan 31 '16 at 10:16
  • $\begingroup$ 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. $\endgroup$ – Ilya Gazman Feb 1 '16 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.