Computing a Lattice Basis Revisited

Autor: Phong Q. Nguyen, Jianwei Li
Přispěvatelé: Centre for Quantum Technologies [Singapore] (CQT), National University of Singapore (NUS), Key Laboratory of Mathematics Mechanization (KLMM), Chinese Academy of Sciences [Changchun Branch] (CAS)-Institute of Systems Science (ISS), China-Academy of Mathematics and Systems Science [Beijing], Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Japanese French Laboratory for Informatics (JFLI), National Institute of Informatics (NII)-The University of Tokyo (UTokyo)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Zdroj: ISSAC '19: International Symposium on Symbolic and Algebraic Computation
ISSAC '19: International Symposium on Symbolic and Algebraic Computation, Jul 2019, Beijing, China. pp.275-282, ⟨10.1145/3326229.3326265⟩
ISSAC
DOI: 10.1145/3326229.3326265⟩
Popis: Given (a,b) \in \mZ^2, Euclid's algorithm outputs the generator \gcd(a,b) of the ideal a\mZ + b\mZ. Computing a lattice basis is a high-dimensional generalization: given \mathbfa _1,\dots,\veca _n \in \mZ^m, find a \mZ-basis of the lattice L=\ \sum_i=1 ^n x_i \veca _i, x_i \in \mZ\ generated by the \veca _i's. The fastest algorithms known are HNF algorithms, but are not adapted to all applications, such as when the output should not be much longer than the input. We present an algorithm which extracts such a short basis within the same time as an HNF, by reduction to HNF. We also present an HNF-less algorithm, which reduces to Euclid's extended algorithm and can be generalized to quadratic forms. Both algorithms can extend primitive sets into bases.
Databáze: OpenAIRE
Externí odkaz: