A lower bound for the multiplication of polynomials modulo a polynomial (Q1197994): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the algorithmic complexity of associative algebras / rank
 
Normal rank
Property / cites work
 
Property / cites work: Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. I: The algebra \(G[u]/<Q(u)^{\ell}>\), \(\ell >1\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3776615 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Number of Multiplications Required for Matrix Multiplication / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algebraic complexities and algebraic curves over finite fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4162484 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The computational complexity of a set of quadratic functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Multiplicative complexity of polynomial multiplication over finite fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the complexity of multiplication in finite fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: A new approach to error-correcting codes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Gaussian elimination is not optimal / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3946078 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On multiplication of 2 \(\times\) 2 matrices / rank
 
Normal rank

Latest revision as of 14:34, 16 May 2024

scientific article
Language Label Description Also known as
English
A lower bound for the multiplication of polynomials modulo a polynomial
scientific article

    Statements

    A lower bound for the multiplication of polynomials modulo a polynomial (English)
    0 references
    0 references
    16 January 1993
    0 references
    In 1983 \textit{A. Lempel}, \textit{G. Seroussi} and \textit{S. Winograd} [Theor. Comput. Sci. 22, 285-296 (1983; Zbl 0498.68027)] proved the lower bound \((2+1/(q-1))n-o(n)\) for the multiplicative complexity of the multiplication of two polynomials of degree \(n-1\) modulo an irreducible polynomial \(p\) of degree \(n\) over a finite field \(F\) with \(q\) elements. using a combination of the coding method and the substitution method the author generalizes this result to any kind of polynomials.
    0 references
    computational complexity
    0 references
    quadratic algorithms
    0 references
    linear codes
    0 references
    multiplicative complexity
    0 references
    multiplication of two polynomials
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references