Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
Изогения между двумя эллиптическими кривыми – это полиномиальное отображение одной из них на другую, сохраняющее структуру группы Морделла – Вейля. Мы используем изогении для определения ребер графа. Для этого следует взять второе простое число q. Ребра этого графа соответствуют изогениям q-й степени между двумя эллиптическими кривыми, соответствующими концам данного ребра. Из каждой вершины исходит ровно q + 1 ребер. Такие графы называются экспандерами, или расширяющими, это означает, что случайные пути, начинающиеся в любой вершине, быстро расходятся после их начала, по крайней мере на протяжении большого числа шагов.
Граф-экспандер может быть использован для создания функции хеширования – булевой функции, формирующей из n-битных строк m-битные, где m много меньше n. Алиса может использовать хеш-функцию, чтобы убедить Боба, что она знает конкретную n-битную строку, известную также и Бобу, не раскрывая самой строки. Для этого она формирует намного более короткую хеш-функцию этой строки и отправляет ее Бобу. Боб вычисляет хеш-функцию своей строки и сравнивает.
Для того чтобы этот метод надежно работал, необходимо выполнить два условия. Одно из них – это условие потайного входа, известное как стойкость к восстановлению прообраза: с вычислительной точки зрения невозможно обратить хеш-функцию и найти n-битную строку, которая дает данный хеш. В общем случае таких строк существует множество, но дело в том, что на практике невозможно найти ни одной. Второе условие – стойкость функции хеширования к коллизиям. Это означает, что с вычислительной точки зрения невозможно найти две разные n-битные строки с одним и тем же m-битным хешем. Раз так, то даже если Ева – любительница подслушивать (или устройство перехвата сообщений) – сумеет подслушать разговор, то хеш, который Алиса пересылает Бобу, не поможет ей разобраться, что представляла собой первоначальная n-битная строка.
Если у нас имеется два простых числа p и q, удовлетворяющие дополнительным формальным условиям, мы можем воспользоваться этой идеей, построив соответствующий SIG, а затем использовать его свойства экспандера, чтобы определить стойкую как к восстановлению прообраза, так и к коллизиям функцию хеширования. Эту функцию можно использовать для создания высоконадежного шифра. Взлом такого шифра требует вычисления множества изогений между эллиптическими кривыми. Лучший квантовый алгоритм для одного такого расчета выполняется за время p1/4. Сделайте p и q достаточно большими (математика подсказывает, насколько большими), и вы получите криптосистему, которую не сможет взломать даже квантовый компьютер.
Все это выглядит очень заумно. Вряд ли вы разобрались во всех деталях, тем более что большую их часть я опустил. Но, я надеюсь, вы поняли главное: чтобы успешно защитить личную, коммерческую и военную связь от любителей подслушивать, вооруженных гипотетическими сегодня, но вполне реальными в скором времени квантовыми компьютерами, нам потребуется не что иное, как очень продвинутая и абстрактная математика, имеющая отношение к алгебраической геометрии над конечными полями.
Теория чисел, столь любимая Харди, оказалась куда более полезной, чем он мог вообразить. Но некоторые из сегодняшних ее применений наверняка разочаровали бы его. Думается, нам следовало бы извиниться перед ним за это.
6
Числовая плоскость
Божественный дух указал на возвышенное применение того чуда анализа, того предвестника идеального мира, той двойственной сущности, находящейся между бытием и небытием, которую мы называем мнимым корнем из отрицательной единицы.
ГОТФРИД ВИЛЬГЕЛЬМ ЛЕЙБНИЦ.
Acta Eruditorium (1702)
В настоящее время мы являемся свидетелями второй квантовой революции. Первая квантовая революция дала нам новые правила, которые управляют физической реальностью. Вторая квантовая революция позволит создавать новые технологии на основе этих правил.
ДЖОНАТАН ДАУЛИНГ И ДЖЕРАРД МИЛБЕРН.
Philosophical Transactions of the Royal Society (2003)
В нашем районе города Ковентри в последние месяцы наблюдается какая-то непонятная, но активная деятельность. Всюду вдоль обочин виднеются припаркованные белые автобусы, часто в сопровождении грузовиков с лопатами и тачками. Мини-экскаваторы ездят туда-сюда по улицам, копают канавы вдоль тротуаров, поперек дорог, через газоны и скверы, а полосы свежеуложенного асфальта тянутся во все стороны, подобно следам, оставленным слизнями размером с собаку. Люди в куртках со светоотражающими элементами то и дело ныряют в колодцы с открытыми люками. Катушки с кабелем красуются на газонах, притулившись к живым изгородям, и ждут, когда кабель засосет в колодцы. Сосредоточенные инженеры сидят под навесами от дождя и разбираются с тысячами разноцветных проводов в больших металлических ящиках.
На бортах автобусов имеется надпись, объясняющая происходящее: «Сверхбыстрая широкополосная связь уже в вашем районе».
В центры крупных городов Великобритании это чудо современных телекоммуникаций пришло уже давно, но наш дом находится на тихой окраине. Как-то к нам даже отказались ехать по вызову, потому что мы живем слишком далеко – на расстоянии целых пяти километров. Справедливости ради замечу, что граница города проходит всего в нескольких сотнях метров от нас. Прокладка кабелей здесь стоит дороже, а плотность населения меньше, потому что сразу за границей города начинаются фермерские поля. Здесь нет возможности легкого расширения с минимальными затратами. Мы просто не были привлекательным предложением. Но в конечном итоге, после того как правительство надавило на телекоммуникационные корпорации, началось повсеместное подключение к оптико-волоконным линиям всех городских и большинства сельских районов. Наконец, остальная страна начала догонять районы с максимальной плотностью населения, где подключение к интернету становится все быстрее и быстрее. Отставание как минимум перестало расти.
В век, когда чуть ли не все виды деятельности перебираются, хотя бы частично, в интернет, быстрая широкополосная связь из роскоши превратилась в жизненную необходимость. Может быть, не настолько жизненную, как вода или электричество, но уж никак не менее важную, чем телефон. Хитроумная электроника – движитель компьютерной революции и систем быстрой всемирной связи – сделала мир 2020-х годов таким, какой невозможно было представить еще в 1990-е годы. И это только начало. Расширение предложения вызывает взрывной рост спроса. Дни, когда телефонные линии представляли собой медные провода и передавали голосовые сообщения, быстро уходят в прошлое, да и домашние телефоны в последние годы работают только благодаря хитроумным электронным и математическим фокусам, позволяющим повысить пропускную способность. Сегодня телекоммуникационные кабели передают куда больше цифровых данных, чем разговоров. Именно поэтому на передний план вышло оптическое волокно.
Пройдет еще несколько десятилетий, и оптоволокно так же устареет, как устарели в свое время лошади и повозки. На очереди другие новинки, которые позволят передавать намного большие объемы данных с захватывающей дух скоростью.
