1
$\begingroup$

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.

$\endgroup$

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.