PGMLLL: 新しい多項式時間で停止するLLL with deep-insertionsの提案

準備

記号の準備

本記事で使用する記号は以下の表に従います．

格子

Gram-Schmidtの直交化法

B1やB2の線形代数学で習うようなGram-Schmidtの直交化法そのものです．

体積

LLL

LLL簡約基底を求めるアルゴリズムは，多項式時間で停止することが知られています．

DeepLLL(LLL with deep-insertion)

DeepLLL簡約はLLL簡約の自然な一般化であり，以下の様に定義されます．

しかし，DeepLLL基底を求めるアルゴリズムはLLLアルゴリズムとは異なり停止性は証明されておらず，潜在的にはsuper-exponentialな計算量をもつとされています(Gama and Nguyen, 2008)．
また，deep-insertion後の基底のGram-Schmidtの直交化ベクトルについては次の定理が成立します．

既存の多項式時間で停止するLLL with deep-insertions

PotLLL

PotLLLはFontein, Schneider and Wagner, 2014で初めて提案されたLLL with deep-insertionsの変種で，格子基底のpotentialと呼ばれる量(定義 6)がLovász条件を満たさない2つの隣接する基底ベクトル$(\boldsymbol{b}_{k-1},\boldsymbol{b}_k)$を交換した際に単調減少することに着目し，基底のpotentialが単調に減少するdeep-insertionのみを施すことにより多項式時間で停止する様に完了したものです．

また，PotLLL簡約基底とは以下のような基底を言います．

S$\!{}^2$LLL

S$\!{}^2$LLLはYasuda and Yamaguchi, 2019によって提案された多項式時間で停止するLLL with deep-insertionの変種で，PotLLLはpotentialを減少させていましたが，S$\!{}^2$LLLは格子基底のGram-Schmditの直交化ベクトルの二乗和と呼ばれる量がLovász条件を満たさない2つの隣接する基底ベクトル$(\boldsymbol{b}_{k-1},\boldsymbol{b}_k)$を交換した際に単調減少することに着目し，基底のGram-Schmditの直交化ベクトルの二乗和が単調に減少するdeep-insertionのみを施すことにより多項式時間で停止する様に改良したものです．

新しく提案する簡約PGMLLL

Gram-Schmidt幾何平均の積

今回新しくLLL with deep-insertionの変種を提案するに当たって，新しい格子基底に対して定まる量を定義しました．具体的には，以下で定義されるものです．

Gram-Schmidt幾何平均の積の性質

この，格子基底のGram-Schmidt幾何平均の積は，次の性質を持っています．

PGMLLL

このGram-Schmidt幾何平均の積とその性質（主に命題2）を利用してPGMLLL簡約基底を次のように定義します．

PGMLLLアルゴリズム

Algorithm 1に命題3，並びにその系を利用したPGMLLL簡約基底アルゴリズムを示す．

$$ \begin{array}{l} & \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Algorithm~1}~\text{PGMLLL}(\delta): \text{簡約パラメタ}\delta\text{に関するPGMLLL基底簡約アルゴリズム}\\ & \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Input}:~n\text{次元格子の基底}\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}\\ & \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Output}:~\delta\text{に関するPGMLLL簡約基底}\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}\\ 1 & (B_i)_{1\le i\le n}, (\mu_{i, j})_{1\le i, j\le n}\gets \texttt{gram\_schmidt}()\\ 2 & k\gets 1\\ 3 & \textbf{while}~k\le n~\textbf{do}\\ 4 & \quad \textbf{for}~j=k-1~\text{downto}~1~\textbf{do}\\ 5 & \quad\quad \texttt{size\_reduce}(k, j)\\ 6 & \quad P\gets 1;~P_{\min}\gets 1\\ 7 & \quad i\gets 1\\ 8 & \quad \textbf{for}~j=k-1~\text{downto}~1~\textbf{do}\\ 9 & \quad\quad P\gets P\cdot \left(\frac{B_k+\sum_{\ell=j}^{k-1}\mu_{k, \ell}^2B_\ell}{B_j}\right)^\frac{1}{j}\\ 10 & \quad\quad \textbf{if}~P< P_{\min}~\textbf{then}\\ 11 & \quad\quad\quad i\gets j\\ 12 & \quad\quad\quad P_{\min}\gets P\\ 13 & \quad \textbf{if}~\delta^{\frac{1}{i}} > P_{\min}~\textbf{then}\\ 14 & \quad\quad \{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}\gets \sigma_{i, k}(\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\})\\ 15 & \quad\quad \text{Gram-Schmidtの直交化情報の更新}\\ 16 & \quad\quad k\gets i\\ 17 & \quad \textbf{else}\\ 18 & \quad\quad k\gets k+1 \end{array} $$

