Some Abstract Algebra (Understanding Cryptography, Second Edition, pp. 244-253)

groups.py

#!/usr/bin/env python3

import operator
from math import gcd, sqrt


def multiplication_modulo(n):
    return lambda a, b: (a * b) % n


# Definition 8.2.1
def is_closed(G, op):
    for a in G:
        for b in G:
            if op(a, b) not in G:
                return False
    return True


def is_associative(G, op):
    for a in G:
        for b in G:
            for c in G:
                if op(op(a, b), c) != op(a, op(b, c)):
                    return False
    return True


def has_identity(G, op):
    for identity in G:
        if all(op(a, identity) == a and op(identity, a) == a for a in G):
            return True
    return False


def has_inverse(G, op):
    for a in G:
        if not any(op(a, b) == 1 and op(b, a) == 1 for b in G):
            return False
    return True


def is_commutative(G, op):
    for a in G:
        for b in G:
            if op(a, b) != op(b, a):
                return False
    return True


def is_finite_group(G, op):
    return (
        is_closed(G, op)
        and is_associative(G, op)
        and has_identity(G, op)
        and has_inverse(G, op)
    )


def is_abelian_group(G, op):
    return is_finite_group(G, op) and is_commutative(G, op)


# Theorem 8.2.1
def Z_star(n):
    return {i for i in range(1, n) if gcd(i, n) == 1}


def theorem_8_2_1(n):
    G = Z_star(n)
    return is_abelian_group(G, multiplication_modulo(n))


# Definition 8.2.3
def ord(a, n):
    return next(k for k in range(1, n) if pow(a, k, n) == 1)


# Definition 8.2.4
def is_cyclic(G, n):
    return len(generators(G, n)) > 0


def generators(G, n):
    return {alpha for alpha in G if ord(alpha, n) == len(G)}


def is_primitive(alpha, G, n):
    return alpha in generators(G, n)


def generate_in_order(alpha, n):
    generated = [pow(alpha, k, n) for k in range(0, n)]
    return generated[: len(set(generated))]


def generate(alpha, n):
    return set(generate_in_order(alpha, n))


# Theorem 8.2.2
def theorem_8_2_2(p):
    if not is_prime(p):
        return False
    G = Z_star(p)
    if not is_abelian_group(G, multiplication_modulo(p)):
        return False
    if not is_cyclic(G, p):
        return False
    return True


# Theorem 8.2.3
def divides(a, b):
    return b % a == 0


def theorem_8_2_3(G, n):
    if not is_cyclic(G, n):
        return False
    for a in G:
        if pow(a, len(G), n) != 1:
            return False
        if not divides(ord(a, n), len(G)):
            return False
    return True


# Definition 6.3.1
def phi(m):
    return sum(1 for i in range(1, m) if gcd(i, m) == 1)


# Theorem 8.2.4
def is_prime(n):
    return n > 1 and all(n % i for i in range(2, int(sqrt(n)) + 1))


def primes(iterable):
    return {x for x in iterable if is_prime(x)}


def theorem_8_2_4(G, n):
    if not is_cyclic(G, n):
        return False
    primitives = generators(G, n)
    if len(primitives) != phi(len(G)):
        return False
    if is_prime((len(G))):
        for a in G:
            if a == 1:
                continue
            if a not in primitives:
                return False
    return True


# Theorem 8.2.5
def subgroups(G, n):
    H = {}
    for a in G:
        s = ord(a, n)
        if s not in H:
            H[s] = generate(a, n)
    return {k: v for k, v in sorted(H.items())}


def theorem_8_2_5(G, n):
    if not is_cyclic(G, n):
        return False
    for a in G:
        s = ord(a, n)
        H = generate(a, n)
        if not is_primitive(a, H, n):
            return False
        if not is_cyclic(H, n):
            return False
        if len(H) != s:
            return False
    return True


# Theorem 8.2.6
def theorem_8_2_6(G, n):
    for H in subgroups(G, n).values():
        if not divides(len(H), len(G)):
            return False
    return True


# Theorem 8.2.7
def theorem_8_2_7(G, n):
    if not is_cyclic(G, n):
        return False
    order = len(G)
    H = subgroups(G, n)
    for alpha in generators(G, n):
        for k in range(1, order + 1):
            if not divides(k, order):
                continue
            if not k in H:
                return False
            if len(H[k]) != k:
                return False
            beta = pow(alpha, order // k, n)
            H_k = generate(beta, n)
            if H[k] != H_k:
                return False
            if H[k] != {a for a in G if pow(a, k, n) == 1}:
                return False
    return True


def subgroup_generator(G, alpha, k, modulus):
    n = len(G)
    beta = pow(alpha, n // k, modulus)
    assert len(generate(beta, modulus)) == k
    return beta


# Definition 8.3.1
def discrete_logarithm(alpha, beta, p):
    for x in range(1, p):
        if pow(alpha, x, p) == beta:
            return x
    return None


# Definition 8.3.2
def generalized_discrete_logarithm(G, op, alpha, beta):
    n = len(G)
    product = alpha
    x = 1
    while x <= n:
        if product == beta:
            return x
        product = op(product, alpha)
        x += 1


def show(expr, end="\n"):
    val = eval(expr, globals())
    print(f"{expr}\t# => {val}{end}")
    return val


if __name__ == "__main__":
    print("# Example 8.3")
    Z_star_n = show("Z_star(9)")

    print("# Example 8.5")
    show("ord(3, 11)")

    print("# Example 8.6")
    show("generate(2, 11)")

    print("# Example 8.7")
    for i in Z_star(11):
        show(f"ord({i}, {11})", end="")
    print()

    print("# Example 8.8")
    show(f"is_abelian_group({1, 3, 4, 5, 9}, multiplication_modulo(11))\n")

    print("# Example 8.9")
    H = show(f"subgroups(Z_star(11), 11)\n")

    for subgroup in H.values():
        show(f"generators({subgroup}, 11)", end="")
    print()

    print("# Example 8.10")
    beta = show(f"subgroup_generator(Z_star(11), 8, 10, 11)")

    print("# Example 8.11")
    show("discrete_logarithm(5, 41, 47)")

    print("# Example 8.12")
    cardinality = show("len(Z_star(47))", end="")
    show("is_prime(cardinality)")

    H = subgroups(Z_star(47), 47)
    show("H.keys()", end="")
    show("primes(H.keys())", end="")
    show("H[23]")

    show("discrete_logarithm(2, 36, 47)", end="")
    show("generalized_discrete_logarithm(Z_star(47), multiplication_modulo(47), 2, 36)")