Teoria_chisel_i_kriptozashita

2.2. Квадратичные вычеты и закон взаимности

Простые числа р, которые появляются при разложении в непрерывную дробь числа n , имеют особые свойства: для каждого такого р существует х, для которого х2 ≡ n (mod p).

Определение. Пусть р является нечётным простым числом, а число n не делится на p. Тогда n называется квадратичным вычетом по модулю р, если n ≡ x2 (mod p) для некоторого х (записывается nRp), или квадратичным невычетом по модулю р, если не существует таких х (записы-

n

вается nNp). Мы также будем использовать символ Лежандра . Он

p

n

определяется так: для p, не делящего n, будет = + 1, если nRp, и

p

р. Случаем р = 2 пренебрегаем, так как он неинтересен (для каждого нечётного числа выполняется n ≡ 12 (mod 2)). Для выбранного простого числа р мы можем найти n, для которого принадлежность к nRp определяется возведением в квадрат по очереди чисел х = 1, 2, . . . , р – 1. Например, для р = 5 получим 1R5, 4R5, в то же время, 2N5, 3N5.

Критерий Эйлера для квадратичных вычетов. Если g является примитивным корнем по модулю p, где р — нечётное простое число, и

пусть p не делит n, причем n ≡ gk (mod p) для некоторого k. Тогда, если k является чётным n(p-1)/2 ≡ 1 (mod p) nRp.

k является нечётным n(p-1)/2 ≡ –1 (mod p) nNp. Основные свойства символа Лежандра:

а) альтернативное утверждение критерия Эйлера :

n ≡ n(p-1) / 2 (mod p) (здесь р является простым числом и p не де-

p

лит n);

б) если р является простым числом и p не делит n, то

т.е.

nmRp (nRp и mRp) или (nNp и mNp);

21

Закон квадратичной взаимности. Если р и q являются различными

сравнимыми с 3 (mod 4). Это эквивалентно утверждению

p q = (–1)(р-1)(q-1)/4 .

q p

Доказательство. В плоской системе координат х и у отметим целые

12 (p −1)12 (q −1), обе координаты которых являются целыми числами.

Рассмотрим диагональ прямоугольника, которая описывается уравнением

y = xq / p для 0 ≤ х ≤ р/2 и 0 ≤ у ≤ q / 2, и поэтому не может содержать никаких других точек решётки.

Линия х =k (1 ≤ k ≤ 12 (p −1) содержит точки решётки (k, 1), (k,

kq

2), . . . , (k, p ), расположенные ниже диагонали. Таким образом, обо-

значая через М общее число точек решётки, получим qp = (–1)M .

Аналогично, если N представляет собой количество точек, располо-

а так как N + M = 12 (p −1)12 (q −1), то последний результат завершает

доказательство.

Квадратичный закон взаимности обнаруживает простое и в то же

время замечательное взаимоотношение между разрешимостью сравнений

х2 ≡ n (mod p) и х2 ≡ p (mod n).

22

1711

Вычислим, например, для некоторых простых чисел р.

p

мость в разложении n на сомножители.

Определение символа Якоби. Пусть k является нечётным числом, большим нуля, а (n, k) = 1 и предположим, что k является произведением (необязательно различных) простых чисел: k = p1 p2 . . . pr, тогда

Заметим, что все эти символы Лежандра определены, так как нет pi, которое может разделить n (k и n являются взаимно простыми). Таким об-

разом, kn = ±1, и если так случится, что k будет простым числом, тогда символы Якоби и Лежандра совпадут. Заметим также, что если nRk, тогда

обратная теорема не верна, как это видно из следующего

23

в то время как х2 ≡ 2 (mod 15) не имеет решений.

Это позволяет символ Якоби рассматривать менее полезным, чем символ Лежандра, но символ Якоби описывает несколько критических свойств символа Лежандра. Они, действительно, очень полезны.

Основные свойства символа Якоби:

а) если k является нечётным числом и > 0, а (k, n) = (k, m) =1, тогда

б) если k является нечётным положительным целым числом, а

Доказательство следует немедленно из определения символа Якоби совместно с соответствующими свойствами символа Лежандра.

2.3. Вычисление обратных по модулю величин [2; 4; 10]

Определение. Целое число а является обратным числу b по модулю n, если выполняется сравнение: ab ≡ 1 (mod n).

Теорема. Для целых а и n существует b такое, что ab ≡ 1 (mod n), если и только если (a, n) = 1. Когда b существует, оно также будет взаимно простым с b и единственным по модулю n. Последнее утверждение означает: если ab′ ≡ 1 (mod n), тогда b ≡ b′ (mod n).

Доказательство. Если ab ≡ 1(mod n), тогда ab = 1 + k n, так что некоторый общий множитель а и n должен делить 1, что даёт (a, n) = 1 (аналогично (b, m) = 1). Обратно, если (а, n) = 1, тогда, используя алгоритм Евклида, найдём такие целые числа b и k, что ab + n k = 1. Для этого b