但し，$\texttt{gram\_schmidt}()$は基底のGram-Schmidtの直交化ベクトルの二乗ノルムとGram-Schmidtの直交化係数行列（この$2$つをまとめてGram-Schmidtの直交化情報と呼ぶことにする）を計算する関数，$\texttt{size\_reduce}(k, j)$はサイズ基底簡約アルゴリズム，$\texttt{updata\_gso\_deep\_insertion}(i, k)$はdeep-insertion$\sigma_{i, k}$を施した後のGram-Schmidtの直交化情報の更新アルゴリズムで，それぞれ以下のアルゴリズムの様になる．

$$ \begin{array}{l} & \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Algorithm~2}~\text{gram\_schmidt}(): \text{Gram-Schmidtの直交化情報を求める}\\ & \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Input}:~n\text{次元格子の基底}\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}\\ & \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Output}:~\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}\text{のGram-Schmidt情報}(B_i)_i,~(\mu_{i, j})_{i, j}\\ 1 & B\gets \boldsymbol{0}_n\\ 2 & \mu \gets \boldsymbol{E}_n\\ 3 & \boldsymbol{b}_1^\star\gets \boldsymbol{0}_n;~\cdots;~\boldsymbol{b}_n^\star\gets \boldsymbol{0}_n\\ 4 & \textbf{for}~i=1~\text{to}~n~\textbf{do}\\ 5 & \quad \boldsymbol{b}_i^\star\gets \boldsymbol{b}_i\\ 6 & \quad \textbf{for}~j=1~\text{to}~i-1~\textbf{do}\\ 7 & \quad\quad \mu_{i, j}\gets \frac{\langle\boldsymbol{b}_i, \boldsymbol{b}_j^\star\rangle}{B_j}\\ 8 & \quad\quad \boldsymbol{b}_i^\star\gets \boldsymbol{b}_i^\star-\mu_{i, j}\boldsymbol{b}_j^\star\\ 9 & \quad B_i\gets \norm{\boldsymbol{b}_i^\star}^2\\ 10 & \textbf{return}~B, \mu \end{array} $$

PGMLLLの計算量

まず，PGMLLLにおける$3$行目から始まる$\textbf{while}$文の呼び出し回数について次がわかります．

PGMLLLの実装 and 実験

