0
$\begingroup$

I wan to know how to solve this equation where $\rm\ D $ and $\rm\ k $ values are know and I want to find $x$:

$x (x\ mod\ k\ ) ^ 2 \rm\ mod\ k = D$

And I dont know how to start and how to exactly the problem is expressed in math notation. I using the mod of remainder operation no the congruences.

I extract the equation analizing some ofuscated source code the code that looks like

if (x*((x % k) * (x % k))) % k == D ...

I put the code if i made a mistake traslating to math notation .

update

Maybe is not computable after all. But i want to know the teory for the great good. The values are very big:

$\ k=$ 134908246421120481758163246661992595636170321686448474706440739628688109783740860298237556469237969452644490512779389250731193716102265810626226010445308778149257733945246516748118415698788521821626025173366644769118674263043277444473840006708507357109944794039692095527291233717252207868936434225226739116901

$\ D= $

5486124068793688683255936251187209270074392635932332070112001988456197381759672947165175699536362793613284725337872111744958183862744647903224103718245670299614498700710006264535590197791934024641512541262359795191593953928908168990292758500391456212260079471274317399924646987873523990414169975398570173

$\endgroup$
5
  • $\begingroup$ What is the order of precedence for the $\%$ sign versus multiplication? $\endgroup$ Commented Sep 5, 2017 at 21:14
  • $\begingroup$ In other words, is $a*b\% c*d$ interpreted as $(a*b)\%(c*d)$ or as $a*(b\%c)*d$, or as $((a*b)\%c)*d$? $\endgroup$ Commented Sep 5, 2017 at 21:16
  • $\begingroup$ is the same that x*((x % k) * (x % k)) % k i edit $\endgroup$ Commented Sep 5, 2017 at 21:17
  • $\begingroup$ Still, is the middle parenthetical multiplied by the $x$ on the left first, or remainder-divided with the $k$ on the right first? $\endgroup$ Commented Sep 5, 2017 at 21:18
  • $\begingroup$ aja i think the correct is the same precedence and left to rigth, know i edit again , this is in python and i check against the values, but better is to not use parentesis because this code is valid in many languajes and maybe not have the same precedence $\endgroup$ Commented Sep 5, 2017 at 21:19

2 Answers 2

1
$\begingroup$

This is a little tricky, because in math notation, we don't use the symbol $\mod{}$ to mean the same thing as the computer operator %.

However, it appears that we're starting with a number $x$, reducing it to its least positive residue modulo $k$, squaring the result, multiplying again by $x$, and then reducing modulo $k$ one more time.

If that's right, the the initial reduction modulo $k$ has no effect, and this is the same as just taking $x^3$ % $k$. In math, we would write

$$x^3\equiv D \pmod{k}$$

where the $\pmod{k}$ isn't applying to the $D$, but to the equivalence. A clearer way of writing it might be:

$$x^3\equiv_k D$$

Anyway, solving uniquely for $x$ isn't possible here, but you can narrow your options down somewhat. The most straightforward way would be to look at all the numbers $0,1, 2,\ldots k-1$, cube each one, reduce each cube modulo $k$, and see which ones equal $D$. Then you can say that the original $x$ must have been equivalent, modulo $k$, to one of those.

$\endgroup$
1
$\begingroup$

There isn't a single solution, but instead very many solutions. But it is possible to give a partial description.

Firstly, the inner $\bmod k$ is actually redundant. This is because if we replace the inner mod by $x + ky$ for any multiple $y$ of $k$, then we have $$\begin{align} x (x \bmod k)^2 \bmod k &= x( x + ky)^2 \bmod k = x^3 + 2x^2ky + xk^2y^2 \bmod k \\ & x^3 + k(2x^2y + xky^2) \bmod k = x^3 \bmod k. \end{align}$$

So adding or removing multiples to the inner mod doesn't change anything, and what you're really trying to do is solve $$ x^3 \equiv D \bmod k.$$ The bad news is that actually solving this is a bit nontrivial, and not something that I know how to do well. Generically, the thought would be to factor $k$ and solve the cubic for each prime power factor. This other question and answer is exactly this problem for primes.


I will also note that there might be a good reason to computer inner mods in the context of computers, because multiplication is quicker on small numbers and large numbers might exceed limits of finite precision arithmetic. For example, if $x$ might have $10$ digits and one only has $15$ digits of accuracy, then computing $x^2$ and then modding out by a $5$ digit number would be much lossier than modding first, squaring, and then modding again. Finite precision arithmetic is tremendously annoying.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .