# Quadratic Sieve: Sieving with prime powers

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?

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.

• Thank you. For a odd-prime $p$, if $x^2 \equiv N\pmod p$ has a solution, then is it guaranteed that $x^2 \equiv N\pmod {p^m}$ also has a solution. I know this is not true for powers of 2. But is it the same for odd primes or is it guaranteed? Jul 29 at 11:07
• @user93353: Yes, for a odd prime $p$, if $x^2\equiv N\pmod p$ has a solution, then is it guaranteed that $x^2\equiv N\pmod {p^m}$ also has a solution. There are at most two, modulo $p^m$.
– fgrieu
Jul 29 at 11:08
• Great! I guess I assumed that it's not (just like it's not for powers of 2). My whole question becomes meaningless if it's guaranteed. Is there any proof or theorem which shows this? A reference in some book? Jul 29 at 11:10
• @user93353: The Dickson source (itself citing Tonelli) at the end of my answer is the best I have found so far. The HAC's note 3.41 states it's easy to find square roots in a field of order a prime power, thus including modulo a prime power, but unfortunately the justification using fact 3.42, and method, seems to cover only the prime 2. A direct proof of Tonelli's formula (in my answer) might be possible, by squaring and simplifying.
– fgrieu
Jul 29 at 11:28