Discrete Subgroups of \(\ZZ^n\)¶
AUTHORS:
Martin Albrecht (2014-03): initial version
Jan Pöschko (2012-08): some code in this module was taken from Jan Pöschko’s 2012 GSoC project
-
class
sage.modules.free_module_integer.
FreeModule_submodule_with_basis_integer
(ambient, basis, check=True, echelonize=False, echelonized_basis=None, already_echelonized=False, lll_reduce=True)¶ Bases:
sage.modules.free_module.FreeModule_submodule_with_basis_pid
This class represents submodules of \(\ZZ^n\) with a distinguished basis.
However, most functionality in excess of standard submodules over PID is for these submodules considered as discrete subgroups of \(\ZZ^n\), i.e. as lattices. That is, this class provides functions for computing LLL and BKZ reduced bases for this free module with respect to the standard Euclidean norm.
EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: L = IntegerLattice(sage.crypto.gen_lattice(type='modular', m=10, seed=1337, dual=True)); L Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [-1 1 2 -2 0 1 0 -1 2 1] [ 1 0 0 -1 -2 1 -2 3 -1 0] [ 1 2 0 2 -1 1 -2 2 2 0] [ 1 0 -1 0 2 3 0 0 -1 -2] [ 1 -3 0 0 2 1 -2 -1 0 0] [-3 0 -1 0 -1 2 -2 0 0 2] [ 0 0 0 1 0 2 -3 -3 -2 -1] [ 0 -1 -4 -1 -1 1 2 -1 0 1] [ 1 1 -2 1 1 2 1 1 -2 3] [ 2 -1 1 2 -3 2 2 1 0 1] sage: L.shortest_vector() (-1, 1, 2, -2, 0, 1, 0, -1, 2, 1)
-
BKZ
(*args, **kwds)¶ Return a Block Korkine-Zolotareff reduced basis for
self
.INPUT:
*args
– passed through tosage.matrix.matrix_integer_dense.Matrix_integer_dense.BKZ()
*kwds
– passed through tosage.matrix.matrix_integer_dense.Matrix_integer_dense.BKZ()
OUTPUT:
An integer matrix which is a BKZ-reduced basis for this lattice.
EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: A = sage.crypto.gen_lattice(type='random', n=1, m=60, q=2^60, seed=42) sage: L = IntegerLattice(A, lll_reduce=False) sage: min(v.norm().n() for v in L.reduced_basis) 4.17330740711759e15 sage: L.LLL() 60 x 60 dense matrix over Integer Ring (use the '.str()' method to see the entries) sage: min(v.norm().n() for v in L.reduced_basis) 5.19615242270663 sage: L.BKZ(block_size=10) 60 x 60 dense matrix over Integer Ring (use the '.str()' method to see the entries) sage: min(v.norm().n() for v in L.reduced_basis) 4.12310562561766
Note
If
block_size == L.rank()
whereL
is this lattice, then this function performs Hermite-Korkine-Zolotareff (HKZ) reduction.
-
HKZ
(*args, **kwds)¶ Hermite-Korkine-Zolotarev (HKZ) reduce the basis.
A basis \(B\) of a lattice \(L\), with orthogonalized basis \(B^*\) such that \(B = M \cdot B^*\) is HKZ reduced, if and only if, the following properties are satisfied:
The basis \(B\) is size-reduced, i.e., all off-diagonal coefficients of \(M\) satisfy \(|\mu_{i,j}| \leq 1/2\)
The vector \(b_1\) realizes the first minimum \(\lambda_1(L)\).
The projection of the vectors \(b_2, \ldots,b_r\) orthogonally to \(b_1\) form an HKZ reduced basis.
Note
This is realized by calling
sage.modules.free_module_integer.FreeModule_submodule_with_basis_integer.BKZ()
withblock_size == self.rank()
.INPUT:
OUTPUT:
An integer matrix which is a HKZ-reduced basis for this lattice.
EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: L = sage.crypto.gen_lattice(type='random', n=1, m=40, q=2^60, seed=1337, lattice=True) sage: L.HKZ() 40 x 40 dense matrix over Integer Ring (use the '.str()' method to see the entries) sage: L.reduced_basis[0] (0, 0, -1, -1, 0, 0, -1, 1, 0, 0, -1, 1, 1, 0, 0, 1, 1, 1, -1, 0, 0, 1, -1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 0, 1, 1, 0, 0, -2)
-
LLL
(*args, **kwds)¶ Return an LLL reduced basis for
self
.A lattice basis \((b_1, b_2, ..., b_d)\) is \((\delta, \eta)\)-LLL-reduced if the two following conditions hold:
For any \(i > j\), we have \(\lvert \mu_{i, j} \rvert \leq η\).
For any \(i < d\), we have \(\delta \lvert b_i^* \rvert^2 \leq \lvert b_{i+1}^* + \mu_{i+1, i} b_i^* \rvert^2\),
where \(\mu_{i,j} = \langle b_i, b_j^* \rangle / \langle b_j^*,b_j^* \rangle\) and \(b_i^*\) is the \(i\)-th vector of the Gram-Schmidt orthogonalisation of \((b_1, b_2, \ldots, b_d)\).
The default reduction parameters are \(\delta = 3/4\) and \(\eta = 0.501\).
The parameters \(\delta\) and \(\eta\) must satisfy: \(0.25 < \delta \leq 1.0\) and \(0.5 \leq \eta < \sqrt{\delta}\). Polynomial time complexity is only guaranteed for \(\delta < 1\).
INPUT:
*args
– passed through tosage.matrix.matrix_integer_dense.Matrix_integer_dense.LLL()
**kwds
– passed through tosage.matrix.matrix_integer_dense.Matrix_integer_dense.LLL()
OUTPUT:
An integer matrix which is an LLL-reduced basis for this lattice.
EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: A = random_matrix(ZZ, 10, 10, x=-2000, y=2000) sage: L = IntegerLattice(A, lll_reduce=False); L Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [ -645 -1037 -1775 -1619 1721 -1434 1766 1701 1669 1534] [ 1303 960 1998 -1838 1683 -1332 149 327 -849 -1562] [-1113 -1366 1379 669 54 1214 -1750 -605 -1566 1626] [-1367 1651 926 1731 -913 627 669 -1437 -132 1712] [ -549 1327 -1353 68 1479 -1803 -456 1090 -606 -317] [ -221 -1920 -1361 1695 1139 111 -1792 1925 -656 1992] [-1934 -29 88 890 1859 1820 -1912 -1614 -1724 1606] [ -590 -1380 1768 774 656 760 -746 -849 1977 -1576] [ 312 -242 -1732 1594 -439 -1069 458 -1195 1715 35] [ 391 1229 -1815 607 -413 -860 1408 1656 1651 -628] sage: min(v.norm().n() for v in L.reduced_basis) 3346.57... sage: L.LLL() [ -888 53 -274 243 -19 431 710 -83 928 347] [ 448 -330 370 -511 242 -584 -8 1220 502 183] [ -524 -460 402 1338 -247 -279 -1038 -28 -159 -794] [ 166 -190 -162 1033 -340 -77 -1052 1134 -843 651] [ -47 -1394 1076 -132 854 -151 297 -396 -580 -220] [-1064 373 -706 601 -587 -1394 424 796 -22 -133] [-1126 398 565 -1418 -446 -890 -237 -378 252 247] [ -339 799 295 800 425 -605 -730 -1160 808 666] [ 755 -1206 -918 -192 -1063 -37 -525 -75 338 400] [ 382 -199 -1839 -482 984 -15 -695 136 682 563] sage: L.reduced_basis[0].norm().n() 1613.74...
-
closest_vector
(t)¶ Compute the closest vector in the embedded lattice to a given vector.
INPUT:
t
– the target vector to compute the closest vector to
OUTPUT:
The vector in the lattice closest to
t
.EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: L = IntegerLattice([[1, 0], [0, 1]]) sage: L.closest_vector((-6, 5/3)) (-6, 2)
ALGORITHM:
Uses the algorithm from [MV2010].
-
discriminant
()¶ Return \(|\det(G)|\), i.e. the absolute value of the determinant of the Gram matrix \(B \cdot B^T\) for any basis \(B\).
OUTPUT:
An integer.
EXAMPLES:
sage: L = sage.crypto.gen_lattice(m=10, seed=1337, lattice=True) sage: L.discriminant() 214358881
-
is_unimodular
()¶ Return
True
if this lattice is unimodular.OUTPUT:
A boolean.
EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: L = IntegerLattice([[1, 0], [0, 1]]) sage: L.is_unimodular() True sage: IntegerLattice([[2, 0], [0, 3]]).is_unimodular() False
-
reduced_basis
¶ This attribute caches the currently best known reduced basis for
self
, where “best” is defined by the Euclidean norm of the first row vector.EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: L = IntegerLattice(random_matrix(ZZ, 10, 10), lll_reduce=False) sage: L.reduced_basis [ -8 2 0 0 1 -1 2 1 -95 -1] [ -2 -12 0 0 1 -1 1 -1 -2 -1] [ 4 -4 -6 5 0 0 -2 0 1 -4] [ -6 1 -1 1 1 -1 1 -1 -3 1] [ 1 0 0 -3 2 -2 0 -2 1 0] [ -1 1 0 0 1 -1 4 -1 1 -1] [ 14 1 -5 4 -1 0 2 4 1 1] [ -2 -1 0 4 -3 1 -5 0 -2 -1] [ -9 -1 -1 3 2 1 -1 1 -2 1] [ -1 2 -7 1 0 2 3 -1955 -22 -1] sage: _ = L.LLL() sage: L.reduced_basis [ 1 0 0 -3 2 -2 0 -2 1 0] [ -1 1 0 0 1 -1 4 -1 1 -1] [ -2 0 0 1 0 -2 -1 -3 0 -2] [ -2 -2 0 -1 3 0 -2 0 2 0] [ 1 1 1 2 3 -2 -2 0 3 1] [ -4 1 -1 0 1 1 2 2 -3 3] [ 1 -3 -7 2 3 -1 0 0 -1 -1] [ 1 -9 1 3 1 -3 1 -1 -1 0] [ 8 5 19 3 27 6 -3 8 -25 -22] [ 172 -25 57 248 261 793 76 -839 -41 376]
-
shortest_vector
(update_reduced_basis=True, algorithm='fplll', *args, **kwds)¶ Return a shortest vector.
INPUT:
update_reduced_basis
– (default:True
) set this flag if the found vector should be used to improve the basisalgorithm
– (default:"fplll"
) either"fplll"
or"pari"
*args
– passed through to underlying implementation**kwds
– passed through to underlying implementation
OUTPUT:
A shortest non-zero vector for this lattice.
EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: A = sage.crypto.gen_lattice(type='random', n=1, m=30, q=2^40, seed=42) sage: L = IntegerLattice(A, lll_reduce=False) sage: min(v.norm().n() for v in L.reduced_basis) 6.03890756700000e10 sage: L.shortest_vector().norm().n() 3.74165738677394 sage: L = IntegerLattice(A, lll_reduce=False) sage: min(v.norm().n() for v in L.reduced_basis) 6.03890756700000e10 sage: L.shortest_vector(algorithm="pari").norm().n() 3.74165738677394 sage: L = IntegerLattice(A, lll_reduce=True) sage: L.shortest_vector(algorithm="pari").norm().n() 3.74165738677394
-
update_reduced_basis
(w)¶ Inject the vector
w
and run LLL to update the basis.INPUT:
w
– a vector
OUTPUT:
Nothing is returned but the internal state is modified.
EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: A = sage.crypto.gen_lattice(type='random', n=1, m=30, q=2^40, seed=42) sage: L = IntegerLattice(A) sage: B = L.reduced_basis sage: v = L.shortest_vector(update_reduced_basis=False) sage: L.update_reduced_basis(v) sage: bool(L.reduced_basis[0].norm() < B[0].norm()) True
-
volume
()¶ Return \(vol(L)\) which is \(\sqrt{\det(B \cdot B^T)}\) for any basis \(B\).
OUTPUT:
An integer.
EXAMPLES:
sage: L = sage.crypto.gen_lattice(m=10, seed=1337, lattice=True) sage: L.volume() 14641
-
voronoi_cell
(radius=None)¶ Compute the Voronoi cell of a lattice, returning a Polyhedron.
INPUT:
radius
– (default: automatic determination) radius of ball containing considered vertices
OUTPUT:
The Voronoi cell as a Polyhedron instance.
The result is cached so that subsequent calls to this function return instantly.
EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: L = IntegerLattice([[1, 0], [0, 1]]) sage: V = L.voronoi_cell() sage: V.Vrepresentation() (A vertex at (1/2, -1/2), A vertex at (1/2, 1/2), A vertex at (-1/2, 1/2), A vertex at (-1/2, -1/2))
The volume of the Voronoi cell is the square root of the discriminant of the lattice:
sage: L = IntegerLattice(Matrix(ZZ, 4, 4, [[0,0,1,-1],[1,-1,2,1],[-6,0,3,3,],[-6,-24,-6,-5]])); L Free module of degree 4 and rank 4 over Integer Ring User basis matrix: [ 0 0 1 -1] [ 1 -1 2 1] [ -6 0 3 3] [ -6 -24 -6 -5] sage: V = L.voronoi_cell() # long time sage: V.volume() # long time 678 sage: sqrt(L.discriminant()) 678
Lattices not having full dimension are handled as well:
sage: L = IntegerLattice([[2, 0, 0], [0, 2, 0]]) sage: V = L.voronoi_cell() sage: V.Hrepresentation() (An inequality (-1, 0, 0) x + 1 >= 0, An inequality (0, -1, 0) x + 1 >= 0, An inequality (1, 0, 0) x + 1 >= 0, An inequality (0, 1, 0) x + 1 >= 0)
ALGORITHM:
Uses parts of the algorithm from [VB1996].
-
voronoi_relevant_vectors
()¶ Compute the embedded vectors inducing the Voronoi cell.
OUTPUT:
The list of Voronoi relevant vectors.
EXAMPLES:
sage: from sage.modules.free_module_integer import IntegerLattice sage: L = IntegerLattice([[3, 0], [4, 0]]) sage: L.voronoi_relevant_vectors() [(-1, 0), (1, 0)]
-
-
sage.modules.free_module_integer.
IntegerLattice
(basis, lll_reduce=True)¶ Construct a new integer lattice from
basis
.INPUT:
basis
– can be one of the following:a list of vectors
a matrix over the integers
an element of an absolute order
lll_reduce
– (default:True
) run LLL reduction on the basis on construction.
EXAMPLES:
We construct a lattice from a list of rows:
sage: from sage.modules.free_module_integer import IntegerLattice sage: IntegerLattice([[1,0,3], [0,2,1], [0,2,7]]) Free module of degree 3 and rank 3 over Integer Ring User basis matrix: [-2 0 0] [ 0 2 1] [ 1 -2 2]
Sage includes a generator for hard lattices from cryptography:
sage: from sage.modules.free_module_integer import IntegerLattice sage: A = sage.crypto.gen_lattice(type='modular', m=10, seed=1337, dual=True) sage: IntegerLattice(A) Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [-1 1 2 -2 0 1 0 -1 2 1] [ 1 0 0 -1 -2 1 -2 3 -1 0] [ 1 2 0 2 -1 1 -2 2 2 0] [ 1 0 -1 0 2 3 0 0 -1 -2] [ 1 -3 0 0 2 1 -2 -1 0 0] [-3 0 -1 0 -1 2 -2 0 0 2] [ 0 0 0 1 0 2 -3 -3 -2 -1] [ 0 -1 -4 -1 -1 1 2 -1 0 1] [ 1 1 -2 1 1 2 1 1 -2 3] [ 2 -1 1 2 -3 2 2 1 0 1]
You can also construct the lattice directly:
sage: from sage.modules.free_module_integer import IntegerLattice sage: sage.crypto.gen_lattice(type='modular', m=10, seed=1337, dual=True, lattice=True) Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [-1 1 2 -2 0 1 0 -1 2 1] [ 1 0 0 -1 -2 1 -2 3 -1 0] [ 1 2 0 2 -1 1 -2 2 2 0] [ 1 0 -1 0 2 3 0 0 -1 -2] [ 1 -3 0 0 2 1 -2 -1 0 0] [-3 0 -1 0 -1 2 -2 0 0 2] [ 0 0 0 1 0 2 -3 -3 -2 -1] [ 0 -1 -4 -1 -1 1 2 -1 0 1] [ 1 1 -2 1 1 2 1 1 -2 3] [ 2 -1 1 2 -3 2 2 1 0 1]
We construct an ideal lattice from an element of an absolute order:
sage: K.<a> = CyclotomicField(17) sage: O = K.ring_of_integers() sage: f = O(-a^15 + a^13 + 4*a^12 - 12*a^11 - 256*a^10 + a^9 - a^7 - 4*a^6 + a^5 + 210*a^4 + 2*a^3 - 2*a^2 + 2*a - 2) sage: from sage.modules.free_module_integer import IntegerLattice sage: IntegerLattice(f) Free module of degree 16 and rank 16 over Integer Ring User basis matrix: [ -2 2 -2 2 210 1 -4 -1 0 1 -256 -12 4 1 0 -1] [ 33 48 44 48 256 -209 28 51 45 49 -1 35 44 48 44 48] [ 1 -1 3 -1 3 211 2 -3 0 1 2 -255 -11 5 2 1] [-223 34 50 47 258 0 29 45 46 47 2 -11 33 48 44 48] [ -13 31 46 42 46 -2 -225 32 48 45 256 -2 27 43 44 45] [ -16 33 42 46 254 1 -19 32 44 45 0 -13 -225 32 48 45] [ -15 -223 30 50 255 1 -20 32 42 47 -2 -11 -15 33 44 44] [ -11 -11 33 48 256 3 -17 -222 32 53 1 -9 -14 35 44 48] [ -12 -13 32 45 257 0 -16 -13 32 48 -1 -10 -14 -222 31 51] [ -9 -13 -221 32 52 1 -11 -12 33 46 258 1 -15 -12 33 49] [ -5 -2 -1 0 -257 -13 3 0 -1 -2 -1 -3 1 -3 1 209] [ -15 -11 -15 33 256 -1 -17 -14 -225 33 4 -12 -13 -14 31 44] [ 11 11 11 11 -245 -3 17 10 13 220 12 5 12 9 14 -35] [ -18 -15 -20 29 250 -3 -23 -16 -19 30 -4 -17 -17 -17 -229 28] [ -15 -11 -15 -223 242 5 -18 -12 -16 34 -2 -11 -15 -11 -15 33] [ 378 120 92 147 152 462 136 96 99 144 -52 412 133 91 -107 138]
We construct \(\ZZ^n\):
sage: from sage.modules.free_module_integer import IntegerLattice sage: IntegerLattice(ZZ^10) Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [1 0 0 0 0 0 0 0 0 0] [0 1 0 0 0 0 0 0 0 0] [0 0 1 0 0 0 0 0 0 0] [0 0 0 1 0 0 0 0 0 0] [0 0 0 0 1 0 0 0 0 0] [0 0 0 0 0 1 0 0 0 0] [0 0 0 0 0 0 1 0 0 0] [0 0 0 0 0 0 0 1 0 0] [0 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 0 0 0 0 1]
Sage also interfaces with fpylll’s lattice generator:
sage: from sage.modules.free_module_integer import IntegerLattice sage: from fpylll import IntegerMatrix sage: A = IntegerMatrix.random(8, "simdioph", bits=20, bits2=10) sage: A = A.to_matrix(matrix(ZZ, 8, 8)) sage: IntegerLattice(A, lll_reduce=False) Free module of degree 8 and rank 8 over Integer Ring User basis matrix: [ 1024 829556 161099 11567 521155 769480 639201 689979] [ 0 1048576 0 0 0 0 0 0] [ 0 0 1048576 0 0 0 0 0] [ 0 0 0 1048576 0 0 0 0] [ 0 0 0 0 1048576 0 0 0] [ 0 0 0 0 0 1048576 0 0] [ 0 0 0 0 0 0 1048576 0] [ 0 0 0 0 0 0 0 1048576]