1
$\begingroup$

Solving systems of equations with Modular Arithmetic can be complex, especially with the following equations:

$$(a_0x+{a_0}^2)^e \equiv C_0\;(mod\;n)$$ $$(a_1x+{a_1}^2)^e \equiv C_1\;(mod\;n)$$

My problem is to solve for $x$ (I am given the values of everything else). I have attempted to solve these equations to the best of my ability, but I am not even sure how I would begin to simplify this. I have been told that the interesting $am+a^2$ relates the two $C$'s in a helpful manner, but that is all.

$\endgroup$
0
$\begingroup$

Powers often simplify modulos. For example, it is well known that all cubes are either $0$, $1$, or $-1$ $($mod $7)$. You can verify this yourself by simply cubing all numbers modulo $7$ (that is, cube $0,1,2,3,4,5,$ and $6$ and you will find all results are $0$, $1$, or $-1$ $($mod $7)$ ). Here you have two numbers raised to a power $e$. Without too much difficulty you should be able to find the set of all modulo values $($mod $n)$ that result from raising a number to the $e$th power. $C_0$ and $C_1$ will be two of those. Match them to the corresponding modulo you raised to the $e$th power to get the set of possible values for $a_0x+a_0^2$ and $a_1x+a_1^2$ $($mod $n)$. From there it is merely a matter of using some simple algebra to arrive at your solution.

$\endgroup$
  • $\begingroup$ What if the case is that $n$ is extremely large and $e$ is small? (The difference is so large that there are in fact more than $2*10^{63}$ powers of $e$ that are less than $n$) $\endgroup$ – Nicholas Pipitone Nov 2 '14 at 16:07
  • $\begingroup$ That is quite a large number, about how big are the numbers we are dealing with here? $\endgroup$ – Ari Nov 2 '14 at 16:12
  • $\begingroup$ This is relating to an RSA problem I have in CS, $n$ is a 1024 byte number and $e$ is simply 3. I have to simplify this algebraically because doing arithmetic to these numbers is impossible (I can multiply them or do small exponents, but that's it). $a_0$ and $a_1$ are 2 digits. $\endgroup$ – Nicholas Pipitone Nov 2 '14 at 16:17
  • $\begingroup$ What about $C_0$ and $C_1$? $\endgroup$ – Ari Nov 2 '14 at 16:22
  • $\begingroup$ Also 1024 byte numbers, they contain the encrypted message ($x$ being the message I am attempting to obtain) $\endgroup$ – Nicholas Pipitone Nov 2 '14 at 16:23

Your Answer

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

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