Satins, lattices, and extended Euclid's algorithm
| Autor: | Josep M. Brunat, Joan-C. Lario |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. TN - Grup de Recerca en Teoria de Nombres |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Basis (linear algebra)
Applied Mathematics General Engineering Lattice theory Symmetric satins Reticles Teoria de Algorismes Shortest vector Extended Euclid’s algorithm Square (algebra) Matemàtiques i estadística::Àlgebra::Ordres reticles estructures algebraiques ordenades [Àrees temàtiques de la UPC] Null vector Satins Algorithm Square satins Lagrange–Gauss lattice basis reduction Optimal basis Algorithms Mathematics |
| Zdroj: | UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| Popis: | Motivated by the design of satins with draft of period m and step a, we draw our attention to the lattices $$L(m,a)=\langle (1,a),(0,m)\rangle$$ L ( m , a ) = ⟨ ( 1 , a ) , ( 0 , m ) ⟩ where $$1\le a 1 ≤ a < m are integers with $$\gcd (m,a)=1$$ gcd ( m , a ) = 1 . We show that the extended Euclid's algorithm applied to m and a produces a shortest no null vector of L(m, a) and that the algorithm can be used to find an optimal basis of L(m, a). We also analyze square and symmetric satins. For square satins, the extended Euclid's algorithm produces directly the two vectors of an optimal basis. It is known that symmetric satins have either a rectangular or a rombal basis; rectangular basis are optimal, but rombal basis are not always optimal. In both cases, we give the optimal basis directly in terms of m and a. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|