jb

#include <iostream>
//#include <unordered_map>
//#include <map>
using namespace std;
//using namespace NTL;

int f[9] = {-1, 3, 7, 11, 19, 37, 67, 131, 285 };
int pow2[9] = {1, 2, 4, 8, 16, 32, 64, 128, 256};


int power(int b, int z) ///y=b^z
{
    int y = 1;
    while (z > 0)
    {
        if (z % 2 == 1)
            y = (y * b) ;
        b = (b * b);
        z = z / 2;
    }

    return y;
}

int mult_obr(int a, int n)/// a*x = d (mod n)
{
    int d = a;
    int m = n;
    int y = 0;
    int x = 1;
    int q, z;
    int r = m % d;
    while (r > 0)
    {
        q = m / d;
        z = (y + (n - ((q * x) % n))) % n;
        m = d;
        d = r;
        y = x;
        x = z;
        r = m % d;
    }
    return x;
}

int kit_ost(int* a, int* m, int k)
{
    int M = 1;
    for (int i = 0; i < k; i++)
    {
        M *= m[i];
    }

    int z = 0, M_s, N_s;
    for (int s = 0; s < k; s++)
    {
        M_s = M / m[s];
        N_s = mult_obr(M_s, m[s]);
        z = (z + ((a[s] * M_s ) % M * N_s) % M ) % M ;
    }

    return z ;
}

int Mult(int a, int b, int pow)//// Для 𝑎(𝑥), 𝑏(𝑥) возвращает 𝑐(𝑥)=𝑎(𝑥)∙𝑏(𝑥) 𝑚𝑜𝑑 𝑓(𝑥).
{
    int t = 0, mask = 1;
    for (int i = 0; i < pow; i++)
    {
        if ((b & mask) != 0)
            t ^= a;
        if ((a & pow2[pow-1]) == 0) a = a << 1;
        else a = (a << 1) ^ f[pow];
        mask = mask << 1;
    }
    return t;
}

