Question: How to find the smallest value $x$ satisfying the equation: $x^2 = a \pmod c$ (known is $a$ and $c$, $c$ is not the prime)?

Question

Question: How to find the smallest value $x$ satisfying the equation: $x^2 = a \pmod c$ (known is $a$ and $c$, $c$ is not the prime)?

Using the Tonelli-Shanks algorithm and the Chinese remainder theorem does not always give me the smallest $x$ satisfying condition.

Is there any solution for calculating the smallest $x$?

Does anyone have an idea?

---- Edit:

I will describe more accurately my problem:

Let's assume that we are looking for a solution: $x^2 \equiv 1024 \pmod{1302}$.

We need to know the distribution of the factors $1302$, so $1302 = 2 \cdot 3 \cdot 7 \cdot 31$.

Now, using the Tonelli-Shanks algorithm we calculate for all divisors:

For 2:

$1024 \equiv k_1 \pmod 2$

$k_1 = 0$

$x_1 ^ 2 \equiv k_1 \pmod{2}$

$x_1^2 \equiv 0 \pmod{2}$

$x_1 = 0$

For 3:

$1024 \equiv k_2 \pmod 3$

$k_2 = 1$

$x_2^2 \equiv k_1 \pmod{3}$

$x_2^2 \equiv 1 \pmod{3}$

$x_2 = 1$

For 7:

$1024 \equiv k_3 \pmod 7$

$k_3 = 2$

$x_3 ^ 2 \equiv k_3 \pmod{7}$

$x_3^2 \equiv 2 \pmod {7}$

$x_3 = 4$

For 31:

$1024 \equiv k_4 \pmod 31$

$k_4 = 1$

$x_4 ^ 2 \equiv k_4 \pmod{31}$

$x_4 ^ 2 \equiv 1 \pmod{31}$

$x_4 = 1$

Then we solve the system of equations from the Chinese remainder theorem. We know the factors and also the values of $x$ from the formula: $x ^ 2 \equiv c \pmod {p}$ where $p$ and $c$ are known.

We solve the system of equations.

$x \equiv 0 \pmod{2}$

$x \equiv 1 \pmod{3}$

$x \equiv 4 \pmod{7}$

$x \equiv 1 \pmod{31}$

The Chinese remainder theorem comes out $x = 32$, and this is the good, smallest solution: $32 ^ 2 \equiv 1024 \pmod {1302}$ - quite trivial case.

The problem, however, is that it does not always agree. And so I write why.

In the above case, for example, for the first factor $31$ I assumed that I found a result equal to $1$. I do not necessarily have to find exactly $1$ as well:

$(31-1)^2 \equiv k_4 \pmod{31}$

$(31-1)^2 \equiv 1 \pmod{31}$

$30^2 \equiv 1 \pmod{31}$

The above is that for $30$ will also be $1$.

For such a system of equations (new value at $31$):

$x \equiv 0 \pmod{2}$

$x \equiv 1 \pmod{3}$

$x \equiv 4 \pmod{7}$

$x \equiv 30 \pmod{31}$

From the Chinese remainder theorem we get $x = 2944$. This also agrees, because $2944 ^ 2 \equiv 1024 \pmod {1302}$ but this is no longer the smallest possible value (smallest possible is $x = 32$).

Knowing the first value ($1$ for factor = $31$), the second one ($30$ for factor = $31$) that fits is easy to calculate as I did here.

However, since all combinations of values will be $2 ^ k$ (where $k$ is the number of prime factors (in different example). I have not found a way to do some search for these combinations in a better way than bruteforce.

Any ideas for that so I'm looking for.

Can someone suggest something?

Answer 1

This is an NP-hard problem. That is, Manders and Adleman [1] proved that given $a$, $b$, and $c$, it is NP-complete to determine if there exists $x\le b$ such that $x^2\equiv a\pmod c$, and that it remains NP-complete even if the prime factorization of $c$ is also given as input.

Reference:

[1] Kenneth L. Manders and Leonard Adleman, NP-complete decision problems for binary quadratics, Journal of Computer and System Sciences 16 (1978), pp. 168--184, doi: 10.1016/0022-0000(78)90044-2

Answer 2

In general, finding the smallest integer solution to a system of modular (in)equalities seems to be very hard. To be precise: the question is how to find the smallest $x$ such that e.g. $x\mod{3}\in\{1,2\},\ x\mod{5}\in\{2,3,4\},\ x\mod{7}\in\{1,4\},...$ for a finite number of primes. [I'm almost totally ignorant on these matters, but I do not recall any proof of it being NP-complete, I would appreciate any reference!]

In your case, I see a very slight improvement over brute force. I'll mention it here in an answer, but hopefully someone much more knowledgeable will pick up from there.

In your case, you're looking for the smallest $x$ such that $x^2=a+kc$, in other words the smallest $k$ such that $a+kc$ is a square. That means that $kc$ must be a square $\mod{a}$. Since $a,c$ are known, you can restrict your brute force to numbers $k$ for which $kc$ is a square $\mod{a}$. Depending on the number of prime factors of $a$, this can give quite a reduction.