Bachelor's thesis

LLL and quadratic forms

Viktorie Blahová
Abstract

Tato práce řeší problém nejkratšího vektoru mřížky hledáním minima kvadratických forem. Analyzujeme případy, kdy samotné minimum kvadratické formy nestačilo k najití nejkratšího vektoru. Dále analyzujeme Semaeův exaktní algoritmus pro dimenzi 3 a navrhujeme jeho modifikované rozšíření na libovolnou dimenzi. Jednu iteraci této modifikace pak ve zkrácené verzi aplikujeme na vstupní bázi LLL algoritmu …more

Abstract

This thesis is solving the shortest lattice vector problem by finding the minimum of quadratic forms. We analyse cases where the minimum of the quadratic form alone is not sufficient to find the shortest vector. We also analyse Semaev's exact algorithm for dimension 3 and propose a modified extension for an arbitrary dimension. We then apply a single iteration of this modification to the input basis …more

Thesis description
Well-known LLL algorithm can be viewed as greedy algorithm for solving shortest vector problem. The algorithm can be changed so it will work with Gram matrix (of dot products) of basis vectors b_i. Norm of each lattice vector can be expressed as quadratic form with Gram matrix as its associated matrix. For fixed non-zero x_j, it is easy to find analytically shortest vector v_min,j = (x_1, ..., x_k)*(b_1, ..., b_k)^T. It suffices to minimize quadratic form (x_1, ..., x_k)*G(x_1, ..., x_k). Unfortunately, resulted vector v_min is not (in general) part of the lattice. On the other hand this v_min should be close to some small vector of the lattice. The goal of the thesis is to analyze quadratic forms defined by Gram matrix and propose alternative approach to LLL algorithm that will be based on quadratic forms. Student will: 1. generate many random lattices, find exact SVP using enumeration or sieving, and find corresponding coefficients SV = (X_1, ..., X_k)*(b_1, ..., b_k)^T. 2. analyze distances between v_min, j (for x_j = X_j) and SV. 3. based on statistics or information gained from 3. propose alternative approach or tweak of the LLL algorithm that will use quadratic forms.
The thesis has been checked:
9/5/2024 14:58, Mgr. Marek Sýs, Ph.D., UČO 232886
Language used
English English
Defence date
25/6/2024
The thesis was defended successfully

Supervisor

Mgr. Marek Sýs, Ph.D., UČO 232886
KPSK FI MU

Reader

Mgr. Jan Jurka, Ph.D.
ÚMS Ústavy PřF MU

Masaryk University Faculty of Science
Programme
Plan
Mathematics

Theses on a related topic

List of theses with an identical keyword.

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.
  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.
  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.
  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.
  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.