Здравствуйте, Иванов Петр Сергеевич!

Добрый день! Нужно написать программу нахождения примитивного многочлена третьей степени над полем GF(31)

Я надеюсь, что Вы сможете и сами написать программу по той схеме, что я Вам предлагаю.

Многочлен примитивный, если его нельзя разложить на множители.
В случае многочлена третьей степени это означает, что как минимум один из множителей будет многочлен первой степени.
Это значит, что такой многочлен равен нулю при каком-то значении x.
В вашем случае проверять надо x от 0 до 30.
Причём проверка на 0 тривиальна: Вам надо обеспечить, чтобы был ненулевой константный член.

Теперь, когда мы разобрались с теорией, перейдём к практике.
Как правило интересны моноидальные полиномы (т.е. те у которых коэффициент при старшем члене равен 1).
Вы, значит, должны рассматривать полиномы типа x³+ax²+bx+c.
Значения коэффициентов a,b,c должны меняться от 0 до 30.
Значение полинома считается по модулю 31, т.е. в конце вычислений просто ставите %31.
Для каждого такого полинома Вы должны подставить значения x от 0 до 1 и проверить, что не получается 0 (при вычислении по модулю 31).
Т.о. Ваша программа будет содержать 4 вложенных цикла.
Что-то типа:
for(int a = 0; a < 31; ++a)
{
for(int b = 0; b < 31; ++b)
{
for(int c = 1; c < 31; ++c)
{
bool primitive = true;
for(int x = 1; x < 31; ++x)
{
if((x*x*x + a*x*x + b*x + c)%31 == 0)
{
primitive = false;
break;
}
}
if(primitive)
{
cout << "Found primitive polynomial: x^3+" << a << "x^2 + " << b << "x + " << c << endl;
}
}
}
}