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

Основные подробности

Пример

Положим задано два числа: X и Y, каждое длиной 512 бит. Требуется найти значение RES = (X*Y) mod 2^N+1

1. Этап 1: len1 = 512, len2 = 512, N = 1024, 2^k ~ sqrt(N) = 32, k = 5, n >= 2*N/2^k+k = (2048/32)+5 = 69. Поскольку n должно делиться на 2^k, то можно выбрать n = 128.
2. Этап 2 (возникает на умножении DFT(X)*DFT(Y) mod 2¹²⁸+1): len1 = 129, len2 = 129, N = 128, 2^k ~ (sqrt(N) = 11.3). Выберем k = 4. n >= 2*N/2^k+k = (256/16)+4 = 20. Поскольку n должно делиться на 2^k, то можно выбрать n = 32.
3. Этап 3 (возникает на умножении DFT(X)*DFT(Y) mod 2³²+1): это умножение можно делать аппаратно, не углубляюсь в рекурсию.