У математиці метою зведення базису ґратки є знаходження базису з короткими, майже ортогональними векторами, коли на вхід подається ґратка із цілочисельним базисом. Це здійснюють за допомогою різних алгоритмів, час роботи яких зазвичай щонайменше експоненційно залежить від розмірності ґратки.

Пошук зведеного базису ґратки також тісно пов'язаний із кристалографічною задачею знаходження однозначної елементарної комірки. Історично теорію зведення вперше дослідив Лагранж (у 1773 році), а згодом незалежно від нього — Гаус (у 1801 році) із метою класифікації , що є класичною проблемою теорії чисел. У короткій примітці до рецензії на книгу 1831 року, Гаус зауважує, що теорія зведення для певних квадратичних форм еквівалентна знаходженню елементарної комірки для точкових ґраток, і відзначає важливість цього зв'язку для кристалографії. Ця глибока спорідненість між теорією чисел та геометрією точкових ґраток надихнула чимало наступних праць із квадратичних форм, вершиною яких стала визначна праця Мінковського «Геометрія чисел» (1896 та 1910 роки).

Міра близькості до ортогональності Однією з мір близькості до ортогональності є дефект ортогональності. Він зіставляє добуток довжин базисних векторів з об’ємом утвореного ними паралелепіпеда. Для цілком ортогональних векторів базису ці величини збігаються.

Будь-який конкретний базис із векторів можна подати матрицею ,стовпцями якої є базисні вектори У повновимірному випадку, коли кількість базисних векторів збігається з розмірністю простору, який вони займають, ця матриця є квадратною, а об’єм фундаментального паралелепіпеда є просто абсолютним значенням (модулем) визначника цієї матриці . Якщо ж кількість векторів менша за розмірність базового простору, то об’єм дорівнює . Для заданої ґратки цей об’єм є незмінним (з точністю до знака) для будь-якого базису, тому його називають визначником ґратки або сталою ґратки .

Дефект ортогональності — це добуток довжин базисних векторів, поділений на об’єм паралелепіпеда;

З геометричного випливає, що , причому рівність досягається тоді й лише тоді, коли базис є ортогональним.

Якщо задачу зведення ґратки визначити як пошук базису з найменшим можливим дефектом ортогональності, то вона є NP-повною . Однак, існують алгоритми з поліноміальним часом для знаходження базису з дефектом де c — деяка константа, що залежить лише від кількості базисних векторів та розмірності базового простору (якщо вони різні). акого розв’язку цілком достатньо для багатьох практичних застосувань, як-от під час розкладання многочленів на множники.

Випадок двох вимірів Для базису, що складається лише з двох векторів, існує простий та ефективний метод зведення, дуже подібний до алгоритму Евкліда для знаходження найбільшого спільного дільника двох цілих чисел. Як і алгоритм Евкліда, цей метод є ітераційним; на кожному кроці більший із двох векторів зменшують, додаючи або віднімаючи ціле кратне меншого вектора.

Псевдокод алгоритму, часто відомого як алгоритм Лагранжа або алгоритм Лагранжа-Гауса, виглядає наступним чином: Вхідні дані: основа для ґратки . Припустимо, що , інакше поміняйте їх місцями. Результат: Базис з .

Допоки : # Округлення до найближчого цілого числа

Див. розділ про алгоритм Лагранжа в для отримання додаткової інформації.

Застосування Алгоритми зведення ґраток застосовують у низці сучасних теоретико-числових задач, зокрема під час відкриття алгоритму spigot для обчислення числа .. Хоча знаходження найкоротшого базису, ймовірно, є NP-повною задачею, такі алгоритми, як здатні знайти короткий (не обов’язково найкоротший) базис за поліноміальний час із гарантованими характеристиками у найгіршому випадку швидкодії. широко використовується в криптоаналізі криптосистем із відкритим ключем .

У разі застосування для пошуку цілочисельних співвідношень на вхід алгоритму зазвичай подають розширену одиничну матрицю, останній стовпець якої містить елементів (що помножені на велику додатну константу , аби штрафувати вектори, що в сумі не дають нуля), між якими шукають зв'язок.

для обчислення майже ортогонального базису був використаний, щоб показати, що цілочисельне програмування в будь-якій фіксованій розмірності може бути виконане за поліноміальний час.

Алгоритми Наведені нижче алгоритми зводять базиси ґраток; також перераховано кілька публічних реалізацій цих алгоритмів. Рік Алгоритм Впровадження 1773 рік Зведення Лагранжа для бінарних квадратичних форм 1801 рік Гаусове зведення для бінарних квадратичних форм у його ранній роботі «Арифметичні роздуми» 1831 рік Гаусс згадує в огляді книги зв'язок певних квадратичних форм з 2D та 3D точковими ґратками як додаткову примітку (Goettingische gelehrte Anzeigen 1831, розділ 108) 1840 рік Рецензія на книгу Гаусса передрукована в журналі Крелла 1850 рік Ерміт закладає основу для зведення ґратки у вищих вимірах 1851 рік Стаття Ейзенштейна, що закладає основу для теорії Нігглі 1873 рік Коркін і Золотарьов уточнюють метод Ерміта (HKZ) 1874 рік Зведення Селінга для потрійних квадратичних форм з використанням геометричних понять Гауса 1896 рік Зведення Мінковського за допомогою найкоротших послідовних векторів (до 4D) 1928 рік Зведення Нігглі для 3D-ґраток у кристалографії для визначення найкращої елементарної комірки 1933 рік Зведення Делоне (Делоне), що оптимізують метод Селінга для кристалографії 1970 рік Санторо та Мігелл пропонують метод знаходження зведеної елементарної комірки в кристалографії 1982 рік , fpll 1987 рік Блок Коркіна–Золотарьова , fpll 1993 рік Зведення Сейзена

Посилання