# Sieve higher powers with logarithmic optimization

I am factoring number $N = 90283$ using quadratic sieve. Bound is $B = 44$. I find factor base to be $\{2, 3, 7, 17, 23, 29, 37, 41\}$. I have $50$ element sieving interval:

$\{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, 19278, 19941, 20606, 21273, 21942, 22613, 23286, 23961, 24638, 25317, 25998, 26681, 27366, 28053, 28742, 29433, 30126, 30821, 31518, 32217\}$

Using Tonelli-Shanks I found starting sieving positions for primes in factor base:

prime: 2 start: 0
prime: 3 start: 0
prime: 3 start: 1
prime: 7 start: 2
prime: 7 start: 5
prime: 17 start: 13
prime: 17 start: 14
prime: 23 start: 11
prime: 23 start: 8
prime: 29 start: 26
prime: 29 start: 10
prime: 37 start: 10
prime: 37 start: 17
prime: 41 start: 28
prime: 41 start: 26


Now for $p \ne 2$ I visit every element in the interval in positions $x_1 + i * p$ and $x_2 + i * p$, when $x_1, x_2 =$ starting position for given $p$ and $i \ge 0$ (for $p = 2$ I have only one sequence $x_1 + i * p$) and divide this element by $p$ until element is not divisible by $p$, such that all higher powers $p^\alpha$ are removed. In the end I get this list:

$\{53, 307, 109, 79, 457, 479, 661, 509, 113, 277, 1, 307, 61, 163, 263, 3191, 1, 293, 1913, 577, 6379, 1489, 2341, 2099, 2557, 1777, 1, 5767, 73, 18617, 1, 1, 10303, 1013, 53, 22613, 3881, 163, 12319, 97, 619, 26681, 4561, 1039, 2053, 9811, 5021, 1, 103, 10739\}$

Values that are reduced to $1$ are $B$-smooth.

This works but there are a lot of divisions. I've read of the ways to speed sieving up: you initialize sieving array and add $\log p$ to $x + i * p$ positions. Smooths then are those that accumulate values close to $2x \sqrt N$.

My question is, how can I know how many times I have to add $\log p$ to take into account all higher powers of $p$?

-

The simple answer is that sieving for prime powers is usually a lot of work without much benefit. However, if you do want to sieve for prime powers, you don't need to do any division at all, you can just do the same thing for prime powers that you are doing for primes in the factor base: solve the quadratic to find the offsets of the solutions and sieve with them.

You might decide to sieve only for primes and their squares. In your case this is like having a "virtual" factor base of: $2, 3, 4, 7, 9, ...$, for example. In practice, the benefit of sieving for prime powers can be better achieved by simply lowering the cutoff for trial division a little bit. After all most numbers are squarefree and those that aren't usually have the higher exponents in the smallest primes, so a little room in the cutoff goes a long way towards including the powers of the small primes in the factor base.

-