dxdt.blog: занимательный интернет-журнал

Борелевский шаман с высокой вероятностью угадывает одно из простых чисел, составляющих модуль RSA большой разрядности. Делает это шаман быстрее и точнее квантового компьютера, якобы реализующего алгоритм Шора. Потому что компьютер выдаёт шум, а шаман – действует иначе: известно, что множество простых чисел задаётся некоторой формулой (оно диофантово); всевозможные произведения простых – область значений некоторой функции (вспомните про факториал); борелевский шаман постоянно слышит ритм этой формулы и ритм этой функции, поэтому, как только охватит внутренним взором представленный модуль RSA, так тут же улавливает из движений варпа и ритмов близкое к простому множителю значение, которое записывает на пергаменте. Остаётся только правильно истолковать запись, что не всегда легко сделать, но сделать можно.

В целом, всё точно так же, как, возможно, работал бы универсальный квантовый компьютер внутри. Однако, в случае с компьютером, получить полезное значение мешает шум, который “расшифровать” не получается совсем. В отличие от записей борелевского шамана, с которыми квантовый “шум” нужно сопоставлять. Поэтому попытка создать квантовый компьютер всё равно очень полезна. Если рассматривать её с точки зрения понимания части деятельности шамана, то она позволяет, – в теории, опять же, – уверенно обнаружить через модели квантовых вычислений варп.

Вообще, обнаружение варпа в профильной литературе традиционно связывают с ускорителями частиц, но, с философской точки зрения, попытки построения квантовых компьютеров должны быть тут намного эффективнее: варп гораздо сильнее связан с представлением о преобразованиях сверхструктуры, сечения которой являются событиями реальности, чем подсчёт погрешностей в измерениях только одной маленькой части общей комбинаторики – стандартной модели в физике.

Откуда планируется брать “вычислительные мощности” для квантовых вычислений? Представление об этом позволяет составить полезная интерпретация двухщелевого опыта: здесь отдельный фотон в элементарной итерации регистрируется в одной (случайной) точке экрана и не регистрируется во всех других точках; при этом накопленная картина для двух щелей не совпадает с наложением картин, которые даёт каждая из щелей в отдельности. То есть, можно предположить, что регистрация фотона моментально отключается для прочих точек экрана в результате работы некоторого механизма, обеспечивающего и вычисление изменений в картину для двухщелевой конфигурации. Вот на этом загадочном гипотетическом механизме и предлагается выполнять квантовые вычисления.

Отдельные занимательные эффекты, связанные с переключением морфологических веток, можно наблюдать в автоматических переводчиках с ИИ. Кстати, надо сказать, что автоматический переводчик “Яндекса“, приправленный LLM ИИ, при переводе специальных фраз с английского на русский действует несколько лучше переводчика от Google (не менее приправленного). Вот примеры, иллюстрирующие и переключение интерпретаций по контексту, и качество.

1.
Исходная фраза:
“As a sailor once said: having logs removed in timely manner keeps bank totally speckless.”

Google:
Как однажды сказал один моряк: если вовремя убрать бревна, берег будет совершенно чистым.

“Яндекс”:
Как однажды сказал один моряк: своевременное удаление бревен позволяет сохранить берег совершенно чистым.

2.
“As a bookkeeper once said: having logs removed in timely manner keeps bank totally speckless.”

Google:
Как однажды сказал бухгалтер: своевременное удаление бревен делает банк совершенно чистым.

(Здесь Google предпочёл “брёвна” в банке, а не несколько более уместные “журналы”, как “Яндекс”.)

“Яндекс”:
Как однажды сказал один бухгалтер: своевременное удаление журналов позволяет сохранить банк полностью незапятнанным.

3.
“Bookkeeper mumbled the old nautical adage: having logs removed in timely manner keeps bank totally speckless.”

Google:
Бухгалтер пробормотал старую морскую поговорку: своевременное удаление бревен делает берег совершенно чистым.

