# Use Python Enum to implement residue ring and multiplicative residue group

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)

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.

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.