2
$\begingroup$

I have a system of $n$ congruences.

the generic $m$_th congruence of the system ($m = 1,\dots,n$) is in the form:

$(p_n\#)^2(\displaystyle\sum_{\substack{i=1\\i\neq m}}^n{\frac{x_iy_m}{p_ip_m}}+\sum_{\substack{j=1\\j\neq m}}^n{\frac{x_my_i}{p_jp_m}}+\frac{x_my_m}{p_m^2}-n_2\frac{x_m}{p_m}-n_1\frac{y_m}{p_m})\equiv b_m \:\:\: (mod \:\: p_m^2)$

where:

$p_n\#=\displaystyle\prod_{\substack{i=1}}^np_i$ and $p_i$ is the $i$_th prime number.

$x_i$ and $y_i$ are the unknows while $n_1$ and $n_2$ are known.

for every couple of unknowns $(x_m,y_m)$ $(m=1,\dots,n)$ i know $p_m-1$ couple of values where the solution lies, therefore, in order to avoid nonlinearity, for every congruence of the system i can build a set of $p_m-1$ linear congruences in which the values of $(x_m,y_m)$ are fixed. The problem now is to choose the correct combination of linear congruences (one for each set) in order to build a consistent system. Every congruence of the complete system should be $0\equiv0\:\:(mod\:p_m^2)$ because every time i choose a congruence from the $m$_th set, i choose implicitly the values of the couple of unknowns $(x_m,y_m)$.

I know that there is at least a solution (and i am interested in finding a single solution) but i'm afraid of not being able to do an exaustive search over the linear congruences because the size of the problem is too big (30+ nonlinear congruences resulting in a 30+ set of linear congruences).

Any help would be appreciated. Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

Here is a reduction to a bivariate polynomial equation modulo $p_n\#^2$.

Let $C_m$ denote the set of candidate values for $(x_m,y_m)$.

Set $P:=p_n\#$, $X:=P\sum_{i=1}^n \frac{x_i}{p_i}$, and $Y:=P\sum_{i=1}^n \frac{y_i}{p_i}$. Then the $m$-th congruence takes form: $$P(\frac{y_m}{p_m} X + \frac{x_m}{p_m} Y) - P^2(\frac{x_my_m}{p_m^2} + n_2\frac{x_m}{p_m} + n_1\frac{y_m}{p_m})\equiv b_m\pmod{p_m^2}.$$

From the candidate values for $(x_m,y_m)$, we obtain the following congruence holds: $$f_m(X,Y)\equiv 0\pmod{p_m^2},\qquad(\star)$$ where $$f_m(X,Y) := \prod_{(x_m,y_m)\in C_m} \left[ P(\frac{y_m}{p_m} X + \frac{x_m}{p_m} Y) - P^2(\frac{x_my_m}{p_m^2} + n_2\frac{x_m}{p_m} + n_1\frac{y_m}{p_m}) - b_m\right].$$

Clearly, $\deg f_m \leq p_m-1$. Then, we combine congruences $(\star)$ into a single one: $$F(X,Y) \equiv 0\pmod{P^2},$$ where $$F(X,Y) := \sum_{m=1}^n \frac{P^2}{p_m^2} f_m(X,Y).$$

If we solve the resulting congruence for $(X,Y)$, then from $X\equiv \frac{P}{p_m}x_m\pmod{p_m}$ and $Y\equiv \frac{P}{p_m}y_m\pmod{p_m}$ we can find a suitable pair $(x_m,y_m)$ from $C_m$ for each $m$, and then verify that they altogether deliver a solution (as they may be extraneous ones).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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