On to the next section! The “Algebra and Number Theory” section should take us through the end of the year.

**The problem: **Quadratic Congruences. This is problem AN1 in the appendix.

**The description: **Given positive integers a,b, and c, can we find a positive integer x < c such that x^{2} ≡ a (mod b)?

**Example: **Let a = 3, b = 7, c = 13. It turns out that for every x < c, x^{2}≡ either 0,1,2 or 4 mod b. So this isn’t solvable. But if we change a to 2, then the first c that works is 3.

One thing I learned in doing this problem is that the squares of mod b will always form a cycle with period b. The proof is a pretty cool algebra problem if you set it up right.

**Reduction:** The paper by Manders and Adleman uses 3SAT. Starting from the list of variables, they define a set Σ that holds all 3-element clauses of 3 different literals from that list of variables. We won’t actually *build* this set (that’s exponential), but we can list out a *number* j for each of those clauses. Then define τ_{Φ} to be -1* the sum of 8^{j} for each of the j numbers that correspond to the clauses in our actual formula.

For each variable i, we define f_{i}^{+} to be the sum of 8^{j} for each j number in ∑ that has that variable positively, and f_{i}^{–} to be -1* the sum of 8^{j} for each number in Σ that has the variable negatively.

Let m be|Σ|, and set n=2m +The number of variables, and define a set C wit values c_{0} through c_{n}:

- c
_{0} = 1
- If j is odd(=2k-1) and ≤ 2m, c
_{j} = -8^{k}/2
- If j is even (=2k) and ≤ 2m, c
_{j} = -8^{k}
- If j is > 2m (= 2m+i), then c
_{j} = (f_{i}^{+}+f_{i}^{–})/2

Set τ = τ_{Φ} + The sum of all of the c_{i}‘s + The sum of all of the f_{i}^{–}‘s.

This actually turns into a Subset Sum problem: Let C be our set, and count each value positively if we take it, and negatively if we don’t take it.

But we still need to prove this is SOS problem is solvable exactly when the original problem is.

Create a set p_{0} .. p_{n} of consecutive prime numbers where the first one (p_{0}) is 13. Then define a set of θ_{j} values as the smallest number satisfying:

- θ
_{j}≡ c_{i} (mod 8^{m+1})
- θ
_{j} ≡ 0 (mod The product of each (p_{i})^{n+1}, except for j.)
- θ
_{j} is NOT ≡ 0 (mod p_{j})

Set H = The sum of all of the θ_{j}‘s. Set L=the product of all of the (p_{i})^{n+1}. We are finally ready to create our Quadric Congruence instance:

b = 2*8^{m+1}*K.

Let d = The inverse of (2*8^{m+1}+K), mod b.

Then a = d*(K*τ^{2}+2*8^{m+1 }* H^{2})

c = H.

From here, it’s a bunch of algebra to show that an x exists if and only if the original formula was satisfiable.

**Difficulty: **9. Maybe it should be 10. I don’t know enough number theory to be convinced that the θ’s exist, and be computed in polynomial time. The algebra I’m glossing over is pretty complicated as well.