1

Fairly new to modular arithmetic and I've searched through several sources and have not figured out how to do this. I have the following equation:

  • s = (k * (h + x * r)) mod q

How would one solve for x? I am quite unsure of what to do with the mod q.

yurishima
  • 11
  • 1
  • 4
    x = (s - kh) / (kr) mod q, if gcd(k\*r, q) == 1. (1/kr) is the [modular inverse of k\*r](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse). It basically the same answer you'd get if you were solving over the reals, except division is a different algorithm and "can't divide by zero" is replaced by gcd(k\*r, q) == 1 – President James K. Polk Dec 05 '21 at 19:54
  • This doesn't seem to work. I also arrived at this equation earlier and if I use it, X ends up being a fractional number rather than the integer it needs to be – yurishima Dec 05 '21 at 21:07
  • 2
    "except division is a different algorithm" which the link in my comment explains. – President James K. Polk Dec 05 '21 at 21:28
  • 1
    @Yurishima The wikipedia link given by @PresidentJamesKPolk explains what is the meaning of `1/(kr)` in this context; it's not the usual division of real numbers. The wikipedia article even contains a section explaining how to compute this number, using the extended Euclidean algorithm. – Stef Dec 05 '21 at 22:11
  • @yurishima All that being said, your question is quite vague. What do you mean by "how would one solve for x?" ? Do you want to understand the math behind it? Do you want to solve this equation by hand? Do you want to write an algorithm to solve it? Do you want to use a standard library that already implements this algorithm for a certain programming language? – Stef Dec 05 '21 at 22:12
  • Related question on math.stackexchange: [What is a modular inverse?](https://math.stackexchange.com/questions/1396947/what-is-a-modular-inverse) – Stef Dec 05 '21 at 22:16
  • Related question about python: [Modular multiplicative inverse function in Python](https://stackoverflow.com/questions/4798654/modular-multiplicative-inverse-function-in-python) – Stef Dec 05 '21 at 22:17
  • @Stef I am trying to understand the math behind it as well as implement an algorithm to solve for x in python given all the other variables. – yurishima Dec 05 '21 at 22:52
  • 1
    @yurishima Have you read the questions I linked and the wikipedia article linked by PresidentJamesKPolk and do you still have a question? – Stef Dec 06 '21 at 13:12

0 Answers0