Целочисленная арифметика многоратной точности

Присвоить u0u1.. um+n:= u1.. um+nd, v1... vn:=v1.. .

vn· d.(Из теоремы 1.6 следует, что новое значение v1 больше или равно [b/2].) 2 шаг. j :=0.3 шаг (обеспечение выполнения условий основной задачи). Присвоить l :=0. Если, то выполнены условия основной задачи; мы переходим на4 шаг.

Если то uj. .. uj+n :=uj. .. uj+n− bv, l :=l +1.Снова проверить выполнение неравенства если да, то перейти на 4 шаг.

Иначе еще раз присвоить uj. .. uj+n :=uj. .. uj+n− bv, l :=l +1Замечание 1.

7. Покажем, что после 3 шага будет выполнено неравенство, т. е. выполнены условия основной задачи. Поскольку v1≥[b/2], то v =v1... vn≥[b/2]bn−1. Та кже uj. .. uj+n ≤bn+1 − 1.

Покажем, чтоuj. .. uj+n bn+1 − 1≥ uj. .

uj+n, так как при b =2 неравенство3 2n[2/2] >2n+1 — 1очевидно, а при b ≥3 либо [b/2] =b/2, либо [b/2]=b/2−½, и тогдатак как. Итак, после 3 шага uj. .. uj+n < bv. Замечание 1.

8. Значение переменной l показывает, что из первоначального значения uj. .. uj+n мы вычли lbv. Впоследствии нам надо будет добавить lb в соответствующий разряд итогового частного на9 шаге.

4 шаг (нахождение qˆ). На этом шаге выполнено неравенство uj≤ v1, так как, если uj >v1, то что противоречит условию основной задачи, которое выполнено. Если uj= v1, то, и тогда мы присваиваем qˆ:=b−1.Если uj < v1, то, так как иначечто невозможно, посколькуb −1 ≥uj+1, b (v1− uj) ≥b.В этом случае мы присваиваем 5 шаг. Проверить выполнение неравенстваv2qˆ > (ujb +uj+1 − qˆ v1) b + uj+2. (1.19)Если оно выполнено, то qˆ := qˆ −1. Снова проверить (1.19), и если оно выполнено, то присвоить еще раз qˆ := qˆ −1.Замечание 1.

9. Поскольку n≥ 2, то v—не менее чем двухразрядное, а число u= u0... um+n—не менее чем трехразрядное; значит, цифра uj+2 с номером j +2 определена. Замечание 1.

10. После 4 шага выполнены условия теорем 1.3 и 1.

4. Знаичт, qˆ − 2≤ q ≤qˆ, т. е. qˆ равно либо q, либо q +1, либо q + 2. Положим r˜:= ujb + uj+1 − qˆ v1—выражение, стоящее в формуле (1.19) в скобках. Покажем, что если v2qˆ > r˜b + uj+2, (1.20)то qˆ >q. В самом деле, надо доказать, что uj. .. uj+n −qˆ v <0.Справедливы следующие соотношения: uj .

.. uj+n − qˆ v≤ uj. .. uj+n − qˆ v1bn−1 − qˆ v2bn−2 = uj+2bn−2 +…+uj+n +ujbn+ +uj+1bn−1 − qˆ v1bn−1 − qˆ v2bn−2 =r˜ bn−1 + uj+2bn−2 +.. .+uj+n − qˆ v2bn−2 < r˜bn−1 + +(uj+2 +1)bn−2 − qˆ v2bn−2 = bn−2 (r˜ b +uj+2 + 1 −qˆ v2).

(1.21)Если выполнено неравенство (1.20), то в формуле (1.21)r˜ b +uj+2 + 1− qˆ v2< r˜b + uj+2 +1 − (r˜ b +uj+2) =1.Поэтому r˜ b +uj+2 + 1− qˆ v2<0, и из (1.21) следует, что uj… uj+n −qˆv<0, т. е. qˆ ≤q + 1. Следовательно, надо заменить qˆ на qˆ − 1—это будет лучшим приближением к q. Эта процедура 5 шага делается не более двух раз, так как qˆ ≤ q+ 2 по теореме 1.

4.Замечание 1.

11. Сейчас для текущего значения qˆ, удовлетворяющего неравенству q ≤ qˆ ≤q+ 2, и для значения r˜ =ujb + uj+1−qˆv1 выполняется неравенство v2qˆ ≤ br˜ + uj+2. (1.22)Докажем, что в этом случае qˆ равно либо q, либо q + 1. Предположим противное, т. е. что

q = qˆ − 2. Но тогдаuj. uj+n < (qˆ − 1) v < qˆ (v1bn−1 + (v2 +1)bn−2) − v < qˆ v1bn−1 + qˆ v2bn−2 +bn−1 −v, поскольку qˆ bn−2

uj+n < qˆ v1bn−1 + (br˜ + uj+2)bn−2 +bn−1−v = qˆ v1bn−1 + (ujb2 + uj+1b +uj+2 −qˆ v1b) bn−2 + bn−1 − v ≤ ujbn + uj+1bn−1 + uj+2bn−2, (1.23)поскольку bn−1 −v ≥ 0. Формула (1.23) означает, что uj… uj+n

.. uj+n, а знак в переменную δ.7 шаг. qj:=qˆ. Если разность (1.24) неотрицательна, то уходим на9 шаг.

