z12.1.cpp

#include <iostream>
#include <vector>
using namespace std;

// Умножение полиномов над F2 (без сокращения по модулю x^n)
unsigned int polyMul(unsigned int a, unsigned int b)
{
    // a и b в двоичном представлении
    // например, a=101(2) = x^2 + 1
    // Перемножаем как биты над F2
    unsigned int res = 0;
    while (b > 0)
    {
        if (b & 1) res ^= a; // XOR вместо +
        a <<= 1;
        b >>= 1;
    }
    return res;
}

// Проверка, делится ли p(x) на q(x) над F2 (где deg(q)<deg(p)?)
// Можно выполнить обычное полиномиальное деление по модулю 2
bool isDivisible(unsigned int p, unsigned int q)
{
    // копируем
    unsigned int r = p;
    // получим степени
    int degP = 31 - __builtin_clz(r);
    int degQ = 31 - __builtin_clz(q);

    while (degP >= degQ)
    {
        // Сдвигаем q, чтобы выровнять старший бит с r
        unsigned int shift = degP - degQ;
        r ^= (q << shift);
        // новый degP
        if (r == 0) return true;
        degP = 31 - __builtin_clz(r);
    }
    return (r == 0);
}

// Проверка неприводимости
bool isIrreducible(unsigned int poly, int n)
{
    // Старший бит (x^n) должен быть = 1 (иначе степень меньше n)
    // poly < 2^n -> это значит старший коэффициент не 1. Нам нужны именно степени ровно n.
    // Поэтому poly должен быть в диапазоне [2^(n), 2^(n+1)-1].
    // Также не должно быть делителя степени < n
    // Перебираем все полиномы степени от 1 до n-1 и проверяем делимость
    for (int d = 1; d < n; d++)
    {
        // перебираем все полиномы степени d
        unsigned int start = 1u << d;           // 100..0 (d+1 бит)
        unsigned int end   = (1u << (d+1)) - 1; // 111..1 (d+1 бит)
        for (unsigned int q = start; q <= end; q++)
        {
            // Если q делит poly, то poly приводим
            if (isDivisible(poly, q))
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int n;
    cout << "Введите n (<=8): ";
    cin >> n;

    // Перебираем многочлены от 2^n (100...0b) до 2^(n+1)-1 (111...1b)
    unsigned int start = 1u << n;
    unsigned int end   = (1u << (n+1)) - 1;

    int countIrred = 0;
    for (unsigned int poly = start; poly <= end; poly++)
    {
        if (isIrreducible(poly, n))
        {
            countIrred++;
            // Выводим двоичное представление
            cout << "Неприводимый: ";
            for (int bit = n; bit >= 0; bit--)
            {
                cout << ((poly >> bit) & 1);
                if (bit > 0) cout << " ";
            }
            cout << endl;
        }
    }

    cout << "Всего неприводимых: " << countIrred << endl;
    return 0;
}