title: How to use Logarithm in the Sieving step of Quadratic Sieve technique
body: <p>I am working on a program to factor large semi-prime numbers. I am using the simple Quadratic Sieve technique. My program works well but lot slower because during the sieving process (when I was looking for B-Smooth numbers), I used division process (division method of Java "BigInteger" class). I heard that using logarithm instead of division can make it much faster. Now I know how logarithm works but I don't understand how can I fit the log operator instead of division because, in the sieving process where I need to divide the number to find it's all the prime factors. </p>
  
  <p>Here is an example:</p>
  
  <p>N=15347, number to be factored.
  rootN = Ceil(sqrt(N)) = 124, factor base {2, 17, 23, 29}</p>
  
  <p>Q(x) = (124+x)^2 - N</p>
  
  <p>Now, for some x we need to find Q(x) that are completely factored over the factor base:</p>
  
  <p>Q(0) = (124+0)^2 - N = 29 = 2^0 + 17^0 + 23^0 + 29^1 : B-Smooth number</p>
  
  <p>Q(1) = (124+1)^2 - N = 278 = NOT completely factored over the factor base.</p>
  
  <p>Q(2) = (124+2)^2 - N = 529 = 2^0 + 17^0 + 23^2 + 29^0 : B-Smooth number</p>
  
  <p>Q(3) = (124+3)^2 - N = 782 = 2^1 + 17^1 + 23^1 + 29^0 : B-Smooth number</p>
  
  <p>and so on,</p>
  
  <p>So, to determine B-Smooth number, we need to try to divide the Q(x) with all the primes of the factor base and with their maximum possible exponent. I also used the Tonelli–Shanks algorithm to speed up finding B-Smooth numbers. Still I need the mod and division process to determine whether Q(x) is a B-Smooth or not.</p>
  
  <p>Now I don't understand how can I use logarithm to avoid division that can help finding B-smooth numbers quickly.</p>
  
  <p>Thank you.</p>