search

keeganryan / flatter

Fast lattice reduction
GNU Lesser General Public License v3.0
160 stars 13 forks source link

Wrong profile #15

Closed ludopulles closed 6 months ago

ludopulles commented 6 months ago

When running printf "[[127 0]\n[75 1]]" | flatter -q -p, the output profile (log2) is 2.96537 3.95405. However, the actual profile should have norms [7.81025, 16.2607] instead of [7.81026, 15.4984]. This can e.g. be checked with printf "[[127 0]\n[75 1]]" | fplll -a bkz -b 2 -bkzdumpgso log_norms which outputs the natural log of all the GS squared norms.

Note that in all cases, the same reduced basis is acquired (up to signs): [[-6 5 ], [11 12 ]].

keeganryan commented 6 months ago

Thanks for the report! I've replicated it and confirm that the correct output should be [7.81025, 16.2607]. I'll investigate.

keeganryan commented 6 months ago

There was a sign error in how the output profile was calculated for 2-dimensional lattices.

Since the profile is recomputed using a different method at higher recursion levels, this bug would only appear in the final output for these small lattices. However, it's possible this bug also led to incorrect precision calculations for the second-to-last recursive level, leading to some unnecessary extra computation.