Message Boards Message Boards

0
|
1769 Views
|
4 Replies
|
2 Total Likes
View groups...
Share
Share this post:

The different lattice reduction results given by Mathematica and fplll.

Posted 1 year ago

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

http://perso.ens-lyon.fr/damien.stehle/

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

POSTED BY: Hongyi Zhao
4 Replies
Posted 1 year ago

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

POSTED BY: Hongyi Zhao
Posted 1 year ago

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

POSTED BY: Hongyi Zhao

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.

POSTED BY: Daniel Lichtblau

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.

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract