Am văzut că se poate folosi uneori $B=HNF(G)$, dar s-ar putea să nu funcționeze întotdeauna pentru a obține o bază proastă și, prin urmare, nu este explicit (și nici foarte clar pentru mine...).
Lăsa $\mu : \mathbb{R}^{n\times n}\la \mathbb{R}_{\geq 0}$ fi o măsură a calității unei baze.
De exemplu, s-ar putea avea $\mu(B) = \lVert LLL(B)_1\rVert$ fi norma primei coordonate a reducerii LLL a $B$ (după cum sugerați), dar există multe alte măsuri de calitate posibile.
Scopul utilizării HNF nu este că duce la o bază care este „cea mai proastă” în mod abstract (pentru majoritatea măsurilor de calitate, înmulțirea cu o matrice unimodulară aleatorie de normă ridicată de operator ar duce probabil la o bază de calitate foarte scăzută), dar că este cel mai rău pe care orice adversar îl va folosi în mod plauzibil.
Acest lucru se datorează următorului rezultat simplu.
Lăsa $\mu$ să fie eficient calculabil.
Lăsa $A$ fi un adversar eficient care, la intrare $B$, calculează unele $U$ astfel încât $\mu(BU) \leq f(B)$ pentru o funcție de mărginire $f$. Apoi, există un adversar eficient $A'$ care calculează $U$ astfel încât $\mu(BU) \leq \min(f(B), f(HNF(B))$.
În special, $HNF(B)$ este un invariant al lui zăbrele, și nu baza particulară utilizată.
Prin urmare, rezultatul de mai sus spune că cea mai proastă bază de calitate pe care o poate găsi un adversar este cel mult $f(HNF(B))$, deci acordarea adversarului o bază non-HNF poate duce doar la calculul a mai bine baza de calitate decât ar avea-o cu o bază HNF.
Adversarul $A'$ este ușor de descris.
Pur și simplu rulează $A$ pe $B$ și $HNF(B)$, și returnează baza care (dintre acestea două) minimizează măsura calității.
Acest lucru necesită ca măsura calității să fie eficient calculată, dar în majoritatea cazurilor acest lucru este adevărat.
Editați | ×: Ca răspuns la clarificarea dvs. din comentarii, vă voi indica un răspuns parțial, care este „în principiu da, dar nu am o matrice explicită la îndemână”.
Următoarele sunt din capitolul 3 din teza lui Seungki Kim.
Teorema 3.4 Lăsa $n$ să fie suficient de mare, $p\în (0.100)$, și să presupunem $k < \frac{n}{6(\log n + K(p))}$ este un întreg pozitiv, unde $K(p)$ este o constantă care depinde numai de $p$. Atunci cel putin $p\%$ de $n$-dimensională $(1, 1/2)$-Bazele LLL au
$$\forall 1\leq i \leq n-1 : \frac{k-1}{k}\frac{1}{2}\leq |\mu_{i+1,i}|\leq \frac{ 1}{2}.$$
Aici „majoritatea” necesită îngrijire tehnică pentru a fi corect (a se vedea teza lui Kim pentru detalii).
Kim continuă cum să discute acest rezultat este contraintuitiv, în sensul că implică că pentru „majoritatea bazelor LLL $B$", $\lVert LLL(B)_1\rVert \aprox (4/3)^{n/4}\aprox (1,0745)^n$, cel mai rău caz legat pentru LLL.
Dar asta este de asemenea se știe că, pentru majoritatea distribuțiilor pe baze de rețea $B$, $\lVert LLL(B)_1\rVert \aproximativ 1,02^n$ --- ce dă?
Pretenția este că $LLL$ este cumva părtinitoare, în sensul că o face nu transportă distribuțiile menționate mai sus peste bazele rețelei la distribuția uniformă peste bazele LLL.
Prin urmare, pentru a găsi baze LLL proaste, are sens să eșantionăm (direct) matricele care satisfac condiția LLL (mai degrabă decât să încercați să utilizați LLL pentru a calcula bazele experimental).
Nu m-am gândit dacă modalitatea naturală de a face acest lucru (un vector la un moment dat, uniform la întâmplare dintr-un set adecvat, condiționat de păstrarea condiției LLL) va da rezultatul dorit.
Poate exista o modalitate mai inteligentă de a eșantiona uniform o bază LLL (care, după rezultatul lui Kim, este probabil o bază proastă).
Dar, în lumina tezei lui Kim, este un lucru rezonabil să încerci.
Merită menționat că rezultatul lui Kim este (cel puțin) un rezultat al existenței.
În mod plauzibil, motivul pentru care LLL se comportă bine în medie este că limita din cel mai rău caz este liberă.
Lucrările lui Kim arată însă că acest lucru nu este adevărat.
