Теорема Лагранжа

Пример 8.2

Пример 8.1

В элемент примитивен, что легко проверить вычислениями:,,,,. Это можно сделать одновременно:

Mod[3 ^ {1, 2, 3, 4, 5, 6}, 7]

|| {3, 2, 6, 4, 5, 1}

В элемент примитивен. Такой элемент можно найти с помощью функции PowerList пакета "Mathematica" (для чего сначала нужно инициализировать пакет 'FiniteFields'). Эта функция находит примитивный элемент в и порождает все его степени (начиная с 0-й). Второй элемент (т.е.) получаемого списка — сам, примитивный элемент.

<< FiniteFields`

p = 197;

PowerList[GF[p,1]] [[2]]

|| {2}

Для проверки того, что является примитивным элементом поля, необходимо проверить утверждение теоремы Лагранжа.

Пусть ‑ конечная мультипликативная группа порядка. Тогда порядок любой ее подгруппы делит. Кроме того, любой элемент имеет порядок, делящий.

В нашем случае мультипликативная группа поля имеет порядок, а примитивный элемент определяет своей степенью порядок каждого элемента, который делит. Функция FactorInteger помогает найти все различные простые делители числа с их экспонентами, т.е. разложить 196 на простые сомножители.

FactorInteger[196]

|| {{2, 2}, {7, 2}}

Т.е., соответственно простыми делителями являются – и дополнительно 196 делится на и само на себя.

Теперь из

PowerMod[2,196/7,197] == 1

PowerMod[2,196/2,197] == 1

|| False

|| False

следует, что порядок элемента 2 по модулю 197 не делит 196/2 и 196/7, так что этот порядок должен быть равен 196.

Если задано, то можно вычислить по формуле (8.1) с помощью умножений (см. [4]). Это можно реализовать, создав таблицу, (каждая степень ‑ квадрат предыдущей) и. Для этой цели можно использовать двоичное представление.

Дата добавления: 2013-12-12