Matroids Matheplanet Forum Index
Moderiert von Fabi Dune ligning
Lineare Algebra » Vektorräume » LLL-Algorithmus für Basisvektoren eines Gitters
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule LLL-Algorithmus für Basisvektoren eines Gitters
Pter87
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.11.2018
Mitteilungen: 338
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-03-08


Ich beschäftige mich zurzeit mit dem LLL Algorithmus für Gitter und weiß nicht weshalb man diesen Algorithmus überhaupt nutzt. Auf dem englischen Wikipedia steht:

"the LLL algorithm calculates an LLL-reduced (short, nearly orthogonal) lattice basis"

Wieso möchte man eine "kurze, fast orthogonale" Basis für das Gitter haben ? Eine Orthogonalbasis kriegt man über das Gram-Schmidt Verfahren aber wieso sollen die Vektoren dann auch noch möglichst kurz sein ?

Wikipedia schreibt "nearly orthogonal". Bedeutet das, dass der LLL Algorithmus grundsätzlich keine Orthogonalbasis liefert oder kann das durchaus passieren ?

Man könnte doch auch einfach das Gram-Schmidt-Verfahren nutzen und die Vektoren im Nachhinein "kürzen" oder dauert das zu lange(laufzeittechnisch), verglichen mit dem LLL Algorithmus ?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3153
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-03-08


2021-03-08 01:45 - Pter87 im Themenstart schreibt:
Wieso möchte man eine "kurze, fast orthogonale" Basis für das Gitter haben?
Eine Orthogonalbasis kriegt man über das Gram-Schmidt Verfahren aber wieso sollen die Vektoren dann auch noch möglichst kurz sein?
Grob gesagt möchte man Gleichungssysteme in ganzen Zahlen lösen, denke ich. Wenn wir kurze Gitterbasen finden, so können wir die Lösungen in den ganzen Zahlen besser charakterisieren.


Wikipedia schreibt "nearly orthogonal". Bedeutet das, dass der LLL Algorithmus grundsätzlich keine Orthogonalbasis liefert oder kann das durchaus passieren?
.Doch, das kann schon passieren, aber häufig haben die Gitter ja gar keine orthogonalen Basen.


Man könnte doch auch einfach das Gram-Schmidt-Verfahren nutzen und die Vektoren im Nachhinein "kürzen" oder dauert das zu lange(laufzeittechnisch), verglichen mit dem LLL Algorithmus ?
Ich weiß nicht genau, was du vorhast, aber so etwas ähnliches macht ja der LLL-Algorithmus. Beachte, dass nicht jede Auswahl von $n$ linear unabhängigen oder gar orthogonalen Gittervektoren eine Gitterbasis bildet. Zum Beispiel $L=\begin{bmatrix} 1 & 1/2\\ 0 & 1\end{bmatrix}\mathbb Z^2$ enthält orthogonale Vektoren aber keine orthogonale Basis.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1377
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2021-03-08


Um das Shortest Vector Problem (SVP) und das Closest Vector Problem (CVP) adäquat lösen zu können, benötigt man kurze Gitterbasen. Beide Probleme besitzen Anwendungen in der Kryptographie.

Das GS-Verfahren liefert auch keine Orthogonalbasis für das Gitter, sondern für den übergeordneten Vektorraum. Das Gitter selbst hat nicht zwingend eine Orthogonalbasis.

Eine mit dem LLL-Verfahren verkürzte Basis ist 'annähernd' orthogonal, weil sich zwei Vektoren mit sehr spitzen/stumpfen Winkeln i.d.R. durch Addition/Subtraktion verkürzen lassen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6777
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-03-08


Das Gram-Schmidt-Verfahren spielt sich ja in einem Vektorraum ab. Aber der liegt hier gar nicht vor, sondern es ist ein Gitter.

In \(\IZ^2\) etwa \(\{xa+yb|x,y\in\IZ\}\), wobei \(a,b\in\IZ^2\) vorgegeben sind.

Möglichst kurze (orthogonale) Vektoren wären hier \(\binom10,\binom01\). Aber es ist i. A. nicht \(\{xa+yb|x,y\in\IZ\}=\{x\binom10+y\binom01|x,y\in\IZ\}\), auch dann nicht, wenn a und b linear unabhängig sind.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Pter87
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.11.2018
Mitteilungen: 338
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2021-03-08


Ja, hab mir gerade noch etwas mehr Gedanken darüber gemacht und gemerkt, dass das mit Gram-Schmidt nicht unbedingt geht.

Sei $L$ ein Gitter mit Basis $a,b \in \mathbb{R}^2$. Wäre in dem Fall das SVP-Problem das Problem $p_1,p_2 \in \mathbb{Z}$ zu finden, sodass $||v|| = ||p_1\cdot a + p_2\cdot b|| \leq ||c_1\cdot a + c_2\cdot b||,\; \forall c_1,c_2 \in \mathbb{Z}$ ?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3153
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2021-03-08


2021-03-08 17:53 - Pter87 in Beitrag No. 4 schreibt:
Sei $L$ ein Gitter mit Basis $a,b \in \mathbb{R}^2$. Wäre in dem Fall das SVP-Problem das Problem $(p_1,p_2)\in\mathbb{Z}^2\setminus\{(0,0)\}$ zu finden, sodass $\|v\| = \|p_1\cdot a + p_2\cdot b\| \leq \|c_1\cdot a + c_2\cdot b\|,\; \forall (c_1,c_2) \in \mathbb{Z}^2\setminus\{(0,0)\}$ ?
Ja :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Pter87 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]