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:
- In \$ \mathbb{Z}/m\mathbb{Z} \$ , you can do addition, subtraction, multiplication and raising elements to a nonnegative integral power.
- 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.
