ТЧМК. 02 - ТЧМК - ПЗ-2 - НДВ. Занятие 2 Решение задач по алгебраическим основам криптографии

• Название: Занятие 2 Решение задач по алгебраическим основам криптографии
• Дата: 30.10.2022
• Размер: 18.3 Kb.
• Имя файла: 02 - ТЧМК - ПЗ-2 - НДВ.docx
• Тип: Занятие; #762378

Практическое занятие №2

«Решение задач по алгебраическим основам криптографии»

Цель занятия: приобретение навыков решения типовых задач по алгебраическим основам криптографии.

Теоретическаячасть.

Одной из актуальных теоретико-числовых задач, используемых в криптографии, является отыскание наибольшего общего делителя двух чисел и его линейного представления.

Пусть MOD(a, b) есть операция взятия остатка от деления a на b, а QUO(a, b) есть частное от деления a на b. Алгоритм Евклида позволяет без разложения двух целых чисел на множители находить их наибольший общий делитель. В данном алгоритме используется следующее утверждение: если a= bq + r, где b 0, и число dделит aи b, то оно делит и r, т. е. имеем d| (a– bq). Это утверждение верно для любого делителя, включая наибольший общий делитель d = НОД(a, b). Отсюда следует, что НОД(a,b) = НОД[b, MOD (a, b)].

Для всякого aимеем также НОД(a,0) = |a|. Определит также НОД(0,0) = 0. Пусть заданы целое число aи ненулевое целое число b. Алгоритм Евклида предполагает выполнение следующей последовательности делений, где принято обозначение a₀ = aи a₁ = b:

a₀ = a₁q₁ + a₂, 0 < a₂ < |a₁|,

a₁ = a₂q₂ + a₃, 0 < a₃ < a₂,

…

^ak-2 ^{= a}k-1^qk-1 ^{+ a}k^{, 0 < a}k^<ak-1^,

a_k-1 = a_kq_k+ 0.

Процесс деления имеет конечное число шагов, поскольку остатки убывают по абсолютной величине |a₁| > a₂ > a₃ >…> 0 (значение a₁ может быть отрицательным, поэтому оно взято по абсолютной величине; остальные остатки положительны). Значение a_kявляется наибольшим общим делителем. С учетом указанного выше утверждения имеем

НОД(a₀, a₁) = НОД(a₁, a₂) =…= НОД(a_k, 0) = a_k,

т. е. на самом деле a_kявляется наибольшим общим делителем чисел a и b. Одновременно мы показали, что приведенный ниже алгоритм работает правильно. Обозначим операцию присвоения следующим образом: x := yозначает присвоение переменной xзначения y; (x,y) := (x₁,y₁) означает выполнение операций x:=x₁ и y:=y₁.

Алгоритм Евклида (нахождение НОД(a, b)) Вход: aи b 0.

1. (a₀, a₁) := (a, b).

2. Пока a₁  0 выполнять (a₀, a₁) := [a₁, MOD (a₀, a₁)] 3. d := a₀.

Выход: d= НОД(a, b).

В любой строке, описанного выше алгоритма Евклида, каждый остаток представляет собой линейное представление делимого и делителя. Очевидно, что, начиная с одного из ненулевых остатков (например, последнего, т. е. начиная с a_k) и выражая остатки, полученные на последующих шагах алгоритма Евклида, через остатки, полученные на предыдущих шагах, можно представить значение a_i(соответственно, a_k) в следующем виде a_i= ax + by (соответственно, a_k= ax + by), где xи yнекоторые целочисленные коэффициенты. Расширенный алгоритм Евклида позволяет вычислить значения коэффициентов xи yв указанном линейном представлении НОД(a, b), т. е. в выражении a_k= ax + by. Работа расширенного алгоритма Евклида организуется так, что значения x и y вычисляются в серии шагов, в каждом из которых мы выражаем a_iв виде указанного представления.

Каждый остаток, вычисленный в процессе работы алгоритма Евклида можно представить в виде ax_i+ by_i.Рассмотрим следующую последовательность такого представления остатков:

a₀ = a, a₀ = ax₀ + by₀,

a₁ = b, a₁ = ax₁ + by₁,

a₂ = a₀ – a₁ q₁, a₂ = ax₂ + by₂,

…

a_i= a_i-2 – a_i-1 q_i-1, a_i= ax_i+ by_i,

…

a_k= a_k-2 – a_k-1 q_k-1, a_k= ax_k+ by_k,

0=a_k-1 – a_kq_k, 0 = ax_k+1 + by_k+1.

В левом столбце фактически приведена последовательность делений, полученная в алгоритме Евклида, но записанная в виде выражения для вычисления остатков. В правом столбце каждый остаток выражен в интересующем нас виде ax_i+ by_i. Пока мы не знаем коэффициентов. Нашей целью является вычисление x_iи y_iдля любого i, а следовательно и для i = k. Очевидно, что x₀=1, y₀=0 и x₁=0, y₁=1. Сравнивая обе части на i-м шаге, получаем

a_i= ax_i+by_i= a_i-2–a_i-1q_i-1 = (ax_i-2+by_i-2) – (ax_i-1+by_i-1)q_i-1 = a(x_i-2–x_i-1q_i-1) + b(y_i-2–y_i-

1^qi-1^),

откуда получатся следующая индуктивная процедура вычисления x_iи y_i: q_i-1 = QUO(a_i-2, a_i-1)

^ai ^{= a}i-2 ^{– a}i-1^qi-1^{, x}i ^{= x}i-2 ^{– x}i-1^qi-1^{, y}i^{= y}i-2 ^{– y}i-1^qi-1^.

Отметим, что значение a_iможет быть вычислено как MOD(a_i-2, a_i-1), но достоинство приведенного выше выражение заключается в том, что a_iвычисляется аналогично вычислению коэффициентов x_iи y_i. Этот факт используется в следующем алгоритме.

Расширенный алгоритм Евклида

Вход: aи b 0

1. (a₀, a₁) := (a, b); (x₀, x₁) := (1, 0); (y₀, y₁) := (0, 1).

2. Пока a₁  0 выполнять

{q := QUO(a₀, a₁); (a₀, a₁) := (a₁, a₀-a₁q);

(x₀, x₁) := (x₁, x₀-x₁q);

(y₀, y₁) := (y₁, y₀-y₁q)}.

3. (d, x, y) := (a₀, x₀, y₀).

Выход: Значения d, x, y, такие, что d = НОД(a, b) = ax+ by.

Вычисление функции Эйлера

Определение Функция  :

, ставящая в соответствие каждому

натуральному числу тколичество

 _m_

натуральных чисел, меньших т

и взаимно простых с т,называется функциейЭйлера.При этом полагают

 _1_  1.

Функция Эйлера обладает свойством мультипликативности: если

^{НОД(т,п) 1, то } ^mn ^{ } ^m^ ⁿ^.

Если число p простое, то случай теоремы Эйлера.

 _ p_  p 1.

Отсюда получаем частный

Теорема (малая теорема Ферма). Пусть число pпростое, число a

целое, aне делится на р. Тогда ^{аp1  1(modp).}

Рассмотрим способ вычисления функции Эйлера.

Теорема. Если число р простое, число п натуральное, то

 _ pⁿ_  pⁿ p^n1.

Заданиена Практическоезанятие№2.

Разработать программу, реализующую алгоритмы:

• 
  Евклида и расширенный алгоритм Евклида;
  
• 
  вычисления функции Эйлера, символов Лежандра и Якоби;
  
• 
  поиска квадратичных и кубических вычетов.