CSE 5313 Exam 1 review

class PrimeField:
    def __init__(self, p: int, value: int = 0):
        if not utils.prime(p):
            raise ValueError("p must be a prime number")
        if value >= p or value < 0:
            raise ValueError("value must be integers in the range [0, p)")
        self.p = p
        self.value = value
 
    def field_check(func):
        def wrapper(self: 'PrimeField', other: 'PrimeField') -> 'PrimeField':
            if self.p != other.p:
                raise ValueError("Fields must have the same prime modulus")
            return func(self, other)
        return wrapper
 
    def additive_inverse(self) -> 'PrimeField':
        return PrimeField(self.p, self.p - self.value)
 
    def multiplicative_inverse(self) -> 'PrimeField':
        # done by Fermat's little theorem
        return PrimeField(self.p, pow(self.value, self.p - 2, self.p))
 
    def next_value(self) -> 'PrimeField':
        return self + PrimeField(self.p, 1)
 
    @field_check
    def __add__(self, other: 'PrimeField') -> 'PrimeField':
        return PrimeField(self.p, (self.value + other.value) % self.p)
 
    @field_check
    def __sub__(self, other: 'PrimeField') -> 'PrimeField':
        return PrimeField(self.p, (self.value - other.value) % self.p)
 
    @field_check
    def __mul__(self, other: 'PrimeField') -> 'PrimeField':
        return PrimeField(self.p, (self.value * other.value) % self.p)
 
    @field_check
    def __truediv__(self, other: 'PrimeField') -> 'PrimeField':
        return PrimeField(self.p, (self.value * other.multiplicative_inverse().value)%self.p)
 
    def __pow__(self, other: int) -> 'PrimeField':
        # no field check for power operation
        return PrimeField(self.p, pow(self.value, other, self.p))
    
    @field_check
    def __eq__(self, other: 'PrimeField') -> bool:
        return self.value == other.value
 
    @field_check
    def __ne__(self, other: 'PrimeField') -> bool:
        return self.value != other.value
 
    @field_check
    def __lt__(self, other: 'PrimeField') -> bool:
        return self.value < other.value
    
    @field_check
    def __le__(self, other: 'PrimeField') -> bool:
        return self.value <= other.value
    
    @field_check
    def __gt__(self, other: 'PrimeField') -> bool:
        return self.value > other.value
    
    @field_check
    def __ge__(self, other: 'PrimeField') -> bool:
        return self.value >= other.value
    
    def __str__(self) -> str:
        return f"PrimeField({self.p}, {self.value})"

