ВУЗ:
Составители:
Рубрика:
53
13. Алгоритм Хэда умножения по mod m
Если Вы умножите два числа по модулю m обычным способом, тогда,
естественно, возникает необходимость обращаться с большими числами
порядка m
2
. Однако умножение – это только повторное сложение, так что, в
принципе, можно проводить умножение без операций над числами, боль-
шими, чем 2 m. (Например, 3 × 8 по модулю 10 можно представить как
8 + 8 = 16 ≡ 6, 6 + 8 = 14 ≡ 4). Конечно, это было бы недопустимо непрак-
тично проделывать для чисел из десяти цифр, и алгоритм Хэда (опублико-
ванный в 1980 г
.) представляет собой более тонкий путь выполнения умно-
жения без представления чисел, больших, чем 2m. Формально мы уже вы-
полнили его, так как в данном случае число 2m заменено на 4m, так что не
стоит беспокоиться. Для повышенной точности это даёт возможность уве-
ренно оперировать с числами, такими как 10
18
. Алгоритм Хэда может быть
включён в виде подпрограммы в степенной алгоритм.
Нам нужно умножить х и у по модулю m, где мы принимаем 0 ≤ х ≤ m,
0 ≤ y ≤ m. Метод проходит несколько стадий, и мы исключим некоторые де-
тали, проверяемые в качестве упражнений.
13.1. Лемма. Пусть m ≥ 2, T =
1
2
m
⎡
⎤
+
⎢
⎥
⎣
⎦
, t = T
2
– m. Тогда –T ≤ t ≤ T и
T
2
≤ 2m.
13.2. Лемма. Пусть x = aT + b, где 0 ≤ b < T. Тогда 0 ≤ а ≤ Т. Пусть
y = c T + d, где 0 ≤ d < T. Тогда 0 ≤ с ≤ Т.
13.3. Лемма. а) определим z ≡ ad + bc (mod m), где 0 ≤ z < m. Тогда
ad ≤ m, bc ≤ m и ху ≡ act + zT + bd (mod m).
б) пусть ac = eT + f, где 0 ≤ f < T. Тогда 0 ≤ е ≤ Т и
xy ≡ (et + z)T + ft + bd (mod m).
в) пусть v ≡ z + et (mod m), 0 ≤ v ≤ m. Пусть
v = gT + h, где 0 ≤ h < T.
Тогда 0 ≤ g ≤ T и xy ≡ hT + (f + g)t + bd (mod m).
Вам, конечно, хотелось бы проверить результирующую программу на
примерах, вышеприведенных для обычного степенного алгоритма. Хоро-
шим тестом для вычислений с большими числами было бы взять a = 2 и
m = некоторому большому простому числу, n = m – 1.
Вычет по теореме
Ферма будет равен 1. Представим целый набор больших простых чисел:
10
9
+ 7, 10
10
+ 19, 10
11
+ 3, 10
12
+ 39, 10
13
+ 37, 10
14
+ 31, 10
15
+ 37.
Страницы
- « первая
- ‹ предыдущая
- …
- 51
- 52
- 53
- 54
- 55
- …
- следующая ›
- последняя »
