The different lattice reduction results given by Mathematica and fplll.

Questions
,
1

I noticed the following description here:

LatticeReduce uses Storjohann’s variant of the Lenstra–Lenstra–Lovasz
lattice reduction algorithm.

On the other hand, Arne Storjohann astorjohann@uwaterloo.ca told me
the following:

Hi Zhao,

“Storjohann’s variant” must be referring to my tech report from 1996.

I have attached the report.

If you are interested in implementation, I suggest you look instead at

Damien Stehle's Homepage

A link to the software fplll is available at the bottom of the page.
I think fplll is what Mathematica is currently using.

Best regards,
-Arne

Therefore, I tried to do the following verification using Mathematica and fplll respectively. But the results given by them are obviously different, and I can’t see any relationship between them:

First, generate data that meets the format requirements of Mathematica:

    werner@X10DAi-00:~$ latticegen u 10 10 | sed -Ee 's/\
    /,/g;s/$/,/g;s/\[/{/g;s/\]/}/g;$ s/,$//'
    {{116,331,303,963,456,225,827,381,99,649},
    {395,975,566,213,694,254,629,303,597,980},
    {462,533,231,443,912,451,926,105,162,742},
    {611,734,668,308,101,863,279,976,127,549},
    {438,456,887,466,634,748,307,1002,621,215},
    {6,340,142,411,250,873,371,554,434,638},
    {939,554,840,633,48,579,291,878,1004,659},
    {439,63,64,579,374,621,395,563,31,844},
    {124,640,944,427,541,255,712,647,33,20},
    {713,407,504,197,234,520,92,18,595,370}}

And then do the test in Mathematica:

In[18]:= (*
$ latticegen u 10 10 | sed -Ee 's/\ /,/g;s/$/,/g;s/\[/{/g;s/\]/}/g;$ \
s/,$//'
*)
xx = {{116, 331, 303, 963, 456, 225, 827, 381, 99, 649},
   {395, 975, 566, 213, 694, 254, 629, 303, 597, 980},
   {462, 533, 231, 443, 912, 451, 926, 105, 162, 742},
   {611, 734, 668, 308, 101, 863, 279, 976, 127, 549},
   {438, 456, 887, 466, 634, 748, 307, 1002, 621, 215},
   {6, 340, 142, 411, 250, 873, 371, 554, 434, 638},
   {939, 554, 840, 633, 48, 579, 291, 878, 1004, 659},
   {439, 63, 64, 579, 374, 621, 395, 563, 31, 844},
   {124, 640, 944, 427, 541, 255, 712, 647, 33, 20},
   {713, 407, 504, 197, 234, 520, 92, 18, 595, 370}};
xx // LatticeReduce


Out[19]= {{433, -277, -78, 168, 124, -252, 24, 9, -403, 206}, {346,
  202, -72, -520, 456, 226, 99, -276, 63, 93}, {366, 165,
  257, -62, -94, -449, -273, 207, 32, 444}, {-164, -362, 37, -265,
  358, -212,
  1, -147, -162, -334}, {337, -264, -10, -98, -228, -381, -15, -271,
  221, 110}, {188, -370, -13, -375, 205, 183, 330, -37, -163,
  414}, {-364, -206, 172, 168, 244, -73, -199, 30, -168, 366}, {-212,
  241, -431, -29, 39, 15, 33, 26, 286, 57}, {-9, 84, 182, 423, 175,
  97, 27, 173, 656, 0}, {323, -268, -239, -384, -82, 396, -432,
  182, -68, 195}}

Second, test with fplll using the same input data:

    werner@X10DAi-00:~$ latticegen u 10 10 | fplll -a lll
    [[-212 241 -431 -29 39 15 33 26 286 57 ]
    [221 -36 -509 139 163 -237 57 35 -117 263 ]
    [337 -264 -10 -98 -228 -381 -15 -271 221 110 ]
    [-364 -206 172 168 244 -73 -199 30 -168 366 ]
    [-206 366 113 23 495 -30 -430 -209 58 45 ]
    [-10 44 -137 -356 303 -646 -239 86 156 167 ]
    [366 165 257 -62 -94 -449 -273 207 32 444 ]
    [188 -370 -13 -375 205 183 330 -37 -163 414 ]
    [-9 84 182 423 175 97 27 173 656 0 ]
    [135 102 -226 -9 -287 213 -762 219 95 -219 ]
    ]
    werner@X10DAi-00:~$ latticegen u 10 10 | fplll -a hlll
    [[-212 241 -431 -29 39 15 33 26 286 57 ]
    [221 -36 -509 139 163 -237 57 35 -117 263 ]
    [337 -264 -10 -98 -228 -381 -15 -271 221 110 ]
    [-364 -206 172 168 244 -73 -199 30 -168 366 ]
    [158 572 -59 -145 251 43 -231 -239 226 -321 ]
    [-10 44 -137 -356 303 -646 -239 86 156 167 ]
    [366 165 257 -62 -94 -449 -273 207 32 444 ]
    [188 -370 -13 -375 205 183 330 -37 -163 414 ]
    [-9 84 182 423 175 97 27 173 656 0 ]
    [135 102 -226 -9 -287 213 -762 219 95 -219 ]
    ]
    werner@X10DAi-00:~$ latticegen u 10 10 | fplll -a hkz
    [[-212 241 -431 -29 39 15 33 26 286 57 ]
    [221 -36 -509 139 163 -237 57 35 -117 263 ]
    [337 -264 -10 -98 -228 -381 -15 -271 221 110 ]
    [-364 -206 172 168 244 -73 -199 30 -168 366 ]
    [-206 366 113 23 495 -30 -430 -209 58 45 ]
    [-10 44 -137 -356 303 -646 -239 86 156 167 ]
    [366 165 257 -62 -94 -449 -273 207 32 444 ]
    [188 -370 -13 -375 205 183 330 -37 -163 414 ]
    [-9 84 182 423 175 97 27 173 656 0 ]
    [135 102 -226 -9 -287 213 -762 219 95 -219 ]
    ]

I don’t know if you can see some clues from these results. Any hints/explanations on the relationship between these two result sets will be appreciated.

Regards,
Zhao

2

Arne Storjohann is correct on all points (no surprise there; he knows this stuff inside and out). We were using the method from his 1996 technical report. We switched to an implementation of the method by Nguyen and Stehle; see my comment from MSE. So those documentation notes are out of date. We do not at this time use fplll directly although I suppose that could change.

It is to be expected that different implementations might give different results and all might be correct as LLL-type reductions. There are invariably details in defaults and implementation, e.g. LLL parameter settings and choices for perturbation values, that are not obvious and give rise to different results.

3

I noticed the following follow-up comment on the above MSE discussion:

@J.M. Actually it was implemented a few years ago, we just never told
anyone. Was available via undocumented SystemOption. Some day I may
even wrap up L1+ (if it doesn’t wrap me up first). – Daniel Lichtblau
Aug 28, 2015 at 15:25

  1. “SystemOption” is not an available command; instead, “SystemOptions” is.
  2. Are there any “L1+” level algorithms available in the lattice basis reduction filed?

Regards,
Zhao

4

There is ExtendedLatticeReduce in the Wolfram Function Repository. It is not a full implementation of L1+ by any means. It uses a variant that will be fast under certain circumstances that arise in practice e.g. one or at most a few large columns and the rest small. As the name is intended to convey, it returns both the reduced lattice and a conversion matrix.

5

Thank you very much for telling me these very valuable information.