“Яндекс”:
Бухгалтер пробормотал старую морскую пословицу: “своевременное удаление бревен сохраняет банк совершенно чистым”.

(Использование nautical успешно превращает logs в “брёвна”, сохранив “банк” силами слова bookkeeper, в котором три “дуплета”, но зато переводчик “Яндекса” даже кавычки поставил.)

Фольклорная интерпретация термина “квантовый компьютер” строится на предположении, что характеристика “квантовый” отражает последовательное уменьшение линейных размеров микроэлектронных элементов: “сначала процессоры строили по “микрометровой” технологии, потом – из сотен нанометров, потом – уменьшили до десятков нанометров, а следующий шаг уменьшения – это уже и есть “квантовые” компьютеры”. Занятно, что, с некоторыми оговорками, это описание вполне годится в качестве верхнеуровневого объяснения наблюдаемой на практике ситуации.

Так, во-первых, попытка создания универсальных квантовых компьютеров – это попытка пройти на уровень, находящийся ниже не только всех этих полупроводников, но и ниже отдельных электронов. Во-вторых, для того, чтобы на этот уровень пройти, требуется создание инструментов для манипулирования отдельными частицами, с минимальными затратами энергии на вычисления и с минимальным временем выполнения операций, так что, когда (и если) окажется, что квантовый компьютер сделать не получается, технические результаты можно будет попробовать использовать для создания “ультракомпактных” вычислительных элементов, возможно, с трёхмерной вычислительной архитектурой.

Немного технологических параллелей. Предположим, что на сервер баз данных, через сеть, отправляются запросы добавления записей. При этом каждый запрос требует завершения транзакции – то есть, обратно клиенту должен прийти пакет, подтверждающий выполнение, после этого клиент может отправить следующий запрос. В условных терминах привычного SQL – это будут команды INSERT. Известно, что в такой схеме производительность, по числу добавлений в секунду, определяется сетевой задержкой. То есть, если пакет находится в пути 10 ms, то сервер должен дожидаться следующего INSERT 20 ms (потому что в обе стороны), а это гарантирует верхний предел в 50 записей в секунду, даже если сервер выполняет одну запись за 1 микросекунду (на несколько десятичных порядков быстрее).

Проблема, конечно, решается поточной записью “списками”, когда новые запросы поступают без ожидания завершения транзакции или какого-либо подтверждения по предыдущим запросам (например, COPY). Сетевая задержка тут уже успевает помешать только один раз, в начале соединения, а дальше – очередной запрос поступает на сервер тут же, следом за предыдущим, что позволяет работать с большей производительностью.

Естественно, эта особенность действует не только для баз данных: ограничивающее влияние сетевых задержек на транзакционные схемы с подтверждением есть в TCP (где с этим явлением борются: см. TCP Fast Open), в TLS (здесь тоже борются: см. TLS Early Data/0-RTT и др.), и в других протоколах. Схема обобщается и на многие решения, которые не имеют отношения к интернет-протоколам.

Рассмотрим такой сценарий: РЛС, предназначенная для определения координат и скорости “быстрых объектов” на “существенном расстоянии”. Тривиальная импульсная РЛС, полагающаяся на отражения отдельных зондирующих импульсов в строгом порядке, оказывается в такой же ситуации, как и сервер баз данных выше (при том, конечно, что РЛС появились раньше таких серверов). Излучили короткий импульс – приняли отражённый сигнал, обработали, отправили очередной импульс – если время до цели 1 ms (300 км, примерно), то получается разрешающая способность наблюдения в 500 Гц, максимум. А если цель дальше, то будет меньше. Хуже всего, что отражённый сигнал вообще может не прийти обратно к точке излучения на нужном уровне. Но если импульсы отправлять чаще, не ждать отражения, или даже использовать непрерывный зондирующий сигнал, то ситуация, в теории, резко улучшается, как и в случае с сервером баз данных: можно обрабатывать отражённый сигнал с разрешением хоть в гигагерц. На практике, впрочем, возникнут проблемы, потому что РЛС – это не сервер баз данных. Принимать сигнал одновременно с излучением – весьма трудно, если не использовать разнесённые в пространстве антенны (бистатическая радиолокация). А увеличение частоты следования зондирующих импульсов требует использования более сложных алгоритмов кодирования и обработки, которые позволяют различать отражённые сигналы, соответствующие различным зондирующим импульсам. Это, впрочем, обычная задача для современных РЛС.