今回は$\texttt{SageMath}$ではなく，$\texttt{C++}$で$\texttt{NTL}$ライブラリを用いて実装しました．実際のコードは
$\texttt{https://github.com/satoshin-des/PGMLLL}$
を見ていただくか，本記事の末尾をご覧ください．

PGMの挙動

まず，80次元における SVP Challenge のseed0の基底に関してPGMの挙動をプロットしました．それが以下の図たちです．

$80$次元における$\log \mathrm{PGM}$の挙動
$100$次元における$\log \mathrm{PGM}$の挙動

RHFの比較

まず，格子基底のRHFとは次のように定義されるものです．

SVP Challenge のseed0，$40$次元～$150$次元までの基底に関して簡約パラメタ$\delta=0.99$でのLLL，PGMLLL，そしてブロックサイズ$\beta=10, 15$でのBKZを施し，RHFをプロットしました．ただし，LLLは$\texttt{SageMath}$の$\texttt{LLL}$関数をBKZは$\texttt{NTL}$ライブラリの$\texttt{BKZ\_FP}$関数を利用しました．

RHFの比較

図4から，少なくとも150次元程度まででは，ブロックサイズ$\beta=10$のBKZと同じ品質であり，ブロックサイズ$\beta=15$のBKZとほぼ同程度の品質を維持することがわかります．

実際のコード

      #include "PGMLLL.h"

#include <vector>
#include <cmath>

#include <NTL/mat_ZZ.h>
#include <NTL/LLL.h>

void PgmLLL::pgmLLL(const double delta)
{
    FLOAT sum;
    FLOAT P, Pmin;

    this->gramSchmidt();

    for (long k = 0, j, i, l; k < this->nrows;)
    {
        for (j = k - 1; j > -1; --j)
        {
            this->sizeReduce(k, j);
        }

        P = Pmin = 1;
        i = 0;
        for (j = k - 1; j > -1; --j)
        {
            sum = this->m_B[k];
            for (l = j; l < k; ++l)
            {
                sum += this->m_mu[k][l] * this->m_mu[k][l] * this->m_B[l];
            }
            P *= std::pow(sum / this->m_B[j], 1.0 / (j + 1));
            if (P < Pmin)
            {
                i = j;
                Pmin = P;
            }
        }

        if (std::pow(delta, 1.0 / (i + 1)) > Pmin)
        {
            this->deepInsertion(i, k);
            this->updateGSODeepInsertion(i, k);
            k = i;
        }
        else
        {
            ++k;
        }
    }
}
    

      void PgmLLL::sizeReduce(const long i, const long j)
{
    if ((this->m_mu[i][j] > 0.5) || (this->m_mu[i][j] < -0.5))
    {
        const FLOAT q = std::roundl(this->m_mu[i][j]);
        this->basis[i] -= NTL::to_ZZ(static_cast<double>(q)) * this->basis[j];
        for (long l = 0; l <= j; ++l)
        {
            this->m_mu[i][l] -= q * this->m_mu[j][l];
        }
    }
}

void PgmLLL::deepInsertion(const long i, const long k)
{
    const NTL::vec_ZZ t = this->basis[k];
    for (long j = k; j > i; --j)
    {
        this->basis[j] = this->basis[j - 1];
    }
    this->basis[i] = t;
}

void PgmLLL::updateGSODeepInsertion(const long i, const long k)
{
    long j, l;
    FLOAT t, eps;
    std::vector<FLOAT> P(this->nrows), D(this->nrows), S(this->nrows);

    P[k] = D[k] = this->m_B[k];
    for (j = k - 1; j >= i; --j)
    {
        P[j] = this->m_mu[k][j] * this->m_B[j];
        D[j] = D[j + 1] + this->m_mu[k][j] * P[j];
    }

    for (j = k; j > i; --j)
    {
        t = this->m_mu[k][j - 1] / D[j];
        for (l = this->nrows - 1; l > k; --l)
        {
            S[l] += this->m_mu[l][j] * P[j];
            this->m_mu[l][j] = this->m_mu[l][j - 1] - t * S[l];
        }
        for (l = k; l > j; --l)
        {
            S[l] += this->m_mu[l - 1][j] * P[j];
            this->m_mu[l][j] = this->m_mu[l - 1][j - 1] - t * S[l];
        }
    }

    t = 1 / D[i];

    for (l = this->nrows - 1; l > k; --l)
    {
        this->m_mu[l][i] = t * (S[l] + this->m_mu[l][i] * P[i]);
    }
    for (l = k; l > i + 1; --l)
    {
        this->m_mu[l][i] = t * (S[l] + this->m_mu[l - 1][i] * P[i]);
    }

    this->m_mu[i + 1][i] = t * P[i];
    for (j = 0; j < i; ++j)
    {
        eps = this->m_mu[k][j];
        for (l = k; l > i; --l)
        {
            this->m_mu[l][j] = this->m_mu[l - 1][j];
        }
        this->m_mu[i][j] = eps;
    }

    for (j = k; j > i; --j)
    {
        this->m_B[j] = D[j] * this->m_B[j - 1] / D[j - 1];
    }
    this->m_B[i] = D[i];
}