Lattices in Sage

asked 2017-11-14 16:44:25 +0100

Anonymous

updated 2019-08-29 18:40:54 +0100

FrédéricC

5206 ●3 ●43 ●114

I have the following Magma code, and I want to rewrite it in Sage.

L:=Lattice(Matrix(Rationals(),2,2,[N2t,0,tau,1]), Matrix(Rationals(),2,2,[1,0,0,D]));
"Lattice:\n",L;
"\nBasis matrix:\n",LLLBasisMatrix(L);

In Sage I have something like this:

M = Matrix(QQ, [(N2t,0,tau,1), (1,0,0,D)])
M.LLL()

Whose output is not exactly the same thing produced by the above Magma code. I think the main problem is that I use a matrix and just apply the LLL algorithm to it in the Sage part. Whereas, in Magma there a lattice created, and then the LLLBasisMatrixfunction (https://magma.maths.usyd.edu.au/magma...) called. Roughly speaking that function does this:

Given a lattice L with basis matrix B, return the LLL basis matrix B' of L, together with the transformation matrix T such that B'=TB. The LLL basis matrix B' is simply defined to be a LLL-reduced form of B; it is stored in L when computed and subsequently used internally by many lattice functions. The LLL basis matrix will be created automatically internally as needed with δ=0.999 by default (note that this is different from the usual default of 0.75); by the use of parameters to this function one can ensure that the LLL basis matrix is created in a way which is different to the default.

How does one create a lattice in Sage? And does Sage have a function similar to LLLBasisMatrix above? If not, how can I achieve the same functionality in Sage?

As for numeric example, I have the following values:

N2t = 1136868377216160297393798828125
D = 53364935730486508893809772233249725927747397616650814998641
tau = 954690521650617175389887577728

and if I call the above Magma code with these values, I get the following result for the basis matrix:

[-182177855565543122003911250397                               1]
[ 772512666085074053385976327331                               2]

whereas if I call the above Sage code with the above values, I get the following result:

[1136868377216160297393798828125                                                           0                              954690521650617175389887577728                                                           1]
[1                                                           0                                                           0 53364935730486508893809772233249725927747397616650814998641]

edit retag flag offensive close merge delete

Comments

Please describe mathematically what is Magma doing here:

L:=Lattice(Matrix(Rationals(),2,2,[N2t,0,tau,1]), Matrix(Rationals(),2,2,[1,0,0,1]));

The answer to this question may bring us closer...

What is $L$ exactly as a mathematical object?

Also, could it be please still possible to get numbers in a normal range, so that a potential helper does not have edit a lot in order to get for example that

sage: B.det().factor()
-1 * 5^673

for the "Basis matrix" (given in Magma, edited with bare hands to work in sage - no magma here).

Since the above cannot be purely incidental, some mathematical background is really welcome...

dan_fulea ( 2017-11-15 21:05:27 +0100 )edit

@dan_fulea $L$ is supposed to be a lattice generated by two vectors $(N_2,0)$ and $(\tau,1)$. The Magma code is not written by me, I'm just trying to convert it to Sage, that's why I also don't know exactly the need of the second matrix in the lattice generation.

whatever ( 2017-11-15 23:30:30 +0100 )edit

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2017-11-16 22:47:44 +0100

dan_fulea
5537 ●5 ●43 ●95

updated 2017-11-19 21:39:57 +0100

After the posted question was rewritten, things become clear...

I will use the initial data, now removed.

N2t = 255160190748097728909073992066681481971266763532072843899089448199446167717167960744601102972601602922181202360582451390444069288993036758893159458257631792288806392427511312959701552997863308272649941168050821236125510145636956726776578414214971100481644977543870051557614456524822448281201070029896628771569285982163522457460577547615506364312525396285709733305329300010560421731105246057719068276050848034151179818471271226677961341255951310813543386757373809814453125

tau = 21889076392558760327677659259934609638463313379802582901440283193366831291164819780840018602360527472447127247594678967295892871925139132561808422151579794094385412974746838548046696943871501539283044945256107967558704847080889510560228755842021930819060356896821169145764886710414494318501436969236483033958717524286008339273426400925089525356222254452347532030101233967584203566313861768653268558884527430972086051680415120281152591994818818861033582581858059564186563

M = Matrix( QQ, 2, 2,
            [ [ N2t, 0 ] ,
              [ tau, 1 ] , ] )

B = M.LLL()
# the two lines that declare M and B are the solution...
# let us put some prints here, to see what happens...

print 'M is a matrix with relatively big coefficients'
print M.change_ring( RR )

print 'B = M.LLL() is a matrix with "half big" coefficients'
print B.change_ring( RR )

print 'The determinants of M and B differ by a unit...'
print 'det(M) = %s' % ( M.det().factor() )
print 'det(B) = %s' % ( B.det().factor() )

Results:

M is a matrix with relatively big coefficients
[2.55160190748098e470    0.000000000000000]
[2.18890763925588e469     1.00000000000000]
B = M.LLL() is a matrix with "half big" coefficients
[-1.02023170379847e235 -8.25694748623678e234]
[-1.02465661838403e235  1.67172644428592e235]
The determinants of M and B differ by a unit...
det(M) = 5^673
det(B) = -1 * 5^673

Note hat B has similar entries to those from the initial post, where magma results were shown:

    sage: print B[0,0]
-10202317037984739003641915820305590772990465825580647714167730574287969828946893597099411030227057452578710890500399597178698718476298665843284580499548238950340493074884696751946997981571943671945095252359926214603290438205260990700057

FURTHER EDIT regarding the declaration of an inner product (diagonal) matrix D in the magma lattice.

Magma seems to accept also a second argument when a lattice is introduced, as in

https://magma.maths.usyd.edu.au/magma/handbook/text/308

so let us give an example of usage for the same data, in parallel in magma and in sage. The link to the magma online calculator was a big help, the following Magma code

d  := 7647976553;
QQ := Rationals();    
A := Matrix( QQ, 2, 2, [2^83-1, 3^47+17, 5^35-2, 7^27-66] );
X := Matrix( QQ, 2, 2, [1,0,0,d] );

L := Lattice( A, X^2 );
"\n LLLBasisMatrix(L):\n", LLLBasisMatrix(L);

was executed, and gave rise to

 LLLBasisMatrix(L):

[   1469426521149510852500378801             -481347751540973298]
[1000322738339202822446199266478            52159285068221467403]

and some further output that i could not figure out using the strict magma documentation in a world without examples.

Let us recover the above in sage. Code:

d = 7647976553;

A = matrix( QQ, 2, [2^83-1, 3^47+17, 5^35-2, 7^27-66] )
X = matrix( QQ, 2, [1,0, 0,d] )
M = A * X
M.LLL() * X^(-1)

Results:

[   1469426521149510852500378801             -481347751540973298]
[1000322738339202822446199266478            52159285068221467403]

So the difference is recovered by a twist with X.

edit flag offensive delete link

Comments

Your result will produce more or less correct results (just the sign will be wrong) if one matrix is used. But, in my case as you can see in the original question, there are two matrices used. I added some numeric examples to the original question, to see the contrast. Please note that there is another value called D.

whatever ( 2017-11-18 19:37:31 +0100 )edit

The answer was typed based on the information in the comment:

$L$ is supposed to be a lattice generated by two vectors $(N_2,0)$ and $(\tau,1)$ .

This made sense immediately, we really have a lattice in $V=\mathbb R^2$, two $2$-component vectors in $V$. Now first, i see there is also that D, did not have seen it before.

Since i do not have magma, thus cannot experiment and compare, please describe in words what is the rôle of the second matrix. The magma doc found here

magma/handbook/text/312

gives me a relatively bad documentation, only one argument, which is a Lat. If there is some other sample code with smaller data, we can try to guess...

dan_fulea ( 2017-11-18 20:56:41 +0100 )edit

You can use the online Magma calculator for the experimental purposes, it is more than enough: http://magma.maths.usyd.edu.au/calc/

As for the Magma code in my question. It will basically create a lattice of rank 2 and degree 2, which has basis:

( 457685173309633 -876887928958864)
( 953127960009412  657836416577629)

and Inner Product Matrix:

[1 0]
[0 53364935730486508893809772233249725927747397616650814998641]

So basically the second matrix is the inner product matrix. I hope this is more clear.

whatever ( 2017-11-18 22:04:51 +0100 )edit

Note that the above diagonal entry is a square:

sage: D = 53364935730486508893809772233249725927747397616650814998641
sage: sqrt(D)
231008518740081334027019279129

The answer was edited above with an other (smaller) value of $\sqrt D$, to also cover such a declaration.

dan_fulea ( 2017-11-19 21:42:29 +0100 )edit

Thanks, this works, and using sqrt(D) for the original values given above, it produces the correct results.

whatever ( 2017-11-20 14:06:32 +0100 )edit

add a comment

answered 2017-11-14 20:19:33 +0100

Sébastien
3246 ●7 ●42 ●88 http://www.slabbe.org/

In Sage, you first create a matrix. Then, each matrix has a method which allows to do lattice reduction to find the short vectors. For example, you may do:

sage: N2t = randint(0, 10^10)
sage: tau = randint(0, 10^10)
sage: m = matrix(QQ, [(N2t,0,tau,1), (1,0,0,1)])
sage: m.LLL()
[          1           0           0           1]
[ 3930321261           0  1228166902 -3930321261]

Beware that the word lattice has many meanings in mathematics. LatticePosetin sage refers to something else : https://en.wikipedia.org/wiki/Lattice....

edit flag offensive delete link

Comments

Thanks for the answer. Though, I wonder whether it is the correct solution here. Please check the above modified question, with some actual values comparing the results of Magma and Sage.

whatever ( 2017-11-15 16:28:48 +0100 )edit

I am not export enough in the LLL algorithm to be able to reverse engeneer what Magma does. But you must know that there are many possible parameters to the LLL algorithm that may affect the output, see:

sage: M.LLL?
sage: M.LLL??    # for the source code

If your objective is to compage Sage and Magma, one thing you can do is to take some smaller matrices and see how Sage do and how Magma does:

sage: M = random_matrix(ZZ, 4,4)
sage: M
[ 0  0 -2  1]
[ 1  1 -1 -3]
[-4  1 -1 10]
[-7 -1  2  1]
sage: M.LLL()
[ 0  0 -2  1]
[ 1  1 -1 -3]
[-1  4  0 -1]
[-4 -3 -2 -3]
sage: magma_M = magma(M)
...

Sébastien ( 2017-11-16 12:42:02 +0100 )edit

I think the main problem is not the LLL algorithm per se, but the used method here. If one creates the same matrix both in Sage and Magma and applies the LLL algorithm, the result is the same. But, in my example above, in Magma, a different method is used, which is called LLLBasisMatrix: https://magma.maths.usyd.edu.au/magma...

I think what I look for is whether Sage supports creating lattices, and if it has method similar to LLLBasisMatrix from Magma.

whatever ( 2017-11-16 15:22:29 +0100 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Lattices in Sage

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Lattices in Sage edit

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Lattices in Sage