Bakalářská práce

LLL and quadratic forms

Viktorie Blahová
Anotace

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 …více

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 …více

Zadání práce
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.
Práce zkontrolována:
9. 5. 2024 14:58, Mgr. Marek Sýs, Ph.D., učo 232886
Jazyk práce
angličtina angličtina
Termín obhajoby
25. 6. 2024
Práce byla úspěšně obhájena

Vedoucí

Mgr. Marek Sýs, Ph.D., učo 232886
KPSK FI MU

Oponent

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

Masarykova univerzita Přírodovědecká fakulta
Studijní program
Plán
Obecná matematika

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

  • 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.