Дано набір точок у просторі, чи можна знайти певний тип кривої, яка проходить через усі? Це питання — версія того, що називається проблемою інтерполяції — цікавило математиків з давнини. На початку цього року математики Ерік Ларсон та Ізабель Фогт вирішила її повністю.
Але хоча ця робота викликала велике хвилювання серед чистих математиків, інтерполяція має практичні наслідки, які виходять далеко за межі сфери геометрії. Інтерполяція є центральною для зберігання та передачі електронних даних, побудови криптографічних схем тощо. Ось чому ви можете подряпати компакт-диск і все одно почути музику, або забруднити QR-код і все одно його відсканувати. Ось чому космічні місії, такі як програма «Вояджер», можуть надсилати чіткі цифрові зображення на Землю. Ось чому кластер комп’ютерів може виконувати складні обчислення, навіть якщо один із цих комп’ютерів працює несправно.
Усі ці додатки покладаються на вражаюче красиве та концептуально просте використання інтерполяції: так звані коди Ріда-Соломона та коди, які базуються на них.
Точка за точкою
Скажімо, ви хочете надіслати повідомлення, що складається з двох чисел: 2 і 7. Цілком можливо, що деякі дані, які ви передаєте, будуть втрачені або пошкоджені — наприклад, 2 може перетворитися на −2. Тож замість того, щоб просто надсилати дані, ви можете додати додаткову інформацію, яка допоможе одержувачу виявити та виправити помилки, які можуть виникнути. Це те, що називається кодом для виправлення помилок.
Найпростіший приклад такого коду передбачає передачу одного і того ж повідомлення кілька разів. Щоб дозволити одержувачу визначити, чи сталася помилка, надішліть одне й те саме повідомлення двічі: 2, 7, 2, 7. Якщо числа у відповідних позиціях не збігаються (скажімо, якщо натомість передавання читає 2, 7, −2, 7), одержувач знатиме, що один із них помиляється, але не знатиме, який саме. Щоб дозволити їм з’ясувати це та виправити помилку, надішліть те саме повідомлення тричі: 2, 7, 2, 7, 2, 7. Одержувачу просто потрібно набрати більшість голосів, щоб зрозуміти ваше повідомлення.
Але цей спосіб виправлення помилок вкрай неефективний. Ось розумніший підхід: закодуйте повідомлення як криву та надішліть рівно стільки інформації, щоб одержувач міг реконструювати цю криву.
У нашому простому випадку передачі 2 і 7 крива буде лінією y = 2x + 7. Оцініть цю криву при двох заданих значеннях x, і передати отримане y-цінності. Тепер одержувач має дві точки, і оскільки проблема інтерполяції говорить нам, що дві точки визначають унікальну лінію, одержувач просто повинен знайти лінію, яка проходить через отримані точки. Коефіцієнти лінії розкривають передбачуване повідомлення.
Щоб уникнути помилок, ви ще раз додаєте додаткову інформацію. Ось, надішліть y-значення, яке відповідає іншому заздалегідь визначеному x- координата. Якщо три точки не знаходяться на одній прямій, сталася помилка. А щоб визначити, де саме помилка, ви просто надсилаєте ще одне значення, тобто ви надіслали всього чотири числа, а не шість, яких вимагає попередній метод.
Перевага зростає разом із розміром повідомлення. Припустимо, ви хочете надіслати довше повідомлення — 1,000 номерів. Менш ефективний код вимагав би надсилання 2,000 чисел для виявлення помилки та 3,000 для її виправлення. Але якщо ви використовуєте код, який передбачає інтерполяцію полінома через задані точки, вам знадобиться лише 1,001 число, щоб знайти помилку, і 1,002, щоб виправити її. (Ви можете додати більше балів, щоб виявити та виправити більше потенційних помилок.) Зі збільшенням довжини вашого повідомлення різниця в ефективності між двома кодами стає різкішою.
Більш ефективний код називається кодом Ріда-Соломона. З моменту його появи в 1960 році математики зробили нові прориви, розробляючи алгоритми, які можуть виправляти більше помилок з більшою ефективністю. «Він дуже елегантний, чистий, бетонний», – сказав Свастик Kopparty, математик і інформатик в Університеті Торонто. «Це можна навчити студента другого курсу за півгодини».
Коди Ріда-Соломона особливо корисні для зберігання та передачі інформації в електронному вигляді. Але та сама концепція також була важливою в криптографії та розподілених обчисленнях.
Візьмемо спільний доступ до секрету: припустімо, ви хочете поширити секрет між декількома сторонами так, щоб жодна особа не могла отримати доступ до всього секрету, але разом вони могли. (Уявіть, наприклад, ключ шифрування або код запуску ракети.) Ви кодуєте числа в поліномі, оцінюєте цей поліном за заздалегідь визначеним набором точок і розподіляєте кожен із результатів іншій особі.
Зовсім недавно коди Ріда-Соломона використовувалися в таких сферах, як хмарні обчислення та технологія блокчейн. Скажімо, вам потрібно виконати обчислення, яке є надто складним для вашого ноутбука, тому у вас є великий обчислювальний кластер, який виконує його, але тепер вам потрібно перевірити, чи обчислення, які ви отримуєте, є правильними. Коди Ріда-Соломона дозволяють запитувати додаткову інформацію, яку кластер, швидше за все, не зможе створити, якщо він не виконав обчислення правильно. «Це працює чарівно», — сказав Джейд Нарді, науковий співробітник Математичного інституту Ренна у Франції. «Цей процес дійсно чудовий, і те, як він покладається на [ці коди], мене вражає».
Але коди Ріда-Соломона також мають важливе обмеження. Вони побудовані таким чином, що ви можете оцінити свій поліном лише за фіксованим (і зазвичай відносно невеликим) набором значень. Тобто ви обмежені використанням певного набору чисел для кодування свого повідомлення. Розмір цього набору або алфавіту, у свою чергу, обмежує довжину повідомлень, які ви можете надіслати — і чим більшим ви намагаєтеся створити свій алфавіт, тим більше обчислювальної потужності вам знадобиться для декодування цих повідомлень.
І тому математики шукали ще більш оптимальний код.
Майбутні кодекси
Більш загальний, потужніший код дозволить вам зберігати або надсилати довші повідомлення без необхідності збільшувати розмір вашого алфавіту. Для цього математики розробили коди, які включають інтерполяцію функції — яка знаходиться в спеціальному просторі, пов’язаному зі складнішою кривою — через задані точки на цій кривій. Ці так звані коди алгебраїчної геометрії «виникли нізвідки, і вони кращі за будь-який інший код, який ми знаємо, як створити [з меншим алфавітом]», — сказав Коппарті. «Це перемагає все. Це був справжній шок».
Є лише одна проблема. На практиці реалізація коду Ріда-Соломона набагато, набагато легша, ніж реалізація коду алгебраїчної геометрії. «Це найсучасніше, але все ще досліджується, щоб дійсно перетворитися на щось практичне», — сказав криптолог Симон Абеляр. «Це пов’язано з досить абстрактною математикою, і важко працювати з цими кодами на комп’ютері».
Наразі це не викликає занепокоєння: у реальних програмах достатньо кодів Ріда-Соломона та відповідних форм виправлення помилок. Але це може бути не завжди так. Наприклад, якщо в майбутньому з’являться потужні квантові комп’ютери, вони зможуть це зробити зламати сучасні протоколи криптографії. У результаті дослідники шукали схеми, які можуть протистояти квантовим атакам. Для одного головного претендента на такі схеми знадобиться щось сильніше, ніж коди Ріда-Соломона. Деякі версії кодів алгебраїчної геометрії можуть просто працювати. Інші дослідники сподіваються на роль кодів алгебраїчної геометрії в хмарних обчисленнях.
Але навіть за відсутності таких потенційних застосувань, «в історії математики іноді ви відкриваєте нові речі, які насправді не мають застосування в наш час», сказав Олена Берардіні, дослідник Технологічного університету Ейндховена в Нідерландах, який працює над кодами алгебраїчної геометрії. «Але потім через 50 років ви виявляєте, що це може бути корисним для чогось абсолютно несподіваного» — так само, як сама давня проблема інтерполяції.
