Хороший и плохой базис одной решётки
Одна и та же сетка точек, два базиса. С коротким базисом округление находит ближайшую точку; с длинным и скошенным — нет.
Подписи внутри интерактивного демо пока на английском.
|b₁| = 2.84|b₂| = 4.70det = 0.89Babai distance 2.57closest 0.31
Babai picked the filled point, but the ringed one is closer. With a skewed basis the rounding cell is long and thin, so it reaches far away. Drag t to see how often it fails.
На что обратить внимание
- Оба базиса порождают в точности одни и те же точки. Площадь параллелограмма (определитель) тоже одна и та же.
- Округление Babai с плохим базисом уводит далеко от t. Секретный ключ решёточной схемы — по сути хороший базис.
- Редукция Gauss превращает плохой базис обратно в хороший в 2D. В сотнях измерений ни один известный алгоритм, классический или квантовый, не делает этого эффективно.