Метод умножения Шёнхаге — Штрассена
Материал из Модулярная арифметики
(Различия между версиями)
Turbo (обсуждение | вклад) (Новая страница: «[http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm Основные подробности] === Пример === Положим задано…») |
Turbo (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
=== Пример === | === Пример === | ||
Положим задано два числа: X и Y, каждое длиной 512 бит. Требуется найти значение RES = (X*Y) mod 2<sup>N</sup>+1 | Положим задано два числа: X и Y, каждое длиной 512 бит. Требуется найти значение RES = (X*Y) mod 2<sup>N</sup>+1 | ||
| − | + | * Этап 1. Основные параметры алгоритма: | |
| − | + | ** len1 = 512 | |
| − | + | ** len2 = 512 | |
| + | ** N = 1024 | ||
| + | ** 2<sup>k</sup> ~ sqrt(N) = 32, k = 5 | ||
| + | ** n >= 2*N/2<sup>k</sup>+k = (2048/32)+5 = 69. Поскольку n должно делиться на 2<sup>k</sup>, то можно выбрать n = 128. | ||
| + | * Этап 2 (возникает на умножении DFT(X)*DFT(Y) mod 2<sup>128</sup>+1): | ||
| + | ** len1 = 129 | ||
| + | ** len2 = 129 | ||
| + | ** N = 128 | ||
| + | ** 2<sup>k</sup> ~ (sqrt(N) = 11.3). Выберем k = 4. | ||
| + | ** n >= 2*N/2<sup>k</sup>+k = (256/16)+4 = 20. Поскольку n должно делиться на 2<sup>k</sup>, то можно выбрать n = 32. | ||
| + | * Этап 3 (возникает на умножении DFT(X)*DFT(Y) mod 2<sup>32</sup>+1): | ||
| + | ** len1 = 33 | ||
| + | ** len2 = 33 | ||
| + | это умножение можно делать аппаратно, не углубляюсь в рекурсию. | ||
Версия 17:27, 24 июля 2013
Пример
Положим задано два числа: X и Y, каждое длиной 512 бит. Требуется найти значение RES = (X*Y) mod 2N+1
- Этап 1. Основные параметры алгоритма:
- len1 = 512
- len2 = 512
- N = 1024
- 2k ~ sqrt(N) = 32, k = 5
- n >= 2*N/2k+k = (2048/32)+5 = 69. Поскольку n должно делиться на 2k, то можно выбрать n = 128.
- Этап 2 (возникает на умножении DFT(X)*DFT(Y) mod 2128+1):
- len1 = 129
- len2 = 129
- N = 128
- 2k ~ (sqrt(N) = 11.3). Выберем k = 4.
- n >= 2*N/2k+k = (256/16)+4 = 20. Поскольку n должно делиться на 2k, то можно выбрать n = 32.
- Этап 3 (возникает на умножении DFT(X)*DFT(Y) mod 232+1):
- len1 = 33
- len2 = 33
это умножение можно делать аппаратно, не углубляюсь в рекурсию.
