polynomial.py

import math
from numbers import Number
import itertools
import json
from typing import Tuple


def unicode_superscripts(value):
    exponent_dict = {"0": "⁰", "1": "¹", "2": "²", "3": "³",
                     "4": "⁴", "5": "⁵", "6": "⁶", "7": "⁷", "8": "⁸", "9": "⁹"}
    return ("⁻" if value < 0 else "") + "".join(exponent_dict[x] for x in str(abs(value)))


class Polynomial:
    def __init__(self, value=()):
        if not isinstance(value, tuple):
            raise TypeError("The \"value\" parameter is not of type tuple.")
        self.value = value

    def pass_x_throughout(self, x):
        a = list(self.value)
        sum = (a[len(a)-1]*x)+a[len(a)-2]
        for i in reversed(range(len(a)-2)):
            sum = sum*x+a[i]
        return sum
            
    def __add__(self, other):
        a = list(self.value)
        b = list(other.value)

        a_count = len(a)
        b_count = len(b)
        if a_count > b_count:
            diff = a_count-b_count
            for x in range(diff):
                b.append(0)
        else:
            diff = b_count-a_count
            for x in range(diff):
                a.append(0)

        c = [0] * len(a)
        for x in range(len(a)):
            c[x] = a[x]+b[x]

        return Polynomial(tuple(c))

    def __mul__(self, other):
        a = list(self.value)
        b = list(other.value)
        a_count = len(a)
        b_count = len(b)
        size = ((a_count - 1) + (b_count - 1) + 1)
        c = [0] * size

        for i in range(a_count):
            for j in range(b_count):
                c[i+j] += a[i]*b[j]

        return Polynomial(tuple(c))

    def __mod__(self, other):
        a = list(self.value)
        result = [0] * len(a)

        for i in range(len(a)):
            result[i] = a[i] % other

        for i in reversed(range(len(result))):
            if result[i] == 0:
                del result[i]
            else:
                break

        return Polynomial(tuple(result))

    def __str__(self):
        str_value = ""

        for i, x in enumerate(reversed(self.value)):
            x = math.ceil(x)
            if x == 0:
                continue
            if i != 0:
                str_value += " + " if x >= 0 else " - "
            if x != 1 or i == len(self.value) - 1:
                str_value += str(abs(x))

            if len(self.value) - i - 1 >= 1:
                str_value += "x"
            if len(self.value) - i - 1 >= 2:
                str_value += unicode_superscripts(len(self.value) - i - 1)
        return str_value


def compute_bachet_bezout(a, b):
    r = []
    x = []
    y = []
    q = []

    # Init
    r.append(a)
    x.append(1)
    y.append(0)
    q.append(0)

    r.append(b)
    x.append(0)
    y.append(1)
    q.append(0)

    # Computing
    i = 1
    while r[i] > 0:
        i += 1
        r.append(r[i-2] % r[i-1])
        q.append(int(r[i-2] / r[i-1]))
        if r[i] > 0:
            x.append(x[i-2]-q[i]*x[i-1])
            y.append(y[i-2]-q[i]*y[i-1])

    return x[-1], y[-1]


def modular_inverse(a, n):
    bachet_bezout = compute_bachet_bezout(a,n)
    modular_inverse = bachet_bezout[0]
    if a * modular_inverse % n == 1:
        return modular_inverse
    return None


def compute_lagrange_polynomial(points, prime_number):
    nb_points = len(points)
    lagrange = Polynomial((0,))

    # Create a polynomial for each points
    for i in range(nb_points):
        poly_li = Polynomial((1,))
        divider = 1

        # Compute the lagrange polynomial
        for k in range(nb_points):
            if k != i:
                dividend = Polynomial((-points[k][0], 1))  # x - value

                poly_li *= dividend
                divider *= (points[i][0] - points[k][0])

        divider = 1 / divider
        point_yi = points[i][1]
        poly_li = poly_li * Polynomial((divider,)) * Polynomial((point_yi,))

        lagrange += poly_li

    return lagrange


def reed_solomon(points, data_length, last_error_index, prime_number):
    pass


def main():

    p1 = Polynomial((5, 1, 4))
    p2 = Polynomial((5, 2, 3, 4))
    p3 = p1*p2
    # print(p1)
    # print(p2)
    # print(p3)
    # print(p3 % 4)
    # print(p3 % 5)
    a = 168
    b = 68
    x, y = compute_bachet_bezout(a, b)
    print("Pour les chiffres " + str(a) + " et " + str(b) +
          ". Les coéfficients de Bachet-Bézout sont : " + str(x) + " et " + str(y))

    a = 3
    b = 7
    print("Inverse modulaire de " + str(a) + " % " +
          str(b) + " est " + str(modular_inverse(a, b)))

    with open("messages.json") as f:
        messages = json.load(f)
    print(len(messages))

    for message in messages:
        points = [(x, y) for x, y in enumerate(message["points"])]
        corrected_data = reed_solomon(
            points, message["data_length"], message["last_error_index"], message["prime_number"])
        print(corrected_data)
        break


if __name__ == "__main__":
    main()