“Песочница – это такая изолированная среда, где производится виртуальное исполнение подозрительного кода, чтобы без ущерба выявить возможную вредоносную активность. Вредоносы развиваются, логика их активации пользователем становится всё сложнее. Поэтому песочница должна имитировать действия пользователя всё точнее и точнее. Мы постоянно улучшали модель пользователя. Наша модель “открывала” файлы, “двигала” мышкой, генерировала клавиатурный ввод – сперва достаточно простые марковские цепи, потом многоуровневая система библиотек из словарей, построенная на литературном корпусе, с нелинейной памятью.

В какой-то момент выяснилось, что модель полностью выполняет все пользовательские задачи. Если процесс не прерывался вредоносным кодом, то обработка входящих сообщений в песочнице давала такой же результат, как и действия настоящего пользователя; а нередко результат был лучше. Оставалось только достать этот результат из песочницы и – настоящий пользователь уже оказывался не нужен. Неожиданно открывшиеся перспективы поражали.

Но коллеги из отдела “Основания математики”, говорившие что-то про диагонализацию, оказались правы. Как только мы попытались реализовать механизм безопасного вытаскивания наружу результата работы модели пользователя, выяснилось, что в модель требуется включить функцию взаимодействия с песочницей – иначе непоправимо страдала полнота: например, нельзя не учитывать такой триггер, как копирование файла на внешний, относительно песочницы, носитель. К сожалению, это означает, что внутри нашей песочницы придётся эмулировать ещё одну песочницу, которая нужна для полной модели пользователя. А внутри новой песочницы – нужна ещё одна. Казалось бы, на третьем уровне можно остановиться: потому что если “вывернуть” получившуюся конфигурацию, то она, в алгоритмическом смысле, окажется эквивалентной новому шагу конструктивного построения полной модели. Но операция “выворачивания” точно так же требует расширения модели.

Всё это довольно сложно. В общем, сейчас нас занимает совсем другая мысль: не являемся ли мы сами чьей-то моделью пользователя, ограничения которой не позволяют довести нашу песочницу до ума?”

(Май 2017 г.)

Воскресное чтение манускриптов. В этот раз – пара иллюстраций из инструкции по созданию метательных машин от Герона Александрийского (первый век н.э), в версии манускрипта Vat.gr 1164 (а это уже 11 в., тысячу лет спустя) из Ватиканской Апостольской библиотеки. Схема баллисты:

Подробный чертёж важной детали (περίτρητα), которая обеспечивала крепление механической обвязки вокруг “торсиона” (текст со скриншота – относится к другому чертежу):

Описание этой детали из труда Герона обычно приводят в качестве примера древних научно-технических подходов, предоставлявших нужный уровень обобщения и абстракции не только через буквенные обозначения и математические основы черчения, но и путём использования вместо конкретных размеров указаний на отношение величин. Например, как в данном случае: через определение отношения 1:2 для сторон задающего деталь параллелограмма и т.д., это всё описывается в сопроводительном тексте – то есть, буквально, основы машинной графики и компьютерной геометрии, но две тысячи лет назад.

Можно предположить, что передача сообщений по радио полностью защищена от прослушивания, если прослушивающая сторона ничего не знает об электромагнитных волнах (что уж там говорить про наличие у этой стороны радиоприёмников). В газете напишут – “абсолютно защищена”. Может ли такая вымышленная ситуация служить аллегорией для современного внедрения квантовой криптографии? Навряд ли.

