Fast multiplication of large numbers (Q2548172): Difference between revisions

In dieser Arbeit werden unter der Verwendung der schnellen Fouriertransformation FFT [vgl. \textit{J. W. Cooley} and \textit{J. W. Tukey}, Math. Comput. 19, 297--301 (1965; Zbl 0127.09002)] zwei Algorithmen zur Multiplikation \(N\)-stelliger Dualzahlen gegeben, die sowohl als Turingmaschinen wie auch als logische Netze so realisiert werden können, dass ihr Aufwand durch \(O(N\log N (\log \log N)^{1+\varepsilon})\) bzw. \(O(N\log N \log \log N)\) abgeschätzt werden kann. Beim ersten Verfahren wird die FFT wie üblich im Körper \(\mathbb C\) benutzt, beim zweiten in den Restklassenringen \(\mathbb Z_{F_n}\) nach den Fermatzahlen \(F_n=2^{2^n}+1\). Darin ist nämlich \(2\) eine \(2^{n+1}\)-te primitive Einheitswurzel, deren Potenzreste extrem einfache Dualdarstellungen besitzen. (German original) English translation: In this article using the fast Fourier transform FFT [see \textit{J. W. Cooley} and \textit{J. W. Tukey}, Math. Comput. 19, 297--301 (1965; Zbl 0127.09002)] two algorithms for the multiplication of \(N\)-digit binary numbers are given that can be realized as Turing machines as well as logical nets such that their steps can be estimated by \(O(N\log N (\log \log N)^{1+\varepsilon})\) resp. \(O(N\log N \log \log N)\). In the first method FFT is used as usual in the field \(\mathbb C\), whereas in the second one it is used in the residue class rings \(\mathbb Z_{F_n}\) of the Fermat numbers \(F_n=2^{2^n}+1\). Therein \(2\) is a \(2^{n+1}\)st primitive unit root the power residues of which possess extremely simple representations.