A Verified Efficient Implementation
of the LLL Basis Reduction Algorithm

General

This site provides supporting material for the paper A Verified Efficient Implementation of the LLL Basis Reduction Algorithm by Ralph Bottesch, Max W. Haslbeck, and René Thiemann.

Experimental Results

The experiments have been conducted as follows.

  • Each input lattice input_n.txt contains n vectors of dimension n. The shape of each lattice is fixed, namely it corresponds to a lattice that stems from a polynomial factorization problem. In particular, the numbers in the lattice are either 0, 1, or a n-digit random number.
  • All experiments have been conducted on an iMac Pro with 3.2 GHz and 64 GB RAM running macOS High Sierra.
  • The old and new verified Haskell code has been compiled with GHC version 8.2.1 using -O2. Measurements are conducted using the command line tool time.
    In order to generate short vectors in Mathematica (version 11.2.0), we basically invoke Timing[LatticeReduce[input]] within a running Mathematica session.
    For the command line tool fplll (version 5.2.1) we again use time for measurement.
    In the verified code (old and new) we set the value of the parameter α to 3/2, whereas for Mathematica and fplll we use their default settings (the default value for Mathematica appears to be undocumented, for fplll it is very close to 4/3). Smaller values of α lead to slightly better results.

The table displays the execution times in seconds of our experiments.

input latticeold verifiednew verifiedMathematicafplll
input_50.020.020.000.01
input_100.070.020.010.01
input_150.720.040.040.01
input_206.840.120.090.01
input_2520.430.270.190.02
input_3080.450.770.430.04
input_35276.191.950.900.09
input_40594.714.031.710.17
input_451666.068.603.240.32
input_503084.3915.695.200.53
input_556578.1130.839.100.90
input_6015599.5060.1414.891.47
input_6520849.2482.3221.732.14
input_7038782.21138.6933.533.16
input_7593912.12275.1452.394.89
input_80140896.27419.7778.666.80
input_85192543.78562.55106.289.27
input_90579173.961178.88166.6913.62
input_95863539.921680.75231.6717.23
input_100633105.251656.73290.9721.61