Modular Equation Solver: (a mod ring_size) * (x mod ring_size) = (b mod ring_size) for specified a and b. This script use Extended Euclidean algorithm

file.py

def gcd(a,b):
  if a < b:
    a, b = b, a
  if b == 0:
    return a, 1, 0
  t_1, t_2 = 0, 1
  s_1, s_2 = 1, 0
  i = 1
  while b > 0:
    q = a // b
    print('{}) q = {} div {} = {}'.format(i, a,b,q))
    r = a - q * b
    t = t_2 - q * t_1
    s = s_2 - q * s_1
    print('r = {} - {} * {} = {}; t = {} - {} * {} = {}; s = {} - {} * {} = {}'.format(a, q, b, r, t_2, q, t_1, t, s_2, q, s_1, s))
    a = b
    b = r
    t_2 = t_1
    t_1 = t
    s_2 = s_1
    s_1 = s
    print('r_1 = {}; r_2 = {}; t_1 = {}; t_2 = {}; s_1 = {}; s_2 = {}'.format(a, b, t_1, t_2, s_1, s_2))
    i += 1
  return a, t_2, s_2

a = 234
b = 253
ring_size = 257
print('r_1 = a = {}; r_2 = {}; t_1 = 0; t_2 = 1; s_1 = 1; s_2 = 0'.format(a, ring_size))
d, t, s = gcd(ring_size, a)

print('\na={}; b={}; d={}; t={}; s={}'.format(a, b, d, t, s))
x = (s * b) % ring_size
if x < 0:
  x += ring_size
print('[x] = [{0}]*[{1}] = [{0}*{1}]=[{2}]={3}'.format(s, b, s*b, x))

print('\nVerification')
print('[a]*[x]=[b]')
print('[{0}]*[{1}]=[{0}*{1}]=[{2}]=[{3}]=b'.format(a,x,a*x, (a*x)%ring_size))