Lattice reduction and other lattice tools in Julia
LLLplus provides lattice tools such as Lenstra-Lenstra-Lovász (LLL)
lattice reduction which are of practical and theoretical use in
cryptography, digital communication, integer programming, and more.
This package is experimental and not a robust tool; use at your own
risk :-)
LLLplus has functions for LLL,
Seysen, and
Hermite-Korkine-Zolotarev
lattice reduction
techniques. Brun
integer relations is included in the form of lattice
reduction. A solver for the closest
vector
problem is also included; for more see the help text for the lll,seysen, hkz, brun, and cvp functions. Several toy (demo)
functions are also included; see the subsetsum, minimalpolynomial,integerfeasibility, rationalapprox, and spigotBBP functions.
Each function contains documentation and examples available via Julia’s
built-in documentation system (try ?lll or @doc(lll)). Documentation
for all functions is available. A tutorial notebook is
found in the docs directory or on
nbviewer.
Here are a few examples of using the functions in the
package on random lattices.julia
Pkg.add("LLLplus")
using LLLplus
# do lattice reduction on a matrix with randn entries
N = 40;
H = randn(N,N);
Bbrun,_ = brun(H);
Blll,_ = lll(H);
Bseysen,_ = seysen(H);
Bhkz,_ = hkz(H);
# check out the CVP solver
Q,Rtmp=qr(H); R = UpperTriangular(Rtmp);
u=Int.(rand(0:1e10,N));
y=H*u+rand(N)/100;
uhat=cvp(Q'*y,R);
sum(abs.(u-uhat))
To give a flavor of the behavior of the functions in LLLplus,
we show execution time for several built-in datatypes (Int32,
Int64, Int128, Float32, Float64, BitInt, and BigFloat) as well as type
from external packages (Float128 from
Quadmath.jl and Double64
from DoubleFloat.jl)
which are used to generate 100 16x16 matrices with elements uniformly
distributed over -100 to 100. The figure shows average execution
time when using these matrices as input lattice bases for several
functions from LLLplus. See test/perftest.jl for the code to
regenerate the figure and for another line of code that generates a
figure of execution time versus basis dimension.
The 2020 Simons Institute lattice
workshop, a
survey paper by Wuebben, and the
monograph by Bremner
were helpful in writing the tools in LLLplus
and are good resources for further study. If you are trying to break
one of the Lattice Challenge
records or are looking for robust, well-proven lattice tools, look at
fplll. Also, for many
number-theoretic problems the
Nemo.jl package is appropriate;
it uses the FLINT C library to do LLL
reduction on Nemo-specific data types. Finally, no number theorists
or computer scientists
have worked on LLLplus; please treat the package as experimental.