class Polynomial():
    # strict constructor
    def __init__(self, p: int, coefficients: list[PrimeField]=[]):
        if len(coefficients) == 0:
            # no empty list is allowed
            coefficients = [PrimeField(p, 0)]
        if not utils.prime(p):
            raise ValueError("p must be a prime number")
        self.p = p
        for coefficient in coefficients:
            if not isinstance(coefficient, PrimeField) or coefficient.p != p:
                raise ValueError("coefficients must be in the same field")
        self.coefficients = coefficients
        self.remove_leading_zero_coefficients()
 
    # lazy constructor
    @classmethod
    def from_integers(cls, p: int, coefficients: list[int]) -> 'Polynomial':
        # coefficients test
        for coefficient in coefficients:
            if 0 > coefficient or coefficient >= p:
                raise ValueError("coefficients must be integers in the range [0, p)")
        return cls(p, [PrimeField(p, coefficient) for coefficient in coefficients])
 
    def __len__(self) -> int:
        return len(self.coefficients)
 
    def degree(self) -> int:
        return len(self.coefficients) - 1
 
    def evaluate(self, x: PrimeField) -> PrimeField:
        if x.p != self.p:
            raise ValueError("x must be in the same field as the polynomial")
        return sum([(x ** i) * coefficient for i, coefficient in enumerate(self.coefficients)], PrimeField(self.p, 0))
 
    def padding_coefficients(self, degree: int) -> None:
        if degree < self.degree():
            raise ValueError("degree must be greater than or equal to the current degree")
        self.coefficients += [PrimeField(self.p, 0) for _ in range(degree - self.degree())]
 
    def remove_leading_zero_coefficients(self) -> None:
        while self.degree() > 0 and self.coefficients[self.degree()].value == 0:
            self.coefficients.pop()
 
    def field_check(func):
        def wrapper(self: 'Polynomial', other: 'Polynomial') -> 'Polynomial':
            if self.p != other.p:
                raise ValueError("Fields must have the same prime modulus")
            return func(self, other)
        return wrapper
 
    def is_constant(self) -> bool:
        return self.degree() == 0
 
    def next_value(self) -> 'Polynomial':
        # function enumerate all possible polynomials, degree may increase by 1
        new_coefficients = self.coefficients.copy()
        # do list addition
        pt=0
        new_coefficients[pt] = new_coefficients[pt].next_value()
        while pt < self.degree() and new_coefficients[pt] == PrimeField(self.p, 0):
            pt += 1
            new_coefficients[pt] = new_coefficients[pt].next_value()
        if pt == self.degree():
            new_coefficients.append(PrimeField(self.p, 1))
        return Polynomial(self.p, new_coefficients)
 
    def is_irreducible(self) -> bool:
        # brute force check all possible divisors
        if self.is_constant():
            return False
        # start from first non-constant coefficient
        divisor = self.from_integers(self.p, [0,1])
        while divisor.degree() < self.degree():
            # debug
            # print(f"{self}, enumerate divisor: {divisor.as_integers()}")
            if self % divisor == self.from_integers(self.p, [0]):
                # debug
                # print(f"divisor: {divisor}, self: {self}")
                return False
            divisor = divisor.next_value()
        return True
 
    @field_check
    def __add__(self, other: 'Polynomial') -> 'Polynomial':
        padding_degree = max(self.degree(), other.degree())
        self.padding_coefficients(padding_degree)
        other.padding_coefficients(padding_degree)
        new_coefficients = [self.coefficients[i] + other.coefficients[i] for i in range(padding_degree + 1)]
        return Polynomial(self.p, new_coefficients)
 
    @field_check
    def __sub__(self, other: 'Polynomial') -> 'Polynomial':
        padding_degree = max(self.degree(), other.degree())
        self.padding_coefficients(padding_degree)
        other.padding_coefficients(padding_degree)
        new_coefficients = [self.coefficients[i] - other.coefficients[i] for i in range(padding_degree + 1)]
        return Polynomial(self.p, new_coefficients)
 
    @field_check
    def __mul__(self, other: 'Polynomial') -> 'Polynomial':
        new_coefficients = [PrimeField(self.p, 0) for _ in range(self.degree() + other.degree() + 1)]
        for i in range(self.degree() + 1):
            for j in range(other.degree() + 1):
                new_coefficients[i + j] += self.coefficients[i] * other.coefficients[j]
        return Polynomial(self.p, new_coefficients)
 
    def __long_division__(self, other: 'Polynomial') -> 'Polynomial':
        if self.degree() < other.degree():
            return self.from_integers(self.p, [0]), self
        quotient = self.from_integers(self.p, [0])
        remainder = self
        while remainder.degree() != 0 and remainder.degree() >= other.degree():
            # debug
            # print(f"remainder: {remainder}, remainder degree: {remainder.degree()}, other: {other}, other degree: {other.degree()}")
            # reduce to primitive operation
            division_result = (remainder.coefficients[remainder.degree()] / other.coefficients[other.degree()]).value
            division_polynomial = self.from_integers(self.p,[0]* (remainder.degree() - other.degree()) + [division_result])
            quotient += division_polynomial
            # degree automatically adjusted
            remainder = remainder - (division_polynomial * other)
        return quotient, remainder
 
    @field_check
    def __truediv__(self, other: 'Polynomial') -> 'Polynomial':
        return Polynomial(self.p, self.__long_division__(other)[0].coefficients)
    
    @field_check
    def __mod__(self, other: 'Polynomial') -> 'Polynomial':
        return Polynomial(self.p, self.__long_division__(other)[1].coefficients)
 
    def __pow__(self, other: int) -> 'Polynomial':
        # you many need better algorithm to speed up this operation
        if other == 0:
            return Polynomial(self.p, [PrimeField(self.p, 1)])
        if other == 1:
            return self
        # fast exponentiation
        if other % 2 == 0:
            return (self * self) ** (other // 2)
        return self * (self * self) ** ((other - 1) // 2)
    
    @field_check
    def __eq__(self, other: 'Polynomial') -> bool:
        return self.degree() == other.degree() and all(self.coefficients[i] == other.coefficients[i] for i in range(self.degree() + 1))
    
    @field_check
    def __ne__(self, other: 'Polynomial') -> bool:
        return self.degree() != other.degree() or any(self.coefficients[i] != other.coefficients[i] for i in range(self.degree() + 1))
    
    def __str__(self) -> str:
        string_arr = [f"{coefficient.value}x^{i}" for i, coefficient in enumerate(self.coefficients) if coefficient.value != 0]
        return f"Polynomial over GF({self.p}): {' + '.join(string_arr)}"
 
    def as_integers(self) -> list[int]:
        return [coefficient.value for coefficient in self.coefficients]
 
    def as_number(self) -> int:
        return sum([coefficient.value * self.p ** i for i, coefficient in enumerate(self.coefficients)])

class FiniteField():
    def __init__(self, p: int, n: int = 1, value: Polynomial = None, irreducible_polynomial: Polynomial = None):
        # set default value to zero polynomial
        if value is None:
            value = Polynomial.from_integers(p, [0])
        if value.degree() >= n:
            raise ValueError("Value must be a polynomial of degree less than n")
        if not utils.prime(p):
            raise ValueError("p must be a prime number")
        if n<1:
            raise ValueError("n must be non-negative")
        # auto set irreducible polynomial
        if irreducible_polynomial is not None:
            if not irreducible_polynomial.is_irreducible():
                raise ValueError("Irreducible polynomial is not irreducible")
        else:
            irreducible_polynomial = Polynomial.from_integers(p, [0]*(n) + [1])
            while not irreducible_polynomial.is_irreducible():
                irreducible_polynomial = irreducible_polynomial.next_value()
        self.p = p
        self.n = n
        self.value = value
        self.irreducible_polynomial = irreducible_polynomial
 
    @classmethod
    def from_integers(cls, p: int, n: int, coefficients: list[int], irreducible_polynomial: Polynomial = None) -> 'FiniteField':
        return cls(p, n, Polynomial.from_integers(p, coefficients), irreducible_polynomial)
 
    def additive_inverse(self) -> 'FiniteField':
        coefficients = [-coefficient for coefficient in self.value.coefficients]
        return FiniteField(self.p, self.n, Polynomial(self.p, coefficients), self.irreducible_polynomial)
 
    def multiplicative_inverse(self) -> 'FiniteField':
        # via Fermat's little theorem
        return FiniteField(self.p, self.n, self.value ** ((self.p**self.n) - 2) % self.irreducible_polynomial, self.irreducible_polynomial)
 
    def get_subfield(self) -> list['FiniteField']:
        subfield = [
            FiniteField(self.p, self.n, Polynomial.from_integers(self.p, [0]), self.irreducible_polynomial),
            FiniteField(self.p, self.n, Polynomial.from_integers(self.p, [1]), self.irreducible_polynomial)
        ]
        current_element = self
        for _ in range(0, (self.p**self.n) - 1):
            if current_element in subfield:
                break
            subfield.append(current_element)
            current_element = current_element * self
        return subfield
 
    def is_primitive(self) -> bool:
        # check if the element is a primitive element from definition
        subfield = self.get_subfield()
        return len(subfield) == (self.p**self.n)
 
    def next_value(self) -> 'FiniteField':
        new_value = self.value.next_value()
        # do modulo over n
        while new_value.degree() >= self.n:
            new_value = new_value % self.irreducible_polynomial
        return FiniteField(self.p, self.n, new_value, self.irreducible_polynomial)
 
    def field_property_check(func):
        def wrapper(self: 'FiniteField', other: 'FiniteField') -> 'FiniteField':
            if self.n != other.n:
                raise ValueError("Fields must have the same degree")
            if self.p != other.p:
                raise ValueError("Fields must have the same prime modulus")
            if self.irreducible_polynomial != other.irreducible_polynomial:
                raise ValueError("Irreducible polynomials must be the same")
            return func(self, other)
        return wrapper
 
    @field_property_check
    def __add__(self, other: 'FiniteField') -> 'FiniteField':
        return FiniteField(self.p, self.n, (self.value + other.value)%self.irreducible_polynomial, self.irreducible_polynomial)
 
    @field_property_check
    def __sub__(self, other: 'FiniteField') -> 'FiniteField':
        return FiniteField(self.p, self.n, (self.value + other.additive_inverse()).value%self.irreducible_polynomial, self.irreducible_polynomial)
 
    @field_property_check
    def __mul__(self, other: 'FiniteField') -> 'FiniteField':
        return FiniteField(self.p, self.n, (self.value * other.value)%self.irreducible_polynomial, self.irreducible_polynomial)
 
    @field_property_check
    def __truediv__(self, other: 'FiniteField') -> 'FiniteField':
        return FiniteField(self.p, self.n, (self.value * other.multiplicative_inverse()).value%self.irreducible_polynomial, self.irreducible_polynomial)
 
    @field_property_check
    def __eq__(self, other: 'FiniteField') -> bool:
        return self.value == other.value
 
    @field_property_check
    def __ne__(self, other: 'FiniteField') -> bool:
        return self.value != other.value
 
    def __str__(self) -> str:
        return f"FiniteField over GF({self.p}) of degree {self.n}: {self.value}"
 
    def as_vector(self) -> list[int]:
        return [coefficient.value for coefficient in self.value.coefficients]
 
    def as_number(self) -> int:
        return self.value.as_number()
 
    def as_polynomial(self) -> Polynomial:
        return self.value