z12.2.cpp

#include <iostream>
using namespace std;

// Старшая степень полинома
int degree(unsigned int poly)
{
    if (poly == 0) return -1;
    return 31 - __builtin_clz(poly);
}

// Деление polyA на polyB (оба ненулевые) над F2, возвращает остаток
unsigned int polyMod(unsigned int A, unsigned int B)
{
    int degA = degree(A);
    int degB = degree(B);

    while (degA >= degB && A != 0)
    {
        int shift = degA - degB;
        A ^= (B << shift); // XOR - вычитание
        degA = degree(A);
    }
    return A; // остаток
}

// Проверка неприводимости: poly не делится на любой ненулевой полином меньшей степени
bool isIrreducible(unsigned int poly, int n)
{
    if (degree(poly) != n) return false;
    // проверяем делители степени [1..n-1]
    // перебор всех полиномов для степеней поменьше:
    for (int d = 1; d < n; d++)
    {
        unsigned int low = 1u << d;
        unsigned int high = (1u << (d+1)) - 1u;
        for (unsigned int test = low; test <= high; test++)
        {
            // если remainder = 0, значит poly делится
            if (polyMod(poly, test) == 0)
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int n;
    cout << "Введите степень n: ";
    cin >> n;
    unsigned int start = 1u << n;          // 100..0
    unsigned int end   = (1u << (n+1)) - 1u; // 111..1

    int countIrr = 0;
    for (unsigned int p = start; p <= end; p++)
    {
        if (isIrreducible(p, n))
        {
            countIrr++;
            // Выведем в двоичном виде
            cout << "Полином: ";
            for (int b = n; b >= 0; b--)
            {
                cout << ((p >> b) & 1);
            }
            cout << " — неприводим\n";
        }
    }

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