fpylll is a Python library for performing lattice reduction on lattices over the Integers. It is based on the fplll, a C++ library which describes itself as follows:
fplll contains several algorithms on lattices that rely on floating-point computations. This includes implementations of the floating-point LLL reduction algorithm, offering different speed/guarantees ratios. It contains a ‘wrapper’ choosing the estimated best sequence of variants in order to provide a guaranteed output as fast as possible. In the case of the wrapper, the succession of variants is oblivious to the user. It also includes a rigorous floating-point implementation of the Kannan-Fincke-Pohst algorithm that finds a shortest non-zero lattice vector, and the BKZ reduction algorithm.
fplll is distributed under the GNU Lesser General Public License (either version 2.1 of the License, or, at your option, any later version) as published by the Free Software Foundation.
In short, fplll is your best bet at a publicly available fast lattice-reduction library and fpylll provides a convenient interface for it — for experimentation, development and extension — from Python.
For the rest of this post, I’ll give you a tour of the features currently implemented in fpylll and point out some areas where we could do with some help.
An Interface to fplll
First of all, fpylll is a thin wrapper around fplll. In the example below, we first generate an NTRU-like matrix and consider the norm of the first row:
from fpylll import IntegerMatrix, LLL q = 1073741789 A = IntegerMatrix.random(30, "ntrulike", bits=30, q=q) A[0].norm()
3294809651.09
We then call LLL reduction, i.e. we perform integer-linear combinations of the rows to make shorter rows and observe the output:
LLL.reduction(A) A[0].norm()
82117.5815888
If LLL reduction isn’t strong enough, we can call the BKZ algorithm for some block size 
from fpylll import BKZ BKZ.reduction(A, o=BKZ.Param(block_size=10)) A[0].norm()
71600.8858744
We may want to increase the block size
from fpylll import BKZ BKZ.reduction(A, o=BKZ.Param(block_size=20)) A[0].norm()
68922.4558181
Or, we just go for the shortest vector. Solving the Shortest Vector Problem (SVP) is supposed to be hard problem, so we only attempt it for a small lattice.
from fpylll import SVP q = 1073741789 B = IntegerMatrix.random(10, "ntrulike", bits=7, q=127) SVP.shortest_vector(B)
(1, 2, -3, 5, -2, 4, 5, -1, 1, 1, 0, -1, 6, -3, 0, 2, 6, -8, 0, 1)
Of course, fpylll being a Python library means you can use your favourite Python libraries with it. For example, say, we want to LLL reduce many matrices in parallel, using all our cores, and to compute the norm of the shortest vector across all matrices after LLL reduction. We’ll make use of Python’s multiprocessing:
from multiprocessing import Pool
If we want to recover the reduced matrix, we have to return it. However, LLL.reduction returns nothing and its input A will live in its own process. So we add a small function which returns A.
def f(A): from fpylll import LLL LLL.reduction(A) return A
For this example, we want dimension 40, four worker processes and 32 matrices:
from fpylll import IntegerMatrix d = 20 workers = 4 tasks = 32 A = [IntegerMatrix.random(d, "ntrulike", bits=30, q=1073741789) for _ in range(tasks)]
Let’s get to work: we create a pool of workers and kick off the computation:
pool = Pool(workers) A = pool.map(f, A)
Finally, we output the minimal norm found:
min([A_[0].norm() for A_ in A])
7194.545155880252
A Python Library for Developing Lattice-Reduction Algorithms
The main objective of fpylll is to make developing and experimenting with the kind of algorithms implemented in fplll easier. For example, there are a few variants of the BKZ algorithm in the literature which essentially re-combine the same building blocks — LLL and an SVP oracle — in some way. These kind of algorithms should be easy to implement. The code below is an implementation of the plain BKZ algorithm in 70 lines of Python.
from fpylll import IntegerMatrix, GSO, LLL, BKZ from fpylll import Enumeration as Enum from fpylll import gso class BKZReduction: def __init__(self, A): wrapper = LLL.Wrapper(A) wrapper() self.A = A self.M = GSO.Mat(A, flags=gso.GSO.ROW_EXPO) self.lll_obj = LLL.Reduction(self.M) def __call__(self, block_size): self.M.discover_all_rows() while True: clean = self.bkz_tour(block_size, 0, self.A.nrows) if clean: break def bkz_tour(self, block_size, min_row, max_row): clean = True for kappa in range(min_row, max_row-1): bs = min(block_size, max_row - kappa) clean &= self.svp_reduction(kappa, bs) return clean def svp_reduction(self, kappa, block_size): clean = True self.lll_obj(0, kappa, kappa + block_size) if self.lll_obj.nswaps > 0: clean = False max_dist, expo = self.M.get_r_exp(kappa, kappa) delta_max_dist = self.lll_obj.delta * max_dist solution, max_dist = Enum.enumerate(self.M, max_dist, expo, kappa, kappa + block_size, None) if max_dist >= delta_max_dist: return clean nonzero_vectors = len([x for x in solution if x]) if nonzero_vectors == 1: first_nonzero_vector = None for i in range(block_size): if abs(solution[i]) == 1: first_nonzero_vector = i break self.M.move_row(kappa + first_nonzero_vector, kappa) self.lll_obj.size_reduction(kappa, kappa + 1) else: d = self.M.d self.M.create_row() with self.M.row_ops(d, d+1): for i in range(block_size): self.M.row_addmul(d, kappa + i, solution[i]) self.M.move_row(d, kappa) self.lll_obj(kappa, kappa, kappa + block_size + 1) self.M.move_row(kappa + block_size, d) self.M.remove_last_row() return False
Beyond fplll
In the meantime fpylll has gained a contrib module which implements additional algorithms. As of writing, it contains a simple demo implementation of BKZ (see above), a simple implementation of Dual BKZ and a slightly feature enhanced re-implementation of fplll’s BKZ: it collects additional statistics compared to fplll’s implementation of the same algorithm. Let’s run it to see what that means:
from copy import copy from fpylll.contrib.bkz import BKZReduction C = copy(A) b = BKZReduction(C) b(BKZ.Param(block_size=30, flags=BKZ.AUTO_ABORT|BKZ.VERBOSE)) stats = b.stats; stats
{"i": 5, "total": 1.02, "time": 0.16, "preproc": 0.03, "svp": 0.05, "r_0": 4.7503e+09, "slope": -0.0541, "enum nodes": 19.29, "max(kappa)": 10}
That output isn’t that different from fplll outputs. However, in contrast to fplll (because I didn’t bother to implement it over there, yet) we also get access to a stats object after the computation finished. Let’s use it to inquire how many nodes where visited during enumeration
stats.enum_nodes
4085856
and how much time we spent in enumeration:
stats.svp_time
0.32868
fpylll also offers a few additional utility functions which go beyond what fplll offers such as copying submatrices and modular reduction.
Integration with other Projects
fpylll integrates reasonably nicely with Sage (once #20291 is merged, that is): converting back and forth between data types is seamless. For example:
sage: A = random_matrix(ZZ, 10, 10) sage: from fpylll import IntegerMatrix, LLL sage: B = IntegerMatrix.from_matrix(A) sage: LLL.reduction(B) sage: B.to_matrix(A)
[ -1 1 -1 0 1 0 -1 -2 0 -3] [ 4 0 0 0 -1 0 -1 -1 0 1] [ -1 1 0 2 -3 -1 -2 0 0 3] [ 0 -1 -3 -1 -1 0 -3 0 2 3] [ -2 2 0 0 -1 2 -1 2 -5 0] [ -1 0 3 0 4 2 1 -2 1 2] [ -1 6 -4 1 2 -1 -2 4 2 0] [ -1 1 -7 -3 2 -3 6 -2 -4 3] [ 0 -7 -2 8 7 -9 -4 1 -4 -1] [ -1 5 6 -12 4 -14 -4 -1 -2 5]
In fact, when installed inside Sage, element access for IntegerMatrix accepts and returns sage.rings.integer.Integer directly, instead of Python integers.
sage: type(B[0,0]) <type 'sage.rings.integer.Integer'>
fpylll also integrates somewhat with NumPy. To see how, let’s create a small NTRU-like matrix again:
from fpylll import * A = IntegerMatrix.random(4, "ntrulike", bits=7, q=127)
We’d like to do some analysis on its Gram-Schmidt matrix, so let’s compute it:
sage: M = GSO.Mat(A) sage: M.update_gso() True
Let’s dump it into a NumPy array and spot check that the result is reasonably close:
sage: import numpy sage: from fpylll.numpy import dump_mu sage: N = numpy.ndarray(dtype="double", shape=(8,8)) sage: dump_mu(N, M, 0, 8) sage: N[1,0] - M.get_mu(1,0) 0.0
Finally, let’s do something more or less useful with our output:
sage: numpy.linalg.eigvals(N) [ -2.14381988e-39 +0.00000000e+00j -1.51590958e-39 +1.51590958e-39j -1.51590958e-39 -1.51590958e-39j 3.26265223e-55 +2.14381988e-39j 3.26265223e-55 -2.14381988e-39j 2.14381988e-39 +0.00000000e+00j 1.51590958e-39 +1.51590958e-39j 1.51590958e-39 -1.51590958e-39j]
Tests
fpylll runs tests on every check-in for Python 2 and 3. As an added benefit, this extends test coverage for fplll as well, which only has a few highlevel tests.
Lisp
“This is all nice and well”, I hear you say, “but I prefer to do my computations in Lisp, so thanks, but not thanks”.
No worries, Hy has you covered:
=> (import [fpylll [*]]) => (setv q 1073741789) => (setv A (.random IntegerMatrix 30 "ntrulike" :bits 30 :q q)) => (car A) row 0 of <IntegerMatrix(60, 60) at 0x7f1cbbfbf888> => (get A 1) row 1 of <IntegerMatrix(60, 60) at 0x7f1cbbfbf888> => (-> (car A) (.norm)) 4019682565.5285482 => (.reduction LLL A) => (.norm (car A)) 6937.9845776709535
Help Wanted
fpylll isn’t quite done yet. Besides testing and documentation, it would be nice if someone would attempt to re-implement fplll’s LLL wrapper in pure Python. This would serve as a test case to see if everything that’s needed really is exposed and as a starting point for others who like to tweak the strategy. Speaking of LLL, fpylll is currently somewhat biased towards playing with BKZ, i.e. it would be nice to see how useful it is for trying out tweaks to the LLL algorithm.
One thought on “fpylll”