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)^>, >1
Let K be a field and let \(r=\sum^{n-1}_{i=0}x_ iu^ i\in K[x_ 0,...,x_{n-1},u]\) and \(s=\sum^{n-1}_{i=0}y_ iu^ i\in K[y_ 0,...,y_{n-1},u]\) be polynomials with indeterminate coefficients. Let h be a polynomial of degree n in K[u]. This paper investigates algorithms for computing \(rs\quad mod h\in K[x_ 1,...,x_{n-1},y_ 1,...,y_{n- 1},u].\) A bilinear algorithm is an algorithm that uses apart from computations in K only multiplications of the form \((\sum^{n- 1}_{i=0}u_ ix_ i)(\sum^{n-1}_{i=0}t_ iy_ i)\). A minimal bilinear algorithm for a given computation uses the least number of such multiplications. In this paper the minimal bilinear algorithms for computing rs mod h in the case that \(h=q^{\ell}\) is given, where q is a monic irreducible polynomial over K and \(\ell >1\). Moreover, they assume that \(\deg (q)>1\). They find that the minimal algorithms all use 2n-1 multiplications of the given form. In all these algorithms one of the following facts is used: \[ rs=rs\quad mod\prod^{2n-2}_{i=0}(u-\alpha_ i)\quad, \] or \[ rs=(rs\quad mod\prod^{2n-2}_{i=1}(u-\beta_ i))+x_{n-1}y_{n- 1}(u-\beta_ i)\quad, \] for certain \(\alpha_ i\) or \(\beta_ i\) in K. These computations are done by using the fact that rs mod (u- \(\alpha)=r(\alpha)s(\alpha).\) The cases that \(\ell =1\) or that h is the product of two relatively prime polynomials is treated before. The case that \(\ell >1\) and \(\deg (q)=1\) will be treated in a forthcomming paper.
- Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. II: The algebra \(G[u]/\langle{} u^ n \rangle\)
- scientific article; zbMATH DE number 1222346
- scientific article; zbMATH DE number 4037188
- Multiplicative complexity of polynomial multiplication over finite fields
- Multiplication of Polynomials over Finite Fields
- Algebras Having Linear Multiplicative Complexities
- Certain systems of bilinear forms whose minimal algorithms are all quadratic
- scientific article; zbMATH DE number 4037188 (Why is no real title available?)
- scientific article; zbMATH DE number 3688713 (Why is no real title available?)
- scientific article; zbMATH DE number 3322464 (Why is no real title available?)
- On Computing the Discrete Fourier Transform
- On multiplication in algebraic extension fields
- On systems of bilinear forms whose minimal division-free algorithms are all bilinear
- On the multiplicative complexity of the discrete Fourier transform
- On the number of multiplications necessary to compute certain functions
- On varieties of optimal algorithms for the computation of bilinear mappings. I. The isotropy group of a bilinear mapping
- On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for \(2\times 2\)-matrix multiplication
- On varieties of optimal algorithms for the computation of bilinear mappings. III. Optimal algorithms for the computation of xy and yx where x,y M₂(K)
- Some bilinear forms whose multiplicative complexity depends on the field of constants
- An efficient algorithm for product computations on computer
- Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. II: The algebra \(G[u]/\langle{} u^ n \rangle\)
- A lower bound for the multiplication of polynomials modulo a polynomial
- On the direct sum conjecture in the straight line model
- Multiplicative complexity of direct sums of quadratic systems
- scientific article; zbMATH DE number 4037188 (Why is no real title available?)
This page was built for publication: 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\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1110328)
