Skip to main content
SpringerLink
Log in

On fast multiplication of polynomials over arbitrary algebras

  • Published:
Acta Informatica Aims and scope Submit manuscript

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

References

  1. Aho, A., Hopcroft, J., Ullman, J.: The design and analysis of computer algorithms. Reading, MA: Addison-Wesley 1974

    Google Scholar 

  2. Apostol, T.M.: Resultants of cyclotomic polynomials. Proc. Am. Math. Soc.24, 457–462 (1970)

    Google Scholar 

  3. Cantor, D.G.: On arithmetical algorithms over finite fields. J. Combinat. Theory A50, 285–300 (1989)

    Google Scholar 

  4. Chudnovsky, D.V., Chudnovsky, G.V.: Algebraic complexities and algebraic curves over finite fields. J. Complexity4, 285–316 (1988)

    Google Scholar 

  5. Grigoriev, D.Yu.: Multiplicative complexity of a pair of bilinear forms and of the polynomial multiplication. Proc. 7th MFCS. (Lect. Notes Comput. Sci., vol. 64, pp. 250–256) Berlin, Heidelberg, New York: Springer 1978

    Google Scholar 

  6. Kaltofen, E.: Greatest common divisors of polynomials given by straight-line programs. J. ACM35, 231–264 (1988)

    Google Scholar 

  7. Kaminski, M.: An algorithm for polynomial multiplication that does not depend on the ring of constants. J. Algorithms9, 137–147 (1988)

    Google Scholar 

  8. Knuth, D.E.: The art of computer programming, vol. 2. 2nd edn. Reading, MA: Addison-Wesley 1981

    Google Scholar 

  9. Lang, S.: Algebraic number theory. Reading, MA: Addison-Wesley 1970

    Google Scholar 

  10. Lempel, A., Seroussi, G., Winograd, S.: On the complexity of multiplication in finite fields. Theoret. Comput. Sci.22, 285–296 (1983)

    Google Scholar 

  11. Nussbaumer, H.J.: Fast polynomial transform algorithms for digital convolutions. IEEE Trans. ASSP28, 205–215 (1980)

    Google Scholar 

  12. Schönhage, A.: Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Inf.7, 395–398 (1977)

    Google Scholar 

  13. Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing7, 281–292 (1971)

    Google Scholar 

  14. Winograd, S.: Arithmetic complexity of computations. CBMS-NSF Regional Conference Series in Applied Math. 33. Philadelphia, PA: SIAM 1980

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of California, 90024-1555, Los Angeles, CA, USA

    David G. Cantor

  2. Department of Computer Science, Rensselaer Polytechnic Institute, 12180-3590, Troy, NY, USA

    Erich Kaltofen

Authors
  1. David G. Cantor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Erich Kaltofen
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The authors would like to acknowledge the partial support of NSA Grant MDA-904-II-2031 and NSF Grant Nr. CCR-87-05363

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cantor, D.G., Kaltofen, E. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica 28, 693–701 (1991). https://doi.org/10.1007/BF01178683

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01178683

Keywords

Search

Navigation