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

Версия 05:50, 29 июля 2013

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

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

@@ Строка 21: / Строка 21: @@
 === Описание ===
-[http://gmplib.org/manual/FFT-Multiplication.html#FFT-Multiplication Документация GMP LIB]
+* [http://gmplib.org/manual/FFT-Multiplication.html#FFT-Multiplication Документация GMP LIB]
+* [http://hal.archives-ouvertes.fr/docs/00/12/64/62/PDF/fft.pdf Статья A GMP-BASED IMPLEMENTATION OF SCHONHAGE-STRASSEN’S LARGE INTEGER MULTIPLICATION ALGORITHM]
+* [http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm Описание в английской Wikipedia]
 === Исходники ===
 [http://www.ginac.de/CLN/cln.git/?p=cln.git;a=blob;f=src/base/digitseq/cl_DS_mul_fftm.h;h=a984802ce039e8179a26fda2681a2e133dba6fbd;hb=refs/heads/master CLN - Class Library for Numbers]