Quadratic Sieve: Sieving with prime powers

Question

I am trying to understand the Quadratic Sieve algorithm.

Currently I am stuck at the sieving part.

Let's say the number to be factored is 9788111. I decide to look for 50-smooth factors. My initial factor base (FB) = $p_i$ = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}.

I go through each number in the FB & their powers.

For each number in the FB, I first check if there if N is a Quadratic Residue mod the number (i.e. Is N a QR $\pmod {p_i}$. If it is, then I find the roots.

For 2, it's trivial to check if N is a QR $\pmod 2$. You can also extend this for powers of 2. For other primes, you can use Euler's Criteria for Quadratic Residues to check if N is a QR $\pmod {p_i}$. If it is a QR, then you can use Tonelli-Shanks to find the roots & then sieve with that prime.

What do I for prime powers? For e.q. $5^2$, how do I check if $t^2 \equiv N \pmod {5^2}$ has a solution? Is there any test or rule to do check this before I try finding the root?

For small prime powers such as $5^2$, it may be possible to find check manually if N is a QR $\pmod {{p_i}^n}$, but how do you do it for bigger prime powers?

Answer 1

Recall that the (basic) Quadratic Sieve requires finding some $x$ with $x^2-N$ smooth. Towards that, it adds the (scaled, approximate) logarithm of $p_i$ to small divisors ${p_i}^m$ of $x^2-N$ in the index $x>0$ of an array. This is relatively fast, because only two out of ${p_i}^m$ entries in the array need to be touched for each ${p_i}^m$.

What to do for prime powers (that is, ${p_i}^m$ for $m>1$)?

The lazy and sub-optimal option is to ignore them in the sieving phase, compensating by a lower smooth thresold and/or more primes in the base.

A better option is to solve $x^2\equiv N\pmod{{p_i}^m}$, and then sieve for ${p_i}^m$ as we did for $p_i$. For odd prime $p_i$, we have already solved $x\equiv N\pmod{p_i}$, say it has (two) solutions $x_j\in[0,p_i)$. The (two) solutions of $x^2\equiv N\pmod{{p_i}^m}$ in $[0,{p_i}^m)$ are $${x_j}^{({p_i}^{m-1})}\cdot N^{({p_i}^m - 2{p_i}^{m-1} + 1)/2}\bmod {p_i}^m$$

Dickson attributes this to Tonelli. I used this answer as a refresher. The formula is also in Wikipedia, with examples.