Просмотр исходного текста страницы Метод умножения Шёнхаге — Штрассена

[http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm Основные подробности]

=== Пример ===
Положим задано два числа: 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): это умножение можно делать аппаратно, не углубляюсь в рекурсию.