DZone Snippets: euclid code

Modular linear equation solver

scvalex (Alexandru Scvortov) — Fri, 22 Jun 2007 15:13:40 GMT

Prints the roots of this equation:
ax = b (mod n)

Relies on Euclid's extended algorithm:
http://snippets.dzone.com/posts/show/4192



def solveLinearModularEquation(a, b, n):

  d, xx, yy = euclidExtended(a, n)

  if (b % d == 0):

    x0 = (xx * (b / d)) % n

    for i in xrange(0, d):

      print (x0 + i * (n / d)) % n,

  else:

    print "No solution"

  print

Euclid's extended algorithm

scvalex (Alexandru Scvortov) — Fri, 22 Jun 2007 14:59:27 GMT

Basically Euclid's algorithm for finding the largest common denominator, this one is modified in order to obtain the numbers d, x, y, where d is the dennominator and they check the following equation:
d = ax + by



def euclidExtended(a, b):

  if b == 0:

    return a, 1, 0

  dd, xx, yy = euclidExtended(b, a % b)

  d, x, y = dd, yy, xx - int(a / b) * yy

  return d, x, y

Euclid's algorithm

scvalex (Alexandru Scvortov) — Fri, 22 Jun 2007 14:54:15 GMT

Euclid(a, b) calculates the largest common denominator d, and returns it.

Uses the well-known Euclid's algorithm.



def euclid(a, b):

  while b != 0:

    r = a % b

    a = b

    b = r

  return a