Lattice basis reduction in function fields
The author generalizes an algorithm of \textit{A. K. Lenstra} [J. Comput. Syst. Sci. 30, 235-248 (1985; Zbl 0577.12013)] for a basis reduction of lattices of polynomials. Here a lattice is a \(K[x]\) submodule of \(K[x]^n\) for a field \(K\). The author gives an algorithm that starting with a generating set for the lattice computes a reduced basis for the lattice. An important feature of the reduced bases is that they are build of the minima of the lattice. In particular, the first vector of a reduced basis will always be a shortest vector. The author gives a complexity analysis (in terms of field operations) for his algorithm, showing it to be of polynomial runtime (quite similar to the algebraic complexity of the LLL-algorithm [\textit{A. K. Lenstra, H. W. Lenstra jun.} and \textit{L. Lovasz}, Math. Ann. 261, 515-534 (1982; Zbl 0488.12001)]. As an application the author suggests to apply the reduction technique to the arithmetic in ideal (divisor) class groups, namely to the problem of ideal (divisor) reduction. For the entire collection see [Zbl 0891.00022].
- On lattice reduction for polynomial matrices
- Computing Riemann-Roch spaces in algebraic function fields and related topics.
- Computing explicit isomorphisms with full matrix algebras over \(\mathbb {F}_q(x)\)
- Lattice basis reduction for indefinite forms and an application
- Fast reduction of algebraic lattices over cyclotomic fields
- Efficient hash maps to \(\mathbb{G}_2\) on BLS curves
- Explicit formula for optimal ate pairing over cyclotomic family of elliptic curves
- A note on short vectors in lattices from function fields
- scientific article; zbMATH DE number 1643950 (Why is no real title available?)
- A generalization of reduced Arakelov divisors of a number field
- Reducing number field defining polynomials: an application to class group computations
- Fast lattice reduction for F₂-linear pseudorandom number generators
- On reduced Arakelov divisors of real quadratic fields
- On LLL lattice basis reduction over imaginary quadratic fields by introducing reduction parameters
- Pairing Lattices
- scientific article; zbMATH DE number 5532109 (Why is no real title available?)
- A polynomial reduction algorithm
- On integral basis reduction in global function fields
- scientific article; zbMATH DE number 1944706 (Why is no real title available?)
- On computing quaternion quotient graphs for function fields
- The arithmetic of Jacobian groups of superelliptic cubics
- Short bases of lattices over number fields
- Computing a lattice basis revisited
- A generalization of LLL lattice basis reduction over imaginary quadratic fields
- Rankin’s Constant and Blockwise Lattice Reduction
- Reduced ideals from the reduction algorithm
- An efficient lattice reduction method for \(\mathbf F_2\)-linear pseudorandom number generators using Mulders and Storjohann algorithm
- Calculation of Minkowski-reduced lattice bases
- Reduction of an algebraic function field modulo a prime in the constant field
- An application of lattice basis reduction to polynomial identities for algebraic structures
This page was built for publication: Lattice basis reduction in function fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3840198)
