5
$\begingroup$

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 samllest 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 brutal-force.

Any ideas for that so I'm looking for.

Can someone suggest something?

$\endgroup$
  • $\begingroup$ If the question is still not obvious please write in the comments. I'm looking for a possible quick method. $\endgroup$ – Aurelio Nov 5 '17 at 15:17
  • $\begingroup$ Is this a purely theoretical question or a computational problem from some programming contest? If the latter, I presume there would be some bounds on the size of $c$, which would also provide a reasonable bound on the number of its prime divisors $k$ -- e.g. $32$-bit numbers have at most $9$ distinct prime divisors, while $64$-bit ones won't have more than $15$. This makes even the $2^k$ algorithm usable. If the numbers are arbitrarily-sized, the main problem could be the initial factorization, rather than subsequent exhaustive search. $\endgroup$ – Peter Košinár Nov 10 '17 at 12:54
  • $\begingroup$ Pure question - pessimistic complexity $\endgroup$ – Aurelio Nov 11 '17 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.