Size reduced of a basis

62 visualizações
Pular para a primeira mensagem não lida

Santanu Sarkar

não lida,
16 de mar. de 2021, 18:17:4316/03/2021
para 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

não lida,
17 de mar. de 2021, 06:18:0017/03/2021
para 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

não lida,
19 de mar. de 2021, 13:19:1219/03/2021
para 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

não lida,
22 de mar. de 2021, 10:19:0822/03/2021
para 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

não lida,
20 de abr. de 2021, 13:09:5320/04/2021
para sage-support
Hi Martin, 
    Thank you so much for your kind help. It works! 

Kind regards,
Santanu

Responder a todos
Responder ao autor
Encaminhar
0 nova mensagem