Size reduced of a basis

35 views
Skip to first unread message

Santanu Sarkar

unread,
Mar 16, 2021, 6:17:43 PMMar 16
to sage-support
Dear all,
   In Sagemath, is it possible to change a basis 
of a lattice which is size reduced? That is my interest is only on 
1st condition of LLL basis. 
 

Kind regards,
Santanu 

Martin R. Albrecht

unread,
Mar 17, 2021, 6:18:00 AMMar 17
to sage-s...@googlegroups.com
Hi there,

You can do it by calling down to FPyLLL which (together with NTL) powers lattice reduction in Sage. Here’s an example:

#+begin_src jupyter-python :kernel sagemath
A = random_matrix(ZZ, 10, 10, x=-1, y=2)
A.echelonize() # make it interesting by turning into HNF
print("# Input")
print(A)
print()

from fpylll import IntegerMatrix, GSO, LLL
B = IntegerMatrix.from_matrix(A)
M = GSO.Mat(B)
M.update_gso()
L = LLL.Reduction(M)
L.size_reduction()
C = B.to_matrix(matrix(ZZ, 10, 10)) # back to Sage's format

print("# Output")
print(C)
print()
#+end_src

#+RESULTS:
#+begin_example
# Input
[ 1 0 0 0 0 0 0 0 0 41]
[ 0 1 0 0 0 0 0 0 0 34]
[ 0 0 1 0 0 0 0 0 1 27]
[ 0 0 0 1 0 0 0 0 1 96]
[ 0 0 0 0 1 0 0 0 0 38]
[ 0 0 0 0 0 1 0 0 1 78]
[ 0 0 0 0 0 0 1 0 1 1]
[ 0 0 0 0 0 0 0 1 1 91]
[ 0 0 0 0 0 0 0 0 2 69]
[ 0 0 0 0 0 0 0 0 0 100]

# Output
[ 1 0 0 0 0 0 0 0 0 41]
[ -1 1 0 0 0 0 0 0 0 -7]
[ -1 0 1 0 0 0 0 0 1 -14]
[ -1 -1 -1 1 0 0 0 0 0 -6]
[ -1 0 0 0 1 0 0 0 0 -3]
[ 0 0 0 -1 0 1 0 0 0 -18]
[ 0 0 0 0 0 0 1 0 1 1]
[ 0 0 0 -1 0 0 0 1 0 -5]
[ 1 0 0 -1 0 0 0 0 1 14]
[ 0 0 0 -1 0 0 0 0 -1 4]
#+end_example


Cheers,
Martin
--

_pgp: https://keybase.io/martinralbrecht
_www: https://malb.io

Santanu Sarkar

unread,
Mar 19, 2021, 1:19:12 PMMar 19
to sage-support

Hi Martin,
   Thanks a lot. For entries upto 500 bits, it works fine. 
But for large entries, I am getting error. 
A = random_matrix(ZZ, 10, 10, x=-2^550, y=2^550)
File "abc.sage.py", line 28, in <module>
    L.size_reduction()
  File "src/fpylll/fplll/lll.pyx", line 379, in fpylll.fplll.lll.LLLReduction.size_reduction
fpylll.util.ReductionError: b'success'

Kind regards,
Santanu 


--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/871rcet773.fsf%40googlemail.com.

Martin R. Albrecht

unread,
Mar 22, 2021, 10:19:08 AMMar 22
to sage-s...@googlegroups.com
Hi Santanu,

With very high precision it goes through:

#+begin_src jupyter-python :kernel sagemath
A = random_matrix(ZZ, 10, 10, x=-2^500, y=2^500)
A.echelonize() # make it interesting by turning into HNF

from fpylll import FPLLL, IntegerMatrix, GSO, LLL
B = IntegerMatrix.from_matrix(A)
FPLLL.set_precision(20000) # 20000 bits of precision!
M = GSO.Mat(B, float_type="mpfr")
M.update_gso()
L = LLL.Reduction(M)
L.size_reduction()
C = B.to_matrix(matrix(ZZ, 10, 10)) # back to Sage's format
#+end_src

HNF is pretty bad for precision, so it’s an extreme example.

Santanu Sarkar

unread,
Apr 20, 2021, 1:09:53 PMApr 20
to sage-support
Hi Martin, 
    Thank you so much for your kind help. It works! 

Kind regards,
Santanu

Reply all
Reply to author
Forward
0 new messages