Я видел, что иногда можно использовать $B=HNF(G)$, но не всегда может получиться плохая основа, и поэтому она не является явной (и не очень ясной для меня...).
Позволять $\mu : \mathbb{R}^{n\times n}\to \mathbb{R}_{\geq 0}$ быть мерой качества основы.
Например, можно было бы $\mu(B) = \lVert LLL(B)_1\rVert$ – норма первой координаты LLL-редукции $В$ (как вы предлагаете), но есть много других возможных мер качества.
Смысл использования ГНФ не в том, что он приводит к абстрактно «худшему» базису (для большинства показателей качества умножение на случайную унимодулярную матрицу с высокой операторной нормой, вероятно, приведет к очень низкокачественному базису), а что это худшее что любой противник будет правдоподобно использовать.
Это происходит из-за следующего простого результата.
Позволять $\му$ быть эффективно вычислимым.
Позволять $А$ быть эффективным противником, который на входе $В$, вычисляет некоторые $U$ такой, что $\mu(BU)\leq f(B)$ для некоторой ограничивающей функции $f$. Тогда существует эффективный противник $А'$ который вычисляет $U$ такой, что $\mu(BU) \leq \min(f(B), f(HNF(B))$.
Примечательно, $ХНФ(Б)$ является инвариантом решетка, а не конкретное используемое основание.
Таким образом, приведенный выше результат говорит о том, что наихудший базис качества, который может найти противник, не более чем $f(HNF(B))$, поэтому предоставление противнику базы, отличной от HNF, может привести только к тому, что он вычислит лучше качественную основу, чем они могли бы иметь с основой HNF.
Противник $А'$ легко описать.
Он просто работает $А$ на $В$ и $ХНФ(Б)$и возвращает базис, который (из этих двух) минимизирует меру качества.
Это требует, чтобы мера качества была эффективно вычисляемой, но в большинстве случаев это верно.
Редактировать: В ответ на ваше уточнение в комментариях укажу вам на частичный ответ, который "в принципе да, но у меня нет под рукой явной матрицы".
Нижеследующее из главы 3 Диссертация Сынки Кима.
Теорема 3.4 Позволять $n$ быть достаточно большим, $p\in (0,100)$, и предположим $k < \frac{n}{6(\log n + K(p))}$ является положительным целым числом, где $К(р)$ является константой, зависящей только от $р$. Тогда по крайней мере $р\%$ из $n$-размерный $(1, 1/2)$-LLL базы имеют
$$\forall 1\leq i \leq n-1 : \frac{k-1}{k}\frac{1}{2}\leq |\mu_{i+1,i}|\leq \frac{ 1}{2}.$$
Здесь «большинство» требует технической осторожности, чтобы все получилось правильно (подробности см. в тезисе Кима).
Ким продолжает обсуждать, что этот результат противоречит здравому смыслу в том смысле, что он подразумевает, что для «большинства баз LLL $В$", $\lVert LLL(B)_1\rVert \приблизительно (4/3)^{n/4}\приблизительно (1,0745)^n$, оценка наихудшего случая для LLL.
Но это также известно, что для большинства распределений по основаниям решетки $В$, $\lVert LLL(B)_1\rVert \приблизительно 1,02^n$ --- что дает?
Претензия в том, что $LLL$ как-то пристрастный, в том смысле, что это делает нет перевести упомянутые выше распределения по основаниям решетки в равномерное распределение по основаниям LLL.
Следовательно, чтобы найти плохие базы LLL, имеет смысл (непосредственно) выбирать матрицы, которые удовлетворяют условию LLL (вместо того, чтобы пытаться использовать LLL для экспериментального вычисления баз).
Я не думал, что естественный способ сделать это (по одному вектору за раз, равномерно случайным образом из подходящего набора, при условии сохранения условия LLL) даст желаемый результат.
Возможно, существует более разумный способ равномерной выборки базы LLL (которая, согласно результату Кима, вероятно, является плохой базой).
Но, в свете тезиса Кима, попытаться сделать это разумно.
Стоит отметить, что результат Кима является (как минимум) результатом существования.
Вероятно, причина того, что LLL в среднем ведет себя хорошо, заключается в том, что граница для наихудшего случая является слабой.
Однако работа Ким показывает, что это не так.
