fpLLL library
Wrapper for the fpLLL library by Damien Stehle, Xavier Pujol and David Cade found at http://perso.ens-lyon.fr/damien.stehle/fplll/.
This wrapper provides access to fpLLL’s LLL, BKZ and enumeration implementations.
AUTHORS:
Bases: object
A basic wrapper class to support conversion to/from Sage integer matrices and executing LLL/BKZ computations.
Run BKZ reduction.
INPUT:
OUTPUT:
Nothing is returned but the internal state is modified.
EXAMPLES:
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = sage.crypto.gen_lattice(type='random', n=1, m=60, q=2^90, seed=42)
sage: F = FP_LLL(A)
sage: F.LLL()
sage: F._sage_()[0].norm().n()
7.810...
sage: F.BKZ(10)
sage: F._sage_()[0].norm().n()
6.164...
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = sage.crypto.gen_lattice(type='random', n=1, m=60, q=2^90, seed=42)
sage: F = FP_LLL(A)
sage: F.BKZ(10, max_loops=10, verbose=True)
====== Wrapper: calling fast<mpz_t,double> method ======
...
loops limit exceeded in BKZ
sage: F._sage_()[0].norm().n()
6.480...
Run HKZ reduction.
OUTPUT:
Nothing is returned but the internal state is modified.
EXAMPLE:
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = sage.crypto.gen_lattice(type='random', n=1, m=10, q=2^60, seed=42)
sage: F = FP_LLL(A)
sage: F.HKZ()
sage: F._sage_()
[ -8 27 7 19 10 -5 14 34 4 -18]
[-22 23 3 -14 11 30 -12 26 17 26]
[-20 6 -18 33 -26 16 8 -15 -14 -26]
[ -2 30 9 -30 -28 -19 -7 -28 12 -15]
[-16 1 25 -23 -11 -21 -39 4 -34 -13]
[-27 -2 -24 -67 32 -13 -6 0 15 -4]
[ 9 -12 7 31 22 -7 -63 11 27 36]
[ 14 -4 0 -21 -17 -7 -9 35 79 -22]
[-17 -16 54 21 0 -17 28 -45 -6 12]
[ 43 16 6 30 24 17 -39 -46 -18 -22]
-LLL reduce this lattice.
INPUT:
OUTPUT:
Nothing is returned but the internal state is modified.
EXAMPLES:
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = random_matrix(ZZ,10,10); A
[ -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: F = FP_LLL(A)
sage: F.LLL(method="wrapper")
sage: L = F._sage_(); L
[ 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]
sage: L.is_LLL_reduced()
True
sage: L.hermite_form() == A.hermite_form()
True
sage: set_random_seed(0)
sage: A = random_matrix(ZZ,10,10); A
[ -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: F = FP_LLL(A)
sage: F.LLL(method="proved")
sage: L = F._sage_(); L
[ 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]
sage: L.is_LLL_reduced()
True
sage: L.hermite_form() == A.hermite_form()
True
sage: A = random_matrix(ZZ,10,10,x=-(10^5),y=10^5)
sage: f = FP_LLL(A)
sage: f.LLL(method="fast")
sage: L = f._sage_()
sage: L.is_LLL_reduced(eta=0.51,delta=0.99)
True
sage: L.hermite_form() == A.hermite_form()
True
sage: set_random_seed(0)
sage: A = random_matrix(ZZ,10,10); A
[ -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: F = FP_LLL(A)
sage: F.LLL(method="fast", early_red=True)
sage: L = F._sage_(); L
[ 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]
sage: L.is_LLL_reduced(eta=0.51,delta=0.99)
True
sage: L.hermite_form() == A.hermite_form()
True
sage: set_random_seed(0)
sage: A = random_matrix(ZZ,10,10); A
[ -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: F = FP_LLL(A)
sage: F.LLL(method="heuristic")
sage: L = F._sage_(); L
[ 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]
sage: L.is_LLL_reduced(eta=0.51,delta=0.99)
True
sage: L.hermite_form() == A.hermite_form()
True
sage: set_random_seed(0)
sage: A = random_matrix(ZZ,10,10); A
[ -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: F = FP_LLL(A)
sage: F.LLL(method="heuristic", early_red=True)
sage: L = F._sage_(); L
[ 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]
sage: L.is_LLL_reduced(eta=0.51,delta=0.99)
True
sage: L.hermite_form() == A.hermite_form()
True
Perform LLL reduction using fpLLL’s fast implementation. This implementation is the fastest floating point implementation currently available in the free software world.
INPUT:
OUTPUT:
Nothing is returned but the internal is state modified.
EXAMPLE:
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = random_matrix(ZZ,10,10,x=-(10^5),y=10^5)
sage: f = FP_LLL(A)
sage: f.fast()
sage: L = f._sage_()
sage: L.is_LLL_reduced(eta=0.51,delta=0.99)
True
sage: L.hermite_form() == A.hermite_form()
True
Perform LLL reduction using fpLLL’s fast implementation with early reduction.
This implementation inserts some early reduction steps inside the execution of the ‘fast’ LLL algorithm. This sometimes makes the entries of the basis smaller very quickly. It occurs in particular for lattice bases built from minimal polynomial or integer relation detection problems.
INPUT:
OUTPUT:
Nothing is returned but the internal state modified.
EXAMPLE:
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = random_matrix(ZZ,10,10); A
[ -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: F = FP_LLL(A)
sage: F.fast_early_red()
sage: L = F._sage_(); L
[ 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]
sage: L.is_LLL_reduced(eta=0.51,delta=0.99)
True
sage: L.hermite_form() == A.hermite_form()
True
Perform LLL reduction using fpLLL’s heuristic implementation.
INPUT:
OUTPUT:
Nothing is returned but the internal state modified.
EXAMPLE:
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = random_matrix(ZZ,10,10); A
[ -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: F = FP_LLL(A)
sage: F.heuristic()
sage: L = F._sage_(); L
[ 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]
sage: L.is_LLL_reduced(eta=0.51,delta=0.99)
True
sage: L.hermite_form() == A.hermite_form()
True
Perform LLL reduction using fpLLL’s heuristic implementation with early reduction.
This implementation inserts some early reduction steps inside the execution of the ‘fast’ LLL algorithm. This sometimes makes the entries of the basis smaller very quickly. It occurs in particular for lattice bases built from minimal polynomial or integer relation detection problems.
INPUT:
OUTPUT:
Nothing is returned but the internal state modified.
EXAMPLE:
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = random_matrix(ZZ,10,10); A
[ -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: F = FP_LLL(A)
sage: F.heuristic_early_red()
sage: L = F._sage_(); L
[ 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]
sage: L.is_LLL_reduced(eta=0.51,delta=0.99)
True
sage: L.hermite_form() == A.hermite_form()
True
Perform LLL reduction using fpLLL’s proved implementation. This implementation is the only provable correct floating point implementation in the free software world. Provability is only guaranteed if the 'mpfr' implementation is chosen.
INPUT:
OUTPUT:
Nothing is returned but the internal state modified.
EXAMPLE:
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = random_matrix(ZZ,10,10); A
[ -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: F = FP_LLL(A)
sage: F.proved()
sage: L = F._sage_(); L
[ 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]
sage: L.is_LLL_reduced()
True
sage: L.hermite_form() == A.hermite_form()
True
Return a shortest vector.
INPUT:
OUTPUT:
A shortest non-zero vector for this lattice.
EXAMPLE:
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = sage.crypto.gen_lattice(type='random', n=1, m=40, q=2^60, seed=42)
sage: F = FP_LLL(A)
sage: F.shortest_vector('proved') == F.shortest_vector('fast')
True
Perform LLL reduction using fpLLL’s code{wrapper} implementation. This implementation invokes a sequence of floating point LLL computations such that
INPUT:
OUTPUT:
Nothing is returned but the internal state is modified.
EXAMPLE:
sage: from sage.libs.fplll.fplll import FP_LLL
sage: A = random_matrix(ZZ,10,10); A
[ -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: F = FP_LLL(A)
sage: F.wrapper()
sage: L = F._sage_(); L
[ 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]
sage: L.is_LLL_reduced()
True
sage: L.hermite_form() == A.hermite_form()
True
Return Ajtai-like -matrix of floating point parameter
. The matrix is lower-triangular,
is
and
is
for
.
INPUT:
OUTPUT:
An integer lattice.
EXAMPLE:
sage: from sage.libs.fplll.fplll import gen_ajtai
sage: A = gen_ajtai(10, 0.7); A # random output
[117 0 0 0 0 0 0 0 0 0]
[ 11 55 0 0 0 0 0 0 0 0]
[-47 21 104 0 0 0 0 0 0 0]
[ -3 -22 -16 95 0 0 0 0 0 0]
[ -8 -21 -3 -28 55 0 0 0 0 0]
[-33 -15 -30 37 8 52 0 0 0 0]
[-35 21 41 -31 -23 10 21 0 0 0]
[ -9 20 -34 -23 -18 -13 -9 63 0 0]
[-11 14 -38 -16 -26 -23 -3 11 9 0]
[ 15 21 35 37 12 6 -2 10 1 17]
sage: L = A.LLL(); L # random output
[ 4 7 -3 21 -14 -17 -1 -1 -8 17]
[-20 0 -6 6 -11 -4 -19 10 1 17]
[-22 -1 8 -21 18 -29 3 11 9 0]
[ 31 8 20 2 -12 -4 -27 -22 -18 0]
[ -2 6 -4 7 -8 -10 6 52 -9 0]
[ 3 -7 35 -12 -29 23 3 11 9 0]
[-16 -6 -16 37 2 11 -1 -9 7 -34]
[ 11 55 0 0 0 0 0 0 0 0]
[ 11 14 38 16 26 23 3 11 9 0]
[ 13 -28 -1 7 -11 11 -12 3 54 0]
sage: L.is_LLL_reduced()
True
sage: L.hermite_form() == A.hermite_form()
True
Return a -dimensional knapsack-type random lattice,
where the
‘s are random b bits integers.
INPUT:
OUTPUT:
An integer lattice.
EXAMPLE:
sage: from sage.libs.fplll.fplll import gen_intrel
sage: A = gen_intrel(10,10); A
[116 1 0 0 0 0 0 0 0 0 0]
[331 0 1 0 0 0 0 0 0 0 0]
[303 0 0 1 0 0 0 0 0 0 0]
[963 0 0 0 1 0 0 0 0 0 0]
[456 0 0 0 0 1 0 0 0 0 0]
[225 0 0 0 0 0 1 0 0 0 0]
[827 0 0 0 0 0 0 1 0 0 0]
[381 0 0 0 0 0 0 0 1 0 0]
[ 99 0 0 0 0 0 0 0 0 1 0]
[649 0 0 0 0 0 0 0 0 0 1]
sage: L = A.LLL(); L
[ 1 1 1 0 0 0 0 -1 1 0 0]
[ 1 0 1 0 0 -1 1 0 0 -1 0]
[ 0 0 1 1 0 -1 0 -1 0 0 1]
[ 0 -1 0 -1 -1 1 0 1 0 1 0]
[-1 -1 0 -1 0 -1 1 0 0 0 1]
[ 0 1 -1 0 0 -1 1 1 -1 0 0]
[ 0 0 0 0 -1 1 1 0 1 -1 0]
[ 1 -1 -1 0 0 -1 -1 0 1 1 1]
[-1 0 0 -1 -1 0 -1 1 2 -1 0]
[-1 -1 0 0 1 0 2 0 0 0 -2]
sage: L.is_LLL_reduced()
True
sage: L.hermite_form() == A.hermite_form()
True
Generate a NTRU-like lattice of dimension , with the
coefficients
chosen as random
bits integers and parameter
:
[[ 1 0 ... 0 h0 h1 ... h_{d-1} ]
[ 0 1 ... 0 h1 h2 ... h0 ]
[ ................................ ]
[ 0 0 ... 1 h_{d-1} h0 ... h_{d-1} ]
[ 0 0 ... 0 q 0 ... 0 ]
[ 0 0 ... 0 0 q ... 0 ]
[ ................................ ]
[ 0 0 ... 0 0 0 ... q ]]
INPUT:
OUTPUT:
An integer lattice.
EXAMPLE:
sage: from sage.libs.fplll.fplll import gen_ntrulike
sage: A = gen_ntrulike(5,10,12); A
[ 1 0 0 0 0 320 351 920 714 66]
[ 0 1 0 0 0 351 920 714 66 320]
[ 0 0 1 0 0 920 714 66 320 351]
[ 0 0 0 1 0 714 66 320 351 920]
[ 0 0 0 0 1 66 320 351 920 714]
[ 0 0 0 0 0 12 0 0 0 0]
[ 0 0 0 0 0 0 12 0 0 0]
[ 0 0 0 0 0 0 0 12 0 0]
[ 0 0 0 0 0 0 0 0 12 0]
[ 0 0 0 0 0 0 0 0 0 12]
sage: L = A.LLL(); L
[-1 -1 0 0 0 1 1 -2 0 -2]
[-1 0 0 0 -1 -2 1 1 -2 0]
[ 0 -1 -1 0 0 1 -2 0 -2 1]
[ 0 0 1 1 0 2 0 2 -1 -1]
[ 0 0 0 1 1 0 2 -1 -1 2]
[-2 -1 -2 1 1 1 0 1 1 0]
[-1 -2 1 1 -2 0 1 0 1 1]
[ 2 -1 -1 2 1 -1 0 -1 0 -1]
[-1 -1 2 1 2 -1 -1 0 -1 0]
[ 1 -2 -1 -2 1 0 1 1 0 1]
sage: L.is_LLL_reduced()
True
sage: L.hermite_form() == A.hermite_form()
True
Like gen_ntrulike() but with the vectors coming first.
INPUT:
OUTPUT:
An integer lattice.
EXAMPLE:
sage: from sage.libs.fplll.fplll import gen_ntrulike2
sage: A = gen_ntrulike2(5,10,12); A
[ 12 0 0 0 0 0 0 0 0 0]
[ 0 12 0 0 0 0 0 0 0 0]
[ 0 0 12 0 0 0 0 0 0 0]
[ 0 0 0 12 0 0 0 0 0 0]
[ 0 0 0 0 12 0 0 0 0 0]
[902 947 306 40 908 1 0 0 0 0]
[947 306 40 908 902 0 1 0 0 0]
[306 40 908 902 947 0 0 1 0 0]
[ 40 908 902 947 306 0 0 0 1 0]
[908 902 947 306 40 0 0 0 0 1]
sage: L = A.LLL(); L
[ 1 0 0 2 -3 -2 1 1 0 0]
[-1 0 -2 1 2 2 1 -2 -1 0]
[ 0 2 -1 -2 1 0 -2 -1 2 1]
[ 0 3 0 1 3 1 0 -1 1 0]
[ 2 -1 0 -2 1 1 -2 -1 0 2]
[ 0 -1 0 -1 -1 1 4 -1 -1 0]
[ 2 1 1 1 -1 -3 -2 -1 -1 -1]
[-1 0 -1 0 -1 4 -1 -1 0 1]
[ 0 1 -2 1 1 -1 0 1 -3 -2]
[-2 1 1 0 1 -3 -2 -1 0 1]
sage: L.is_LLL_reduced()
True
sage: L.hermite_form() == A.hermite_form()
True
Return a d-dimensional simultaneous diophantine approximation random
lattice, where the d ‘s are random b bits integers.
INPUT:
OUTPUT:
An integer lattice.
EXAMPLE:
sage: from sage.libs.fplll.fplll import gen_simdioph
sage: A = gen_simdioph(10,10,3); A
[ 8 395 975 566 213 694 254 629 303 597]
[ 0 1024 0 0 0 0 0 0 0 0]
[ 0 0 1024 0 0 0 0 0 0 0]
[ 0 0 0 1024 0 0 0 0 0 0]
[ 0 0 0 0 1024 0 0 0 0 0]
[ 0 0 0 0 0 1024 0 0 0 0]
[ 0 0 0 0 0 0 1024 0 0 0]
[ 0 0 0 0 0 0 0 1024 0 0]
[ 0 0 0 0 0 0 0 0 1024 0]
[ 0 0 0 0 0 0 0 0 0 1024]
sage: L = A.LLL(); L
[ 192 264 -152 272 -8 272 -48 -264 104 -8]
[-128 -176 -240 160 -336 160 32 176 272 -336]
[ -24 -161 147 350 385 -34 262 161 115 257]
[ 520 75 -113 -74 -491 54 126 -75 239 -107]
[-376 -133 255 22 229 150 350 133 95 -411]
[-168 -103 5 402 -377 -238 -214 103 -219 -249]
[-352 28 108 -328 -156 184 88 -28 -20 356]
[ 120 -219 289 298 123 170 -286 219 449 -261]
[ 160 -292 44 56 164 568 -40 292 -84 -348]
[-192 760 152 -272 8 -272 48 264 -104 8]
sage: L.is_LLL_reduced()
True
sage: L.hermite_form() == A.hermite_form()
True
Return a matrix where the entries are random b
bits integers.
INPUT:
OUTPUT:
An integer lattice.
EXAMPLE:
sage: from sage.libs.fplll.fplll import gen_uniform
sage: A = gen_uniform(10,10,12); A
[ 980 3534 533 3303 2491 2960 1475 3998 105 162]
[1766 3683 2782 668 2356 2149 1887 2327 976 1151]
[1573 438 1480 887 1490 634 3820 3379 4074 2669]
[ 215 2054 2388 3214 2459 250 2921 1395 3626 434]
[ 638 4011 3626 1864 633 1072 3651 2339 2926 1004]
[3731 439 1087 1088 2627 3446 2669 1419 563 2079]
[1868 3196 3712 4016 1451 2589 3327 712 647 1057]
[2068 2761 3479 2552 197 1258 1544 1116 3090 3667]
[1394 529 1683 1781 1779 3032 80 2712 639 3047]
[3695 3888 3139 851 2111 3375 208 3766 3925 1465]
sage: L = A.LLL(); L
[ 200 -1144 -365 755 1404 -218 -937 321 -718 790]
[ 623 813 873 -595 -422 604 -207 1265 -1418 1360]
[ -928 -816 479 1951 -319 -1295 827 333 1232 643]
[-1802 -1904 -952 425 -141 697 300 1608 -501 -767]
[ -572 -2010 -734 358 -1981 1101 -870 64 381 1106]
[ 853 -223 767 1382 -529 -780 -500 1507 -2455 -1190]
[-1016 -1755 1297 -2210 -276 -114 712 -63 370 222]
[ -430 1471 339 -513 1361 2715 2076 -646 -1406 -60]
[-3390 748 62 775 935 1697 -306 -618 88 -452]
[ 713 -1115 1887 -563 733 2443 816 972 876 -2074]
sage: L.is_LLL_reduced()
True
sage: L.hermite_form() == A.hermite_form()
True