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

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

Пример

Положим задано два числа: 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

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

Описание

• Документация GMP LIB
• Статья A GMP-BASED IMPLEMENTATION OF SCHONHAGE-STRASSEN’S LARGE INTEGER MULTIPLICATION ALGORITHM
• Описание в английской Wikipedia

Исходники

CLN - Class Library for Numbers