fpLLL library

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:

  • Martin Albrecht (2007-10) initial release
  • Martin Albrecht (2014-03) update to fpLLL 4.0 interface
class sage.libs.fplll.fplll.FP_LLL

Bases: object

A basic wrapper class to support conversion to/from Sage integer matrices and executing LLL/BKZ computations.

BKZ(block_size, delta='LLL_DEF_DELTA', float_type=None, precision=0, max_loops=0, max_time=0, verbose=False, no_lll=False, bounded_lll=False, auto_abort=False)

Run BKZ reduction.

INPUT:

  • block_size – an integer from 1 to nrows
  • delta – (default: 0.99) LLL parameter \(0.25 < \delta < 1.0\)
  • float_type – (default: None) can be one of the following:
    • None - for automatic choice
    • 'double'
    • 'long double'
    • 'dpe'
    • 'mpfr'
  • verbose – (default: False) be verbose
  • no_lll – (default: False) to use LLL
  • bounded_lll – (default: False) bounded LLL
  • precision – (default: 0 for automatic choice) bit precision to use if fp is 'rr'
  • max_loops – (default: 0 for no restriction) maximum number of full loops
  • max_time – (default: 0 for no restricion) stop after time seconds (up to loop completion)
  • auto_abort – (default: False) heuristic, stop when the average slope of \(\log(\lVert b_i^* \rVert)\) does not decrease fast enough

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...
HKZ()

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(delta='LLL_DEF_DELTA', eta='LLL_DEF_ETA', method=None, float_type=None, precision=0, verbose=False, siegel=False, early_red=False)

\((\delta,\eta)\)-LLL reduce this lattice.

INPUT:

  • delta – (default: 0.99) parameter \(0.25 < \delta < 1.0\)
  • eta `` -- (default: ``0.51) parameter \(0.5 \leq \eta < \sqrt{\delta}\)
  • method – (default: None) can be one of the following:
    • 'wrapper' (None)
    • 'proved'
    • 'fast'
    • 'heuristic'
  • float_type – (default: None) can be one of the following:
    • None - for automatic choice
    • 'double'
    • 'long double'
    • 'dpe'
    • 'mpfr'
  • precision – (default: 0 for automatic choice) precision to use
  • verbose – (default: False) be verbose
  • siegel – (default: False) use Siegel conditioning
  • early_red – (default: False) use early reduction

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
fast(precision=0, eta=0.51, delta=0.99, implementation=None)

Perform LLL reduction using fpLLL’s fast implementation. This implementation is the fastest floating point implementation currently available in the free software world.

INPUT:

  • precision – (default: auto) internal precision
  • eta – (default: 0.51) LLL parameter \(\eta\) with \(1/2 \leq \eta < \sqrt{\delta}\)
  • delta – (default: 0.99) LLL parameter \(\delta\) with \(1/4 < \delta \leq 1\)
  • implementation – ignored

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
fast_early_red(precision=0, eta=0.51, delta=0.99, implementation=None)

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:

  • precision – (default: auto) internal precision
  • eta – (default: 0.51) LLL parameter \(\eta\) with \(1/2 \leq \eta < \sqrt{\delta}\)
  • delta – (default: 0.99) LLL parameter \(\delta\) with \(1/4 < \delta \leq 1\)
  • implementation – (default: "mpfr") which floating point implementation to use, can be one of the following:
    • "double"
    • "dpe"
    • "mpfr"

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
heuristic(precision=0, eta=0.51, delta=0.99, implementation=None)

Perform LLL reduction using fpLLL’s heuristic implementation.

INPUT:

  • precision – (default: auto) internal precision
  • eta – (default: 0.51) LLL parameter \(\eta\) with \(1/2 \leq \eta < \sqrt{\delta}\)
  • delta – (default: 0.99) LLL parameter \(\delta\) with \(1/4 < \delta \leq 1\)
  • implementation – (default: "mpfr") which floating point implementation to use, can be one of the following:
    • "double"
    • "dpe"
    • "mpfr"

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
heuristic_early_red(precision=0, eta=0.51, delta=0.99, implementation=None)

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:

  • precision – (default: auto) internal precision
  • eta – (default: 0.51) LLL parameter \(\eta\) with \(1/2 \leq \eta < \sqrt{\delta}\)
  • delta – (default: 0.99) LLL parameter \(\delta\) with \(1/4 < \delta \leq 1\)
  • implementation – (default: "mpfr") which floating point implementation to use, can be one of the following:
    • "double"
    • "dpe"
    • "mpfr"

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
proved(precision=0, eta=0.51, delta=0.99, implementation=None)

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:

  • precision – (default: auto) internal precision
  • eta – (default: 0.51) LLL parameter \(\eta\) with \(1/2 \leq \eta < \sqrt{δ}\)
  • delta – (default: 0.99) LLL parameter \(\delta\) with \(1/4 < \delta \leq 1\)
  • implementation – (default: "mpfr") which floating point implementation to use, can be one of the following:
    • "double"
    • "dpe"
    • "mpfr"

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
shortest_vector(method=None)

Return a shortest vector.

INPUT:

  • method - (default: "proved") "proved" or "fast"

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
wrapper(precision=0, eta=0.51, delta=0.99)

Perform LLL reduction using fpLLL’s code{wrapper} implementation. This implementation invokes a sequence of floating point LLL computations such that

  • the computation is reasonably fast (based on an heuristic model)
  • the result is proven to be LLL reduced.

INPUT:

  • precision – (default: auto) internal precision
  • eta – (default: 0.51) LLL parameter \(\eta\) with \(1/2 \leq \eta < \sqrt{\delta}\)
  • delta – (default: 0.99) LLL parameter \(\delta\) with \(1/4 < \delta \leq 1\)

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
sage.libs.fplll.fplll.gen_ajtai(d, alpha)

Return Ajtai-like \((d \times d)\)-matrix of floating point parameter \(\alpha\). The matrix is lower-triangular, \(B_{imi}\) is \(~2^{ (d-i+1)^{\alpha} }\) and \(B_{i,j}\) is \(~B_{j,j} / 2\) for \(j < i\).

INPUT:

  • d – dimension
  • alpha – the \(\alpha\) above

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
sage.libs.fplll.fplll.gen_intrel(d, b)

Return a \((d+1 \times d)\)-dimensional knapsack-type random lattice, where the \(x_i\)‘s are random b bits integers.

INPUT:

  • d – dimension
  • b – bitsize of entries

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
sage.libs.fplll.fplll.gen_ntrulike(d, b, q)

Generate a NTRU-like lattice of dimension \((2d \times 2d)\), with the coefficients \(h_i\) chosen as random \(b\) bits integers and parameter \(q\):

[[ 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:

  • d – dimension
  • b – bitsize of entries
  • q – the \(q\) above

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
sage.libs.fplll.fplll.gen_ntrulike2(d, b, q)

Like gen_ntrulike() but with the \(q\) 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
sage.libs.fplll.fplll.gen_simdioph(d, b, b2)

Return a d-dimensional simultaneous diophantine approximation random lattice, where the d \(x_i\)‘s are random b bits integers.

INPUT:

  • d – dimension
  • b – bitsize of entries
  • b2 – bitsize of entries

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
sage.libs.fplll.fplll.gen_uniform(nr, nc, b)

Return a \((nr \times nc)\) matrix where the entries are random b bits integers.

INPUT:

  • nr – row dimension
  • nc – column dimension
  • b – bitsize of entries

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

Previous topic

FLINT fmpz_poly class wrapper

Next topic

The Elliptic Curve Method for Integer Factorization (ECM)

This Page