Бинарные отношения 4 страница

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

Пример 30. Имеется многочлен вида f(x) = x¹⁰ + x⁹ + x³ + x² + 1Î F₂[x].

Каноническое разложение f(x) над полем F₂ имеет вид

f(x) = (x²+x+1)³(x⁴+x+1). Так как ord(x² + x + 1) = 3 и имея

ord(gⁿ(x) = p^t ord(g(x)), получаем, что ord((x² + x + 1)³) = 2²× 3 = 12 так как у нас F₂ то есть p = 2 и t = 2 чтобы 2² > 3. Далее ord(x⁴ + x + 1) = 15. Тогда ord(f(x)) = НОК(12, 15) = 60. ▲

4. ТЕОРЕТИКО – ЧИСЛОВЫЕ МОДЕЛИ криптологии

4.1. Основная теорема арифметики

Целое число s называется делителем (или множителем) целого числа n, если n = s∙ t для некоторого t Î Z. В свою очередь n называется кратным s. Делимость n на s обозначается символом |. Делимость – транзитивное свойство на множестве Z. Целое число p, делители которого исчерпываются числами ± p, ±1 (несобственные делители), называется простым. Обычно в качестве простых берутся положительные простые числа > 1.

Фундаментальную роль простых чисел вскрывает так называемая основная теорема арифметики.

Теорема. Каждое положительное целое число n ≠ 1 может быть записано в виде произведения простых чисел: n = p₁∙ p₂∙ p₃∙ …∙ p_S. Эта запись единственна с точностью до порядка сомножителей. (Без доказательства).

Собрав вместе одинаковые простые множители и изменив обозначения, получим запись n в виде: n = p₁¹∙ p₂² ∙ p₃³…p_S^S.

Теорема Евклида гласит, что множество P = {2, 3, 5, 7, 11, 13, …} всех простых чисел бесконечно.

4.2. Свойства чисел

1. Каждое натуральное число n > 1 имеет хотя бы один простой делитель.

2. Наименьший простой делитель составного числа n не превосходит Ö n.

3. Если p – простое число, то любое целое число а либо взаимно простое с р, либо делится на р т.е. р|а.

Построение в настоящие время таблицы простых чисел показывают, что с ростом их величин они встречаются все реже и реже. Например, в первой сотне чисел (N=100) их 25, во второй – 21, третьей 16 и т.д. В первой 1000 их 168, во второй тысяче – 135, в третьей – 120 и т.д. Особый класс простых чисел составляют числа вида 2ⁿ -1. Такие числа называют простыми числами Мерсенна и они являются наибольшими по своему размеру среди других известных простых чисел. Во времена Эйлера наибольшим простым числом было пятое число Мерсенна 2³¹-1. Через сто лет было найдено шестое число Мерсенна 2⁶¹-1. В 1992 найдено самое большое известное число Мерсенна. Его запись содержит 227 832 цифры и требует около ста страниц текста.

4.3. Алгоритм деления с остатком в множестве целых чисел

При заданных a, b Î Z, b > 0, всегда найдутся q, r Î Z такие, что a = bq + r, 0 ≤ r < b (теорема справедлива для любого целого b ≠ 0, при условии, что ограничение r < b заменяетсяна r < |b|).

Алгоритм деления в Z можно также использовать для определения наибольшего общего делителя (НОД), известного из школьного курса математики для заданных целых числах n, m, одновременно не равных нулю. Положим J = { nu + mv | u, v Î Z }. Выберем в J наименьший положительный элемент d = nu₀ + mv₀. Используя алгоритм деления, запишем n = dq + r, 0 ≤ r < d. Ввиду выбора d включение r = n – dq = n – (nu₀ + mv₀)q = n (1– u₀q) +

+ m (– v₀q) Î J влечет равенство r = 0. Стало быть, d | n. Аналогично доказывается, что d | m.

Пусть теперь d' – любой делитель чисел n и m. Тогда d' | n, d ' |m Þ d' | nu₀, d' | mv₀ Þ d' | (nu₀ + mv₀) Þ d' |d.

Итак, d обладает всеми свойствами НОД, и поэтому d = НОД(n, m).

Мы пришли к следующему утверждению.

Наибольший общий делитель двух целых чисел n, m, не равных одновременно нулю, всегда записывается в виде НОД(n, m) = nu+mv; u, v ∈ Z.

В частности, целые числа n, m взаимно просты тогда и только тогда, когда nu + mv = 1 при некоторых u, v ∈ Z.

Для доказательства этого утверждения нужно взять любой положительный элемент из множества J, а затем уменьшать его при помощи алгоритма деления до тех пор, пока не получится наименьший элемент, который и будет наибольшим общим делителем.

4.4. Алгоритм Евклида

Это классический алгоритм вычисления наибольшего общего делителя целых чисел. Мы предполагаем заданными два натуральных числа a и b (a > b; a, b Î Z) и вычисляем их НОД (a, b).

1. Вычислим r – остаток от деления числа a на b, a = b*q +r, 0 ≤ r < b.

2. Если r =0, то b есть искомое число.

3. Если r ≠ 0, то заменить пару чисел (a, b) парой (a, r) и перейти к шагу 1.

a = b q ₁ + r ₁ 0 ≤ r₁ < b
b = r ₁ q ₂ + r ₂ 0 ≤ r₂ < r₁
r ₁ = r ₂ q ₃ + r ₃ 0 ≤ r₃ < r₂
r ₂ = r ₃ q ₄ + r ₄ 0 ≤ r₄ < r₃

_...

r _{n -3} = r _{n -2} q _{n -1} + r _{n -1} 0 ≤ r_n-1 < r_n-2
r _{n -2} = r _{n -1} q _n + r _n 0 ≤ r_n < r_n-1
r _{n -1} = r _n q _{n +1}0 ≤ r_n+1 = 0

r _n – наибольший общий делитель чисел а и b.

Имеем: b > r ₁ > r ₂ >... > r _n > 0, следовательно, процесс оборвется максимум через b шагов. При вычислении наибольшего общего делителя (a, b) с помощью алгоритма Евклида будет выполнено не более 5*p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.

Алгоритма Евклида дает практический способ нахождения чисел u и v из Z таких, что r _n = au + bv = (a, b).

Действительно, из цепочки равенств имеем:

r _n = r _{n -2} - r _{n -1} q _n = r _{n -2} - (r _{n -3} - r _{n -2} q _{n -1} ) q _n =... = au + bv = (a, b).

(идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение).

Пример 31. Пусть а = 525, b = 231

525 = 231 · 2 + 63
231 = 63 · 3 + 42
63 = 42 · 1 + 21
42 = 21 · 2

Таким образом, (525, 231) = 21. Линейное представление наибольшего общего делителя: 21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 =
= 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) = 525 · 4 - 231 · 9,

и u и v из Z равны, соответственно, 4 и - 9. ▲

a. Диофантово уравнение первой степени

Для нахождения секретных ключей в криптосистемах с открытым ключом, часто применяется математический аппарат на базе диофантовых уравнений. Рассмотрим его основные положения.

Поставим задачу отыскания целочисленного решения так называемого линейного диофантова уравнения:

ax - by = c, где a, b, c Î Z. (4.1)

Такое уравнение называется диофантовым. Рассмотрим два метода его решения.

Так как Z – евклидово факториальное кольцо, то в нем всегда возможно нахождение наибольшего общего делителя чисел a и b – (НОД(a, b)) при помощи алгоритма Евклида. Находим его. Если НОД(a, b) = 0, то уравнению удовлетворяют любые целые x и y. Если НОД(a, b) ¹ 0, и c не делитсяна НОД(a, b), то уравнение не имеет решения. Иначе производим сокращение коэффициентов a, b, c и получаем уравнение вида (4.1), но с взаимно простыми a, b, c .