Математические основы защиты информации

Контрольная работа №1. Математические основы защиты информации.

Вариант №1

1. Дано конечное поле GF(р) , р=43 и два элемента  этого поля а=1, b=5. Найти а+в, а-b, a*b, a-1 ,b-1  ,b/a, a/b. 

a=1, b=5. 1=001, 5=101 a+b=001+101=100=4

      a*b=001*101=101=5

   Вычислим в простом поле GF(43) обратный элемент по умножению для элемента a =1 .

   Сначала применим расширенный алгоритм Евклида для чисел a =1 и p = 43 , и определим число g. В качестве «начальных» условий алгоритма принимаются  r0 = p =43 , r1 = a = 1,  g0 = 0, g1 =1 . Начинаем с итерации s = 2 .

q2=43, r2=0

  Поскольку остаток от деления равен нулю, то работа алгоритма на этом завершается, а в качестве результатов принимаются начальные результаты =1.

Для b=5. В качестве «начальных» условий алгоритма принимаются  r0 = p =43 , r1 = b= 5,  g0 = 0, g1 =1.

Начинаем с итерации s = 2

q2=8, r2=3, g2=0-1*8=-8, продолжим

s=3, q3=1, r3=2, g3=1-(-8)*1=9, продолжим

s=4, q4=1, r4=1, g4=-8-9*1=-17 продолжим

s=5, q5=2, r5=0

    Поскольку остаток от деления равен нулю, то работа алгоритма на этом завершается, а в качестве результатов принимаются результаты вычислений на предпоследней итерации.  Поскольку в результате работы расширенного алгоритма Евклида мы получили отрицательное число g = −17 , то в качестве итогового результата, являющегося обратным элементом по умножению для элемента b =5 в простом поле GF(43) принимается число = −17 + 43 = 26.

1. Дано конечное поле GF(17). Найти наименьшие значения примитивного элемента и квадратичного невычета этого поля

   Если [pic 1] — примитивный элемент поля GF(17), то любой другой примитивный элемент может быть получен как степень [pic 2], где k — целое число взаимно простое с 17. Поэтому количество различных примитивных элементов в поле GF(17) равно значению функции Эйлера для GF(16),

Φ(16)= φ(22)=2

   Определение 1. Пусть p — простое нечетное число. Тогда число a, такое, что НОД(a, p) = 1, называется вычетом степени n, если ∃(x) : xn ≡ a (mod p).

Наименьший квадратичный невычет

12=1(mod 17)

22=4(mod 17)

32=9(mod 17)