How to solve for y in formula (y*known_number)%145 = 81 without a loop
Is it possible to solve for y in this equation without a loop?
known_number = 7 (y * known_number) % 145 == 81
I'm using a loop, but i'm thinking since it's simple multiplication, there may be a formula that can be used to solve it without a loop, or is there?
Here is my code i use to solve for it:
known_number = 7 for y in range(145): if (y * known_number) % 145 == 81: print(y) # -> 53
There is an other way, though it has a different kind of loop if you look closely.. anyway, it can be solved like this:
y*known_number ≡ 81 (mod 145) y ≡ 81 * known_number ^ -1 (mod 145)
Which works iff
known_numberindeed has a modular multiplicative inverse modulo 145, which happens when the GCD between the known number and the modulus is 1 (
gcd(7, 145) = 1so in this case it would work). Here the inverse is 83, so we compute
y = 81 * 83 % 145 = 53.
In general you may find that inverse by using the Extended Euclidean Algorithm, but also through various other methods, for example
pow(known_number, 111, 145), where 111 is
totient(145) - 1. Computing a totient is not easy unless you have the prime-factorization of the number. The
powfunction hides a loop, but a much shorter loop than brute-forcing the equation.