Банковские карты, суммы произведений, или несколько слов о Сергее Владимировиче Конягине
Свой рассказ о выдающемся российском математике Сергее Владимировиче Конягине, члене-корреспонденте РАН, лауреате Салемовской премии я хочу начать с небольшого анекдота.
В 2004 году, будучи аспирантом и еще мало зная о Сергее Владимировиче, я впервые посетил США, где познакомился с другим замечательным математиком --- Беном Грином. При нашей первой встрече мы обсуждали одну мою работу и он спросил меня, где я собираюсь ее опубликовать. Бен начал говорить про английские журналы, про то, что статья с большой вероятностью попадет к нему, он ее с удовольствием отрецензирует и так далее в том же духе. Я ему ответил, что уже подал работу в русский журнал. Видно было, что Бен огорчился, но быстро взял себя в руки и стал говорить, что ему горько это слышать, что русские журналы, к сожалению, имеют достаточно узкий круг читателей и т.д. Что же это за журнал, спросил он в конце своей речи? Я ответил, что Известия (Имеются ввиду "Известия Академии Наук : серия математическая"). Он воскликнул : "О, ОК!", Но, все равно, продолжал Бен, (и здесь я привожу его слова дословно) : ''Кто там у вас сможет это прочитать?'' Я ответил --- Конягин и он снова воскликнул : "О, ОК!" Думаю, что до сих пор этот возглас служит для меня лучшей рекомендацией о Сергее Владимировиче.
С.В. Конягин --- автор нескольких сотен научных работ. Ясно, что я не смогу описать даже общие направления его исследований. Остановлюсь лишь на двух достижениях Сергея Владимировича : доказательстве гипотезы Литтлвуда из теории функций и результатах о суммах произведений из аддитивной комбинаторики. Хотя исторически эти два сюжета идут в обратном порядке, я начну с сумм произведений, поскольку данная тематика вполне элементарна и важность ее практических применений объясняется достаточно просто. Вторая часть чуть более математична.
1. Суммы произведений.
Суммы произведений --- это важный новый феномен в аддитивной комбинаторике и теории чисел, уже нашедший целый ряд важных приложений в криптографии, Computer Science, теории графов-расширителей, задачах о почти изометричных матрицах, а также, собственно, в таких областях математики, как, эргодическая теория, аналитическая теория чисел и т.д. Как сейчас убедится читатель, сформулировать и проиллюстрировать главный принцип науки о суммах произведений: сумма и произведение множества не могут быть одновременно малы, чрезвычайно просто. Предположим, что A --- это некоторое конечное подмножество целых или действительных чисел. Мы знаем, что обычные числа можно складывать и перемножать; оказывается, так же просто можно складывать и перемножать само множество A. Суммой A с собой (обозначается A+A) называется множество всех попарных сумм элементов A, а произведением A с собой (обозначается, разумеется, AA) --- множество всех попарных произведений из A. Например, если A = { 0, 1, 3, 4 }, то
и
(разумеется, если в результате операции сложения или умножения многократно появляется одно и тоже число, то оно в A+A / AA указывается единожды). Очень легко складывать и перемножать арифметические и геометрические прогрессии. Действительно, если, скажем, A --- это арифметическая прогрессия
, то
, а если теперь $A$ --- это геометрическая прогрессия
, то
. Из последних примеров видно, что сумма/произведение арифметических/геометрических прогрессий
от сложения/умножения увеличиваются не слишком сильно, а именно, размер (общее количество элементов множества) A+A, AA вырастает, по сравнению с размером исходного множества A, не больше, чем в два раза. Конечно, бывают примеры множеств которые от сложения/умножения увеличиваются значительно. Скажем, возьмем нашу арифметическую прогрессию
и будем ее не складывать, а перемножать. Тогда, AA представляет собой все числа от нуля до ста, у которых есть два делителя, не превосходящих 10. Другими словами, AA --- это все числа, появляющиеся в школьной таблице умножения от 0 до 10. Таких чисел, как не сложно посчитать, будет уже не двадцать, как раньше, а 39. Более того, если теперь брать арифметические прогрессии подлиннее, а именно
, где n --- большое натуральное число, то, как и раньше, A+A имеет размер 2n+1, a размер AA будет примерно
, где c>0 --- некоторая константа. Это очень большая величина. Действительно, количество всевозможных пар чисел, составленных из A, будет не больше, чем
, то есть размер AA (а также, к слову, A+A) для любого множества A из n элементов всегда не превосходит
, а здесь мы имеем почти ту же самую величину. Итак, мы осознали, что существуют множества, которые от сложения/умножения не сильно увеличиваются --- это арифметические/геометрические прогрессии, соответственно. С другой стороны, есть и множества, которые от сложения/умножения растут достаточно быстро. Основной вопрос, который и породил науку о суммах произведений звучит так :
а существуют ли множества, которые не сильно увеличиваются и от сложения, и от умножения?
Замечательно, что ответ здесь отрицательный : любое множество либо от сложения, либо от умножения, да увеличится. Неформально говоря, множеству очень сложно быть одновременно похожим и на арифметическую, и на геометрическую прогрессию. Прежде чем формулировать четкие результаты и теоремы, позвольте мне сказать о неизвестном, о таинственной дали, которая нас влечет и к которой мы стремимся. Центральный вопрос в науке о суммах произведений --- это гипотеза Эрдеша--Семереди :
Пусть A --- произвольное конечное подмножество действительных чисел размера n. Тогда либо сумма, либо произведение A имеет размер по крайней мере
,
.
На
можно не обращать внимание (хотя оно и нужно, см. рассуждения с таблицей умножения ранее), смысл утверждения выше понятный: от сложения или от умножения произвольное множество вырастет почти максимально возможным образом. К сожалению, эта гипотеза пока не доказана. Наилучший результат здесь принадлежит Шоймоши, который получил вместо
оценку
. Его метод очень красив и использует простые геометрические соображения. В чем же состоит вклад Сергея Владимировича в область задач о суммах произведений? Ему, вместе с соавторами Ж. Бургеном и А.А. Глибичуком удалось доказать результат о росте сумм или произведений не в действительных числах, а в других алгебраических объектах --- конечных полях. Надо отметить, что весь шквал полученных в последнее время приложений относится как раз к этой ситуации, а не к обычным числам. Например, именно конечные поля используются в криптографии. Задача о суммах произведений в таких объектах гораздо сложнее вопросов о действительных числах, поскольку, в конечных полях не работают наши обыкновенные геометрические представления. Чтобы не перегружать читателя, рассмотрим пример простого поля. Простое поле из p элементов --- это числа от 0 до p-1, где p --- заданное простое число, а умножение и сложение в таких полях берется, как говорят, по модулю p. Иными словами, если результат умножения или сложения "вылезает", из отрезка от 0 до p-1, то мы должны вычитать из результата число p до тех пор, пока не попадем в промежуток от 0 до p-1. Например, если p=5, то простое поле состоит из элементов {0,1,2,3,4}. Элементы этого поля умножаются и складываются так, скажем,
, но не 6, поскольку 6>5 и, следовательно, мы должны из 6 вычесть 5, далее
, но не 12, а 4+4=3, но не 8. Развивая подход Бургена-Катца-Тао С.В. Конягин с соавторами доказывают такой результат.
Пусть)
--- любое число, A --- произвольное конечное подмножество простого поля из p элементов. Предположим, что A имеет размер n, где
. Тогда либо сумма, либо произведение A имеет размер по крайней мере
, где число
зависит только от
.
Говоря неформально, теорема выше утверждает, что любое подмножество простого поля, у которого число элементов несколько меньше p, обладает тем свойством, что либо его сумма, либо произведение вырастают. Бесспорно, упомянутый результат бесконечно далек от гипотезы Эрдеша--Семереди о суммах произведений подмножеств действительных чисел. Более того, теорема Бургена--Глибичука--Конягина слабее, чем оценка Шоймоши. Тем не менее, данный результат представляет собой важное продвижение, нашедшее многочисленные приложения. Как отмечалось выше, причина почему оценка в простом поле получилась хуже, чем у Шоймоши, заключается в том, что в простом поле почти нет никакой геометрии, а, следовательно, и наглядности. Доказательство Бургена-Глибичука-Конягина использует целый ряд чисто комбинаторных идей и из-за своей комбинаторной природы является достаточно гибким. Как уже отмечалось выше, подобного рода результаты справедливы и для более сложно устроенных объектов.
Закончу свой рассказ одним приложением феномена сумм произведений, важным для криптографии. Как известно, одним из способов кодирования информации является следующий. Берется большое простое число p, а также некоторое специально подобранное число g от 0 до p-1. Пользователь вводит сообщение, представляющее натуральное число n, например, номер банковской карты или зашифрованный цифрами некоторый текст. Кодирование производится очень просто: закодированное сообщение есть
, то есть результат перемножения числа g на себя ровно n раз (напоминаем, что умножаем мы по модулю p).
Вопрос. Как, зная почти все, а именно, закодированное сообщение
, число p и пусть даже исходное число g, злоумышленнику определить наше число n, то есть номер нашей банковской карты? Эта задача называется задачей дискретного логарифмирования, поскольку неизвестное n это, так сказать, логарифм по основанию g от
. Как решать эту задачу --- непонятно. На том факте, что ее неясно, как решать, и покоится данный метод кодирования. Тривиальный подход, а именно, взять g, начать считать степени g :
и сравнивать каждую степень с зашифрованным посланием
нам не подходит, поскольку, как легко видеть, такой способ требует перебора всех p чисел (предположим даже, что злоумышленник умеет быстро возводить в степень), а это нереально, поскольку, по условию, мы выбрали p огромным (вот, кстати, зачем в криптографии нужны большие простые числа). С другой стороны, это, может быть, сейчас нам не понятно, как решать задачу дискретного логарифмирования, а в будущем обнаружится, что есть простой способ ее дешифрования и все наши карточки окажутся взломанными. А может быть злоумышленник очень умный и изобрел свои, не известные нам подходы к расшифровке. Например, он заметил, что какое бы ни было j от 0 до p/10 число
всегда попадает в какой--нибудь отрезок, скажем, от 0 до p/3. Если теперь закодированное послание
не попало в отрезок от 0 до p/3, то числа j от 0 до p/10 перебирать не надо, а это уже сокращает вычисления. У умного злоумышленника могут быть и другие подобные соображения. Замечательно, что из результата Бургена-Глибичука-Конягина о суммах произведений, казалось бы очень далекого от криптографии, вытекает, что сценарии, подобные вышеизложенному (и даже более сложные), невозможны и, значит, алгоритм дешифрования, построенный на таких соображениях, не может существовать в принципе, каким бы умным ни был злоумышленник. Все это дает некоторую, пусть небольшую, но зато теоретически обоснованную и не базирующуюся на непонятной вере в "сложность", и "невскрываемость", алгоритма гарантию, что задачу дискретного логарифмирования, а, значит, задачу об определении номера банковской карты при данном методе шифрования быстро решить невозможно.
2. Гипотеза Литтлвуда.
Мы все знаем со школьных времен, что функции
и
имеют период
, а также, что эти функции принимают и положительные и отрицательные значения. Можно даже сказать, что положительные и отрицательные значения принимаются ими одинаково часто, в том смысле, что среднее значение этих функций на их периоде равно нулю или, наконец, если говорить формально, что
,
. Тоже самое выполнено для функций
и
, где n --- целое ненулевое число, у них тоже средние значения --- нулевые. Интересно, а что будет если перемножить две тригонометрических функции, скажем,
и
? Все знают, что по формуле двойного угла
, а, значит, снова
и среднее значение произведения синуса на косинус опять равно нулю. Конечно, если перемножить синус на синус или косинус на косинус, то полученные функции будет неотрицательными и, следовательно, они никак не могут иметь нулевой интеграл. Если вспомнить чуть более сложные тригонометрические формулы для произведения двух синусов, двух косинусов и синуса на косинус
x)%20-%20%5Ccos(%20(n%2Bm)x)%20%5Cright)%20%5C%2C%2C)
x)%20%2B%20%5Ccos(%20(n-m)x)%20%5Cright)%20%5C%2C%2C)
x)%20%2B%20%5Csin(%20(n-m)x)%20%5Cright)%20%5C%2C%2C)
то из них будет легко вытекать, что произведения тригонометрических функций имеют нулевые средние, если
. В случае n=m в первых двух формулах появится квадрат синуса или косинуса и интегралы от них, конечно, ненулевые, а в третьей формуле будет, как и раньше, половина синуса двойного угла, у которого среднее, как мы отмечали выше, равно нулю. На чуть более продвинутом математическом языке все это означает, что синусы и косинусы ортогональны (перпендикулярны) друг другу, то есть, что тригонометрическая система на отрезке от нуля до
состоит из ортогональных функций. (Интересно, как просто, без знания геометрии (фактически исключенной из школьной программы) и тригонометрии (которую пока лишь покушаются исключить), объяснить важнейшее понятие ортогональности/ортонормированности, использующееся везде в науке, если не иметь перед глазами пример тригонометрической системы?! ) Синусы и косинусы можно собрать в единую функцию --- комплексную экспоненту, если вспомнить знаменитую формулу Эйлера
. Здесь
. На этом языке рассуждения об ортогональности можно записать более единообразно
Снова при n=m интеграл выше не будет зануляться, он, как легко вычислить, равен
.
Итак, у нас появилась ортогональная система функций. Со школы мы знаем, что для двух ортогональных (перпендикулярных) друг другу векторов a и b справедлива знаменитая теорема Пифагора : сумма квадратов длин a и b равна квадрату длины их суммы. Несложно доказать и трехмерный вариант этого факта, а именно, если имеются три попарно ортогональные вектора a, b и c (например, как ребра в прямоугольном параллелепипеде), то снова сумма квадратов длин a, b и c равна квадрату длины их суммы (в прямоугольном параллелепипеде это соответствует большой диагонали). Экспоненты
представляют собой ортогональные функции (вектора), причем их не три, а целое бесконечное множество. Бесконечным аналогом теоремы Пифагора является, так называемое, равенство Парсеваля
Действительно, в левой части формулы выше складываются ортогональные вектора --- k экспонент
, где
--- произвольные натуральные числа, а затем, вычисляется квадрат длины их суммы. Справа же, как и положено, стоит сумма длин k экспонент
--- то есть в точности
. Множитель
возник здесь поскольку мы интегрируем от 0 до
.
Теперь можно задать основной вопрос. Что будет если в формуле выше посчитать не квадрат длины суммы экспонент
, а просто длину суммы? Иными словами, что можно сказать о выражении
Конечно, интеграл выше будет уже сильно зависеть от выбора чисел
. Хорошо, а можно тогда хотя бы указать оценку снизу на наш интеграл, но так, чтобы оценка не зависела от чисел
? Это и составляет предмет знаменитой гипотезы Литтлвуда (о замечательном английском математике Д. Литтлвуде можно прочитать здесь).
Он предположил, что вне зависимости от выбора
, выполнено
где C>0 --- некоторая константа, значение которой сейчас не важно. Логарифм выше появляется из--за выбора наипростейшей последовательности
. Если посчитать интеграл от нее, то как раз появится логарифм. Иными словами, гипотеза Литтлвуда утверждает, что как бы мы не выбирали последовательность
, в смысле нашего интеграла (теоремы Пифагора без квадратов) она будет вести себя еще хуже (по крайней мере не лучше) простейшей последовательности
. Это очень сложный вопрос из теории тригонометрических рядов, которым занималось множество сильных математиков со всего мира. Замечательно, что именно наш ученый --- Сергей Владимирович Конягин окончательно справился с данной
задачей (одновременно с ним проблему Литтлвуда решили американские математики McGehee--Pigno--Smith).
Илья Шкредов
Математический институт им. В.А. Стеклова РАН
В 2004 году, будучи аспирантом и еще мало зная о Сергее Владимировиче, я впервые посетил США, где познакомился с другим замечательным математиком --- Беном Грином. При нашей первой встрече мы обсуждали одну мою работу и он спросил меня, где я собираюсь ее опубликовать. Бен начал говорить про английские журналы, про то, что статья с большой вероятностью попадет к нему, он ее с удовольствием отрецензирует и так далее в том же духе. Я ему ответил, что уже подал работу в русский журнал. Видно было, что Бен огорчился, но быстро взял себя в руки и стал говорить, что ему горько это слышать, что русские журналы, к сожалению, имеют достаточно узкий круг читателей и т.д. Что же это за журнал, спросил он в конце своей речи? Я ответил, что Известия (Имеются ввиду "Известия Академии Наук : серия математическая"). Он воскликнул : "О, ОК!", Но, все равно, продолжал Бен, (и здесь я привожу его слова дословно) : ''Кто там у вас сможет это прочитать?'' Я ответил --- Конягин и он снова воскликнул : "О, ОК!" Думаю, что до сих пор этот возглас служит для меня лучшей рекомендацией о Сергее Владимировиче.
С.В. Конягин --- автор нескольких сотен научных работ. Ясно, что я не смогу описать даже общие направления его исследований. Остановлюсь лишь на двух достижениях Сергея Владимировича : доказательстве гипотезы Литтлвуда из теории функций и результатах о суммах произведений из аддитивной комбинаторики. Хотя исторически эти два сюжета идут в обратном порядке, я начну с сумм произведений, поскольку данная тематика вполне элементарна и важность ее практических применений объясняется достаточно просто. Вторая часть чуть более математична.
1. Суммы произведений.
Суммы произведений --- это важный новый феномен в аддитивной комбинаторике и теории чисел, уже нашедший целый ряд важных приложений в криптографии, Computer Science, теории графов-расширителей, задачах о почти изометричных матрицах, а также, собственно, в таких областях математики, как, эргодическая теория, аналитическая теория чисел и т.д. Как сейчас убедится читатель, сформулировать и проиллюстрировать главный принцип науки о суммах произведений: сумма и произведение множества не могут быть одновременно малы, чрезвычайно просто. Предположим, что A --- это некоторое конечное подмножество целых или действительных чисел. Мы знаем, что обычные числа можно складывать и перемножать; оказывается, так же просто можно складывать и перемножать само множество A. Суммой A с собой (обозначается A+A) называется множество всех попарных сумм элементов A, а произведением A с собой (обозначается, разумеется, AA) --- множество всех попарных произведений из A. Например, если A = { 0, 1, 3, 4 }, то
и
(разумеется, если в результате операции сложения или умножения многократно появляется одно и тоже число, то оно в A+A / AA указывается единожды). Очень легко складывать и перемножать арифметические и геометрические прогрессии. Действительно, если, скажем, A --- это арифметическая прогрессия
, то
, а если теперь $A$ --- это геометрическая прогрессия
, то
. Из последних примеров видно, что сумма/произведение арифметических/геометрических прогрессий
от сложения/умножения увеличиваются не слишком сильно, а именно, размер (общее количество элементов множества) A+A, AA вырастает, по сравнению с размером исходного множества A, не больше, чем в два раза. Конечно, бывают примеры множеств которые от сложения/умножения увеличиваются значительно. Скажем, возьмем нашу арифметическую прогрессию
и будем ее не складывать, а перемножать. Тогда, AA представляет собой все числа от нуля до ста, у которых есть два делителя, не превосходящих 10. Другими словами, AA --- это все числа, появляющиеся в школьной таблице умножения от 0 до 10. Таких чисел, как не сложно посчитать, будет уже не двадцать, как раньше, а 39. Более того, если теперь брать арифметические прогрессии подлиннее, а именно
, где n --- большое натуральное число, то, как и раньше, A+A имеет размер 2n+1, a размер AA будет примерно
, где c>0 --- некоторая константа. Это очень большая величина. Действительно, количество всевозможных пар чисел, составленных из A, будет не больше, чем
, то есть размер AA (а также, к слову, A+A) для любого множества A из n элементов всегда не превосходит
, а здесь мы имеем почти ту же самую величину. Итак, мы осознали, что существуют множества, которые от сложения/умножения не сильно увеличиваются --- это арифметические/геометрические прогрессии, соответственно. С другой стороны, есть и множества, которые от сложения/умножения растут достаточно быстро. Основной вопрос, который и породил науку о суммах произведений звучит так :
а существуют ли множества, которые не сильно увеличиваются и от сложения, и от умножения?
Замечательно, что ответ здесь отрицательный : любое множество либо от сложения, либо от умножения, да увеличится. Неформально говоря, множеству очень сложно быть одновременно похожим и на арифметическую, и на геометрическую прогрессию. Прежде чем формулировать четкие результаты и теоремы, позвольте мне сказать о неизвестном, о таинственной дали, которая нас влечет и к которой мы стремимся. Центральный вопрос в науке о суммах произведений --- это гипотеза Эрдеша--Семереди :
Пусть A --- произвольное конечное подмножество действительных чисел размера n. Тогда либо сумма, либо произведение A имеет размер по крайней мере
,
.
На
можно не обращать внимание (хотя оно и нужно, см. рассуждения с таблицей умножения ранее), смысл утверждения выше понятный: от сложения или от умножения произвольное множество вырастет почти максимально возможным образом. К сожалению, эта гипотеза пока не доказана. Наилучший результат здесь принадлежит Шоймоши, который получил вместо
оценку
. Его метод очень красив и использует простые геометрические соображения. В чем же состоит вклад Сергея Владимировича в область задач о суммах произведений? Ему, вместе с соавторами Ж. Бургеном и А.А. Глибичуком удалось доказать результат о росте сумм или произведений не в действительных числах, а в других алгебраических объектах --- конечных полях. Надо отметить, что весь шквал полученных в последнее время приложений относится как раз к этой ситуации, а не к обычным числам. Например, именно конечные поля используются в криптографии. Задача о суммах произведений в таких объектах гораздо сложнее вопросов о действительных числах, поскольку, в конечных полях не работают наши обыкновенные геометрические представления. Чтобы не перегружать читателя, рассмотрим пример простого поля. Простое поле из p элементов --- это числа от 0 до p-1, где p --- заданное простое число, а умножение и сложение в таких полях берется, как говорят, по модулю p. Иными словами, если результат умножения или сложения "вылезает", из отрезка от 0 до p-1, то мы должны вычитать из результата число p до тех пор, пока не попадем в промежуток от 0 до p-1. Например, если p=5, то простое поле состоит из элементов {0,1,2,3,4}. Элементы этого поля умножаются и складываются так, скажем,
, но не 6, поскольку 6>5 и, следовательно, мы должны из 6 вычесть 5, далее
, но не 12, а 4+4=3, но не 8. Развивая подход Бургена-Катца-Тао С.В. Конягин с соавторами доказывают такой результат.
Пусть
--- любое число, A --- произвольное конечное подмножество простого поля из p элементов. Предположим, что A имеет размер n, где
. Тогда либо сумма, либо произведение A имеет размер по крайней мере
, где число
зависит только от
.
Говоря неформально, теорема выше утверждает, что любое подмножество простого поля, у которого число элементов несколько меньше p, обладает тем свойством, что либо его сумма, либо произведение вырастают. Бесспорно, упомянутый результат бесконечно далек от гипотезы Эрдеша--Семереди о суммах произведений подмножеств действительных чисел. Более того, теорема Бургена--Глибичука--Конягина слабее, чем оценка Шоймоши. Тем не менее, данный результат представляет собой важное продвижение, нашедшее многочисленные приложения. Как отмечалось выше, причина почему оценка в простом поле получилась хуже, чем у Шоймоши, заключается в том, что в простом поле почти нет никакой геометрии, а, следовательно, и наглядности. Доказательство Бургена-Глибичука-Конягина использует целый ряд чисто комбинаторных идей и из-за своей комбинаторной природы является достаточно гибким. Как уже отмечалось выше, подобного рода результаты справедливы и для более сложно устроенных объектов.
Закончу свой рассказ одним приложением феномена сумм произведений, важным для криптографии. Как известно, одним из способов кодирования информации является следующий. Берется большое простое число p, а также некоторое специально подобранное число g от 0 до p-1. Пользователь вводит сообщение, представляющее натуральное число n, например, номер банковской карты или зашифрованный цифрами некоторый текст. Кодирование производится очень просто: закодированное сообщение есть
, то есть результат перемножения числа g на себя ровно n раз (напоминаем, что умножаем мы по модулю p).
Вопрос. Как, зная почти все, а именно, закодированное сообщение
, число p и пусть даже исходное число g, злоумышленнику определить наше число n, то есть номер нашей банковской карты? Эта задача называется задачей дискретного логарифмирования, поскольку неизвестное n это, так сказать, логарифм по основанию g от
. Как решать эту задачу --- непонятно. На том факте, что ее неясно, как решать, и покоится данный метод кодирования. Тривиальный подход, а именно, взять g, начать считать степени g :
и сравнивать каждую степень с зашифрованным посланием
нам не подходит, поскольку, как легко видеть, такой способ требует перебора всех p чисел (предположим даже, что злоумышленник умеет быстро возводить в степень), а это нереально, поскольку, по условию, мы выбрали p огромным (вот, кстати, зачем в криптографии нужны большие простые числа). С другой стороны, это, может быть, сейчас нам не понятно, как решать задачу дискретного логарифмирования, а в будущем обнаружится, что есть простой способ ее дешифрования и все наши карточки окажутся взломанными. А может быть злоумышленник очень умный и изобрел свои, не известные нам подходы к расшифровке. Например, он заметил, что какое бы ни было j от 0 до p/10 число
всегда попадает в какой--нибудь отрезок, скажем, от 0 до p/3. Если теперь закодированное послание
не попало в отрезок от 0 до p/3, то числа j от 0 до p/10 перебирать не надо, а это уже сокращает вычисления. У умного злоумышленника могут быть и другие подобные соображения. Замечательно, что из результата Бургена-Глибичука-Конягина о суммах произведений, казалось бы очень далекого от криптографии, вытекает, что сценарии, подобные вышеизложенному (и даже более сложные), невозможны и, значит, алгоритм дешифрования, построенный на таких соображениях, не может существовать в принципе, каким бы умным ни был злоумышленник. Все это дает некоторую, пусть небольшую, но зато теоретически обоснованную и не базирующуюся на непонятной вере в "сложность", и "невскрываемость", алгоритма гарантию, что задачу дискретного логарифмирования, а, значит, задачу об определении номера банковской карты при данном методе шифрования быстро решить невозможно.
2. Гипотеза Литтлвуда.
Мы все знаем со школьных времен, что функции
и
имеют период
, а также, что эти функции принимают и положительные и отрицательные значения. Можно даже сказать, что положительные и отрицательные значения принимаются ими одинаково часто, в том смысле, что среднее значение этих функций на их периоде равно нулю или, наконец, если говорить формально, что
,
. Тоже самое выполнено для функций
и
, где n --- целое ненулевое число, у них тоже средние значения --- нулевые. Интересно, а что будет если перемножить две тригонометрических функции, скажем,
и
? Все знают, что по формуле двойного угла
, а, значит, снова
и среднее значение произведения синуса на косинус опять равно нулю. Конечно, если перемножить синус на синус или косинус на косинус, то полученные функции будет неотрицательными и, следовательно, они никак не могут иметь нулевой интеграл. Если вспомнить чуть более сложные тригонометрические формулы для произведения двух синусов, двух косинусов и синуса на косинус
то из них будет легко вытекать, что произведения тригонометрических функций имеют нулевые средние, если
. В случае n=m в первых двух формулах появится квадрат синуса или косинуса и интегралы от них, конечно, ненулевые, а в третьей формуле будет, как и раньше, половина синуса двойного угла, у которого среднее, как мы отмечали выше, равно нулю. На чуть более продвинутом математическом языке все это означает, что синусы и косинусы ортогональны (перпендикулярны) друг другу, то есть, что тригонометрическая система на отрезке от нуля до
состоит из ортогональных функций. (Интересно, как просто, без знания геометрии (фактически исключенной из школьной программы) и тригонометрии (которую пока лишь покушаются исключить), объяснить важнейшее понятие ортогональности/ортонормированности, использующееся везде в науке, если не иметь перед глазами пример тригонометрической системы?! ) Синусы и косинусы можно собрать в единую функцию --- комплексную экспоненту, если вспомнить знаменитую формулу Эйлера
. Здесь
. На этом языке рассуждения об ортогональности можно записать более единообразно
Снова при n=m интеграл выше не будет зануляться, он, как легко вычислить, равен
.
Итак, у нас появилась ортогональная система функций. Со школы мы знаем, что для двух ортогональных (перпендикулярных) друг другу векторов a и b справедлива знаменитая теорема Пифагора : сумма квадратов длин a и b равна квадрату длины их суммы. Несложно доказать и трехмерный вариант этого факта, а именно, если имеются три попарно ортогональные вектора a, b и c (например, как ребра в прямоугольном параллелепипеде), то снова сумма квадратов длин a, b и c равна квадрату длины их суммы (в прямоугольном параллелепипеде это соответствует большой диагонали). Экспоненты
представляют собой ортогональные функции (вектора), причем их не три, а целое бесконечное множество. Бесконечным аналогом теоремы Пифагора является, так называемое, равенство Парсеваля
Действительно, в левой части формулы выше складываются ортогональные вектора --- k экспонент
, где
--- произвольные натуральные числа, а затем, вычисляется квадрат длины их суммы. Справа же, как и положено, стоит сумма длин k экспонент
--- то есть в точности
. Множитель
возник здесь поскольку мы интегрируем от 0 до
.
Теперь можно задать основной вопрос. Что будет если в формуле выше посчитать не квадрат длины суммы экспонент
, а просто длину суммы? Иными словами, что можно сказать о выражении
Конечно, интеграл выше будет уже сильно зависеть от выбора чисел
. Хорошо, а можно тогда хотя бы указать оценку снизу на наш интеграл, но так, чтобы оценка не зависела от чисел
? Это и составляет предмет знаменитой гипотезы Литтлвуда (о замечательном английском математике Д. Литтлвуде можно прочитать здесь).
Он предположил, что вне зависимости от выбора
, выполнено
где C>0 --- некоторая константа, значение которой сейчас не важно. Логарифм выше появляется из--за выбора наипростейшей последовательности
. Если посчитать интеграл от нее, то как раз появится логарифм. Иными словами, гипотеза Литтлвуда утверждает, что как бы мы не выбирали последовательность
, в смысле нашего интеграла (теоремы Пифагора без квадратов) она будет вести себя еще хуже (по крайней мере не лучше) простейшей последовательности
. Это очень сложный вопрос из теории тригонометрических рядов, которым занималось множество сильных математиков со всего мира. Замечательно, что именно наш ученый --- Сергей Владимирович Конягин окончательно справился с данной
задачей (одновременно с ним проблему Литтлвуда решили американские математики McGehee--Pigno--Smith).
Илья Шкредов
Математический институт им. В.А. Стеклова РАН