**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?



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)?
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](https://doi.org/10.1016/0022-0000(78)90044-2)