ab ≡ 1 (mod n).

Для нахождения числа а необходимо решить сравнение

a х ≡ 1 (mod n).

Это эквивалентно нахождению таких значений целых чисел хи k, что

а х = n k +1.

Существует три основных способа нахождения числа а, обратного числу b по модулю n:

24

1.Проверять путем поочередной подстановки чисел натурального ряда в формулу, пока не будет найдено число а, удовлетворяющее сравнению ab ≡ 1 (mod n).

2.Используя фи-функцию Эйлера ϕ(n) , можно вычислить

а≡ b−1 ≡ bϕ(n)−1(mod n) .

3.С помощью расширенного алгоритма Евклида.

В этом случае при решении сравнения a х ≡ 1 mod n алгоритм Евклида позволяет найти а ≡ (−1)k −1Qk −1(mod n), где Qk −1 — знамена-

тель предпоследней подходящей дроби разложения аn в непрерывную

дробь.

Непрерывная дробь имеет вид:

аn ={q0 ,q1,q2 ,..., qk },

где qi — частное в цепочке следующих равенств:

а = nq0 + r1, 0 < r1 < n , n = r1q1 + r2 , 0 < r2 < r1 , r1 = r2q2 + r3, 0 < r3 < r2,

..........................................

rk −2 = rk −1qk −1 + rk , 0 < rk < rk −1, rk −1 = rлqk + 0,

где ri — остатки от деления.

Поскольку остатки от деления ri в алгоритме Евклида представляют

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

ется, что rk — общий делитель чисел а и n. Любой общий делитель чисел а и n делит и rk . Таким образом, rk =( а, n).

Последовательности {Рm} и {Qm} числителей и знаменателей подходящих дробей в непрерывной дроби определяются рекуррентно:

Р–2 = 0, Р–1 = 1, Рm = qmPm–1+Pm–2 для m ≥ 0,

Q–2 =1, Q–1 = 0, Qm = qmQm–1 +Qm–2 для m ≥ 0.

Для решения более сложных сравнений

a x ≡ b(mod n), b ≠1

25

2.4. Сравнение арифметических операций по их трудоемкости

В современных шифрующих устройствах обычно имеют дело с большим объемом информации, записанной в цифровом виде, т.е. в виде знаков какой-нибудь выбранной системы счисления. В процессе переработки информации приходится выполнять те или иные операции: логические, арифметические, функциональные и др. При этом возникает задача выбора эффективных приемов их выполнения и оценки эффективности используемых методов.

Из арифметических операций над целыми числами простейшими являются сложение, вычитание, умножение, возведение в степень. При этом следует учитывать выбранную систему счисления: позиционную, непозиционную и др.

Широко применяемые для выполнения арифметических операций способы на основе позиционной системы счисления (ПСС) изучены достаточно полно. Вместе с тем повышение требований к основным характеристикам вычислительных средств стимулирует поиск новых форм шифрования, а следовательно, новых форм выполнения арифметических операций. Большое внимание уделяется кодам с параллельной структурой (непозиционным арифметическим кодам). Поэтому особое внимание уделяется модулярным система счисления, обладающим максимальным уровнем внутреннего параллелизма.

Информация в виде позиционного двоичного кода представляет собой набор из k разрядов для представления любого целого числа х между 0 и 2k −1, а именно,

ляются целыми степенями по этому числовому основанию (j = 1, 2, …, k). Рассмотрим теперь использование ряда весов w1, w2 ,..., wn для

представления n—разрядного числа x = (ck ck −1...c2c1) в том же виде, а именно:

26

Для s = 2, например, получим весовую последовательность: w1=1, w1 = 2, w1 = 3, w1 = 5, w1 = 8, w1 = 13 и т. д. Эта последовательность является известными числами Фибоначчи.

Эта конструкция получается по индукции, т.е. итеративно, и генерирует представление х сначала наиболее значимым разрядом с дальнейшим понижением веса последующих разрядов. Пусть yn = x, тогда образуем последовательно числа yn−1, yn−2 ,..., y1 в соответствии с алгоритмом

где сj = 1, если wj ≤ y j < wj+1 .

Иными словами, число х последовательно уменьшается с помощью некоторых коэффициентов последовательности wn , wn−1,..., w1 , взятых в порядке понижения их веса, пока не достигнем отрицательного результата. Если вес wj в настоящее время вычитается из текущей разности, тогда сj = 1; в противоположном случае сj = 0. Например, если s = 2, n = 6 и х = 19, тогда эта конструкция получается из весовой последовательности 13, 8, 5, 3, 2, 1 (выписанной ранее), представление 1910 = (1010012) получается следующим образом:

