This is a python library to use lattices on python.
This library has algorithms to lattice reduce, solve SVP, solve CVP, and other many operation for lattices.
If you want to use A = numpy.array([[123, 0, 0], [234, 1, 0], [345, 0, 1]]) as lattice basis matrix, you can do like below:
import PythonLatticeLibrary as PLL import numpy as np A = np.array([[123, 0, 0], [234, 1, 0], [345, 0, 1]]) b = PLL.lattice(A) b.print()Output is below.
Basis = [[123 0 0] [234 1 0] [345 0 1]] Rank = 3 Volume = 122.99999999999994 Not only numpy.array but list is available for argument of PLL.lattice():
import PythonLatticeLibrary as PLL import numpy as np A = [[123, 0, 0], [234, 1, 0], [345, 0, 1]] b = PLL.lattice(A) b.print()Output is below.
Basis = [[123 0 0] [234 1 0] [345 0 1]] Rank = 3 Volume = 122.99999999999994 You can generates a random lattice like below:
import PythonLatticeLibrary as PLL b = PLL.random_lattice(5) # Generates 5-dimensional lattice basis. b.print()Output is below:
Basis = [[875 0 0 0 0] [932 1 0 0 0] [951 0 1 0 0] [801 0 0 1 0] [754 0 0 0 1]] Rank = 5 Volume = 875.0000000044823 You can reduce lattice basis(e.g. LLL-reduction, Deep-LLL-reduction, etc.) like below:
import PythonLatticeLibrary as PLL b = PLL.random_lattice(5) b.print() b.basis = b.LLL() # LLL-reduction b.print()Output is below.
Basis = [[711 0 0 0 0] [940 1 0 0 0] [500 0 1 0 0] [592 0 0 1 0] [555 0 0 0 1]] Rank = 5 Volume = 710.9999999597205 Basis = [[ 0 1 2 1 -2] [-1 2 2 -1 1] [ 1 -3 2 0 2] [ 0 2 -1 3 2] [-4 -1 1 1 1]] Rank = 5 Volume = 710.9999999999999 You can select reduction parameter:
import PythonLatticeLibrary as PLL b = PLL.random_lattice(5) b.print() b.basis = b.LLL(delta=0.5) # LLL-reduction b.print()Output is below:
Basis = [[814 0 0 0 0] [659 1 0 0 0] [723 0 1 0 0] [912 0 0 1 0] [781 0 0 0 1]] Rank = 5 Volume = 813.9999999534335 Basis = [[ 1 1 -1 1 1] [-2 -1 1 0 2] [ 2 -4 0 2 0] [-2 -2 -3 2 -1] [-1 2 2 4 -3]] Rank = 5 Volume = 813.9999999999997 You can use other functions for lattice reduction like LLL. Below is the examples.
import PythonLatticeLibrary as PLL b = PLL.random_lattice(5) b.print() b.basis = b.DeepLLL() # Deep-LLL-reduction b.print()Output is below:
Basis = [[726 0 0 0 0] [952 1 0 0 0] [676 0 1 0 0] [655 0 0 1 0] [900 0 0 0 1]] Rank = 5 Volume = 726.0000000397084 Basis = [[-2 -1 -1 0 1] [ 1 -1 1 1 2] [ 0 -2 2 0 -1] [-3 3 4 -1 1] [ 0 -1 -2 6 -1]] Rank = 5 Volume = 725.9999999999999 You can solve SVP using function ENUM_SVP():
import PythonLatticeLibrary as PLL b = PLL.random_lattice(7) b.print() b.basis = b.LLL() # LLL-reduction v = b.ENUM_SVP() print(v)Output is below:
Basis = [[924 0 0 0 0 0 0] [719 1 0 0 0 0 0] [552 0 1 0 0 0 0] [723 0 0 1 0 0 0] [608 0 0 0 1 0 0] [834 0 0 0 0 1 0] [995 0 0 0 0 0 1]] Rank = 7 Volume = 924.000000001688 [ 0 -1 0 -1 1 1 0] As same as solving an SVP, you can solve CVP to target t using ENUM_CVP(t):
import PythonLatticeLibrary as PLL import numpy as np b = PLL.random_lattice(7) t = np.random.randint(1, 20, size=7) b.print() print(t) b.basis = b.LLL() # LLL-reduction v = b.ENUM_CVP(t) print(v)Output is below:
Basis = [[885 0 0 0 0 0 0] [799 1 0 0 0 0 0] [566 0 1 0 0 0 0] [766 0 0 1 0 0 0] [650 0 0 0 1 0 0] [654 0 0 0 0 1 0] [541 0 0 0 0 0 1]] Rank = 7 Volume = 884.9999999999998 [18 1 4 17 18 9 15] [17 2 5 17 18 8 15] Available functions in this library are below(This is not a list of all functions in this library):
vol(): Computes volume of the lattice.GSO(): Computes Gram-Schmidt information of the lattice basis.potential(): Computes potential of the lattice basis.size(): Size-reduces the lattice basis.Gauss(): Gauss-reduces the 2-dimensional lattice basis.LLL(delta): LLL-reduces the lattice basis.DeepLLL(delta): Deep-LLL-reduces the lattice basis.ENUM_SVP(): Enumerates the shortest vector on the lattice.Babai(t): Computes an approximate solution of CVP to target t on the lattice with Babai's nearest plane algorithm.ENUM_CVP(t): Enumerates the closest vector to target t on the lattice.