#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import numpy as np
from sympy import Poly, Symbol
from scipy.signal import fftconvolve

x = Symbol('x')

k = 19937
# k = 12

jump = 1234567
# jump = 21

# phi is minimal polynomial
phi = Poly(np.append(1, np.random.random_integers(0, 1, k - 1)), x, modulus=2)
# print(phi)

# # it's big initial polynomial, which we'd like to reduce
# f = Poly(x ** jump, x, modulus=2)
# # print(f)

# # g is resulted polynomial
# g = f.rem(phi)
# print(g)


def my_mul(f, g):
    return fftconvolve(f, g) % 2


def my_rem(f, g):
    f = np.array(f, dtype=np.int)
    g = np.array(g, dtype=np.int)
    df = len(f)
    dg = len(g)
    shift = df - dg + 1
    for i in range(shift):
        if f[i] == 1:
            f[i:i + dg] ^= g
    return f[shift:]


def my_foo(power, phi, degree):
    # print('I\'m in %d' % power)
    if power < degree:
        return np.append(1, np.zeros(power, dtype=np.int))
    temp = my_foo(power // 2, phi, degree)
    result = np.array(my_mul(temp, temp), dtype=np.int)
    result = my_rem(result, phi)
    if power % 2 == 1:
        result = my_rem(my_mul(result, [1, 0]), phi)
    return result


g1l = my_foo(jump, np.array(phi.all_coeffs()), phi.degree())
print(g1l)
g1 = Poly.from_list(g1l, x, modulus=2)
# print(g1)