I've been trying to figure out how sieving works in the quadratic sieve factorization algorithm. Example: to factorize 90283. The ceil of the square root of 90283 is 301. We generate a sequence $x^{2}$ - 90283, starting from x = 301. The first couple of values are:
318, 921, 1526, 2133, 2742, 3353, 3966, 4581, 5198, 5817, 6438, 7061, 7686, 8313, 8942, 9573, 10206, 10841, 11478, 12117, 12758, 13401, 14046, 14693, 15342, 15993, 16646, 17301, 17958, 18617.
Choosing a smoothness bound of 30, our factor base is: {2,3,7,17,23,29}.
Using Shanks Tonelli algorithm to compute square roots of 90283 modulo primes in the factor base, one solution set corresponding to the factor base in order is {0,1,2,8,10,8}.
I know I need to sieve the sequence for smooth numbers using values from the Shanks Tonelli algorithm, this is where I'm stuck, how do I go about this?
The exact steps depend on the optimizations involved.
But in a simple form, this is what you could do.
You take the first number in your list - i.e. 318 & then sieve it with the first number from your factor base. 318 is now reduced to 159. Then you divide by next one by one with all the numbers in your factor base, it remains 53 till the end of the factor base, so it isn't part of your solution
On the other if you have a smooth number, then it will sieve down to 1. For e.g. in your list, 10206 is a smooth number. You sieve with 2, it reduces to 5103. You then sieve with 3 & powers of 3. 5103 is divisible by $3^6$ & it reduces to 7. Which is the sieved with 7 & it reduces to 1. So $10206 = 2 * 3^6 * 7$
After doing this for all the numbers, you find all those numbers which have been reduced to 1, by the sieving process. Next step is to find relations between these numbers such that the product of these numbers form a square modulo N. You can do this by Gaussian elimination & then GCD to find the factors.