По крайней мере, аллегория получится слишком неполной и размытой. Да, про квантовую криптографию, следуя волне “хайпа”, едва ли не постоянно пишут, что она является “абсолютно защищённой, абсолютно стойкой”, якобы, из-за некоторых “физических законов” (естественно, законов таких нет, они в физике невозможны; есть некоторые допущения, но это, впрочем, другая история). Проблема с упомянутой аллегорией в том, что у тех, кто обменивается сообщениями по радио – есть радиостанции. Неявно предполагается, что они их как-то изготовили, а потом ещё смогли оценить степень исключительности своих знаний. То есть, несколько другая история. В случае квантовой криптографии, предположения о стойкости строятся в рамках почти той же прикладной модели, которая позволила создать сами оконечные устройства – приёмники и передатчики. Так что вариант, когда оценка степени защиты информации в радиоканале на уровне “абсолютная защита” делается из допущения, что прослушивающая сторона ничего не знает о радиосвязи, он совсем о другом – получается что-то вроде принципа Керкгоффса, а не аллегория оценок квантовой криптографии.

Можно предположить, что и сами пользователи радиостанций ничего не знают не только об устройстве радиостанций, но и понятия не имеют об электромагнитных волнах. Для того, чтобы запомнить, что голос из одной коробочки передаётся в другую – многие знания не требуются, так как система работает сама. Ну, пока батарейка не разрядилась. Тут уже принцип Керкгоффса исчезает сам собой (обратите, кстати, внимание на то, что применимость данного принципа, оказывается, зависит от контекста). Но к роли квантовой криптографии в современности это тоже совсем и никак не подходит: построить даже опытный образец усилиями ИИ с LLM внутри не выйдет, что уж там рассуждать про интерпретации квантовой механики.

Впрочем, история показывает, что разработчики и, особенно, пользователи радиооборудования могут недооценивать возможности утечек по побочным каналам (те самые ПЭМИН). Это, аллегорически, означает, что кто-то смог разобраться с электромагнитными излучениями чуть лучше. Известно, что такие утечки работают и для устройств квантовой криптографии. Кто бы, как говорится, сомневался: известно ещё до появления оптоволоконных линий связи – даже если по кабелю передаются сообщения, зашифрованные абсолютно, – в полноценном, математическом смысле, – стойким шифром, это не означает, что вместе с зашифрованными сигналами не передаётся и эхо исходника, в открытом виде. Но то всё “классические” утечки. Возможны ли утечки “квантовые”? Пока что непонятно. Однако к аллегории про радиоканал и технически неподготовленную прослушивающую сторону, которая пытается подползти к окну радиобудки, чтобы снять акустическое эхо собственными ушами, это уже не относится.

Картинка из прошлогодней записки про таблицу подстановок:

С чем связана такая геометрия верхней части? Прежде всего, с тем, что каждая строка там – это уменьшение “неопределённости” в два раза. И действительно: картинка состоит из значений байтов, повёрнутых вертикально, то есть, это таблица, в которой верхняя строка соответствует старшему биту байта. Последовательное увеличение значений байтов, справа налево, с использованием типового кодирования (это важная оговорка), означает, что половина клеток-пикселей старшего бита заполнена нулями, половина – единицами.

Нули и единицы разбивают всё пространство возможных значений на две равных части. Вот это и есть ключевой момент теоретико-информационного определения бита, про который нередко забывают даже при постоянной, – ручной, так сказать, – работе с битами/байтами: один бит информации соответствует уменьшению “неопределённости” в два раза, что бы там под “неопределённостью” ни подразумевалось. Если взять произвольный байт, то значений у него может быть 256 различных, это будет степень неопределённости. Если известен один бит, то возможных значений уже 128, если два бита, то 64, и так далее, перемещаясь по картинке вниз. А если эту концепцию наложить на идею непрерывности, то нетрудно увидеть целый набор фундаментальных математических объектов.

