1. Алфавит дискретных устройств. Конечные поля

При изучении вопросов представления, хранения и переработки информации в качестве алфавита для дискретных логических и вычислительных устройств используется некоторое конечное поле или поле Галуа, которое состоит из конечного числа элементов в отличии от бесконечных полей. На практике чаще всего в качестве поля Галуа применяется поле, состоящее из двух элементов - 0 и 1.

1. 1. Простое поле галуа gf( p )

Пусть Р простое число и * - произвольная арифметическая операция над целыми числами из Z по модулю Р. Тогда

GF( P ) =  0 , 1 , 2 , . . . , Р - 1

образует поле Галуа или конечное поле порядка Р, т. е. поле состоящее из Р элементов с операциями сложения и умножения по модулю Р. Здесь Р называется характеристикой поля GF( P ).

Если Р = 2, то мы имеем наименьшее конечное поле с двумя элементами 0 и 1: GF(2) =  0 , 1 , что и чаще всего является алфавитом для реальных дискретных и логических устройств. Приведём ещё один пример конечного поля GF( 5 ) =  0 , 1 , 2 , 3 , 4  с соответствующими таблицами сложения и умножения ( вычитание и деление неявно определяются этими же таблицами ): + 0 1 2 3 4 * 1 2 3 4

0 0 1 2 3 4 1 1 2 3 4

1 1 2 3 4 0 2 2 4 1 3

2 2 3 4 0 1 3 3 1 4 2

3 3 4 0 1 2 4 4 3 2 1

4 4 0 1 2 3

Очевидно, для любого отрицательного целого числа х по модулю Р имеем х = Р + х ( mod P ), причём можно считать что - х меньше Р.

Так, например, если Р = 5, * - означает умножение, то 13 * 6 = 3 и 14*6 = 4, если * - деление, а - 3 = 2 по модулю 5.

Элемент   0 поля GF( P ) называется примитивным элементом поля, если все его ненулевые элементы могут быть представлены в виде степени элемента . Так, например,  = 2,3 являются примитивными для поля

GF( 5 ).

Арифметика конечных полей ничем не отличается от арифметики бесконечных полей ( например R,Q) за исключением того, что все операции в конечных полях GF( Р ) выполняются по модулю Р.

1.1.1. Составить таблицы сложения и умножения для поля GF( 7 ).

1.1.2. Определить противоположные и обратные элементы поля GF( 7 ).

1.1.3. Найти все примитивные элементы полей GF( 7 ) и GF( 13 ).

1.1.4. Доказать,что каждый ненулевой элемент поля GF(Р) имеет обратный элемент.

1.1.5. Определить число примитивных элементов поля GF( Р ).

1.1.6. Доказать, что для произвольных двух элементов

а, bGF( Р ) имеет место равенство ( а + b) ^Р = а ^Р+ b^Р.

1.1.7. Доказать, что ( Р - 1 ) ! = - 1.

1.1.8. Доказать, что если f ( x ) = a ₀ x ⁿ+ a ₁ x ^{n - 1} + . . . + a _n ,a _n GF( Р ), то f ( х ^Р ) = ( f ( х ) ) ^Р .

1.1.9. Доказать, что корнями уравнения х ^Р - х = 0 являются все элементы поля GF( Р ).

1.1.10. Найти число N _P ( a x + b ) всех линейных функций у = а х + b

в GF( Р ).

1.1.11. Найти число N _P (( a x + b ) / ( с х + d)) всех дробно - линейных функций у = (а х + b ) / ( с х + d ) в GF( Р ).

1.1.12. Определить число N _P ( a d - b c = k ) в GF( Р ) , где k  GF( Р ).

1.1.13. Найти число решений N _P ( х ₁+ х ₂+ . . . + х _n= k ) уравнения

х ₁+ х ₂+ . . . + х _n= k в GF( Р ), где k  GF( Р ).

1.1.14. Доказать, что х ^Р - х =F₁( х ) F_Р ( х ), где F₁( х ) и F_Р ( х ) произведения всех простых над GF( Р ) полиномов степеней 1 и Р соответственно.

1.1.15. Определить число І_P(n)простых над GF( Р ) полиномов степени n. Доказать, что І_P(n) 1.

1.1.16. Разработать алгоритм построения простого над GF( Р ) полиномов заданной степени в явном виде.