Join Log in
Score:3
avatar Crypto

Quadratic Sieve: Sieving with prime powers

et flag
user93353

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?

102
1 + 0
Score:3
fgrieu avatar Crypto
ng flag
fgrieu

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.

0 + 4
et flag
user93353
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?
0
Reply
fgrieu avatar
ng flag
fgrieu
@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$.
0
Reply
et flag
user93353
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?
0
Reply
fgrieu avatar
ng flag
fgrieu
@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](https://cacr.uwaterloo.ca/hac/about/chap3.pdf#page=16) 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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.