#!/usr/bin/env python3
#
# “Irish logarithm” method for multiplication
#
# 1. Select b and n relatively prime
# 2. Compute table z[i] = (b^i) % n
# 3. For primes p_1, p_2, etc. compute dl[p_i]
#    such that z[dl[p_i]] = p_i.
#    (Discrete logarithm)
# 4. Any product ab < n can be computed as
#    z[dl[a] + dl[b]]
#
# Now consider b=2, n=101 which allows us to multiply
# numbers where the product is ≤ 100.
#
# We get:
# dl[ 2] =   1
# dl[ 3] = -31
# dl[ 5] =  24
# dl[ 7] =   9
# dl[11] =  13
#
# Wouldn't it be nice if these numbers were smaller?
# Especially dl[3]?
#
# Maybe if we take some other value for b,
# we will get a better result?
#
# That's what this program is about

def power_table(b, n):
    a = [None] * (n-1)
    a[0] = 1
    for i in range(1, n-1):
        a[i] = b * a[i-1] % n
#    print(a)
    return a

# need to go up to floor(sqrt(n)) for the largest n of interest
small_primes = [2,3,5,7,11,13,17,19,23, 29, 31]

def discrete_log_table(b, n, negatives=True):
    dl = [None] * n
    pt = power_table(b, n)

    for i in range(0, n-1):
        dl[pt[i]] = i
    dl = dl[1:]   # drop initial None
    # b does not generate <Z_n, ×>
    # e.g. 5^14 == 1 (mod 29)
    # but we need 5^k == 1 implies k is a multiple of 28
#    print(dl)
    if any([ x is None for x in dl ]):
        return None
    if negatives:
      dl = [ d if d*2 < n else d-n+1 for d in dl ]
#    print(dl)
    return dl

# discrete logs of small prime numbers
# that is, for each small prime p
# we find k such that p = b^k  (mod n)
def prime_discrete_logs(b, n):
    dl = discrete_log_table(b, n)
    if dl is None:
        return None
    pdl = { p: dl[p-1]
            for p in small_primes
            if p*p < n }
#    print(pdl)
    return pdl

# total “badness” of the primes in the
# table returned by prime_discrete_logs
def badness_primes(pdl):
    if pdl is None:
        return None
    badness = sum([ abs(i) for i in pdl.values() ])
    return badness

# total "badness" of some arbitrary set of elements
# according to some discrete log table
def badness_general(dl_table, items):
    badness = sum([ abs(dl_table[i]) for i in items ])
    return badness

def badness_min(dl_table, items):
    badness = max([ abs(dl_table[i]) for i in items ])
    return badness

# Print Te code that will format the given vector of values
# into (cols) columns
def tex(table, cols):
    formatter = "".join(["r"] * cols)
    print("$$\n\\begin{array}{", formatter, "}\n", end="", sep="")
    i = 0
    while i < len(table):
        for c in range(0, cols):
            amper = "& " if c > 0 else ""
            print(amper, table[i], ", ", end="", sep="")
            i += 1
            if i >= len(table):
                break;
        print("  \\\\\\\\")
    print("\\end{array}\n$$\n")

if __name__ == '__main__':
    tex(power_table(26, 101), 10)
#    tex(discrete_log_table(53, 101, negatives=False), 10)
    n = 101
    for b in range(2, 100):
#        if b*b >= n:
#            break

        # pdl = prime_discrete_logs(b, n)
        # if pdl is None:
        #     print(b, "doesn't work")
        #     continue
        # print("badness of powers of", b, f"({pdl})", "is",
        #       badness_primes(pdl))


        dl_table = discrete_log_table(b, n, negatives=False)
        if dl_table is None:
            continue
        vec = { i+1: (dl_table[i]) for i in range(1, 9) }
        badness = badness_general(dl_table, range(1,9))
        if badness > 216 and b != 2:
            continue
        print("badness of powers of", b, f"({vec})", "is", badness)
