liblat 関数レファレンスページ

基底簡約関係関数

宣言 void setMaxLoop(const long max_loop);
概略 BKZやDeepBKZのツアー回数の上限を設定する
引数
max_loop ツアー回数の上限
戻り値 なし
解説 BKZやDeepBKZのツアー回数の上限を設定する関数です. BKZアルゴリズムやDeepBKZアルゴリズムなどは停止性が保証されていないので,確実に停止させるにはツアー回数の上限を設定してあげる必要があります.

サンプル

なし




宣言 void deepInsertion(const long k, const long l);
概略 deep-insertionを行う
引数
k 基底を挿入するインデックス
l 引き抜く基底のインデックス
戻り値 なし
解説 基底にdeep-insertionを施す関数です. 具体的には基底{,bk,,b,}{,bk1,b,bk,,b1,b+1,}に変換します.

サンプル

なし




宣言 void dualDeepInsertion(const long k, const long l);
概略 双対型deep-insertionを行う
引数
k 引き抜く基底のインデックス
l 基底を挿入するインデックス
戻り値 なし
解説 基底に双対型deep-insertionを施す関数です. 具体的には基底{,bk,,b,}{,bk1,bk+1,,b,bk,b+1,}に変換します.

サンプル

なし




宣言 void updateDeepInsGSO(const long i, const long k, const long start, const long end);
概略 deep-insertionを施した後のGSO情報の効率的な更新
引数
i 引き抜く基底のインデックス
k 基底を挿入するインデックス
start deep-insertionを格子基底の一部に施す際,その開始インデックス
end deep-insertionを格子基底の一部に施す際,その終了インデックス
戻り値 なし
解説 基底にdeep-insertionを施した後のGSO情報の更新を効率的に行う関数です. computeGSO関数を用いてGSO情報を更新することも可能ですが,効率的ではない上に誤差が出やすいのでこの関数を用いて更新することを強くおすすめします.

サンプル

reduction.cppdeepLLL関数を参照のこと.




宣言 void updateDualDeepInsGSO(const long k, const long l, const std::vector dual_D);
概略 双対型deep-insertionを施した後のGSO情報の効率的な更新
引数
i 引き抜く基底のインデックス
k 基底を挿入するインデックス
start deep-insertionを格子基底の一部に施す際,その開始インデックス
end deep-insertionを格子基底の一部に施す際,その終了インデックス
dual_D
戻り値 なし
解説 基底に双対型deep-insertionを施した後のGSO情報の更新を効率的に行う関数です. computeGSO関数を用いてGSO情報を更新することも可能ですが,効率的ではない上に誤差が出やすいのでこの関数を用いて更新することを強くおすすめします.

サンプル

reduction.cppdualDeepLLL関数を参照のこと.




