3-SAT and Systems of Nonlinear Modular Equations

Question

How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?

I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to prove that a problem is NP complete?. But how is this done for systems of nonlinear modular equations specifically?

In that question above, Albert S. lays out nice steps:

"In order to prove that a problem $L$ is NP-complete, we need to do the following steps:

• Prove your problem $L$ belongs to NP (that is that given a solution you can verify it in polynomial time)
• Select a known NP-complete problem $L'$
• Describe an algorithm $f$ that transforms $L'$ into $L$
• Prove that your algorithm is correct (formally: $x ∈ L'$ if and only if $f(x) ∈ L$ )
• Prove that also $f$ runs in polynomial time"

In other words

1) Where can one find (in the literature or elsewhere) the algorithm $f$ that reduced SAT to the problem of solving a system of nonlinear modular equations originally, so that he or she can better learn about the time complexity of nonlinear modular equations or 2) Could anyone answer below how it is reduced?

Does SAT reduce to solving a system of problem q?

Problem q

Given the coefficients $a$, are there any integer solutions for $x$? List them:$$a_n x^n + \dots + a_1 x + a_0 = 0 \pmod m$$

Answer 1

The answer depends on whether we're talking about a single equation, or a system of equations; and whether the modulus $m$ is prime or composite.

A single equation

When the modulus $m$ is prime, then you can find a solution to a single equation

$$a_n x^n + \dots + a_1 x + a_0 = 0 \pmod m$$

in polynomial time (if one exists) by factoring the polynomial $a_n x^n + \dots + a_0$ over the finite field $\mathbb{F}_m$. When $m$ is composite, finding a solution is (in general) at least as hard as factoring $m$. See e.g.,Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?.

System of equations

That's the situation for a single equation. In contrast, finding a solution to a system of (multiple of) these equations (in multiple unknowns) is NP-hard, regardless of whether $m$ is prime or composite. There's a simple reduction, if $m$ is prime. Each clause is translated to a nonlinear equation, e.g., $(x_i \lor x_j \lor x_k)$ translates to the equation

$$(1-x_i)(1-x_j)(1-x_k)=0 \pmod m.$$

As another example, $(\overline{x_i} \lor x_j \lor x_k)$ translates to

$$x_i (1-x_j)(1-x_k)=0 \pmod m.$$

Finally, for each variable $x_i$ we add the equation

$$x_i (1-x_i) = 0 \pmod m$$

to force $x_i$ to be 0 or 1 (this is unnecessary when $m=2$).

An extension of this idea works when $m$ is composite, too; if $m=pr$ where $p$ is prime, then multiply the left-hand-side of each equation above by the constant $r$. This yields a system of nonlinear equations of degree 3. If you want a system of nonlinear equations of degree 2, that is achievable too; translate the clause $(x_i \lor x_j \lor x_k)$ to the two equations

$$(1-x_i) (1-x_j) = 1-y_{i,j} \pmod m \qquad \qquad (1-y_{i,j})(1-x_k)=0 \pmod m$$

where $y_{i,j}$ is a new fresh variable (different for each clause).