Заметим, что та же самая конструкция является одной из часто используемых для представления десятичного числа х в двоичном виде. Для

27

Арифметические операции можно выполнить и с помощью кодов Фибоначчи. Для выполнения арифметических операций необходимо выра-

0 1 1 0 1 0 0 1 0 1

1 0 0 1 0 0 0 0 0 1

1 0 0 1 12 = 1910.

Арифметические операции, выполняемые в весовой системе Фибоначчи, могут быть выполнены для двух случаев, которые обратимы: (2.2)

— для кодирования, а (2.4) — для декодирования. Однако добавление двоичных чисел с весом Фибоначчи не будет таким простым. В системе с весовыми коэффициентами по степеням 2 переполнение в цифровой позиции

j (вес которой соответствует 2 j–1) добавляет количество 2 2 j−1 = 2 j к сумме; это переполнение добавляется перемещением 1 к левой позиции, позиции цифры j+1 (чей вес равен 2 j). В системе весов Фибоначчи определение (2.3) может быть выражено как

28

показывая, что количество 2w j, добавленное от переполнения в цифровой

позиции j, должно теперь перемещено не только слева от позиции (j + 1), но также справа (если эта позиция снимается при представлении) от позиции цифры (j – s).

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

чем s – 1. Следовательно, двоичная арифметика, как следует из описания, обладает предпочтением.

Существует ли процедура преобразования кодирования или декодирования, где кодированные разряды могут генерироваться синхронно по времени с приемом цифр от источника последовательного кода? Исследования двоичных весов, эквивалентных весам Фибоначчи и весовым эквивалентам Фибоначчи по степеням 2, показывают, что ни наиболее важные, ни наименее важные разряды результирующего слова не могут быть известны до получения закодированного слова и соответствующим образом преобразованного. Таким образом, схема, которая выполняет преобразование, должна иметь возможность осуществлять сдвиг влево и вправо внутри длины полученного слова. Упрощение кодера к чисто последовательной и непрерывной форме операций (как в обычном двоичном сумматоре) является, следовательно, в своей основе неосуществимым. Обе процедуры преобразования кодов, описанные ранее, требуют, чтобы двоичное весовое представление n весов Фибоначчи было бы доступно в течение общепринятого процесса. Таким образом, эти веса должны быть или сохранены в памяти с произвольной выборкой, или сгенерированы с помощью локальных схем. Рекуррентные соотношения (2.3) и (2.5) показывают, что каждый из этих весов может быть просто сгенерирован из предыдущих значе-

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

Считаем соотношение между параметрами k и n, достаточными для выполнения условия 2k ≤ N3(m,n) = wn(m+1+1) ; т.е. следует выбрать n та-

ким, что

wn < 2k ≤ wn+1 .

За исключением достаточно малых значений m = s – 1, даже очень длинные коды требуют не более n – k избыточных разрядов.

В криптологии часто приходится выполнять операции с многозначными числами. Обычный прием умножения двух 2n-значных чисел легко сводится к четырем умножениям n-значных чисел. Метод А.А. Карацубы

29

позволяет обойтись тремя умножениями n-значных чисел. Если записать

2n-значное число в виде

Аn + 10n Bn,

то легко установить тождество (Аn + 10n Bn)(Cn + 10n Dn) = =Аn Cn

(10n + 1) + (Dn – Cn) ( Аn – Bn) 10n + Bn Dn (102n +10n ), которое дока-

зывает утверждение.

В дальнейшем этот метод был усовершенствован.

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

чем 2m. Для повышенной точности это даёт возможность уверенно оперировать с числами, такими как 1018. Алгоритм Хэда может быть включён в виде подпрограммы в степенной алгоритм.

Пусть нужно умножить х и у по модулю m, где 0 ≤ х ≤ m, 0 ≤ y ≤ m. Метод проходит несколько стадий, и мы исключим некоторые детали, проверяемые в качестве упражнений.

Сложение левых частей неравенств (2.6) и (2.7) даёт m – 14 < T2 + T,

а так как правая часть представляет собой целое число, мы получим

Т2 + Т ≥ m, что является долей искомого результата.

Вторая часть получается, если сложить правую часть неравенства (2.7) с левой частью неравенства (2.6), умножив на (–1), мы получим

T2 – T < m + 43 , что даёт T2 – T ≤ m. Наконец, T2 ≤ 2 m просто следует

из правой части выражения (2.7).

Пусть x = aT + b, где 0 ≤ b < T. Тогда 0 ≤ а ≤ Т. Пусть y = c T + d, где 0 ≤ d < T. Тогда 0 ≤ с ≤ Т.

Доказательство. Очевидно, что а ≥ 0. Если а > T, тогда x = aT +

+b ≥ aT ≥ (T + 1) T ≥ m. Это является противоречием. Другая половина доказывается аналогично.

30