8 шаг. Присваиваем qj:= qj −1 (так как разность (1.24) в этом случае отрицательна, то qˆ = q +1), а также uj.. uj+n:=v1... vn−uj. .. uj+n.9 шаг. К значению qj прибавляем величину lb из 3 шага. Замечание 1.

12. На3 -м шаге мы обеспечивали выполнение условий основной задачи, вычитая из исходного числа uj. .. uj+n число lbv. Поэтому к найденному частному qjот деления нового (после 3 шага) числа uj .

. uj+n на v надо добавить lb. После этого значение qjуже не всегда будет цифрой в b-ичной системе счисления, оно может стать больше, чем b.10 шаг. Сейчас в текущем значении числа uj. .

uj+nцифра ujравна 0, так как в нем фактически стоит остаток от деления на n-разрядное число v1… vn. Присваиваем j :=j +1. Если j≤m, то возвращаемсяна3 шаг.

11 шаг. Искомое частное от деления u на v равноq := q0bm+ q1bm−1 +. .. qm−1b + qm (здесь qjуже могут не быть цифрами в b-ичной системе счисления, см. замечание на шаге 9). Остаток от деления u на v равен d, где d—из 1 шага алгоритма, um+1 …um+n—значение, полученное после последнего выполнения 10 шага. Конец алгоритма.Корректность работы алгоритма деления обоснованы по ходу его описания. Глава 2. Некоторые алгоритмы модулярной арифметики

Начнем с китайской теоремы об остатках. В Приложении мы привели формулировку этой теоремы о решении системы сравненийгде (mi, mj) =1 при i≠j. Формулировка является конструктивной, т. е. представляет собой метод решения системы уравнений. Однако в ряде случаев более эффективным является алгоритм Гарнерa. По сравнению с классической китайской теоремой об остатках он не требует приведения по модулю M=m1…mk.§ 2.

1. Алгоритм Гарнера. На входе алгоритма заданы числа a1,. ., ak, m1,. .. , mk, (mi, mj) =1 при i≠j, и число M=m1.. .mk. На выходе получается решение xсистемы (2.1), 0≤x

Далее, при i≥ 2 ci== (m1. .mi−1)−1 (mod mi). Очевидно, что x==a1(modm1). Обозначим через xiзначение x в алгоритме, которое получается после выполнения 3 шага для значения переменной i (2 ≤i≤ k); x1 = a1. Тогда

Поскольку итоговое значение x в алгоритме по построению удовлетворяет сравнениям x==xi (mod mi), i= 1,…, k, алгоритм Гарнера работает верно. Теперь опишем вкратце модулярное умножение и возведение в степень по Монтгомери. Зафиксируем натуральное число N > 1 и натуральное число R, R > N, (R, N) = 1. Число R выбирается так, чтобы вычисления по модулю R были достаточно легкими (например, R—размер машинного слова или степень двойки). Пусть заданы R', N' ∈Z, такие, что 0< R'< N, RR' - NN' = 1 (R' и N' можно найти с помощью обобщенного алгоритма Евклида). Для целого числа T, 0≤T

2. Алгоритм Монтгомери. Алгоритм REDC (приведение по Монтгомери).

1 шаг. m:=T (mod R)—наименьший неотрицательный вычет.

2 шаг. m:=mN' (mod R)—наименьший неотрицательный вычет.

3 шаг. 4 шаг. Если t ≥N, то выдать t− N, иначе выдать t. Конец алгоритма.Покажем, что алгоритм работает верно. Поскольку значение m, получающееся на 2 шаге, удовлетворяет сравнению mN== TN’N==−T (modR), то значение t, определяемое на3 шаге, будет целым числом. Далее, tR==T+mN==T (mod N), т.

е. t== TR−1 (mod N). Наконец, 0≤ T + mN < 2N. Это завершает обоснование корректности алгоритма REDC. Заметим, что поскольку мы считаем вычисления по модулю R (в том числе, деление на R) быстрыми, то сложность выполнения алгоритма REDC в основном заключается в двух умножениях целых чисел, по модулю не превосходящих R. Аналогично можно описать приведение по Монтгомери для целых чисел многократной точности, умножение по Монтгомери (т. е.

для x, y ∈Z и N ∈N мы находим xyR−1 (mod N)) и возведение в степень по Монтгомери (т. е. для x, N, e ∈N вычисляется xe (mod N)). Возведение в степень по Монтгомери оказывается эффективным и рекомендуется для практического использования. Еще один алгоритм для эффективного модулярного возведения в степень был предложен в работе. Авторы этой работы утверждают, что их алгоритм эффективнее алгоритма Монтгомери. Для вычисления x (mod m) при заданных x и m эффективен алгоритм Баррета. Заключение

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

Список литературы

1.Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.:МЦНМО, 2003.—328 с. Виноградов И. М. Основы теории чисел. М.: Наука, 1972

Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра.М.:Мир, 1991

Карацуба А.А., Офман Ю. П. Умножение многозначных чиселна автоматах // ДАН СССР. 1961. Т. 145 (2).

С. 293—294.Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы.

Вильямс: М.—СПб.—Киев, 2000. 3-е издание

Чебышев П. Л. Полное собрание сочинений. Т. 1. Теория чисел. Изд-во АН СССР, 1946.