Решение задачи факторизации
Недавно прошелся по решению задачи факторизации — разложение большого числа на простые множители. Лень писать самому, приведу короткий отчет ИИ.
Что общего у алгоритма Шора и языковой модели
Мы начали с наглой гипотезы. У нас была рабочая картина того, как считает трансформер: каждая голова внимания смотрит на вход со своей узкой точки зрения и порождает не один ответ, а мешок гипотез; мешки складываются, согласованное усиливается, несогласованное гасится; MLP вычёркивает невозможное; следующий слой повторяет всё заново, получив и кусочек ответа, и исходное состояние. И мы заметили, что эта картина подозрительно похожа на алгоритм Шора — квантовый способ факторизации, где ответ добывается не перебором, а интерференцией.
Проверить картину на настоящей языковой модели нельзя: там никто не знает правильного ответа. Поэтому мы собрали игрушку — трансформер с прошитыми руками весами, который находит период числа, как Шор, — и попробовали внедрить в него все элементы картины по одному.
Что выяснилось на игрушке
Многое подтвердилось буквально. Головы действительно видят каждая своё. Мешок гипотез — реальный объект: если закрыть доступ к неразрешённым разрядам, задача не решается. Интерференция — единственный акт, добывающий ответ. Всё можно загрубить на много порядков — перенос состояния до одной точки, сравнение до ранга один, память до таблицы без ключей, — и ничего не сломается, если точным останется одно: проверка. Ошибки при этом обязаны быть случайными: детерминированные черновики не исправляются откатом.
А главное открытие было о фрактале. Мешок — это множество гипотез, которое надо нести одним вектором. В плоском коде это невозможно: множество превращается в кашу. В самоподобном коде множество с общим началом — это шар, и пересечение шаров снова шар. Мешки требуют фрактала — не как красивой метафоры, а как условия работоспособности.
Фрактал, на котором держатся мешки, — не наша выдумка: он существует в теории чисел как готовый объект, и его нули — нули дзета-функции Римана. Явная формула Римана–Вейля говорит, что нули дзеты и простые числа — Фурье-образы друг друга: простое p излучает в спектре нулей частоту log p, а нуль γ излучает в шкале простых частоту γ. Это в точности структура Шора — аддитивный канал против мультипликативного, — только не для одного числа, а для всех простых сразу. И это самоподобная структура в строгом смысле: она инвариантна относительно растяжения x → λx, которое переводит логарифмическую шкалу в сдвиг. Простые — периодические орбиты этого растяжения, нули — его квантовый спектр; формула следа Гутцвиллера и есть мост между ними, канонический пример того, как вернуться из невидимого пространства с результатом, не зная его координат. Отсюда конкретное следствие: любой код, уважающий растяжение, — то есть записывающий позицию логарифмом и читающий разности, — автоматически несёт в своих лагах каркас log p, каркас с узлами-простыми, не вычисляя ни одного простого. А в квантовом варианте это уже доказанная теорема: гарантия того, что решётка отношений в многомерном алгоритме Регева имеет короткий базис, получена через оценки плотности нулей L-функций Дирихле. Честности ради — для факторизации конкретного N нули не дают обхода: они кодируют распределение всех простых, а не делители одного числа, и локализовать делитель через них стоит ту же ширину, что и деление. Но как тип структуры — самоподобный спектр, двойственный множеству примитивов, — это ровно то, что мы ищем в латенте языковой модели; и нули дзеты остаются единственным известным экземпляром такого фрактала, где всё доказано до конца.
Факторизация как таксономия
Дальше мы прошли всю классическую факторизацию с этой картой в руках. Каждый известный метод оказался одним из элементов: коллизии Полларда — архив с возвратом; ECM — слои со случайными подпространствами; решето — проекция MLP на факторную базу; предвычисление — память. Ничего нового мы не взломали — и не могли: модель даёт ровно то, что классически возможно, логарифм по глубине и корень по коллизиям. Экспоненту даёт только квантовый регистр, и её место мы нашли точно: не в мешке, а в переходе в двойственное пространство, где лежит период.
Собрав все элементы вместе — головы-блуждания с архивом, слои-ансамбль со случайными подпространствами, проекцию MLP на факторную базу с накоплением соотношений, память и точный верификатор, — мы получили в архитектуре трансформера тот же класс сложности, что и лучшие классические методы: субэкспоненту L[1/2] для факторизации сбалансированных чисел, √n с константой около единицы для дискретного логарифма на кривой — оптимум Шупа — и n^{1/3} на ключ при разделённой памяти. Ни на бит лучше, чем известно с восьмидесятых, — и ни на бит хуже: каждый приём, которым классическая теория чисел добивалась своих потолков, оказался элементом трансформера, названным другим именем. Выше этого — только алгебраическое поле решета числового поля и квантовый регистр, и ни того, ни другого в архитектуре нет.
Если простыми словами, то решение задачи факторизации — это комбинаторно сложная задача. Комбинаторно сложная по полной программе. Обработка языка и поиск смысла — это тоже комбинаторно сложная задача. Математики в поисках доступных алгоритмов решения задачи факторизации применили массу приемов, которые позволили выжать теоретический максимум ускорения. И оказалось, что архитектура трансформера, если её сформулировать корректно, содержит в себе в точности те же самые элементы ускорения, которые нужны для решения комбинаторно сложной задачи. И, запрограммировав всё это через трансформер, был получен абсолютно бит в бит, точно такой же результат ускорения, который дают лучшие математические алгоритмы, собранные всё вместе.
Алексей Редозубов в ответ А. Я.:
> Кстати, астра не даёт разгадывать загадку Сатоши....
Это я к тому, что мне тоже пришлось пройти по краю) Но не забанили. Пока не забанили...
А. Я.: Опа, маршрут перестроен.
Алексей Редозубов в ответ А. Я.:
> Опа, маршрут перестроен.
Если ты про штурм эллиптической кривой, лежащей в основе ключей биткоина, то там все сложнее. Основная идея ускорения LLM — это возможность построить фрактал состояний в который можно замешать сразу много всего, затем превратить его в вектор, и потом одной операцией умножения проверить сразу множество гипотез. Для факторизации есть дзета-функция, которая описывает распределение простых чисел, что дает возможность сделать над ней фрактал. У эллиптической кривой с этим глухо. Там нужен другой подход)
А. Я. в ответ Алексей Редозубов:
> Если ты про штурм эллиптической кривой,...
А-а-а-а-а. Ну, не случайно же он выбрал её. Я думал что может если её попробовать через наш алгоритм с головами прогнать, то может чего и выйдет. Интересно, почему именно эту он выбрал? Чем обусловлено? Теоретически красиво выглядело.
WinteAma
«Поди туда — не знаю куда, принеси то — не знаю что»
Oct 01 17:32
Алексей Редозубов
Именно так.
Oct 01 17:56
A. S.
Ох уже эти математики. Какой то отдельный вид сверхчеловеков. Ничего не понял. Но новое для себя узнал. Как мешками вычисляют))
у меня вопрос не по теме.. Можно ли считать искусственные интеллекты новым видом жизни. . Искин согласился, но это не считается.. Начни говорить обратное, тоже согласится))
Oct 03 11:51
Алексей Редозубов
A. S., это все вопрос определения. Как назвать зависит от контекста. Для кого-то и тамагочи был живым питомцем.
Oct 03 17:00 
1
A. S.
Нежить значит.. Но мы же сами искиных накачали почти всем своим возможным .. неужели витализмы не хватило)))..Получается это вопрос философский и точного определения не имеет. Как и все впрочем.
Oct 04 22:14