- FPLLL[fn:1]
- is a C++11 library for operating on lattices using floating point arithmetic. It implements Gram-Schmidt orthogonalisation, LLL, BKZ, BKZ 2.0, Slide reduction and Self-Dual BKZ. All of those work on lattices given either by bases and Gram matrices.
- FPyLLL[fn:2]
- is a Python wrapper and extension of FPLLL, making its data structures and algorithms available in Python and Sage. It also (re-)implements some algorithms in Python to make their internals easily accessible.
- G6K[fn:3]
- is a sieving framework making use of FPyLLL. It implements a highly efficient sieving kernel and a high-level interface to experimenting with sieving strategies.
These libraries are evolving software projects. This means that (a) you will encounter bugs and (b) we need your help. For example, you will notice that some functions lack documentation, examples and tests. Contributions welcome![fn:4] We also have semi-regular development workshops which you can attend.
You can skip installation by using either https://sagecell.sagemath.org/ – which requires no registration but you can only run short computations and you cannot use G6K – or https://cocalc.com/ – which requires registration and payment is required if you want G6K[fn:5].
If you have a recent Sage you have FPyLLL. If you want G6K inside Sage, run:
sage -sh # replaces source ./activate
cd g6k
./rebuild.shAs far as we know, your only options on windows are either the Windows Subsystem for Linux [fn:6] or /Sage/[fn:7].
At https://hub.docker.com/u/martinralbrecht you’ll find current[fn:8] Docker images for FPLLL, FPyLLL, G6K and Sagemath + G6K. For example, if you have Docker installed, this should just work™ and drop you into a SageMath shell with FPyLLL and G6K available.
docker run -it martinralbrecht/sagemath-g6kYou will need the following packages installed to compile FP(y)LLL
- GMP
- including development headers, this is often the package
(lib)gmp-dev - MPFR
- including development headers, this is often the package
(lib)mpfr-dev - Python (3)
- including development headers, this is often the package
python(3)-dev
Then just run:
git clone https://github.com/fplll/g6k
cd g6k
./bootstrap.sh
source ./activate
./rebuild.sh -fNote that these instructions make use of Python virtual environments. These environments allow to install Python packages on a per-project basis. Practically, this means that whenever you want to use FPyLLL you’ll have to do:
cd g6k
source ./activatewhich activates the G6K virtual environment.
Full installation instructions are available at https://github.com/fplll/fpylll and https://github.com/fplll/g6k
We start with a tutorial on how to use FPyLLL as G6K also relies on it. To start, we first import the fpylll API:
from fpylll import *We might want to load matrices from text files. For example, below we load a lattice challenge. It’s a few lines of code but those are mostly artefacts from the challenges being Bzip2 compressed.
# just getting the right format from the challenge website
from urllib.request import urlopen
import bz2
import tempfile
fn = tempfile.mktemp()
fh = open(fn, "w")
url = "https://www.latticechallenge.org/challenges/challenge-200.bz2"
data = urlopen(url).read()
data = bz2.decompress(data)
data = "\n".join(data.decode("utf-8").splitlines()[3:])
_ = fh.write(data)
_ = fh.close()
A = IntegerMatrix.from_file(fn); AHowever, to experiment, we generate a \(q\)-ary lattice of dimension 100 and determinant $q50$ where
from math import log
FPLLL.set_random_seed(1337)
A = IntegerMatrix.random(100, "qary", k=50, bits=30)
log(A[0].norm(),2)Note: Objects and functions in Python/Sage can be interrogated to learn more about them such as what parameters they accept (for functions) or (often) their documentation.[fn:9]
To run LLL we have two choices. First, We can run the high-level LLL.reduction() function:
from copy import copy
B = LLL.reduction(copy(A))
log(B[0].norm(), 2)Alternatively, we can create the appropriate hierarchy of objects “by hand”. That is, algorithms are represented by objects with which we can interact. In this tutorial, we are going to pursue this strategy. We first create a MatGSO object, which takes care of computing the Gram-Schmidt orthogonalisation.
A MatGSO object stores the following information:
- An integral basis
Bor a Gram matrixG, - the Gram-Schmidt coefficients \(μi,j = \langle \mathbf{b}_i, \mathbf{b}^*_j\rangle / \|\mathbf{b}^*_j\|^2\) for \(i>j\),
- the coefficients \(ri,i = \langle \mathbf{b}^*_i, \mathbf{b}^*_i\rangle\) and
- the coefficients \(ri,j = \langle \mathbf{b}_i, \mathbf{b}^*_j \rangle = μi,j ⋅ rj,j \) for \(i>j\)
It holds that: $\mathbf{B} = \mathbf{R} × \mathbf{Q} = (μ × \mathbf{D}) × (\mathbf{D}-1 × \mathbf{B}^*)$ where
We choose the floating point type (\(≈\) bits of precision) used to represent the Gram-Schmidt coefficients as native double, which is fastest and fine up to dimension 170 or so. If you choose mpfr for arbitrary precision, you must call FPLLL.set_precision(prec) before constructing your object M, i.e. precision is global when picking MPFR!
M = GSO.Mat(A, float_type="d")When we say “internal”, we mean it. Note that M is lazy, i.e. the Gram-Schmidt orthogonalisation is only computed/updated when needed. For example, as of now, none of the coefficients are meaningful:
M.get_r(0,0)To get meaningful results, we need to trigger the appropriate computation. To compute the complete GSO, run:
M.update_gso()This is better:
M.get_r(0,0)
A[0].norm()^2We can now create an LLL object which operates on GSO objects. All operations performed on GSO objects, e.g. M, are automatically also applied to the underlying integer matrix, e.g. A.
L = LLL.Reduction(M, delta=0.99, eta=0.501, flags=LLL.VERBOSE)Now that we have an LLL object, we can call it, i.e. run the algorithm. Note that you can specify a range of rows on which to perform LLL.
L(0, 0, 10)
That’s maybe a bit verbose, let’s continue to the end without all that feedback:
L = LLL.Reduction(M, delta=0.99, eta=0.501)
L()FPLLL guarantees \(\|μi,j\| \leq 2\,η - 1/2\) for all
all(abs(M.get_mu(i,j)) <= 2*0.501-0.5 for i in range(M.d) for j in range(i))We also want to check in on A:
log(A[0].norm(),2)Calling BKZ works similarly, First, there is a high-level function BKZ.reduction().
B = BKZ.reduction(copy(A), BKZ.EasyParam(40, max_loops=8))
log(B[0].norm(),2)This implementation also support SDBKZ:
params = BKZ.EasyParam(40, max_loops=8, flags=BKZ.SD_VARIANT)
B = BKZ.reduction(copy(A), params)
log(B[0].norm(),2)and Slide reduction:
params = BKZ.EasyParam(40, max_loops=8, flags=BKZ.SLD_RED)
B = BKZ.reduction(copy(A), params)
log(B[0].norm(),2)Alternatively, there is a BKZ object BKZ.Reduction. In addition there are also several implementations of the BKZ algorithm in
fpylll.algorithms
These are re-implementations of BKZ-syle algorithms in Python which makes them rather hackable, i.e. we can modify different parts of the algorithms relatively easily. To use those, we first have to import them. We opt for BKZ 2.0:[fn:11]
from fpylll.algorithms.bkz2 import BKZReduction as BKZ2BKZ 2.0 takes a lot of parameters, such as:
block_size- the block size
strategies- we explain this one below
flags- verbosity, early abort, etc.
max_loops- limit the number of tours
auto_abort- heuristic, stop when the average slope of \(log(\|\mathbf{b}_i^*\|)\) does not decrease fast enough
gh_factor- heuristic, if set then the enumeration bound will be set to this factor times the Gaussian Heuristic.
It gets old fast passing these around one-by-one. Thus, FPLLL and FPyLLL introduce an object BKZ.Param to collect such parameters:
flags = BKZ.AUTO_ABORT|BKZ.MAX_LOOPS|BKZ.GH_BND # optionally add |BKZ.VERBOSE
par = BKZ.Param(60, strategies=BKZ.DEFAULT_STRATEGY, max_loops=4, flags=flags)This, too, gets old fast, so we can simply use the equivalent:
par = BKZ.EasyParam(60, max_loops=4, flags=BKZ.GH_BND)The parameter strategies takes a list of “reduction strategies” or a filename for a JSON file containing such strategies. For each block size these strategies determine what pruning coefficients are used and what kind of recursive preprocessing is applied before enumeration. The strategies in BKZ.DEFAULT_STRATEGY were computed using fplll’s strategizer.[fn:12]
strategies = load_strategies_json(BKZ.DEFAULT_STRATEGY)
print(strategies[60])That last line means that for block size 60 we are preprocessing with block size 40 and our pruning parameters are such that enumeration succeeds with probability between 29% and 50% depending on the target enumeration radius.
Finally, let’s call BKZ-60 on our example lattice:
bkz = BKZ2(A) # or
bkz = BKZ2(GSO.Mat(A)) # or
bkz = BKZ2(LLL.Reduction(GSO.Mat(A)))
_ = bkz(BKZ.EasyParam(60, max_loops=4, flags=BKZ.GH_BND))After calling BKZ, the BKZ object will have an attribute trace.
bkz.traceIt collects statistics about that run of BKZ:
print(bkz.trace.get(("tour", 0)).report())
Ironically, the most efficient way to get a shortest vector is not to simply call the function shortest_vector (see below). We can use the following workaround which asks the SVP subroutine in BKZ to do the work for us.
from math import log
FPLLL.set_random_seed(1337)
A = IntegerMatrix.random(50, "qary", k=25, bits=30)
bkz = BKZ2(A)
_ = bkz.svp_reduction(0, 50, BKZ.EasyParam(50))
log(A[0].norm(),2)Alternatively, here is a reasonably efficient way of calling shortest_vector.
from math import log
from fpylll.algorithms.bkz2 import BKZReduction as BKZ2
FPLLL.set_random_seed(1337)
A = IntegerMatrix.random(60, "qary", k=30, bits=30)
M = GSO.Mat(A)
_ = M.update_gso()
_ = BKZ2(M)(BKZ.EasyParam(40))
radius = 0.99*A[0].norm()**2
preproc_cost = 60 * 2**(0.1839*40*log(40,2) - 40 + 16)
target = 0.99
p = Pruning.run(radius, preproc_cost, M.r(), target)
v = SVP.shortest_vector(A, "fast", pruning=p.coefficients)G6K’s central object is a Siever implementing the abstract state machine from the G6K paper footfullcite:EC:ADHKPS19 which is then called by higher-level Python functions.
from fpylll import *
from g6k import *
FPLLL.set_random_seed(1337)
A = IntegerMatrix.random(60, "qary", k=30, bits=30)
g6k = Siever(A, seed=0x1337) # g6k has its own seed
g6k.initialize_local(0, 0, 50) # sieve the entire basis
g6k(alg="bgj1")
v = g6k.best_lifts()[0][2]
w = A.multiply_left(v)
sum(w_**2 for w_ in w), A[0].norm()**2However, just running the sieve directly is not the most efficient strategy. Here’s a bit of a better strategy, a progressive left sieve.
FPLLL.set_random_seed(1337)
A = IntegerMatrix.random(60, "qary", k=30, bits=30)
g6k = Siever(A, seed=0x1337) # g6k has its own seed
g6k.initialize_local(0, 20, 60) # progressive sieve left
g6k(alg="bgj1")
for i in range(20):
g6k()
g6k.extend_left()
v = g6k.best_lifts()[0][2]
w = A.multiply_left(v)
sum(w_**2 for w_ in w), A[0].norm()**2In general, we may want to run the WorkOut. This is the function that was used for breaking SVP challenges.
from g6k.utils.stats import SieveTreeTracer
from g6k.algorithms.workout import workout
FPLLL.set_random_seed(1337)
A = IntegerMatrix.random(60, "qary", k=30, bits=30)
g6k = Siever(A)
tracer = SieveTreeTracer(g6k,
root_label=("full-sieve", 60),
start_clocks=True)
_ = workout(g6k, tracer, 0, 60, dim4free_min=0, dim4free_dec=15)
print(tracer.exit())
v = g6k.best_lifts()[0][2]
w = A.multiply_left(v)
A[0].norm()**2G6K also comes with a BKZ-style algorithm. This is the function that was used for breaking LWE challenges.
from fpylll import *
from g6k import Siever
from g6k.utils.stats import SieveTreeTracer
from g6k.algorithms.bkz import pump_n_jump_bkz_tour
FPLLL.set_random_seed(1337)
A = LLL.reduction(IntegerMatrix.random(100, "qary", k=50, bits=20))
g6k = Siever(A)
tracer = SieveTreeTracer(g6k, root_label=("lwe"), start_clocks=True)
for b in (20, 30, 40, 50, 60): # progressive BKZ
pump_n_jump_bkz_tour(g6k, tracer,
b, pump_params={"down_sieve": True})
print(A[0].norm()**2)In this exercise, we ask you to verify various predictions made about lattice reduction using the implementations available in FpyLLL and G6K.
Recall that lattice reduction returns vectors such that \(\|\vec{v}\| = δ^d ⋅ \mathrm{Vol}(L)1/d\) where
Schnorr’s geometric series assumption (GSA) states that the norms of the Gram-Schmidt vectors after lattice reduction satisfy \[\|\mathbf{b}_i^*\| = αi-1 ⋅ \|\mathbf{b}_0\| \textnormal{ for some } 0 < α < 1.\] Check how well this assumption holds for various block sizes of BKZ.
That is, running several tours of BKZ 2.0, plot the logs of Gram-Schmidt norms agains the GSA after each tour. You have several options to get to those norms:[fn:13]
- Check out the
dump_gso_filenameoption forBKZ.Param. - Set up BKZ parameters to run one tour only an measure between BKZ calls.
- Inherit from
fpylll.algorithms.bkz2.BKZReductionand add the functionality to plot after each tour.
To plot, you again have several options.
If you are running from within Sage, you can simply call line() to plot, e.g.
d = zip(range(10),prime_range(30))
line(d, color="lightgrey", dpi=150r, thickness=2)
In vanilla Python, you can use matplotlib[fn:14]
import matplotlib.pyplot as plt
X = range(10)
Y = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
plt.plot(X, Y)
plt.ylabel('primes!!!')
plt.savefig("lab-plot-line-matplotlib.png", bbox_inches='tight')
plt.close()
# -*- coding: utf-8 -*-
from fpylll import *
df = lambda k: (k/(2*pi*e) * (pi*k)**(1/k))**(1/(2*k-1))
fmt = u"n: %3d, bits: %2d, "
fmt += u"β: %2d, δ: %.4f, pred: 2^%5.2f, real: 2^%5.2f, "
fmt += u"pred/real: %5.2f"
ntrials = 20
for n in (50, 70, 90, 110, 130):
for q in (367867, 706051237):
for k in (2, 20, 50, 60):
if k > n:
continue
k = ZZ(k)
if k == 2:
delta = 1.0219
else:
delta = df(k)
n_p = float(delta**n * sqrt(q))
n_r = []
for i in range(ntrials):
A = IntegerMatrix.random(n, "qary", k=n/2, q=q)
if k == 2:
_ = LLL.reduction(A)
else:
par = BKZ.Param(block_size=k,
strategies=BKZ.DEFAULT_STRATEGY,
max_loops=4,
flags=BKZ.MAX_LOOPS|BKZ.GH_BND)
_ = BKZ.reduction(A, par)
n_r.append(A[0].norm())
n_r = sum(n_r)/ntrials
print(fmt%(n, log(q,2), k, delta,
log(n_p,2), log(n_r,2), n_p/n_r))
print()n: 50, bits: 18, β: 2, δ: 1.0219, pred: 2^10.81, real: 2^10.53, pred/real: 1.21 n: 50, bits: 18, β: 20, δ: 1.0094, pred: 2^ 9.92, real: 2^10.22, pred/real: 0.81 n: 50, bits: 18, β: 50, δ: 1.0119, pred: 2^10.10, real: 2^10.09, pred/real: 1.01 n: 50, bits: 29, β: 2, δ: 1.0219, pred: 2^16.26, real: 2^16.01, pred/real: 1.19 n: 50, bits: 29, β: 20, δ: 1.0094, pred: 2^15.37, real: 2^15.70, pred/real: 0.80 n: 50, bits: 29, β: 50, δ: 1.0119, pred: 2^15.55, real: 2^15.57, pred/real: 0.99 n: 70, bits: 18, β: 2, δ: 1.0219, pred: 2^11.43, real: 2^11.14, pred/real: 1.22 n: 70, bits: 18, β: 20, δ: 1.0094, pred: 2^10.19, real: 2^10.77, pred/real: 0.67 n: 70, bits: 18, β: 50, δ: 1.0119, pred: 2^10.44, real: 2^10.42, pred/real: 1.01 n: 70, bits: 18, β: 60, δ: 1.0114, pred: 2^10.38, real: 2^10.35, pred/real: 1.02 n: 70, bits: 29, β: 2, δ: 1.0219, pred: 2^16.89, real: 2^16.62, pred/real: 1.20 n: 70, bits: 29, β: 20, δ: 1.0094, pred: 2^15.64, real: 2^16.22, pred/real: 0.67 n: 70, bits: 29, β: 50, δ: 1.0119, pred: 2^15.90, real: 2^15.90, pred/real: 1.00 n: 70, bits: 29, β: 60, δ: 1.0114, pred: 2^15.84, real: 2^15.82, pred/real: 1.02 n: 90, bits: 18, β: 2, δ: 1.0219, pred: 2^12.06, real: 2^11.78, pred/real: 1.21 n: 90, bits: 18, β: 20, δ: 1.0094, pred: 2^10.46, real: 2^11.37, pred/real: 0.53 n: 90, bits: 18, β: 50, δ: 1.0119, pred: 2^10.79, real: 2^10.83, pred/real: 0.97 n: 90, bits: 18, β: 60, δ: 1.0114, pred: 2^10.71, real: 2^10.73, pred/real: 0.99 n: 90, bits: 29, β: 2, δ: 1.0219, pred: 2^17.51, real: 2^17.23, pred/real: 1.22 n: 90, bits: 29, β: 20, δ: 1.0094, pred: 2^15.91, real: 2^16.83, pred/real: 0.53 n: 90, bits: 29, β: 50, δ: 1.0119, pred: 2^16.24, real: 2^16.26, pred/real: 0.98 n: 90, bits: 29, β: 60, δ: 1.0114, pred: 2^16.16, real: 2^16.15, pred/real: 1.01 n: 110, bits: 18, β: 2, δ: 1.0219, pred: 2^12.68, real: 2^12.43, pred/real: 1.19 n: 110, bits: 18, β: 20, δ: 1.0094, pred: 2^10.73, real: 2^11.92, pred/real: 0.44 n: 110, bits: 18, β: 50, δ: 1.0119, pred: 2^11.13, real: 2^11.21, pred/real: 0.95 n: 110, bits: 18, β: 60, δ: 1.0114, pred: 2^11.04, real: 2^11.06, pred/real: 0.98 n: 110, bits: 29, β: 2, δ: 1.0219, pred: 2^18.14, real: 2^17.91, pred/real: 1.17 n: 110, bits: 29, β: 20, δ: 1.0094, pred: 2^16.18, real: 2^17.41, pred/real: 0.43 n: 110, bits: 29, β: 50, δ: 1.0119, pred: 2^16.58, real: 2^16.67, pred/real: 0.94 n: 110, bits: 29, β: 60, δ: 1.0114, pred: 2^16.49, real: 2^16.52, pred/real: 0.98 n: 130, bits: 18, β: 2, δ: 1.0219, pred: 2^13.31, real: 2^13.11, pred/real: 1.15 n: 130, bits: 18, β: 20, δ: 1.0094, pred: 2^11.00, real: 2^12.56, pred/real: 0.34 n: 130, bits: 18, β: 50, δ: 1.0119, pred: 2^11.47, real: 2^11.68, pred/real: 0.86 n: 130, bits: 18, β: 60, δ: 1.0114, pred: 2^11.36, real: 2^11.46, pred/real: 0.94 n: 130, bits: 29, β: 2, δ: 1.0219, pred: 2^18.76, real: 2^18.53, pred/real: 1.17 n: 130, bits: 29, β: 20, δ: 1.0094, pred: 2^16.45, real: 2^18.00, pred/real: 0.34 n: 130, bits: 29, β: 50, δ: 1.0119, pred: 2^16.92, real: 2^17.14, pred/real: 0.86 n: 130, bits: 29, β: 60, δ: 1.0114, pred: 2^16.82, real: 2^16.89, pred/real: 0.95
dump_gso_filename
# -*- coding: utf-8 -*-
from fpylll import *
import json
set_random_seed(1)
n, bits = 120, 40
A = IntegerMatrix.random(n, "qary", k=n/2, bits=bits)
beta = 60
tours = 2
fn = b"/tmp/logs.txt"
par = BKZ.Param(block_size=beta,
strategies=BKZ.DEFAULT_STRATEGY,
dump_gso_filename=fn,
max_loops=tours)
par.flags & BKZ.MAX_LOOPS # max_loops sets flag for you
delta_0 = (beta/(2*pi*e) * (pi*beta)**(1/ZZ(beta)))**(1/(2*beta-1))
alpha = delta_0**(-2*n/(n-1))
norms = [map(log, [(alpha**i * \
delta_0**n * 2**(bits/2))**2 for i in range(n)])]
BKZ.reduction(A, par)
for l in json.load(open(fn)):
if l['step'] != "End of BKZ loop":
continue
_norms = map(log, l["norms"])
norms.append(_norms)
CO = ["#4D4D4D", "#5DA5DA", "#FAA43A", "#60BD68",
"#F17CB0", "#B2912F", "#B276B2", "#DECF3F", "#F15854"]
g = line(zip(range(n), norms[0]), legend_label="GSA", color=CO[0])
g += line(zip(range(n), norms[1]), legend_label="lll", color=CO[1])
for i,_norms in enumerate(norms[2:]):
g += line(zip(range(n), _norms),
legend_label="tour %d"%i, color=CO[i+2])
gbkz.tour
# -*- coding: utf-8 -*-
from fpylll import *
from fpylll.algorithms.bkz2 import BKZReduction as BKZ2
set_random_seed(1)
n, bits = 120, 40
A = IntegerMatrix.random(n, "qary", k=n/2, bits=bits)
beta = 60
tours = 2
par = BKZ.Param(block_size=beta,
strategies=BKZ.DEFAULT_STRATEGY)
delta_0 = (beta/(2*pi*e) * (pi*beta)^(1/ZZ(beta)))^(1/(2*beta-1))
alpha = delta_0^(-2*n/(n-1))
LLL.reduction(A)
M = GSO.Mat(A)
M.update_gso()
norms = [map(log, [(alpha^i * delta_0^n \
* 2^(bits/2))^2 for i in range(n)])]
norms += [[log(M.get_r(i,i)) for i in range(n)]]
bkz = BKZ2(M)
for i in range(tours):
bkz.tour(par)
norms += [[log(M.get_r(i,i)) for i in range(n)]]
CO = ["#4D4D4D", "#5DA5DA", "#FAA43A", "#60BD68",
"#F17CB0", "#B2912F", "#B276B2", "#DECF3F", "#F15854"]
g = line(zip(range(n), norms[0]), legend_label="GSA", color=CO[0])
g += line(zip(range(n), norms[1]), legend_label="lll", color=CO[1])
for i,_norms in enumerate(norms[2:]):
g += line(zip(range(n), _norms),
legend_label="tour %d"%i, color=CO[i+2])
gMyBKZ
from fpylll import *
from fpylll.algorithms.bkz2 import BKZReduction as BKZ2
from fpylll.tools.bkz_stats import BKZTreeTracer
from time import process_time
class MyBKZ(BKZ2):
def __call__(self, params, norms, min_row=0, max_row=-1):
"""Run the BKZ with `param` and dump norms to ``norms``
:param params: BKZ parameters
:param norms: a list to append vectors of norms to
:param min_row: start processing in this row
:param max_row: stop processing in this row (exclusive)
"""
try:
label = params["name"]
except KeyError:
label = "bkz"
tracer = BKZTreeTracer(self, root_label=label,
verbosity=params.flags & BKZ.VERBOSE,
start_clocks=True)
if params.flags & BKZ.AUTO_ABORT:
auto_abort = BKZ.AutoAbort(self.M, self.A.nrows)
cputime_start = process_time()
with tracer.context("lll"):
self.lll_obj()
norms.append([self.M.get_r(j, j) for j in range(self.M.d)])
i = 0
while True:
with tracer.context("tour", i,
dump_gso=params.flags & BKZ.DUMP_GSO):
clean = self.tour(params, min_row, max_row, tracer)
norms.append([self.M.get_r(j, j) for j in range(self.M.d)])
i += 1
if clean or params.block_size >= self.A.nrows:
break
if (params.flags & BKZ.AUTO_ABORT) \
and auto_abort.test_abort():
break
if (params.flags & BKZ.MAX_LOOPS) and i >= params.max_loops:
break
if (params.flags & BKZ.MAX_TIME) \
and process_time() - cputime_start >= params.max_time:
break
tracer.exit()
self.trace = tracer.trace
return clean
set_random_seed(1)
n, bits = 120, 40
A = IntegerMatrix.random(n, "qary", k=n/2, bits=bits)
beta = 60
tours = 2
par = BKZ.Param(block_size=beta,
strategies=BKZ.DEFAULT_STRATEGY,
max_loops=tours)
delta_0 = (beta/(2*pi*e) * (pi*beta)^(1/ZZ(beta)))^(1/(2*beta-1))
alpha = delta_0^(-2*n/(n-1))
LLL.reduction(A)
norms = [[(alpha^i * delta_0^n * 2^(bits/2))^2 for i in range(n)]]
bkz = MyBKZ(A)
bkz(par, norms)
colours = ["#4D4D4D", "#5DA5DA", "#FAA43A", "#60BD68", "#F17CB0",
"#B2912F", "#B276B2", "#DECF3F", "#F15854"]
g = line(zip(range(n), map(log, norms[0])),
legend_label="GSA", color=colours[0])
g += line(zip(range(n), map(log, norms[1])),
legend_label="lll", color=colours[1])
for i,_norms in enumerate(norms[2:]):
g += line(zip(range(n), map(log, _norms)),
legend_label="tour %d"%i, color=colours[i+2])
g[fn:1] https://github/com/fplll/fplll
[fn:2] https://github.com/fplll/fpylll
[fn:3] https://github.com/fplll/g6k
[fn:4] https://github.com/fplll/fplll/blob/master/CONTRIBUTING.md
[fn:5] for installing G6K from the Interwebs
[fn:6] https://docs.microsoft.com/en-us/windows/wsl/install-win10
[fn:7] https://github.com/sagemath/sage-windows/releases
[fn:8] as of writing
[fn:9] https://doc.sagemath.org/html/en/tutorial/tour_help.html
[fn:10] See https://github.com/fplll/fplll/blob/master/README.md#fplll-1
[fn:11] See https://github.com/fplll/fpylll/blob/master/src/fpylll/algorithms/simple_bkz.py for a simple implementation of BKZ.
[fn:12] https://github.com/fplll/strategizer
[fn:13] We apologise for violating the Zen of Python so much: “There should be one — and preferably only one — obvious way to do it.” https://www.python.org/dev/peps/pep-0020/
[fn:14] http://matplotlib.org
[fn:15] See http://doc.sagemath.org/html/en/constructions/linear_algebra.html#kernels
PDF version: https://pdfhost.io/v/2v~9DbGF_FPyLLL_G6K_Lab.pdf