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

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

=== Описание ===
* [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]