C++で格子アルゴリズムを扱えるライブラリを作ってみた

はじめに

「$\texttt{liblat}$」という，$\texttt{C++}$用の格子アルゴリズムライブラリを開発しました．是非，本記事を読んで興味を持たれた方がいらっしゃいましたら以下からDLして使用してみてください．

liblatを使うメリット（特徴）

• 整数格子でない格子も扱うことができる
• 多数の基底簡約アルゴリズムを手軽に利用できる(LLL, DeepLLL, BKZ, DeepBKZ, PotLLL, etc.)
• 格子や格子基底の不変量を手軽に求めることができる

$\texttt{liblat}$では，$\texttt{C++}$でこれらの機能をより簡単に利用することができます．

liblatの弱点（デメリット）

• 多倍長には対応していません（ライブラリやSageMathは多倍長ですので，SVP-challengeの格子をそのまま代入するには$\texttt{SageMath}$などをおすすめします）
• BKZ系のアルゴリズムがやや不安定です（$\texttt{NTL}$などでは，Modified LLLが実装されているのに対して，$\texttt{liblat}$ではModified LLLを提供していません．そのため，BKZやDeepBKZなどが不安定になることがあります．）

インストール方法

GitHubのREADMEの方にも書いてありますが，こちらの方にも書いておきます．

まず，レポジトリをクローンして，liblatにcdします．

コマンド

$ git clone https://github.com/satoshin-des/liblat.git
$ cd liblat

出力

Cloning into 'liblat'...
remote: Enumerating objects: 401, done.
remote: Counting objects: 100% (401/401), done.
remote: Compressing objects: 100% (211/211), done.
remote: Total 401 (delta 235), reused 337 (delta 171), pack-reused 0 (from 0)
Receiving objects: 100% (401/401), 3.41 MiB | 5.90 MiB/s, done.
Resolving deltas: 100% (235/235), done.

続いて，cmakeします．

liblat$ mkdir build
liblat$ cd build
liblat/build$ cmake ..
liblat/build$ make

出力例

# cmake ..
-- The C compiler identification is GNU 11.4.0
-- The CXX compiler identification is GNU 11.4.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done (4.0s)
-- Generating done (0.0s)
-- Build files have been written to: /hoge/liblat/build

# make
[  4%] Building CXX object CMakeFiles/lat.dir/src/bkz.cpp.o
[  9%] Building CXX object CMakeFiles/lat.dir/src/core.cpp.o
[ 14%] Building CXX object CMakeFiles/lat.dir/src/deep_bkz.cpp.o
[ 19%] Building CXX object CMakeFiles/lat.dir/src/deep_lll.cpp.o
[ 23%] Building CXX object CMakeFiles/lat.dir/src/dual_bkz.cpp.o
[ 28%] Building CXX object CMakeFiles/lat.dir/src/dual_deep_bkz.cpp.o
[ 33%] Building CXX object CMakeFiles/lat.dir/src/dual_deep_lll.cpp.o
[ 38%] Building CXX object CMakeFiles/lat.dir/src/dual_enum.cpp.o
[ 42%] Building CXX object CMakeFiles/lat.dir/src/dual_lll.cpp.o
[ 47%] Building CXX object CMakeFiles/lat.dir/src/dual_pot_lll.cpp.o
[ 52%] Building CXX object CMakeFiles/lat.dir/src/enum.cpp.o
[ 57%] Building CXX object CMakeFiles/lat.dir/src/hkz.cpp.o
[ 61%] Building CXX object CMakeFiles/lat.dir/src/lattice.cpp.o
[ 66%] Building CXX object CMakeFiles/lat.dir/src/lll.cpp.o
[ 71%] Building CXX object CMakeFiles/lat.dir/src/pot_bkz.cpp.o
[ 76%] Building CXX object CMakeFiles/lat.dir/src/pot_enum.cpp.o
[ 80%] Building CXX object CMakeFiles/lat.dir/src/pot_lll.cpp.o
[ 85%] Building CXX object CMakeFiles/lat.dir/src/size.cpp.o
[ 90%] Linking CXX shared library hoge/liblat/lib/liblat.so
[ 90%] Built target lat
[ 95%] Building CXX object CMakeFiles/test_exec.dir/test.cpp.o
[100%] Linking CXX executable test_exec
[100%] Built target test_exec

test.cppにテストコードが入っていますので（自分で書き換えていただいても問題ございません），そちらをコンパイル＆実行する際は以下のようにしてください．

liblat/build$ ctest

出力例

Test project hoge/liblat/build
    Start 1: RunTestExec
1/1 Test #1: RunTestExec ......................   Passed    0.01 sec

100% tests passed, 0 tests failed out of 1

Total Test time (real) =   0.02 sec

使い方

$\texttt{liblat}$で使用できる関数たちのレファレンスサイトがありますので，ここでは，宣言や初期化など，基本的な使い方のみ説明します．

宣言の仕方

$\texttt{liblat}$では，以下の様に格子を宣言します．

sample.cpp

#include <iostream>

#include "lattice.h"

int main()
{
    Lattice<int> lat(10, 10); // 10次元の完全階数格子

    return 0;
}

この例ではint型の$10$次元の完全階数の整数格子を宣言してますが，同様にLattice<double>でdouble型の整数格子とは限らない格子も宣言できます．

ただ，これだけでは，単に10次元の完全階数格子を用意しただけで，なにも入っていません．
実際，何もせずにcoutすると，10行10列の零行列が出力されます．

sample.cpp

#include <iostream>

#include "lattice.h"

int main()
{
    Lattice<int> lat(10, 10); // 10次元の完全階数格子

    std::cout << lat << std::endl;

    return 0;
}

出力

$ ./test_exec
[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]

そこで，setRandom関数を使ってランダムな格子を入れてみましょう．

sample.cpp

#include <iostream>

#include "lattice.h"

int main()
{
    Lattice<int> lat(10, 10); // 10次元の完全階数格子

    lat.setRandom(10, 10, 1000, 10000); // 10次元のランダムな完全階数格子（下界が1000，上界が10000）

    std::cout << lat << std::endl;

    return 0;
}

これを実行すると以下の様になります．

出力

$ ./test_exec
[
[4049, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[4812, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[6243, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[1719, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[5283, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[1462, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[2179, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[5838, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[1034, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[5948, 0, 0, 0, 0, 0, 0, 0, 0, 1]
]

今後実装したいこと

本ライブラリはまだまだ発展途上です．
特に（近似）最近ベクトル問題のアルゴリズムなどについてはほとんど実装できていない状況です（最短ベクトル問題に帰着して解くこともできます cf. Kannanのアルゴリズム）．
これから，より便利でより使いやすいライブラリを目指して改良を続けて行きます．