宣言 | void setMaxLoop(const long max_loop); | |||
---|---|---|---|---|
概略 | BKZやDeepBKZのツアー回数の上限を設定する | |||
引数 |
|
|||
戻り値 | なし | |||
解説 | BKZやDeepBKZのツアー回数の上限を設定する関数です. BKZアルゴリズムやDeepBKZアルゴリズムなどは停止性が保証されていないので,確実に停止させるにはツアー回数の上限を設定してあげる必要があります. |
なし
宣言 | void deepInsertion(const long k, const long l); | ||||||
---|---|---|---|---|---|---|---|
概略 | deep-insertionを行う | ||||||
引数 |
|
||||||
戻り値 | なし | ||||||
解説 |
基底にdeep-insertionを施す関数です.
具体的には基底 |
なし
宣言 | void dualDeepInsertion(const long k, const long l); | ||||||
---|---|---|---|---|---|---|---|
概略 | 双対型deep-insertionを行う | ||||||
引数 |
|
||||||
戻り値 | なし | ||||||
解説 |
基底に双対型deep-insertionを施す関数です.
具体的には基底 |
なし
宣言 | void updateDeepInsGSO(const long i, const long k, const long start, const long end); | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
概略 | deep-insertionを施した後のGSO情報の効率的な更新 | ||||||||||||
引数 |
|
||||||||||||
戻り値 | なし | ||||||||||||
解説 | 基底にdeep-insertionを施した後のGSO情報の更新を効率的に行う関数です. computeGSO関数を用いてGSO情報を更新することも可能ですが,効率的ではない上に誤差が出やすいのでこの関数を用いて更新することを強くおすすめします. |
reduction.cppのdeepLLL
関数を参照のこと.
宣言 | void updateDualDeepInsGSO(const long k, const long l, const std::vector |
|||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
概略 | 双対型deep-insertionを施した後のGSO情報の効率的な更新 | |||||||||||||||
引数 |
|
|||||||||||||||
戻り値 | なし | |||||||||||||||
解説 | 基底に双対型deep-insertionを施した後のGSO情報の更新を効率的に行う関数です. computeGSO関数を用いてGSO情報を更新することも可能ですが,効率的ではない上に誤差が出やすいのでこの関数を用いて更新することを強くおすすめします. |
reduction.cppのdualDeepLLL
関数を参照のこと.
宣言 | void sizeReduce(const bool compute_gso = true); | |||
---|---|---|---|---|
概略 |
サイズ基底簡約
Y. Aono and M. Yasuda. 格子暗号解読のための数学的基礎.(2019) |
|||
引数 |
|
|||
戻り値 | なし | |||
解説 |
格子基底 |
#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) |
||||||||||||
引数 |
|
||||||||||||
戻り値 | なし | ||||||||||||
解説 |
格子基底 |
#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) |
||||||
引数 |
|
||||||
戻り値 | なし | ||||||
解説 |
格子基底 |
#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) |
||||||||||||
引数 |
|
||||||||||||
戻り値 | なし | ||||||||||||
解説 |
格子基底 |
#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) |
||||||
引数 |
|
||||||
戻り値 | なし | ||||||
解説 |
格子基底 |
#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) |
|||||||||
引数 |
|
|||||||||
戻り値 | なし | |||||||||
解説 |
格子基底 |
#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) |
||||||
引数 |
|
||||||
戻り値 | なし | ||||||
解説 |
格子基底 具体的には,格子基底を格子次元と同じ大きさのブロックサイズに関して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) |
|||||||||
引数 |
|
|||||||||
戻り値 | なし | |||||||||
解説 |
格子基底 具体的には,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) |
|||||||||
引数 |
|
|||||||||
戻り値 | なし | |||||||||
解説 |
格子基底 |
#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) |
||||||
引数 |
|
||||||
戻り値 | なし | ||||||
解説 |
格子基底 |
#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) |
||||||
引数 |
|
||||||
戻り値 | なし | ||||||
解説 |
格子基底 |
#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 と簡約パラメータ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 と簡約パラメータ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 |
|||
---|---|---|---|---|
概略 |
格子上の最短ベクトルの数え上げ
N. Gama and P. Q. Nguyen and O. Regev(2010) |
|||
引数 |
|
|||
戻り値 | なし | |||
解説 |
探索半径 なお,``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;
}