Отправлено andy_P 31 августа 2005 г. 17:19 В ответ на: Скорее всего, что число простых чисел степени не больше N и число примитивных полиномов той же степени равны. Но почему, не знаю. отправлено <font color=gray>729</font> 31 августа 2005 г. 17:07

Теорема о том, что примитивный полином степени m должен делить X^(2^m-1) + 1 (или X^(2^m-1) - 1 , что впрочем все равно, если коэффициенты из GF(2))

И теорема Эйлера: если gcd(a,n) = 1, то a^(phi(n)) = 1 mod n.