int Power(int a, int b, int pow)//// Возведение в степень: возвращает 𝑎(𝑥)^𝑏 𝑚𝑜𝑑 𝑓(𝑥).
{
    int c = 1;
    while (b > 0)
    {
        if (b % 2 != 0) c = Mult(c, a, pow);
        a = Mult(a, a, pow);
        b = b >> 1;
    }
    return c;
}

 int Tr(int betta, int pow)
 {
     int s = betta;
     for (int i = 2; i < pow2[pow]; i*=2)
     {
        // формирую betta^2, betta^4, betta^8...
         s = s ^ Power(betta, i,pow);
     }
     return s;
 }

 int kv_yp(int a, int b, int pow )/// квадратные уравнения x^2+a*x+b=0
 {
     if (a == 0)
         cout << "x= " << (Power(b, pow2[ pow - 1],pow))<<endl;
     else {
         int betta = Mult(b, Power(Power(a, pow2[pow] - 2,pow), 2,pow),pow);

         if (Tr(betta,pow) == 0)
         {
             int y0 = 0, y1 = 1;
             int u = 0;////////////////////////////////////////////

             while ((u < pow2[pow]) && (Tr(u, pow)!=1))
             {
                 u++;
             }

             int summ = 0, s_u;
             int current;
             for (int i = 1; i < pow; i++)
             {
                 s_u = 0;

                 for (int j = 0; j < i; j++)
                 {
                     s_u ^= Power(u, pow2[j], pow);
                 }
                 summ ^= Mult(Power(betta, pow2[i], pow), s_u,pow);
             }
             y0 = (y0 + summ) ;
             y1 = (y1 + summ) ;
             //cout << "x_0= " << Mult_256(y0, a) << " " << "x_1= " << Mult_256(y1, a);
             return (Mult(y1, a,pow));
         }
         return -1;
     }
 }

 int gcd(int a, int b) {
     return b ? gcd(b, a % b) : a;
 }

 int diskr(int b, int pow)// дисретный логарифм
 {
     int q = pow2[pow];
     int s = 2;
     int p[2] = { 3,5 };//{ 3, 5, 17 };
     int k[2] = { 1,1 };// { 1, 1, 1 };
     int v[2];
     int u[13];

     int pp, kk, r, h, t, c;

     for (int i = 0; i < s; i++)
     {
         pp = p[i];
         kk = k[i];
         r = power(p[i], k[i]);
         h = (q - 1) / r;
         c = Power(2, h* power (pp,kk-1),pow);
         u[0] = 0;
         while (Power(b,h*power(pp, kk-1),pow) != Power(c, u[0],pow))
         {
             u[0] += 1;
         }
         int alpha_1 = Power(2, q - 2,pow);
         for (int j = 0; j <= kk -1 ; j++)
         {
             t = 0;

             while (Power(Mult(Power(b, h,pow), Power(alpha_1, h*u[j],pow),pow), power(pp, kk -(j+1)),pow) != Power(c, t,pow))
             {
                 t += 1;
             }
             u[j + 1] = u[j] + Mult(t, Power(pp, j,pow),pow);
         }

         v[i] = u[kk];
     }

     return kit_ost(v, p, s);
 }

 int* dv_yp(int m, int a, int pow)// x^m - a = 0
 {
     int* ar = new int[3];
     for (int i = 0; i < 3; i++)
     {
         ar[i] = -1;
     }
     if (a != 0)
     {
         int s = pow;// степень двойки в нашем поле
         int t = 0;
         int n = m;
         while (n % 2 == 0)
         {
             n /= 2;
             t++;
         }
         /// спорный момент
         int r = s - t;
         int b = Power(a, power(2, r), pow);
         int z = diskr(b, pow);
         int q_1 = pow2[s] - 1;
         int d = gcd(n, q_1);
         if ((Power(b, q_1 / d, pow) == 1) && (z % d == 0))
         {
             n /= d;
             z /= d;
             q_1 /= d;
             int n_1 = mult_obr(n, q_1);
             int y = (z * n_1) % q_1;
             for (int i = 0; i < d; i++)
             {
                 ar[i] = Power(2, y + i * q_1, pow);
             }
         }
     }

     return ar;

}

 void third(int a, int b, int c, int pow)//многочлен третьей степени
 {
     int x = 0;
     int p;
     if (Mult(a, a, pow) == b)
     {
         cout << "kv";
         p = dv_yp(3, (Power(a, 3, pow) ^ c),pow)[0];
         x = p ^ a;
         cout << 'x' << x;
     }
     else
     {
         int k = Mult((Mult(a, b, pow) ^ c), Power(dv_yp(2, Power(Power(a, 2, pow) ^ b, 3, pow),pow)[0], pow2[pow]-2,pow),pow);
        if (Tr(Power( k, pow2[pow]-2,pow),pow) == Tr(1,pow))
        {
             int z = kv_yp(k, 1,pow);
             if ((pow2[pow] - 1) % 3 == 0)
             {
                 for (int i = 0; i < 3; i++)
                 {
                     int w = dv_yp(3, z, pow)[i];
                     int y = w ^ Power(w, pow2[pow] - 2, pow);
                     x = a ^ Mult(y, a ^ Power(b, pow2[pow - 1], pow), pow);
                     cout << x << " ";
                 }
             }
             else
             {
                 int w = Power(z, Power(3, pow2[pow] - 2, pow), pow);
                 int y = w ^ Power(w, pow2[pow] - 2, pow);
                 x = a ^ Mult(y, a ^ Power(b, pow2[pow - 1], pow), pow);
                 cout << x << " ";
             }
             cout << endl;
        }
        else cout << "Net" << endl;

     }
 }

int main()
{
    //cout<<Power(17, 2,5);

    //int k = Mult((Mult(a, b, pow) ^ c), Power(dv_yp(2, Power(Power(a, 2, pow) ^ b, 3, pow), pow)[0], pow2[pow] - 2, pow), pow);
    /*for (int i = 1; i < pow2[6]; i++)
    {
        cout <<i<<' '<< Tr(Power(i, pow2[6] - 2, 6), 6)<<endl;
    }*/
    for (int i = 1; i < 16; i++)
    {
        for (int j = 3; j < 16; j++)
        {
            for (int k = 2; k < 16; k++)
            {
                cout << i << ' ' << j << ' ' << k << ' ';
                third(i, j, k, 4);
                cout << endl;
            }
        }
    }
    third(1, 3, 4, 4);
    //third(37, 10,3,6);
    /*int x = 9;
    cout << (Power(x, 3,4) ^ Mult(1, Power(x, 2,4),4) ^ Mult(1, x,4)^11);*/
    //cout << (Mult_256(, a) == b);
}