3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Jul 29 at 11:07
  • $\begingroup$ @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$. $\endgroup$
    – fgrieu
    Jul 29 at 11:08
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Jul 29 at 11:10
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Jul 29 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.