Reversing mod for a function?

Question

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.

JohanC · Accepted Answer · 2019-12-10 11:43:07Z

(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.

user3353751 · Accepted Answer · 2019-12-10 04:34:30Z

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); } }

Collectives™ on Stack Overflow

Reversing mod for a function?

2 Answers 2

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Linked

Related