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