宣言 void sizeReduce(const bool compute_gso = true);
概略 サイズ基底簡約
Y. Aono and M. Yasuda. 格子暗号解読のための数学的基礎.(2019)
引数
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
戻り値 なし
解説 格子基底{b1,,bn}をサイズ基底簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 80次正方行列を基底行列に持つ格子
    Lattice<int> lat(80, 80);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(80, 80, 1000, 9999);
            
    // サイズ基底簡約
    lat.sizeReduce();

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void LLL(const double delta = 0.75, const bool compute_gso = true, const long start_ = 0, const long end_ = -1);
概略 LLL基底簡約
A. K. Lenstra, H. W. Lenstra and L. Lovasz. Factoring polynomials with rational coefficients.(1982)
引数
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
start_ LLL簡約を基底の一部分にのみ行う場合,その開始インデックス
end_ LLL簡約を基底の一部分にのみ行う場合,その終了インデックス
戻り値 なし
解説 格子基底{b1,,bn}に対して,その部分格子基底{bstart_+1,,bend_}を簡約パラメータdeltaに関してLLL簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 40次正方行列を基底行列に持つ格子
    Lattice<int> lat(40, 40);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(40, 40, 1000, 9999);
            
    // LLL基底簡約
    lat.LLL(0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void L2(const double delta = 0.75, const double eta = 0.51);
概略 L2アルゴリズムを用いたLLL基底簡約
P. Q. Nguyen and D. Stehle. Floating-point LLL revisited.(2005)
P. Q. Nguyen and D. Stehle. An LLL algorithm with quadratic complexity.(2009)
引数
delta LLLの簡約パラメータ(0.25以上1以下)
eta サイズ基底簡約の簡約パラメータ(0.5以上eta以下)
戻り値 なし
解説 格子基底{b1,,bn}を簡約パラメータdeltaとetaに関してL2アルゴリズムを用いてLLL簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 40次正方行列を基底行列に持つ格子
    Lattice<int> lat(40, 40);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(40, 40, 1000, 9999);
            
    // LLL基底簡約
    lat.L2(0.99, 0.51);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void deepLLL(const double delta = 0.75, const bool compute_gso = true, const long start_ = 0, const long end_ = -1);
概略 DeepLLL基底簡約
C. P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problem.(1994)
引数
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
start_ DeepLLL簡約を基底の一部分にのみ行う場合,その開始インデックス
end_ DeepLLL簡約を基底の一部分にのみ行う場合,その終了インデックス
戻り値 なし
解説 格子基底{b1,,bn}に対して,その部分格子基底{bstart_+1,,bend_}を簡約パラメータdeltaに関してDeepLLL簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 40次正方行列を基底行列に持つ格子
    Lattice<int> lat(40, 40);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(40, 40, 1000, 9999);
            
    // DeepLLL基底簡約
    lat.deepLLL(0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void potLLL(const double delta = 0.75, const bool compute_gso = true);
概略 PotLLL基底簡約
F. Fontein, M. Schneider and U. Wagner. PotLLL: A polynomial time version of LLL with deep insertions.(2014)
引数
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
戻り値 なし
解説 格子基底{b1,,bn}を簡約パラメータdeltaに関してPotLLL簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 40次正方行列を基底行列に持つ格子
    Lattice<int> lat(40, 40);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(40, 40, 1000, 9999);
            
    // PotLLL基底簡約
    lat.potLLL(0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void BKZ(const long beta, const double delta = 0.75, const bool compute_gso = true);
概略 BKZ基底簡約
C. P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problem.(1994)
引数
beta ブロックサイズ(2以上格子次元以下)
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
戻り値 なし
解説 格子基底{b1,,bn}をブロックサイズbetaと簡約パラメータdeltaに関してBKZ簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 80次正方行列を基底行列に持つ格子
    Lattice<int> lat(80, 80);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(80, 80, 1000, 9999);
            
    // BKZ基底簡約
    lat.BKZ(40, 0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void HKZ(const double delta = 0.75, const bool compute_gso = true);
概略 HKZ基底簡約
A. Korkine and G. Zolotareff. Sur les formes quadratiques positives ternaires.(1872)
A. Korkine and G. Zolotareff. Sur les formes quadratiques.(1873)
C. P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problem.(1994)
引数
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
戻り値 なし
解説 格子基底{b1,,bn}を簡約パラメータdeltaに関してHKZ簡約する関数です.
具体的には,格子基底を格子次元と同じ大きさのブロックサイズに関してBKZ基底簡約します.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 80次正方行列を基底行列に持つ格子
    Lattice<int> lat(80, 80);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(80, 80, 1000, 9999);
            
    // HKZ基底簡約
    lat.HKZ(0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void deepBKZ(const long beta, const double delta = 0.75, const bool compute_gso = true);
概略 DeepBKZ基底簡約
J. Yamaguchi and M. Yasuda. Explicit formula for Gram-Schmidt vectors in LLL with deep insertions and its applications.(2017)
引数
beta ブロックサイズ(2以上格子次元以下)
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
戻り値 なし
解説 格子基底{b1,,bn}をブロックサイズbetaと簡約パラメータdeltaに関してDeepBKZ簡約する関数です.
具体的には,BKZアルゴリズムのサブルーチンとして使っているLLLの代わりにDeepLLLを使用することによって実現しています.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 80次正方行列を基底行列に持つ格子
    Lattice<int> lat(80, 80);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(80, 80, 1000, 9999);
            
    // DeepBKZ基底簡約
    lat.deepBKZ(40, 0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void potBKZ(const long beta, const double delta = 0.75, const bool compute_gso = true);
概略 PotBKZ基底簡約
A. Sato and M. Yasuda. 自己双対型PotBKZ基底簡約の提案とBKZとの比較.(2025)
引数
beta ブロックサイズ(2以上格子次元以下)
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
戻り値 なし
解説 格子基底{b1,,bn}をブロックサイズbetaと簡約パラメータdeltaに関してPotBKZ簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 80次正方行列を基底行列に持つ格子
    Lattice<int> lat(80, 80);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(80, 80, 1000, 9999);
            
    // PotBKZ基底簡約
    lat.potBKZ(40, 0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void dualDeepLLL(const double delta = 0.75, const bool compute_gso = true);
概略 双対型DeepLLL基底簡約
M. Yasuda, J. Yamaguchi, M. Ooka and S. Nakamura. Development of a dual version of DeepBKZ and its application to solving the LWE challenge.(2018)
引数
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
戻り値 なし
解説 格子基底{b1,,bn}を簡約パラメータdeltaに関して双対型DeepLLL簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 80次正方行列を基底行列に持つ格子
    Lattice<int> lat(80, 80);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(80, 80, 1000, 9999);
            
    // 双対型DeepLLL基底簡約
    lat.dualDeepLLL(0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void dualPotLLL(const double delta = 0.75, const bool compute_gso = true);
概略 双対型PotLLL基底簡約
A. Sato and M. Yasuda. 自己双対型PotBKZ基底簡約の提案とBKZとの比較.(2025)
引数
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
戻り値 なし
解説 格子基底{b1,,bn}を簡約パラメータdeltaに関して双対型PotLLL簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 80次正方行列を基底行列に持つ格子
    Lattice<int> lat(80, 80);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(80, 80, 1000, 9999);
            
    // 双対型PotLLL基底簡約
    lat.dualPotLLL(0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void dualBKZ(const long beta, const double delta = 0.75, const bool compute_gso = true);
概略 双対型BKZ基底簡約
D. Micciancio and M. Walter. Practical, predictable lattice basis reduction.(2016)
引数
beta ブロックサイズ(2以上格子次元以下)
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
戻り値 なし
解説 格子基底{b1,,bn}をブロックサイズbetaと簡約パラメータdeltaに関して双対型BKZ簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
        
int main()
{
    // 80次正方行列を基底行列に持つ格子
    Lattice<int> lat(80, 80);
        
    // ランダムなSVP型格子に設定
    lat.setRandom(80, 80, 1000, 9999);
            
    // 双対型BKZ基底簡約
    lat.dualBKZ(40, 0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
        
    return 0;
}



宣言 void dualDeepBKZ(const long beta, const double delta = 0.75, const bool compute_gso = true);
概略 双対型DeepBKZ基底簡約
D. Micciancio and M. Walter. Practical, predictable lattice basis reduction.(2016)
引数
beta ブロックサイズ(2以上格子次元以下)
delta 簡約パラメータ(0.75以上1以下)
compute_gso 簡約する前にGSO情報を更新するか.
事前にGSO情報を計算していない場合はtrueにする必要がある
戻り値 なし
解説 格子基底{b1,,bn}をブロックサイズbetaと簡約パラメータdeltaに関して双対型BKZ簡約する関数です.

サンプル

#include <iostream>
#include "lattice.h"
    
int main()
{
    // 80次正方行列を基底行列に持つ格子
    Lattice<int> lat(80, 80);
    
    // ランダムなSVP型格子に設定
    lat.setRandom(80, 80, 1000, 9999);
        
    // 双対型DeepBKZ基底簡約
    lat.dualDeepBKZ(40, 0.99);

    // 基底行列の表示
    std::cout << lat << std::endl;
    
    return 0;
}



宣言 std::vector Lattice::ENUM(double R);
概略 格子上の最短ベクトルの数え上げ
N. Gama and P. Q. Nguyen and O. Regev(2010)
引数
R 探索半径
戻り値 なし
解説 探索半径R>0以下の格子ベクトルを数え上げ,格子L上の最短ベクトルを求めますぅ.ただし,R>0以下の格子ベクトルが存在しないときは零ベクトルを返します.
なお,``ENUM``が返すのは,正確には格子ベクトルではなく,格子ベクトルの係数ベクトルであり,格子ベクトルを知りたい場合はmulVecBasis関数を使う必要があります.

サンプル

#include <iostream>
#include "lattice.h"
    
int main()
{
    // 80次正方行列を基底行列に持つ格子
    Lattice<int> lat(80, 80);
    
    // ランダムなSVP型格子に設定
    lat.setRandom(80, 80, 1000, 9999);
    
    // GSOを計算
    lat.computeGSO();

    // 最短ベクトルの係数ベクトル
    std::vector v = lat.ENUM(100);

    // 最短ベクトルの表示
    std::cout << lat.mulVecBasis(v) << std::endl;
    
    return 0;
}



戻る