Python implementation of the Schnorr-Euchner enumeration algorithm

Python implementation of the Schnorr-Euchner enumeration algorithm used to solve the shortest vector problem (SVP) on lattices. The algorithm was created during the author's master's thesis and requires the following libraries:



fpyLLL

Numpy

Sympy


The program SE.py does the following:



Computes random 32-bit integer basis.

LLL reduces the basis along with the computation of it's GSO.

Uses the enumeration to find the shortest vector from the lattice.

This is done 20 times for each dimension 5–51 with a count for the amount of operations and whether the shortest vector was found.

Results are put into a text file.


The program SE_pruning.py is with the addition of the pruning from fpyLLL:



Adds the computation of a random unimodular matrix which is used to randomize the starting basis.

Pruning is done with the Pruning.pruner function with the addition of the function optimize_coefficients_cost_fixed_prob for the pruning coefficients.

Now the dimension is fixed to 50 with bit size being the variable.