Skip to content

Instantly share code, notes, and snippets.

@malb
Created May 7, 2018 21:55
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save malb/b74a766b1d1c52aac299ca9551a0f489 to your computer and use it in GitHub Desktop.
Make illustrative plots for BKZ's behaviour
# -*- coding: utf-8 -*-
"""
Illustrate behaviour of BKZ algorithm.
.. modulauthor: Martin Albrecht <martin.albrecht@royalholloway.ac.uk>
To convert to movie, call e.g. `ffmpeg -framerate 8 -pattern_type glob -i "*.png" bkz.mkv`
"""
from fpylll.tools.bkz_stats import dummy_tracer
from fpylll.algorithms.bkz2 import BKZReduction as BKZ2
from fpylll import BKZ
import matplotlib.pyplot as plt
from math import log, pi, e
import matplotlib.patches as patches
class PlotBKZ(BKZ2):
def __call__(self, params, min_row=0, max_row=-1):
self.M.update_gso()
self._plots = [self.M.r()]
self._toplevel = True
BKZ2.__call__(self, params, min_row, max_row)
self.M.update_gso()
self._plots.append(self.M.r())
def svp_reduction(self, kappa, block_size, params, tracer=dummy_tracer):
_toplevel = self._toplevel
self._toplevel = False
r = BKZ2.svp_reduction(self, kappa, block_size, params, tracer=dummy_tracer)
self._toplevel = _toplevel
if _toplevel:
self.M.update_gso()
self._plots[-1].append(self.M.r())
return r
def tour(self, params, min_row=0, max_row=-1, tracer=dummy_tracer):
if self._toplevel:
self._plots.append([])
return BKZ2.tour(self, params, min_row, max_row, tracer)
def log_line(l):
return [log(l[i], 2) for i in range(len(l))]
def gso_plot(tours, block_size, basename="foo"):
d = len(tours[0])
x = range(d)
beta = float(block_size)
delta_0 = (beta/(2.*pi*e) * (pi*beta)**(1./beta))**(1./(2.*beta-1.))
alpha = delta_0**(-2.*d/(d-1.))
logvol = sum(log_line(tours[0])) # already squared
gsa = [log(alpha, 2)*(2*i) + log(delta_0, 2)*(2*d) + logvol*(1./d) for i in range(d)]
print gsa[0]
fig, ax = plt.subplots()
ax.plot(x, log_line(tours[0]))
ax.set_ylabel("$\\log_2 \\mathbf{b}_i^*$")
ax.set_xlabel("$i$")
ylim = ax.get_ylim()
fig.savefig("%s-aaa.png"%basename, dpi=300)
plt.close()
for i, tour in enumerate(tours[1:-1]):
for kappa, norms in enumerate(tour):
fig, ax = plt.subplots()
rect = patches.Rectangle((kappa, ylim[0]), min(block_size, d-kappa-1), ylim[1]-ylim[0],
fill=True, color="lightgray")
ax.add_patch(rect)
ax.plot(x, log_line(norms), label="$\\mathbf{b}_i^*$")
ax.plot(x, gsa, color="black", label="GSA")
ax.set_ylabel("$\\log_2(\\cdot)$")
ax.set_xlabel("$i$")
ax.set_ylim(*ylim)
ax.legend(loc='upper right')
ax.set_title("BKZ tour: %2d, $\\kappa$: %3d"%(i, kappa))
fig.savefig("%s-t%03d-k%04d.png"%(basename, i, kappa), dpi=300)
plt.close()
fig, ax = plt.subplots()
ax.plot(x, log_line(tours[-1]))
ax.set_ylabel("$\\log_2 \\mathbf{b}_i^*$")
ax.set_xlabel("$i$")
ylim = ax.get_ylim()
fig.savefig("%s-zzz.png"%basename, dpi=300)
plt.close()
def run(d=150, block_size=60):
from fpylll import IntegerMatrix
A = IntegerMatrix.random(d, "qary", bits=30, k=d//2)
bkz = PlotBKZ(A)
bkz(BKZ.EasyParam(block_size, flags=BKZ.VERBOSE, max_loops=8))
gso_plot(bkz._plots, block_size)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment