# How to compute LLL-reduce basis from lattice in Mathematica? And factor N

original article

1. Clear.

2. What is k? What is suitably large? I already have large numbers.

I tried this WITHOUT k:

l = {{257919033808285386982723138014073293916017582745217658572688730, 1, 0, 0, 0,
0}, {96867973320263572974115044506030258341444464854943648267515408, 0, 1, 0, 0,
0}, {214758871433111497694995539195891916824955066662252282354181736, 0, 0, 1, 0,
0}, {178844682241391008034534910988268609252058699869308978135021308, 0, 0, 0, 1,
0}, {71733070775806610412706498828294541707518193810809428776054804, 0, 0, 0, 0, 1}}

LatticeReduce[l]


Then I get

{{0, -1365671033120, 545322066131, 436640563446, 1229893282094, -199684715714},
{0, 866429285712, 2201930198201, -1701760529785, -629220915678, 574851531904},
{-2504853201882, 457178461453, 187071007770, -1221360285756, -142958107186,
2116583547143}, {-1403276934308, 1405303909932,
1893904650270, -561119435707, -967865797993, -3517349825058},
{0, 949922988714, -1339433516640, -3217456270186, 3769708645892, -1372729142485}}


And remove first component from each vector and remove vectors that doesn't have '0' at the first position:

{{-1365671033120, 545322066131, 436640563446, 1229893282094, -199684715714},
{866429285712,  2201930198201, -1701760529785, -629220915678, 574851531904},
{949922988714, -1339433516640, -3217456270186, 3769708645892, 1372729142485}}

1. b_1,1...b_l-2,1 - means that I should take first element in each vector and paste it in the first row? I mean a_n,m, where n - is a column, m - is a row?

and the matrix looks like:

{{-1365671033120,866429285712,949922988714,1,0,0,0,0},
{545322066131,2201930198201,-1339433516640,0,1,0,0,0},
{436640563446,-1701760529785,-3217456270186,0,0,1,0,0},
{1229893282094,-629220915678,3769708645892,0,0,0,1,0},
{-199684715714,574851531904,-1372729142485,0,0,0,0,1}}

LatticeReduce[k]


And I get

{{-8420349, 697170, -12106726, 14903570, 7006595, 12609061,
8539170, -2627280}, {24559242,
7478123, -1193768, -1648108, -2882806, -1692731, 1741079,
10421138}, {-12381450, 30655040,
10519029, -1983832, -1821438, -1804204, -4431,
4621051}, {18435788, -10167847, 22696964, 9681481, 7146820, 8558281,
2240963, -14179160}, {701255, -4498071, 17194245,
8153258, -2535483, 5996610, 12784479, 29168907}}


And remove all, except last l components of each vector:

{{14903570, 7006595, 12609061, 8539170, -2627280},
{-1648108, -2882806, -1692731, 1741079, 10421138},
{-1983832, -1821438, -1804204, -4431, 4621051},
{9681481, 7146820, 8558281,2240963, -14179160},
{8153258, -2535483, 5996610, 12784479, 29168907}}


Q1: Why at the end of 3 step I got matrix 5x5. Where is my {x',y'}?

Q2: In the 4th step, why I get vectorS z, but not one vector? I mean x = 2*{1,2}+3*{0,1} = {2,7} isn't it?

### Update:

I updated matrixes at the 2 and 3 steps. HermiteDecomposition method gives me the same result at the 2 step, as I tried without k. There are still two questions, please, tell me am I on the right way? I mean, steps 2 and 3 are seems to be right? And what about {x',y'}?

• Not sure why this got down votes.. Jan 10 '15 at 20:39
• One possiblity is to take the null space of the matrix with only one row, comprised of that vector. Then clear denominators if need be. In[334]:= NullSpace[{u}] Out[334]= {{-4, 0, 0, 0, 23}, {-3, 0, 0, 23, 0}, {-2, 0, 23, 0, 0}, {-1, 23, 0, 0, 0}} Jan 10 '15 at 20:41
• @OleksandrR, I updated my post. Please, tell me if you can help me to understand it. Jan 10 '15 at 22:07
• (1) You went wrong in step 2, perhaps by failing to use a multiplier k. This is because the instructions are incomplete: you only take those vecotrs for which the first component is 0 (the rest of the vector providing the null relation part). Notice that you do not have 4 such vectors, but only 3, so your null space is not completely generated by the "correct" vectors. And if you took all of them then some are not in the null space. Jan 10 '15 at 22:24
• @OleksandrR I think k in this case is actually the kappa appearing in the post, in parts 2 and 3 (though there is not enough context for me to say whether those must be the same values). As for the k of LLL, actually there's a system option for that.. Jan 10 '15 at 22:32

I don't know what exactly you did using HermiteDecomposition. Here is what I had in mind. It will give four null generators.

lat = {{25791903380828538698272313801407329391601758274521765857268873\
0, 1, 0, 0, 0,
0}, {9686797332026357297411504450603025834144446485494364826751540\
8, 0, 1, 0, 0,
0}, {2147588714331114976949955391958919168249550666622522823541817\
36, 0, 0, 1, 0,
0}, {1788446822413910080345349109882686092520586998693089781350213\
08, 0, 0, 0, 1,
0}, {7173307077580661041270649882829454170751819381080942877605480\
4, 0, 0, 0, 0, 1}};


Form the Hermite decomposition. Check that we got a multiplier matrix that, acting on the input lat, recovers the normal form. Then check the first elements of the normal form (the second matrix returned) to see which positions go with nulls. Actually we know which (all but the first) from the nature of what a Hermite normal form is, but we check anyway.

{umat, hnf} = HermiteDecomposition[lat];
umat.lat === hnf
hnf[[All, 1]]

(* Out[368]= True

Out[369]= {2, 0, 0, 0, 0} *)


So all but the first relation will be null vectors. Lets extract those relations.

nulls =Rest[umat]

(* Out[370]= {{2, 0, 0,
16060416020744237632027833003485692757159619774236696420901290, \
-40041782246735978755823071242771550571702045842751168717694695}, {0,
1, 0, 9141386270736275869209971067568612622712962440763160956460553,\
-22791277511948392239439819572786422403271224453226511720107583}, {0,
0, 1, 3041376591713742238653798070030424380490315075718933218235133\
, -7582751222535164094198296685086819556607555537048261493826425}, {0,
0, 0, 1793326769395165260317662470707363542687954845270235719401370\
1, -44711170560347752008633727747067152313014674967327244533755327}} *)


Note that there are four such. We'll check that these really are null vectors for column 1 of lat.

Rest[umat].lat[[All, 1]]

(* Out[371]= {0, 0, 0, 0} *)

rednulls = LatticeReduce[nulls]

(* Out[373]= {{1365671033120, -545322066131, -436640563446, \
-1229893282094, 199684715714}, {-866429285712, -2201930198201,
1701760529785, 629220915678, -574851531904}, {-949922988714,
1339433516640, 3217456270186, -3769708645892,
1372729142485}, {-942410966805560583101320, \
-1659903127805029065269950, -969551135315600172622247,
1010190877534611184666589, 6014096627437342081817395}} *)


This was the process I had outlined in a comment. It is, or should be, the set {b_1,...,b_l-1} from item (2) in the question.

• thanks a lot. This really helps. Jan 11 '15 at 21:45
• Daniel, could you try to find someone to answer this, please? Jan 12 '15 at 12:48
Solve[{23, 1, 2, 3, 4}.{a, b, c, d, e} == 0, {a, b, c, d, e}]

{{e -> -((23 a)/4) - b/4 - c/2 - (3 d)/4}}


As Yashar points out, there are many different vectors orthogonal to {23, 1, 2, 3, 4}. Solve gives a set of free variables (in this case a, b, c, d) which can assume any values. Setting e to the specified relationship gives a vector that is orthogonal. You can also use Reduce instead of Solve to get the same answer.

• I think in the form you presented it's not possible to get all the variables because that dot product gives one equation while we have 5 unknown.
– MOON
Jan 10 '15 at 19:45
• I updated my post, @bill_s. Jan 10 '15 at 21:09
• Yes, you updated the post to completely change the question. Jan 10 '15 at 21:40