The equivalent problem of testing fermat primes.pdf Неприводимые многочлены - аналог простых чисел - имеют большую ценность в теории информации, помехоустойчивом кодировании, работе конечных автоматов, стандартах защиты информации. Поэтому актуален поиск взаимосвязи между ними [1-4]. Интерес представляют многочлены степени 2n над полем GF(2), коэффициенты которых при преобразовании в битовые строки широко используются для работы ЭВМ. В кодировании применяются симметричные (самовозвратные) многочлены [5] порядка p = 22 +1 степени N = 2k+1. Легко показать, что если неприводимый над GF(2) многочлен имеет степень 2m и порядок 2m + 1, то он симметричен. ^ оА; Утверждение 1. Простота числа Ферма p = 22 +1 эквивалентна равенству p порядков всех неприводимых симметричных многочленов степени n = 2k+1 над GF(2). Так, например, при k = 0, p =3 имеется один симметричный многочлен x2 + x + 1 степени 2, порядка 3; при k = 1, p = 5 - один симметричный многочлен x4+x3+x2+x+1 степени 4, порядка 5; при k = 2, p = 17 - два многочлена степени 8, порядка 17: x8 + x7 + x6 + x4 + x2 + x +1 и x8 + x5 + x4 + x3 + 1; при k = 4, p = 65537 имеется 2048 многочленов степени 32 порядка p [6]. При k = 5 число p = 4294967297 = 64 • 6700417 непростое, это означает, что неприводимые симметричные многочлены степени 64 имеют порядок 4294967297, или 641, или 6700417. Последовательным подбором коэффициентов были найдены 10 неприводимых симметричных многочленов степени 64 порядка 641 [4]. При k = 6 получаем p = 18446744073709551617 = 274177 ■ 67280421310721. До настоящего времени не найдено простых чисел Ферма для k > 4, есть предположение, что их больше нет. Как известно, круговой многочлен xp-1 + ... + x + 1 неприводим над полем GF(q) тогда и только тогда, когда p простое и q - первообразный корень по модулю p [5]. Число Ферма p простое тогда и только тогда, когда 3 - первообразный корень по модулю p [7]. Определение 1 [1, с. 55]. Пусть P = Fq, K = GFqm и a G K. След TrK/P(a) элемента a из поля K в поле P определяется равенством Tr^/p (a) = a + aq + aq2 + т1 + ... + aq . Переход от корней круговых многочленов при помощи функции следа к гауссовым нормальным базисам [1, с. 274] равносилен вычислению следа из поля GF(32S) в поле GF(3) корня уравнения xp-1 + .. .+x+1 = 0 над GF(32S), s = 2k, и даёт неприводимые многочлены над GF(3). Утверждение 2. Пусть p = 22k + 1 и Z - корень кругового многочлена Zp-1 + + Zp-2 + ... + Z + 1 = 0 над GF(3), так что Zp = 1. Тогда простота числа p эквивалентна неприводимости всех характеристических многочленов любого следа элемента Z. Утверждение 3. Пусть p - число Ферма. Тогда равенство следа элемента Z G G GF(3p-1) порядка p в поле GF(32) корню X = x неприводимого над GF(3) многочлена второй степени X2 + X + 2 равносильно простоте числа p. Таким образом, задача проверки простоты чисел Ферма эквивалентна построению многочленов над конечным полем GF(2) или GF(3) и проверке их на неприводимость.

Скачать электронную версию публикации