Is it possible to reverse a function with modulo where the input is multiplied?

user_17438507 0
Viewed 45

Below is an example of what I am trying to solve:

a = 5
b = 21
i = int(input("Enter a number: "))   
c = (a*i+b) % 41

c will result in 17.

My question is if its possible to find i if we have c (the answer):

Mathematically: (5xix21)%41=17

math python
1 Answers

Yes and no.

  • Yes, it is very easy to find the set of all integers i satisfying the modular equation 5*i+21 == 17 (mod 41).
  • No, this integer is not unique, so you can't really guess which one was chosen by the user.

Note that the following statements are equivalent:

  • "5 * i + 21 == 17 (mod 41)";
  • "5 * i + 21 - 17 is divisible by 41";
  • "there exists q such that 5 * i + 21 - 17 == 41 * q".

So now you have an integer linear equation in two variables:

5*i - 41*q = -4

A particular solution (i, q) to that equation can easily be found using the extended Euclidean algorithm, and then a parametric form for all the solutions can be deduced from that particular equation as an application of Gauss' theorem.

I'd like to refer you to a good course material on how to solve this equation by hand, but I don't have a reference at hand at the moment. Perhaps someone else can suggest one, or you can search for "Diophantine equations" at https://math.stackexchange.com

Since you tagged [python], here is a solution using sympy. Reference: https://docs.sympy.org/latest/modules/solvers/diophantine.html

from sympy.solvers.diophantine import diophantine
from sympy import symbols

i, q = symbols('i q', integer=True)

diophantine(5 * i - 41 * q + 4)
# {(41*t_0 + 32, 5*t_0 + 4)}

This tells you that for any integer value of t_0, you'll have a solution by choosing i = 41*t_0 + 32 and q = 5*t_0 + 4.

In particular, by choosing t_0 = 0, we get i = 32, and you can check that i = 32 is indeed a solution of your original problem:

a = 5
b = 21
i = 32  
c = (a*i+b) % 41
print(c)
# 17
user_30807230
Related