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

Положим задано два числа: X и Y, каждое длиной 512 бит. Требуется найти значение RES = (X*Y) mod 2^N+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 (возникает на умножении 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 (возникает на умножении DFT(X)*DFT(Y) mod 2³²+1):
- len1 = 33
- len2 = 33

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

Навигация