Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2 |
| |
| Authors: | Prof Dr Arnold Schönhage |
| |
| Affiliation: | (1) Mathematisches Institut der Universität Tübingen, Auf der Morgenstelle 10, D-7400 Tübingen, Bundesrepublik Deutschland |
| |
| Abstract: | Summary Polynomial multiplication of degree N can be accomplished in time O (N · log N) provided the scalar field contains suitable roots of unity. Otherwise at least O (N · log N · log log N) is obtained by a modified version of the Schönhage-Strassen multiplication which employs computations modulo 1 + xn (where N = 2n), if the field contains 2–1, or modulo 1 + xn + x2N, if 3–1 exists. The latter method covering all fields of characteristic 2 is presented here in detail. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
