# Solving for x (Modular Arithmetic)

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.

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.
• 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$) – Nicholas Pipitone Nov 2 '14 at 16:07
• 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. – Nicholas Pipitone Nov 2 '14 at 16:17
• What about $C_0$ and $C_1$? – Ari Nov 2 '14 at 16:22
• Also 1024 byte numbers, they contain the encrypted message ($x$ being the message I am attempting to obtain) – Nicholas Pipitone Nov 2 '14 at 16:23