Given the equation $$ (x(b+x) + c - f) \mod (2x+2) = 0 $$ Is it possible and if so what is the quickest way to find appropriate value of $x$? Where $x > 0$

The above equation is derived from the following two quadratic equations $$ax^2+bx+c$$ $$dx^2+ex+f$$

example equations are $$x^2 + 27305078x + 20664318$$ $$x^2 + 27305076x + 186391793841444$$

resulting in $$(x(27305078+x) + 20664318 - 186391793841444) \mod (2x+2) = 0$$

All of the above is from an encryption/decryption scheme I am toying with so the example equations are trivial and the answer is found easily by iterative means but for non trivial equations iteration is too computationally expensive.

  • $\begingroup$ Well, just for starters, you can replace $c-f$ by a single name, say $d$, to get $$(x^2 + bx + d) \bmod (2x +2) = 0.$$ Then replacing $x+1$ by $y$, you get $$y^2 -2y + 1 + by - b + d \bmod 2y = 0,$$ which has the general form $$y^2 + b'y + c' \bmod 2y = 0,$$ which is a little easier to look at. And then you see that $y$ must be a factor of $c'$, so you need only check factors of $c'$ rather than all possible numbers. Of course, finding factors of $c'$ may be difficult in general. :) $\endgroup$ – John Hughes Dec 28 '18 at 13:40
  • $\begingroup$ Thanks john, please excuse my ignorance.I am not familiar with the notation $b'y$ does the apostrophe have a special meaning in this context? what happened to the $-2y+1$ in the general form? $\endgroup$ – DeveloperChris Dec 29 '18 at 0:52
  • $\begingroup$ I just worked through an example and using $c'=-b+d+1$ arrived back at my initial starting point of $c'=186391800482203$. which is computationally infeasible to factor in non trivial cases. so it seems this line of inquiry may be a bust $\endgroup$ – DeveloperChris Dec 29 '18 at 1:40
  • $\begingroup$ It just meant "we can reduce the thing above to $y^2 + (b-2)y + (1-b+d)$, and then use new names to replace the coefficients, i.e., we can use new variables --- I've called them $b'$ -- defined by $b' = b-2$, and $c' = 1 - b + d$ -- to make the expression look simpler: it's just an ordinary quadratic. If you know $b$ and $d$, you can find $b'$ and $d'$; if you know $b'$ and $d'$, you can find $b$ and $d$...so there's no magic here; just visual simplicity. And of course you end up back at the same computational problem --- that's the idea. But it's easier to look at. $\endgroup$ – John Hughes Dec 29 '18 at 13:48
  • $\begingroup$ As for "which is computationally infeasible to factor...", in your earlier description you suggested that you were using "iterative means," which sounded to me like trying sequential values of $x$, not "trying to factor something." Anyhow, comments are generally intended as a place to clarify/simplify questions, not to answer them. If you don't think my simplification's actually simpler, so be it. As for actually solving the problem...I've got nothing. I don't do much algebra/number theory, so I have no instant insights. $\endgroup$ – John Hughes Dec 29 '18 at 13:50

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.