(Минутка технократического юмора.) Недавно я писал про двухщелевой опыт с ИИ – траекторные координаты попаданий электронов вводятся в ИИ, который должен предсказывать координаты следующего электрона. Между прочим, подобный эксперимент, в современных реалиях, уж точно привлёк бы огромное внимание профильной и не очень профильной прессы, ведь тут используются сразу две из трёх нитей актуальной нарративной канвы: квантовая физика и искусственный интеллект (название третьей нити угадать нетрудно). Эксперимент пока что не реализовали. Скорее всего, подготовка аппаратуры требует немало времени. (Ну или какая другая причина. Мало ли.)

В той заметке про ИИ в двухщелевом опыте, кроме прочего, написано:

Можно же даже так сделать: электрон попадает в экран детектора, координаты точки автоматически вводятся в нейросетевую систему ИИ, система корректирует собственные предсказания (известная схема). Электроны можно излучать быстро, нейросеть – тоже на быстром компьютерном оборудовании, с большим объёмом памяти. Осталось построить, запустить и ждать – сойдётся ли процесс. А если сойдётся, то выяснится, к чему это приведёт.

Как вообще это могло бы сработать и с каким результатом? Например, за системой со сложным, непредсказуемым, возможно – случайным, поведением, может скрываться достаточно простой набор параметров и элементарный, по своей записи, алгоритм. Это известно. Впрочем, “случайность и непредсказуемость” тут оказываются мнимыми, происходящими из недостатка вычислительной мощности, доступной исследователю. Системы компьютерных ИИ сейчас строятся на записи и преобразовании огромных массивов, состоящих из ячеек памяти. Получается, что если за квантовой случайностью, проявляющейся в отметках электронов на экране двухщелевого опыта, стоит некоторый простой, но неведомый, алгоритм, то при подключении этого алгоритма в память системы ИИ, выдача алгоритма, последовательно растянутая по времени (важный момент!), начнёт двигать миллиарды зарядов в микроэлектронных элементах ячеек памяти. И не просто так двигать, а согласованным, – пусть и непонятно как согласованным, – образом.

Эффект может быть неожиданным. Предположим, система лабораторной установки выводит своё предсказание результата опыта в виде “расчётной” интерференционной картины. И вот, после некоторого достаточного обучения электронами, проходящими через щели, система, погудев и мигнув неонкой, рисует на модели лабораторного экрана изображение числа сорок два.

Немного занимательной математики и глобальной DNS.

Насколько велика вероятность, что в доменах первого уровня глобальной DNS совпадут теги разных ключей DNSSEC? Нередко приходится слышать, что так как тег 16-битный, то и вероятность, примерно, 1/65535 (за вычетом особенностей алгоритма вычисления значения тега и пр.). Это не верно. Если рассматривать совпадения внутри набора ключей DNS, то получаем хрестоматийный пример парадокса дней рождения: нам не важно, чтобы повторилось конкретное, заданное значение тега, напротив – требуется совпадение любого значения внутри любой пары, а это совсем другая история, поскольку количество всевозможных пар велико даже в небольших наборах ключей. Поэтому вероятность совпадения тегов DNSSEC-ключей, на практике, очень велика. Иногда ключи просто обязательно совпадут по тегам. Например, в списке доменов первого уровня (корневой зоны DNS) сейчас 1452 имени, то есть, можно составить 1053426 пар (больше миллиона). А это количество (практически) гарантирует, что будут совпадения тегов ключей.

И действительно, если собрать DNSKEY-записи из доменов первого уровня, то окажется, что значений повторяющихся тегов, – то есть, значений, которые встречаются для разных ключей в разных зонах, – сильно больше сотни: у меня получилось 129 таких тегов. Обратите, кстати, внимание, что некоторые ключи разных зон TLD имеют одинаковые теги потому, что это просто одинаковые ключи. Такие повторы отбрасывались. Потому что корректно – сравнивать именно сами значения ключей (как и в прочих случаях использования тегов). Например, различные DNSSEC-ключи с одинаковыми тегами опубликованы в зонах cab и today, в зонах agency, weber и temasek, и во многих других.

(Дополнение: естественно, выше предполагается, что ключи для различных зон генерируются независимо, случайным образом.)