Damien Stehle’s fpLLL

[Santanu Sarkar]

Can you please tell me  how I can use fplll( Damien Stehle’s fpLLL) in SAGE.
There are some codes like this:
sage:from sage . libs . fplll . fplll  import gen_ntrulike
sage : A = gen_ntru like (200 ,130 ,35)
sage : time  B = A .LLL( )
But how can I  reduce a matrix which is given by me?

[mabshoff]

On Feb 27, 5:10 am, Santanu Sarkar <sarkar.santanu....@gmail.com>
wrote:

You do not need to import anything explicit. See the following code to
access the LLL docstring:

sage: A=random_matrix(ZZ,10)
sage: A.LLL?

The last command will show you all the various options there are, i.e.
which algorithm to use (it defaults to fpLLL) and some examples how to
use this code.

Let us know if this is not what you wanted.

Cheers,

Michael

[Santanu Sarkar]

No since in matrix dimension is (200,200). And entries are of the order of  2^500.
So using just LLL algorithm takes much time.  Hence I want to use  Damien Stehle’s fpLLL
(currently the world’s best).

[mabshoff]

On Feb 27, 5:41 am, Santanu Sarkar <sarkar.santanu....@gmail.com>
wrote:

> No since in matrix dimension is (200,200). And entries are of the order of
> 2^500.
> So using just LLL algorithm takes much time.  Hence I want to use  Damien
> Stehle’s fpLLL
> (currently the world’s best).

Have you read the docstring of A.LLL? To quote the algorithm keyword

- ``algorithm`` - string (default: "fpLLL:wrapper")
one of the algorithms mentioned below

And this refers to the "AVAILABLE ALGORITHMS" section:

AVAILABLE ALGORITHMS:

- ``NTL:LLL`` - NTL's LLL + fp

- ``fpLLL:heuristic`` - fpLLL's heuristic + fp

- ``fpLLL:fast`` - fpLLL's fast

- ``fpLLL:wrapper`` - fpLLL's automatic choice
(default)

And there is is clearly mentioned that fpLLL is used *per default*
when doing a LLL reduction.

Cheers,

Michael

In detail for your reading please:

Returns LLL reduced or approximated LLL reduced lattice R
for this
matrix interpreted as a lattice.

A lattice `(b_1, b_2, ..., b_d)` is
`(delta, eta)` -LLL-reduced if the two following
conditions hold:

- For any `i>j`, we have `|mu_{i, j}| <= eta`,
- For any `i<d`, we have
`delta |b_i^*|^2 <= |b_{i + 1}^* + mu_{i + 1, i} b_i^* |
^2`,

where `mu_{i,j} = <b_i, b_j^*>/<b_j^*,b_j^*>` and
`b_i^*` is the `i`-th vector of the Gram-Schmidt
orthogonalisation of `(b_1, b_2, ..., b_d)`.

The default reduction parameters are `delta=3/4` and
`eta=0.501`. The parameters `delta` and
`eta` must satisfy: `0.25 < delta <= 1.0` and
`0.5 <= eta < sqrt(delta)`. Polynomial time
complexity is only guaranteed for `delta < 1`.

The lattice is returned as a matrix. Also the rank (and
the
determinant) of self are cached if those are computed
during the
reduction. Note that in general this only happens when
self.rank()
== self.ncols() and the exact algorithm is used.

INPUT:


- ``delta`` - parameter as described above (default:
3/4)

- ``eta`` - parameter as described above (default:
0.501), ignored by NTL

- ``algorithm`` - string (default: "fpLLL:wrapper")
one of the algorithms mentioned below

- ``fp``

- None - NTL's exact reduction or fpLLL's
wrapper

- ``'fp'`` - double precision: NTL's FP or fpLLL's
double

- ``'qd'`` - quad doubles: NTL's QP

- ``'xd'`` - extended exponent: NTL's XD or fpLLL's
dpe

- ``'rr'`` - arbitrary precision: NTL'RR or fpLLL's
MPFR

- ``prec`` - precision, ignored by NTL (default: auto
choose)

- ``early_red`` - perform early reduction, ignored by
NTL (default: False)

- ``use_givens`` - use Givens orthogonalization
(default: False) only applicable to approximate
reductions and NTL.
This is more stable but slower.

Also, if the verbose level is = 2, some more verbose
output is
printed during the calculation if NTL is used.

AVAILABLE ALGORITHMS:

- ``NTL:LLL`` - NTL's LLL + fp

- ``fpLLL:heuristic`` - fpLLL's heuristic + fp

- ``fpLLL:fast`` - fpLLL's fast

- ``fpLLL:wrapper`` - fpLLL's automatic choice
(default)


OUTPUT: a matrix over the integers

EXAMPLE::

sage: A = Matrix(ZZ,3,3,range(1,10))
sage: A.LLL()
[ 0 0 0]
[ 2 1 0]
[-1 1 3]

[Santanu Sarkar]

Thank you very much