Use Python Enum to implement residue ring and multiplicative residue group

Question

I have implemented the integer residue ring \$ \mathbb{Z}/m\mathbb{Z} \$ and the integer multiplicative residue group \$ (\mathbb{Z}/m\mathbb{Z})^* \$. Functionalities include:

1. In \$ \mathbb{Z}/m\mathbb{Z} \$ , you can do addition, subtraction, multiplication and raising elements to a nonnegative integral power.
2. In \$ (\mathbb{Z}/m\mathbb{Z})^* \$, you can do multiplication, division, raising elements to any integral power and finding the multiplicative orders of elements.

I don't want users to mess around with classes. So the public interface has only two functions, residue_ring_modulo(m) and residue_group_modulo(m), which create and return \$ \mathbb{Z}/m\mathbb{Z} \$ and \$ (\mathbb{Z}/m\mathbb{Z})^* \$ respectively as subclasses of Enum. All other classes are pseudo-private. I choose Enum because all class elements were fixed upon class creation.

Here is the code:

from enum import Enum
from math import gcd

class _ResidueMonoid(Enum):
    """Abstract base class to represent an integer multiplicative residue monoid.
    Examples include Z/mZ (without addition) and (Z/mZ)*.
    """
    @classmethod
    def _validate_type_and_return_val(cls, other):
        # Ensure the operands are of the same type before any binary operation
        if not isinstance(other, cls):
            raise TypeError("Operands' types not matched")
        return other.value          

    def __mul__(self, other):
        other_val = self._validate_type_and_return_val(other)
        result_val = (self.value * other_val) % self.modulus
        return self.__class__(result_val)

    def __str__(self):
        return f'({self.value} % {self.modulus})'


class _ResidueRing(_ResidueMonoid):
    """Abstract base class to represent an integer residue ring"""
    def __neg__(self):
        result_val = (-self.value) % self.modulus
        return self.__class__(result_val)

    def __add__(self, other):
        other_val = self._validate_type_and_return_val(other)
        result_val = (self.value + other_val) % self.modulus
        return self.__class__(result_val)

    def __sub__(self, other):
        other_val = self._validate_type_and_return_val(other)
        result_val = (self.value - other_val) % self.modulus
        return self.__class__(result_val)

    def __pow__(self, other):
        # A ring element can only be raised to a nonnegative integral power
        if not isinstance(other, int):
            raise TypeError("exponent must be integer")
        if other < 0:
            raise ValueError("exponent must be nonnegative")

        result_val = pow(self.value, other, self.modulus)
        return self.__class__(result_val)


class _ResidueGroup(_ResidueMonoid):
    """Abstract base class to represent an integer multiplicative residue group"""
    @staticmethod
    def _solve_linear_congruence(a, b, m):
        # solve (ax = b mod m) by recursive Euclidean algorithm
        if a == 1:
            return b

        x = _ResidueGroup._solve_linear_congruence(m % a, (-b) % a, a)
        return (m * x + b) // a    

    def __truediv__(self, other):
        other_val = self._validate_type_and_return_val(other)
        result_val = _ResidueGroup._solve_linear_congruence(other_val, self.value, self.modulus)
        return self.__class__(result_val)

    def __pow__(self, other):
        if not isinstance(other, int):
            raise TypeError("exponent must be integer")

        # if the exponent is negative, first find the modular inverse
        if other < 0:
            self = self.__class__(1) / self
            other = -other

        result_val = pow(self.value, other, self.modulus)
        return self.__class__(result_val)

    @property
    def ord(self):
        exponent = 1
        val = self.value

        while val != 1:
            exponent += 1
            val = (val * self.value) % self.modulus

        return exponent


def residue_ring_modulo(m):
    """Create the integer residue ring Z/mZ as a concrete class"""
    ring_name = f'Z/{m}Z'
    members = [str(i) for i in range(m)]
    ring = Enum(ring_name, members, type=_ResidueRing, start=0)
    ring.modulus = m
    return ring

def residue_group_modulo(m):
    """Create the integer multiplicative residue group (Z/mZ)* as a concrete class"""
    group_name = f'(Z/{m}Z)*'
    members = {str(i) : i for i in range(m) if gcd(i, m) == 1}
    group = Enum(group_name, members, type=_ResidueGroup)
    group.modulus = m
    return group

Test output:

>>> Zmod9 = residue_ring_modulo(9)
>>> Zmod9(7) + Zmod9(8)
<Z/9Z.6: 6>
>>> Zmod9(3) * Zmod9(6)
<Z/9Z.0: 0>
>>> Zmod9(4) ** 2
<Z/9Z.7: 7>
>>>
>>> Zmod9_star = residue_group_modulo(9)
>>> for x in Zmod9_star:
...     print(x)
(1 % 9)
(2 % 9)
(4 % 9)
(5 % 9)
(7 % 9)
(8 % 9)
>>>
>>> Zmod9_star(2) / Zmod9_star(8)
<(Z/9Z)*.7: 7>
>>> Zmod9_star(4) ** (-3)
<(Z/9Z)*.1: 1>
>>> Zmod9_star(5).ord
6
>>>

I would like to get advice and feedback to improve my code. Thank you.

Answer 1

An interesting use of Enums!

My only concern with using Enum would be performance -- as you note, all possible values are created when the class itself is created, so if you use a big number then you could also be using a lot of memory.

Otherwise, your __dunder__ (aka magic) methods look good, you don't need the reflected methods (e.g. __radd__) since only the exact same types are used in the operations, and I can see nothing wrong.