Skip to content

Instantly share code, notes, and snippets.

@malb
Last active March 25, 2020 02:34
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save malb/8edc039db7df2550b65881d81aae1a6d to your computer and use it in GitHub Desktop.
Lattice Lab @ Simons

FP(y)LLL & G6K Lab

1 Introduction

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.

2 Installation

2.1 No installation

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].

2.2 Sage

If you have a recent Sage you have FPyLLL. If you want G6K inside Sage, run:

sage -sh # replaces source ./activate
cd g6k
./rebuild.sh

2.3 Windows

As far as we know, your only options on windows are either the Windows Subsystem for Linux [fn:6] or /Sage/[fn:7].

2.4 Docker

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-g6k

2.5 Compiling from source

You 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 -f

Note 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 ./activate

which activates the G6K virtual environment.

Full installation instructions are available at https://github.com/fplll/fpylll and https://github.com/fplll/g6k

3 Getting started

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 *

3.1 Integer matrices

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); A

However, to experiment, we generate a \(q\)-ary lattice of dimension 100 and determinant $q50$ where $q$ is a freshly chosen random 30-bit prime. Before we sample our basis, we set the random seed to ensure we can reproduce our experiments later.

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]

3.2 Gram–Schmidt orthogonalisation

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 B or a Gram matrix G,
  • 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 $\mathbf{Q}$ is orthonormal, $\mathbf{R}$ is lower triangular and $\mathbf{B}^*$ is the Gram-Schmidt orthogonalisation.

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()^2

3.3 LLL

We 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 $i>j$.[fn:10] Let’s check:

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)

3.4 BKZ

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 BKZ2

BKZ 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.trace

It collects statistics about that run of BKZ:

print(bkz.trace.get(("tour", 0)).report())

3.5 Short vectors

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)

3.6 G6K

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()**2

However, 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()**2

In 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()**2

G6K 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)

4 Exercises

In this exercise, we ask you to verify various predictions made about lattice reduction using the implementations available in FpyLLL and G6K.

4.1 root-Hermite factors

Recall that lattice reduction returns vectors such that \(\|\vec{v}\| = δ^d ⋅ \mathrm{Vol}(L)1/d\) where $δ$ is the root-Hermite factor which depends on the algorith. For LLL it is \(δ ≈ 1.0219\) and for BKZ-\(k\) it is \[δ ≈ \left( \frac{k}{2 π e} (π k)\frac{1{k}} \right)\frac{1{2(k-1)}}.\] Experimentally measure root-Hermite factors for various bases and algorithms.

4.2 GS norms & Geometric series assumption

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_filename option for BKZ.Param.
  • Set up BKZ parameters to run one tour only an measure between BKZ calls.
  • Inherit from fpylll.algorithms.bkz2.BKZReduction and 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)

./lab-plot-line-sage.png

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()

./lab-plot-line-matplotlib.png

5 Ignored

6 Example solutions

6.1 root-Hermite factors

# -*- 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

6.2 GS norms & Geometric Series Assumption

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])
g

bkz.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])
g

MyBKZ

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

7 Footnotes

[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

@malb
Copy link
Author

malb commented Mar 6, 2020

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment