"""
[TECC prototype ALGEGRA 2 4D SOLUTIONS 2008]

School standard:  students will gain familiarity
with important algebraic properties of finite and
infinite sets, including the infinite sets
N, Z, Q, R, C and finite sets of permutations,
numbers modulo M.

Xrefs:  polyhedra and symmetry groups; permutation
groups; RSA; Cryptonomicon (Stephenson); In Code
(Flannery)

Note to teachers:  with Python's operator overloading,
group theory comes alive, providing excellent
preparation for future careers in mathematics,
particle physics, cryptography and more.

Note to students:  The M-type below implements the
four operations, + - * /, as well as the comparison
operators > < ==, among integers modulo M.  We will
use this class to investigate properties of groups,
rings and fields.  For example, if M is prime, your
math facts will demonstrate closure.  If M is composite,
but only totatives of M get used, you'll at least have
group properties over multiplication (*).

Lesson plan:
>>> from tecc_alg2_u5 import test
>>> test(11)
Random Math Facts for M11
[m1, m2, m3, m4, m5, m6, m7, m8, m9, m10]
m3 * m9 = m5
m8 * m9 = m6
m4 + m6 = m10
m9 + m3 = m1
m5 * m10 = m6
m3 - m9 = m5
m8 * m5 = m7
m1 / m2 = m6
m10 / m4 = m8
m2 / m3 = m8

>>> test(14)
Random Math Facts for M14
[m1, m3, m5, m9, m11, m13]
m9 / m13 = m5
m13 + m11 = m10
m3 - m9 = m8
m1 / m11 = m9
m3 * m9 = m13
m1 - m9 = m6
m9 / m3 = m3
m3 - m3 = m0
m3 + m1 = m4
m13 / m3 = m9

See also:
Algorithms: A Bit of Math by Andrew Kuchling
http://pythonjournal.cognizor.com/pyj1/AMKuchling_algorithms-V1.html
Copyright (c) 1998 Andrew Kuchling

Background essay:
http://mathforum.org/kb/thread.jspa?threadID=1543229&tstart=0
"""

from random import choice

def ee(a, b):
    """Euclid extended by Alexandru Scvortov
    http://snippets.dzone.com/posts/show/4192
    """
    if b == 0:
        return a, 1, 0
    dd, xx, yy = ee(b, a % b)
    d, x, y = dd, yy, xx - (a // b) * yy
    return d, x, y

class M:

    modulus = 7
    
    """
    Adds extended Euclidean (ee) for finding
    multiplicative inverses
    """
    def __init__(self, val):
        self.val = val % M.modulus
        self.recip = ee(self.val, M.modulus)[1] % M.modulus

    def __repr__(self):
        return "m%s" % (self.val)

    def __add__(self, other):
        return M(self.val + other.val)

    def __sub__(self, other):
        return self + (-other)

    def __mul__(self, other):
        return M(self.val * other.val)

    def __truediv__(self, other):
        return self * other**(-1)
    
    def __neg__(self):
        return M(-self.val)

    def __pow__(self, e):
        # identity:  m**(-e) == (m**(-1))**abs(e)
        if e < 0:
            base = self.recip
        else:
            base = self.val
        return M(pow(base, abs(e), M.modulus))

    def __lt__(self, other):
        return self.val < other.val

    def __gt__(self, other):
        return self.val > other.val

    def __eq__(self, other):
        return self.val == other.val

def gcd(a,b):
    while b:
        a, b = b, a % b
    return a

def totatives(n):
    return [i for i in range(1,n) if gcd(i, n) == 1]

def mathfact(members, ops=["*"]):
    while True:
        elem0 = choice(members)
        elem1 = choice(members)
        op = choice(ops)
        # no divide by zero allowed
        if not (op=="/" and elem1.val == 0):
            break
        
    if op == "*":
        r = elem0 * elem1
    elif op == "/":
        r = elem0 / elem1
    elif op == "+":
        r = elem0 + elem1
    else:
        r = elem0 - elem1
        
    expr = "%s %s %s" % (elem0, op, elem1)
    return "%s = %s" % (expr, r) 

def makemembers(val):
    M.modulus = val
    return [M(i) for i in totatives(val)]

def report(n=7):
    the_members = makemembers(n)
    print(the_members)
    while True:
        yield mathfact(the_members,["*","/","+","-"])

def test(n=7):
    rg = report(n)
    print("Random Math Facts for M%s" % n)
    for i in range(10):
        print(next(rg))