ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 20 Nov 2017 07:06:32 -0600Lattices in Sagehttp://ask.sagemath.org/question/39542/lattices-in-sage/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 `LLLBasisMatrix` function (https://magma.maths.usyd.edu.au/magma/handbook/text/312#2964) 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]Tue, 14 Nov 2017 09:44:25 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/Comment by whatever for <p>I have the following Magma code, and I want to rewrite it in Sage.</p>
<pre><code>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);
</code></pre>
<p>In Sage I have something like this:</p>
<pre><code>M = Matrix(QQ, [(N2t,0,tau,1), (1,0,0,D)])
M.LLL()
</code></pre>
<p>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 <code>LLLBasisMatrix</code>function (<a href="https://magma.maths.usyd.edu.au/magma/handbook/text/312#2964">https://magma.maths.usyd.edu.au/magma...</a>) called. Roughly speaking that function does this:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>How does one create a lattice in Sage? And does Sage have a function similar to <code>LLLBasisMatrix</code> above? If not, how can I achieve the same functionality in Sage?</p>
<p>As for numeric example, I have the following values:</p>
<pre><code>N2t = 1136868377216160297393798828125
D = 53364935730486508893809772233249725927747397616650814998641
tau = 954690521650617175389887577728
</code></pre>
<p>and if I call the above Magma code with these values, I get the following result for the basis matrix:</p>
<pre><code>[-182177855565543122003911250397 1]
[ 772512666085074053385976327331 2]
</code></pre>
<p>whereas if I call the above Sage code with the above values, I get the following result:</p>
<pre><code>[1136868377216160297393798828125 0 954690521650617175389887577728 1]
[1 0 0 53364935730486508893809772233249725927747397616650814998641]
</code></pre>
http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39590#post-id-39590@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.Wed, 15 Nov 2017 16:30:30 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39590#post-id-39590Comment by dan_fulea for <p>I have the following Magma code, and I want to rewrite it in Sage.</p>
<pre><code>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);
</code></pre>
<p>In Sage I have something like this:</p>
<pre><code>M = Matrix(QQ, [(N2t,0,tau,1), (1,0,0,D)])
M.LLL()
</code></pre>
<p>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 <code>LLLBasisMatrix</code>function (<a href="https://magma.maths.usyd.edu.au/magma/handbook/text/312#2964">https://magma.maths.usyd.edu.au/magma...</a>) called. Roughly speaking that function does this:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>How does one create a lattice in Sage? And does Sage have a function similar to <code>LLLBasisMatrix</code> above? If not, how can I achieve the same functionality in Sage?</p>
<p>As for numeric example, I have the following values:</p>
<pre><code>N2t = 1136868377216160297393798828125
D = 53364935730486508893809772233249725927747397616650814998641
tau = 954690521650617175389887577728
</code></pre>
<p>and if I call the above Magma code with these values, I get the following result for the basis matrix:</p>
<pre><code>[-182177855565543122003911250397 1]
[ 772512666085074053385976327331 2]
</code></pre>
<p>whereas if I call the above Sage code with the above values, I get the following result:</p>
<pre><code>[1136868377216160297393798828125 0 954690521650617175389887577728 1]
[1 0 0 53364935730486508893809772233249725927747397616650814998641]
</code></pre>
http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39584#post-id-39584Please 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...Wed, 15 Nov 2017 14:05:27 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39584#post-id-39584Answer by dan_fulea for <p>I have the following Magma code, and I want to rewrite it in Sage.</p>
<pre><code>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);
</code></pre>
<p>In Sage I have something like this:</p>
<pre><code>M = Matrix(QQ, [(N2t,0,tau,1), (1,0,0,D)])
M.LLL()
</code></pre>
<p>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 <code>LLLBasisMatrix</code>function (<a href="https://magma.maths.usyd.edu.au/magma/handbook/text/312#2964">https://magma.maths.usyd.edu.au/magma...</a>) called. Roughly speaking that function does this:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>How does one create a lattice in Sage? And does Sage have a function similar to <code>LLLBasisMatrix</code> above? If not, how can I achieve the same functionality in Sage?</p>
<p>As for numeric example, I have the following values:</p>
<pre><code>N2t = 1136868377216160297393798828125
D = 53364935730486508893809772233249725927747397616650814998641
tau = 954690521650617175389887577728
</code></pre>
<p>and if I call the above Magma code with these values, I get the following result for the basis matrix:</p>
<pre><code>[-182177855565543122003911250397 1]
[ 772512666085074053385976327331 2]
</code></pre>
<p>whereas if I call the above Sage code with the above values, I get the following result:</p>
<pre><code>[1136868377216160297393798828125 0 954690521650617175389887577728 1]
[1 0 0 53364935730486508893809772233249725927747397616650814998641]
</code></pre>
http://ask.sagemath.org/question/39542/lattices-in-sage/?answer=39617#post-id-39617After 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](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`.
Thu, 16 Nov 2017 15:47:44 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?answer=39617#post-id-39617Comment by whatever for <p>After the posted question was rewritten, things become clear...</p>
<p>I will use the initial data, now removed.</p>
<pre><code>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() )
</code></pre>
<p>Results:</p>
<pre><code>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
</code></pre>
<p>Note hat <code>B</code> has similar entries to those from the initial post, where magma results were shown:</p>
<pre><code> sage: print B[0,0]
-10202317037984739003641915820305590772990465825580647714167730574287969828946893597099411030227057452578710890500399597178698718476298665843284580499548238950340493074884696751946997981571943671945095252359926214603290438205260990700057
</code></pre>
<p><strong>FURTHER EDIT</strong> regarding the declaration of an inner product (diagonal) matrix <code>D</code> in the magma lattice.</p>
<p>Magma seems to accept also a second argument when a lattice is introduced, as in</p>
<p><a href="https://magma.maths.usyd.edu.au/magma/handbook/text/308">https://magma.maths.usyd.edu.au/magma/handbook/text/308</a></p>
<p>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</p>
<pre><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);
</code></pre>
<p>was executed, and gave rise to</p>
<pre><code> LLLBasisMatrix(L):
[ 1469426521149510852500378801 -481347751540973298]
[1000322738339202822446199266478 52159285068221467403]
</code></pre>
<p>and some further output that i could not figure out using the strict magma documentation in a world without examples.</p>
<p>Let us recover the above in sage.
Code:</p>
<pre><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)
</code></pre>
<p>Results:</p>
<pre><code>[ 1469426521149510852500378801 -481347751540973298]
[1000322738339202822446199266478 52159285068221467403]
</code></pre>
<p>So the difference is recovered by a twist with <code>X</code>. </p>
http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39669#post-id-39669Thanks, this works, and using `sqrt(D)` for the original values given above, it produces the correct results.Mon, 20 Nov 2017 07:06:32 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39669#post-id-39669Comment by dan_fulea for <p>After the posted question was rewritten, things become clear...</p>
<p>I will use the initial data, now removed.</p>
<pre><code>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() )
</code></pre>
<p>Results:</p>
<pre><code>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
</code></pre>
<p>Note hat <code>B</code> has similar entries to those from the initial post, where magma results were shown:</p>
<pre><code> sage: print B[0,0]
-10202317037984739003641915820305590772990465825580647714167730574287969828946893597099411030227057452578710890500399597178698718476298665843284580499548238950340493074884696751946997981571943671945095252359926214603290438205260990700057
</code></pre>
<p><strong>FURTHER EDIT</strong> regarding the declaration of an inner product (diagonal) matrix <code>D</code> in the magma lattice.</p>
<p>Magma seems to accept also a second argument when a lattice is introduced, as in</p>
<p><a href="https://magma.maths.usyd.edu.au/magma/handbook/text/308">https://magma.maths.usyd.edu.au/magma/handbook/text/308</a></p>
<p>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</p>
<pre><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);
</code></pre>
<p>was executed, and gave rise to</p>
<pre><code> LLLBasisMatrix(L):
[ 1469426521149510852500378801 -481347751540973298]
[1000322738339202822446199266478 52159285068221467403]
</code></pre>
<p>and some further output that i could not figure out using the strict magma documentation in a world without examples.</p>
<p>Let us recover the above in sage.
Code:</p>
<pre><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)
</code></pre>
<p>Results:</p>
<pre><code>[ 1469426521149510852500378801 -481347751540973298]
[1000322738339202822446199266478 52159285068221467403]
</code></pre>
<p>So the difference is recovered by a twist with <code>X</code>. </p>
http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39663#post-id-39663Note 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.Sun, 19 Nov 2017 14:42:29 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39663#post-id-39663Comment by whatever for <p>After the posted question was rewritten, things become clear...</p>
<p>I will use the initial data, now removed.</p>
<pre><code>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() )
</code></pre>
<p>Results:</p>
<pre><code>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
</code></pre>
<p>Note hat <code>B</code> has similar entries to those from the initial post, where magma results were shown:</p>
<pre><code> sage: print B[0,0]
-10202317037984739003641915820305590772990465825580647714167730574287969828946893597099411030227057452578710890500399597178698718476298665843284580499548238950340493074884696751946997981571943671945095252359926214603290438205260990700057
</code></pre>
<p><strong>FURTHER EDIT</strong> regarding the declaration of an inner product (diagonal) matrix <code>D</code> in the magma lattice.</p>
<p>Magma seems to accept also a second argument when a lattice is introduced, as in</p>
<p><a href="https://magma.maths.usyd.edu.au/magma/handbook/text/308">https://magma.maths.usyd.edu.au/magma/handbook/text/308</a></p>
<p>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</p>
<pre><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);
</code></pre>
<p>was executed, and gave rise to</p>
<pre><code> LLLBasisMatrix(L):
[ 1469426521149510852500378801 -481347751540973298]
[1000322738339202822446199266478 52159285068221467403]
</code></pre>
<p>and some further output that i could not figure out using the strict magma documentation in a world without examples.</p>
<p>Let us recover the above in sage.
Code:</p>
<pre><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)
</code></pre>
<p>Results:</p>
<pre><code>[ 1469426521149510852500378801 -481347751540973298]
[1000322738339202822446199266478 52159285068221467403]
</code></pre>
<p>So the difference is recovered by a twist with <code>X</code>. </p>
http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39653#post-id-39653You 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.Sat, 18 Nov 2017 15:04:51 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39653#post-id-39653Comment by dan_fulea for <p>After the posted question was rewritten, things become clear...</p>
<p>I will use the initial data, now removed.</p>
<pre><code>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() )
</code></pre>
<p>Results:</p>
<pre><code>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
</code></pre>
<p>Note hat <code>B</code> has similar entries to those from the initial post, where magma results were shown:</p>
<pre><code> sage: print B[0,0]
-10202317037984739003641915820305590772990465825580647714167730574287969828946893597099411030227057452578710890500399597178698718476298665843284580499548238950340493074884696751946997981571943671945095252359926214603290438205260990700057
</code></pre>
<p><strong>FURTHER EDIT</strong> regarding the declaration of an inner product (diagonal) matrix <code>D</code> in the magma lattice.</p>
<p>Magma seems to accept also a second argument when a lattice is introduced, as in</p>
<p><a href="https://magma.maths.usyd.edu.au/magma/handbook/text/308">https://magma.maths.usyd.edu.au/magma/handbook/text/308</a></p>
<p>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</p>
<pre><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);
</code></pre>
<p>was executed, and gave rise to</p>
<pre><code> LLLBasisMatrix(L):
[ 1469426521149510852500378801 -481347751540973298]
[1000322738339202822446199266478 52159285068221467403]
</code></pre>
<p>and some further output that i could not figure out using the strict magma documentation in a world without examples.</p>
<p>Let us recover the above in sage.
Code:</p>
<pre><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)
</code></pre>
<p>Results:</p>
<pre><code>[ 1469426521149510852500378801 -481347751540973298]
[1000322738339202822446199266478 52159285068221467403]
</code></pre>
<p>So the difference is recovered by a twist with <code>X</code>. </p>
http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39651#post-id-39651The 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](https://magma.maths.usyd.edu.au/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...Sat, 18 Nov 2017 13:56:41 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39651#post-id-39651Comment by whatever for <p>After the posted question was rewritten, things become clear...</p>
<p>I will use the initial data, now removed.</p>
<pre><code>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() )
</code></pre>
<p>Results:</p>
<pre><code>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
</code></pre>
<p>Note hat <code>B</code> has similar entries to those from the initial post, where magma results were shown:</p>
<pre><code> sage: print B[0,0]
-10202317037984739003641915820305590772990465825580647714167730574287969828946893597099411030227057452578710890500399597178698718476298665843284580499548238950340493074884696751946997981571943671945095252359926214603290438205260990700057
</code></pre>
<p><strong>FURTHER EDIT</strong> regarding the declaration of an inner product (diagonal) matrix <code>D</code> in the magma lattice.</p>
<p>Magma seems to accept also a second argument when a lattice is introduced, as in</p>
<p><a href="https://magma.maths.usyd.edu.au/magma/handbook/text/308">https://magma.maths.usyd.edu.au/magma/handbook/text/308</a></p>
<p>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</p>
<pre><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);
</code></pre>
<p>was executed, and gave rise to</p>
<pre><code> LLLBasisMatrix(L):
[ 1469426521149510852500378801 -481347751540973298]
[1000322738339202822446199266478 52159285068221467403]
</code></pre>
<p>and some further output that i could not figure out using the strict magma documentation in a world without examples.</p>
<p>Let us recover the above in sage.
Code:</p>
<pre><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)
</code></pre>
<p>Results:</p>
<pre><code>[ 1469426521149510852500378801 -481347751540973298]
[1000322738339202822446199266478 52159285068221467403]
</code></pre>
<p>So the difference is recovered by a twist with <code>X</code>. </p>
http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39649#post-id-39649Your 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`.Sat, 18 Nov 2017 12:37:31 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39649#post-id-39649Answer by Sébastien for <p>I have the following Magma code, and I want to rewrite it in Sage.</p>
<pre><code>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);
</code></pre>
<p>In Sage I have something like this:</p>
<pre><code>M = Matrix(QQ, [(N2t,0,tau,1), (1,0,0,D)])
M.LLL()
</code></pre>
<p>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 <code>LLLBasisMatrix</code>function (<a href="https://magma.maths.usyd.edu.au/magma/handbook/text/312#2964">https://magma.maths.usyd.edu.au/magma...</a>) called. Roughly speaking that function does this:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>How does one create a lattice in Sage? And does Sage have a function similar to <code>LLLBasisMatrix</code> above? If not, how can I achieve the same functionality in Sage?</p>
<p>As for numeric example, I have the following values:</p>
<pre><code>N2t = 1136868377216160297393798828125
D = 53364935730486508893809772233249725927747397616650814998641
tau = 954690521650617175389887577728
</code></pre>
<p>and if I call the above Magma code with these values, I get the following result for the basis matrix:</p>
<pre><code>[-182177855565543122003911250397 1]
[ 772512666085074053385976327331 2]
</code></pre>
<p>whereas if I call the above Sage code with the above values, I get the following result:</p>
<pre><code>[1136868377216160297393798828125 0 954690521650617175389887577728 1]
[1 0 0 53364935730486508893809772233249725927747397616650814998641]
</code></pre>
http://ask.sagemath.org/question/39542/lattices-in-sage/?answer=39550#post-id-39550In 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. `LatticePoset` in sage refers to something else : https://en.wikipedia.org/wiki/Lattice_(order).Tue, 14 Nov 2017 13:19:33 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?answer=39550#post-id-39550Comment by whatever for <p>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:</p>
<pre><code>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]
</code></pre>
<p>Beware that the word lattice has many meanings in mathematics. <code>LatticePoset</code>in sage refers to something else : <a href="https://en.wikipedia.org/wiki/Lattice_(order)">https://en.wikipedia.org/wiki/Lattice...</a>.</p>
http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39605#post-id-39605I 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/handbook/text/312#2964
I think what I look for is whether Sage supports creating lattices, and if it has method similar to `LLLBasisMatrix` from Magma.Thu, 16 Nov 2017 08:22:29 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39605#post-id-39605Comment by Sébastien for <p>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:</p>
<pre><code>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]
</code></pre>
<p>Beware that the word lattice has many meanings in mathematics. <code>LatticePoset</code>in sage refers to something else : <a href="https://en.wikipedia.org/wiki/Lattice_(order)">https://en.wikipedia.org/wiki/Lattice...</a>.</p>
http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39599#post-id-39599I 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)
...Thu, 16 Nov 2017 05:42:02 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39599#post-id-39599Comment by whatever for <p>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:</p>
<pre><code>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]
</code></pre>
<p>Beware that the word lattice has many meanings in mathematics. <code>LatticePoset</code>in sage refers to something else : <a href="https://en.wikipedia.org/wiki/Lattice_(order)">https://en.wikipedia.org/wiki/Lattice...</a>.</p>
http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39578#post-id-39578Thanks 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.Wed, 15 Nov 2017 09:28:48 -0600http://ask.sagemath.org/question/39542/lattices-in-sage/?comment=39578#post-id-39578