1

I'm trying to solve this equation:

(b(ax+b ) - c) % n = e

Where everything is given except x I tried the approach of :

(A + x) % B = C
(B + C - A) % B = x

where A is (-c) and then manually solve for x given my other subs, but I am not getting the correct output. Would I possibly need to use eea? Any help would be appreciated! I understand this question has been asked, I tried their solutions but it doesn't work for me.

MoonMist
  • 1,232
  • 6
  • 22
Lizzy
  • 211
  • 2
  • 10

2 Answers2

4

(b*(a*x+b) - c) % n = e

can be rewritten as:

(b*a*x) % n = (e - b*b + c) % n
x = ((e - b*b + c) * modular_inverse(b*a, n)) % n

where the modular inverse of u, modular_inverse(u, n), is a number v such that u*v % n == 1. See this question for code to calculate the modular inverse.

Some caveats:

  • When simplifying modular equations, you can never simply divide, you need to multiply with the modular inverse.
  • There is no straightforward formula to calculate the modular inverse, but there is a simple, quick algorithm to calculate it, similar to calculating the gcd.
  • The modular inverse doesn't always exist.
  • Depending on the programming language, when one or both arguments are negative, the result of modulo can also be negative.
  • As every solution works for every x modulo n, for small n only the numbers from 0 till n-1 need to be tested, so in many cases a simple loop is sufficient.
JohanC
  • 71,591
  • 8
  • 33
  • 66
0

What language are you doing this in, and are the variables constant? Here's a quick way to determine the possible values of x in Java:

for (int x = -1000; x < 1000; x++){
    if ((b*((a*x)+b) - c) % n == e){
    System.out.println(x);
    }
}
user3353751
  • 25
  • 5