Метод умножения Шёнхаге — Штрассена — различия между версиями

Материал из Модулярная арифметики
Перейти к: навигация, поиск
(Новая страница: «[http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm Основные подробности] === Пример === Положим задано…»)
 
Строка 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.
+
* Этап 1. Основные параметры алгоритма:  
−
# Этап 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.
+
** len1 = 512
−
# Этап 3 (возникает на умножении DFT(X)*DFT(Y) mod 2<sup>32</sup>+1): это умножение можно делать аппаратно, не углубляюсь в рекурсию.
+
** 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
 +
это умножение можно делать аппаратно, не углубляюсь в рекурсию.

Версия 14: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

это умножение можно делать аппаратно, не углубляюсь в рекурсию.

Источник — «https://vscripts.ru/w/index.php?title=Метод_умножения_Шёнхаге_—_Штрассена&oldid=534»