Иэн Стюарт - Математические головоломки профессора Стюарта
Составные модули усложняют ситуацию. Теперь одни и те же вычеты иногда могут быть квадратами больше чем двух чисел. К примеру, 1 по модулю 8 встречается четыре раза, как квадрат 1, 3, 5 и 7. Лучший способ разобраться во всем этом – воспользоваться современной абстрактной алгеброй, но имеет смысл взглянуть и на модуль 15. У него два простых множителя: 3 × 5. А вот список квадратов:
Таким образом, квадратичные вычеты по модулю 15 равны
0 = 0²
1 = 1², 4², 11², 14²
4 = 2², 7², 8², 13²
6 = 6², 9²
9 = 3², 12²
10 = 5², 10²
Некоторые вычеты возникают один раз, некоторые дважды, некоторые четырежды. Те, которые встречаются в списке меньше четырех раз, являются квадратами чисел, кратных либо 3, либо 5, то есть простым множителям 15. Все остальные числа возникают группами по четыре, где квадраты всех четырех равны.
Это общая закономерность для любого модуля вида pq, где p и q – различные нечетные простые числа. Числа от 0 до pq – 1, не кратные ни p, ни q, разделяются на четверки с равными квадратами. (Это не работает, если одно из простых чисел равно 2: к примеру, 10 = 2 × 5, но мы уже видели, что в этом случае квадраты либо одиноки, либо стоят парами.)
В алгебре мы привыкаем к мысли, что у каждого положительного числа имеется два квадратных корня: один положительный, другой отрицательный. Но в арифметике по модулю pq большая часть чисел (те, что не делятся ни на p, ни на q) имеет по четыре различных квадратных корня.
Этот любопытный факт имеет замечательное приложение, к которому мы и перейдем.
Бросание монетки по телефону
Предположим, что Алиса и Боб хотят сыграть в бросание монетки с вероятностью того или иного результата 50:50. Как мы уже знаем, Алиса находится в Алис-Спрингс, а Боб – в Боббингтоне. Могут ли они бросать монетку по телефону? Главная загвоздка – та же, что при игре в покер. Если бросает монетку (или проделывает любую другую операцию с равновероятным исходом) Алиса и она же сообщает результат Бобу, то тот никак не может быть уверен, что она говорит правду. Конечно, в наше время они могли бы делать это во время общения по скайпу и наблюдать за бросанием монетки, но даже в этом случае результат можно подделать, сняв заранее несколько бросков и показав собеседнику запись вместо онлайн-трансляции.
Бросание монетки – то же, что игра в покер колодой из двух карт, так что игроки вполне могут воспользоваться методикой, описанной выше. Однако существует и другой элегантный способ достичь того же результата с использованием квадратичных вычетов. Вот как это можно сделать.
Алиса выбирает два больших простых числа p и q. Она держит их в секрете, но отправляет Бобу их произведение n = pq. Вы скажете, что Боб мог бы найти p и q путем разложения n на простые множители, но на сегодняшний день, насколько известно, не существует практичного способа сделать это, если числа p и q достаточно велики – скажем, по 100 знаков в каждом. Даже самым быстрым компьютерам, использующим самые быстрые алгоритмы, понадобилось бы на это время, превышающее время жизни Вселенной. Так что Боб останется в неведении.
Однако существуют очень быстрые способы проверить 100-значное число и узнать, является ли оно простым. Так что Алиса сможет подобрать себе p и q методом проб и ошибок.
Боб выбирает произвольное целое x (mod n), которое держит в секрете.
Если он необычайно педантичен, то может быстро проверить, не является ли x произведением p и q: он не будет делить его на эти числа, поскольку их не знает, но найдет наибольший общий делитель (НОД) чисел x и n через алгоритм Евклида. Если результат окажется не равным 1, то получится, что он знает либо p, либо q, и процесс нужно будет начинать заново с новым x. Но на практике можно особо не беспокоиться, поскольку при p и q, содержащих по 100 знаков каждое, вероятность того, что одно из этих чисел окажется делителем произвольно выбранного x, составит 2 × 10–100.
Далее Боб вычисляет x² (mod n), что тоже можно сделать быстро, и отправляет результат Алисе. Они договорились, что если Алиса сможет правильно назвать x или – x, то она выиграет (это будет «орел»). В противном случае – проиграет («решка»).
Из предыдущей главы Алиса знает, что целые числа по модулю pq, не кратные ни p, ни q, имеют ровно по четыре квадратных корня. Поскольку x и – x при возведении в квадрат дают одно и то же, квадратные корни имеют вид a, – a, b, – b для подходящих a и b. Алиса знает p, q и x², из чего следует, что она может быстро вычислить четыре нужных корня. Два из них должны быть равны x и – x; два других – не равны. Так что вероятность угадать ± x верно у Алисы на 50 % – что эквивалентно честному бросанию монетки. Она выбирает одно из четырех чисел, скажем b, и отправляет его Бобу.
Боб сообщает Алисе, действительно b = ± x или нет; то есть права она или нет.
Ах, но как сделать так, чтобы Боб тоже не мог смошенничать? И откуда Бобу знать, что Алиса сделала все так, как должна была сделать?
В любом случае (верно b = ± x или нет) Боб может легко убедиться, что Алиса играла честно, если вычислит b² (mod n). Результат должен совпасть с x².
Если Алиса проигрывает, то она может убедиться в честности Боба, попросив его прислать ей простые множители n, то есть p и q. В обычных условиях это невозможно, но если Алиса проиграла, то Боб знает все четыре квадратных корня из x², а в теории чисел имеется хитрый прием, позволяющий быстро вычислить p и q по этим данным. Наибольшим общим делителем a + b и n является одно из наших двух простых чисел, а НОД опять же можно найти при помощи алгоритма Евклида. После этого второе число можно найти путем деления.
Как устранить нежелательное эхо
Квадратичные вычеты могут показаться типичным примером мудреных умствований, которые так любят математики-теоретики: интеллектуальной игрой, не имеющей никакого практического применения. Но было бы ошибкой думать, что математическая идея бесполезна, только потому, что она не проистекает очевидным образом из практических задач повседневной жизни. Ошибка также считать, что повседневная жизнь настолько прямолинейна, как кажется на поверхностный взгляд. Для изготовления даже такой простой вещи, как банка джема из супермаркета, нужно сварить стекло, вырастить сахарный тростник или сахарную свеклу, очистить сахар… и очень скоро вы обнаружите, что с головой погрузились в статистический анализ испытаний сортов растений на сопротивляемость болезням и в конструирование судов, используемых для перевозки различных компонентов готового продукта по всему земному шару. В мире, где живет 7 млрд человек, массовое производство продуктов питания не сводится к тому, чтобы просто собрать ягоды и сварить их.
Действительно, математики, которые первыми выдвинули эти идеи, не думали ни о каких конкретных практических приложениях для них; просто квадратичные вычеты показались им интересными. Но они также были убеждены, что их понимание станет новым мощным дополнением к математическому инструментарию. Практики не в состоянии пользоваться инструментом, пока его не существует. И хотя на первый взгляд может показаться, что разумнее подождать появления конкретной задачи, прежде чем придумывать инструменты, подходящие для ее решения, при таком подходе мы до сих пор жили бы в пещерах. «Зачем ты теряешь время, стуча камнем по камню, а, Уг? Тебе следовало бы стучать палкой по голове мамонта, как делают остальные мальчики».
У квадратичных вычетов множество самых разных применений. Один из моих любимых примеров – проектирование концертных залов. Музыка, отражаясь от плоского потолка, дает явственное эхо, которое искажает звук и вообще мешает слушать. С другой стороны, звукопоглощающий потолок делает звучание мертвым и смазанным. Для хорошей акустики звук должен отражаться, но в виде рассеянного отзвука, а не резкого эха. Поэтому архитекторы встраивают в потолок специальные рассеиватели. Вопрос в том, какой они должны быть формы.
В 1975 г. Манфред Шрёдер изобрел рассеиватель, состоящий из серии параллельных борозд, глубина которых выводится из последовательности квадратичных вычетов для некоего простого модуля. Возьмем, к примеру, простое число 11. Мы только что видели, что квадраты чисел от 0 до 10 по модулю 11 равны:
