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.

Here is an example:

N=15347, number to be factored. rootN = Ceil(sqrt(N)) = 124, factor base {2, 17, 23, 29}

Q(x) = (124+x)^2 - N

Now, for some x we need to find Q(x) that are completely factored over the factor base:

Q(0) = (124+0)^2 - N = 29 = 2^0 + 17^0 + 23^0 + 29^1 : B-Smooth number

Q(1) = (124+1)^2 - N = 278 = NOT completely factored over the factor base.

Q(2) = (124+2)^2 - N = 529 = NOT completely factored over the factor base.

Q(3) = (124+3)^2 - N = 782 = 2^1 + 17^1 + 23^1 + 29^0 : B-Smooth number

and so on,

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.

Now I don't understand how can I use logarithm to avoid division that can help finding B-smooth numbers quickly.

Thank you.


Your Answer

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

Browse other questions tagged or ask your own question.