Часть VI · Структуры Глава 44 из 60
Дзета-функция и эллиптические кривые
Насколько точна формула Гаусса для числа простых? Ответ спрятан в нулях одной функции комплексного переменного, и где лежат все эти нули, не знает никто. По соседству — кривые третьей степени, на которых точки складываются, как числа: они доказали теорему Ферма и охраняют ваш банк.
Опирается на: 43 · Теория Галуа
Вы научитесь
- доказывать тождество Эйлера ζ(s) = ∏(1 − p⁻ˢ)⁻¹ и выводить из него бесконечность множества простых
- объяснять, как нули дзета-функции управляют ошибкой в законе распределения простых и что утверждает гипотеза Римана
- складывать точки эллиптической кривой по правилу хорд и касательных, в том числе по модулю простого числа
- понимать, как устроен обмен ключами на эллиптических кривых и почему его считают надёжным
5Как работает шифр, который защищает ваш банк?
Прошлая глава закончилась вопросом, насколько точна догадка, которую Гаусс сделал подростком: простых чисел до $x$ примерно $\frac{x}{\ln x}$. Проверим на числе, которое не выписать на одной строке без труда. До $10^{18}$ ровно $24\,739\,954\,287\,740\,860$ простых чисел. Формула $\frac{x}{\ln x}$ даёт $24\,127\,471\,216\,847\,324$ — ошибка в два с половиной процента, и это больше шестисот триллионов штук. Но у Гаусса была и вторая, более точная формула. Она ошибается примерно на $22$ миллиона — меньше чем на одну миллиардную долю.
Откуда такая точность и откуда берутся оставшиеся $22$ миллиона? Эта глава — восхождение. Базовый лагерь — закон распределения простых. Первая стоянка — тождество Эйлера, которое связывает простые числа с суммой ряда. Перевал — функция Римана на комплексной плоскости. А выше — вершина, на которую за сто шестьдесят с лишним лет не поднялся никто: гипотеза Римана. Спустившись, мы перейдём на соседний хребет, к эллиптическим кривым, и закончим там, где закончилась глава о шифрах: у замка, который охраняет ваш банк.
Базовый лагерь
Гаусс заметил, что около числа $t$ простые встречаются с частотой примерно $\frac{1}{\ln t}$ (глава 3). Если частота меняется, количество правильнее не умножать, а складывать по кусочкам — интегрировать (глава 28).
Интегральный логарифм $\operatorname{li}x$ — интеграл $\int_0^x \frac{dt}{\ln t}$. Под интегралом при $t = 1$ бесконечность, и её обходят симметрично: берут предел суммы интегралов по $[0;\,1 - \varepsilon]$ и $[1 + \varepsilon;\,x]$ при $\varepsilon \to 0$.
| $x$ | $\pi(x)$ | $\operatorname{li}x - \pi(x)$ | $\sqrt x$ |
|---|---|---|---|
| $10^3$ | $168$ | $10$ | $32$ |
| $10^6$ | $78\,498$ | $130$ | $1\,000$ |
| $10^9$ | $50\,847\,534$ | $1\,701$ | $31\,623$ |
| $10^{12}$ | $37\,607\,912\,018$ | $38\,263$ | $10^6$ |
| $10^{18}$ | $24\,739\,954\,287\,740\,860$ | $21\,949\,555$ | $10^9$ |
В третьем столбце ошибка, в четвёртом для сравнения $\sqrt x$. Ошибка растёт, но медленнее корня: при $x = 10^{18}$ она в сорок пять раз меньше $\sqrt x$. Почему ошибка ведёт себя как нечто порядка $\sqrt x$ и знаем ли мы, что так будет всегда, — главный вопрос главы. Ответ «почему» нашёл Риман. Ответа «всегда ли» нет до сих пор.
Первая стоянка: тождество Эйлера
В главе 30 Эйлер сложил ряд $1 + \frac1{2^2} + \frac1{3^2} + \dots = \frac{\pi^2}{6}$. Такие суммы можно составить для любой степени.
Дзета-функция Римана $\zeta(s)$ — сумма ряда $1 + \frac{1}{2^s} + \frac{1}{3^s} + \dots = \sum_{n=1}^\infty \frac{1}{n^s}$ при $\operatorname{Re}s > 1$, а при остальных $s \ne 1$ — её аналитическое продолжение.
Пока будем думать о действительных $s > 1$. Ряд сходится (например, по интегральному признаку: $\sum_{n \ge 2} n^{-s} \le \int_1^\infty x^{-s}\,dx = \frac{1}{s - 1}$, глава 30), и сходится абсолютно, поэтому слагаемые можно переставлять и группировать как угодно. В 1737 году Эйлер заметил, что сумма по всем натуральным числам — это произведение по всем простым.
При $s > 1$ (и вообще при $\operatorname{Re}s > 1$) верно $\zeta(s)\prod_{p \le P}\left(1 - \frac{1}{p^s}\right) \to 1$ при $P \to \infty$, то есть $\zeta(s) = \prod_p \left(1 - p^{-s}\right)^{-1}$.
Хитрость в том, чтобы умножение на $1 - \frac1{p^s}$ работало как решето Эратосфена: оно вычёркивает из суммы все слагаемые, кратные $p$. Плитка с числом $n$ означает слагаемое $\frac1{n^s}$.
Тождество — переписанная основная теорема арифметики (глава 3): если раскрыть скобки в произведении геометрических прогрессий, каждое $\frac1{n^s}$ появится ровно один раз, по одному на каждое разложение $n$ на простые. Первое, что оно даёт, — ещё одно доказательство того, что простых бесконечно много.
Для любого $N$ верно $1 + \frac12 + \frac13 + \dots + \frac1N \le \prod_{p \le N}\frac{1}{1 - \frac1p}$, и поэтому простых чисел бесконечно много.
Каждый множитель справа — сумма $1 + \frac1p + \frac1{p^2} + \dots$ Перемножим эти суммы для всех простых $p \le N$ и раскроем скобки: получим сумму дробей $\frac{1}{p_1^{k_1}\cdots p_m^{k_m}}$ по всем наборам показателей. Все слагаемые положительны. Любое $n \le N$ раскладывается на простые, не превосходящие $N$, поэтому дробь $\frac1n$ среди слагаемых есть. Значит, правая часть не меньше суммы $\frac1n$ по $n \le N$.
Гармонический ряд расходится (глава 30): левая часть растёт неограниченно вместе с $N$. Будь простых конечное число, правая часть при больших $N$ перестала бы меняться — это было бы одно и то же конечное произведение. Противоречие. Например, при $N = 10$ слева $2{,}929$, справа $2 \cdot \frac32 \cdot \frac54 \cdot \frac76 = 4{,}375$.
Перевал: Риман, 1859
В 1859 году Бернхарда Римана избрали членом-корреспондентом Берлинской академии, и в ответ он представил статью «О числе простых чисел, не превышающих данной величины». Это меньше десяти страниц и его единственная работа по теории чисел. Риман сделал то, чего не делал Эйлер: разрешил $s$ быть комплексным числом.
При $s = \sigma + it$ слагаемое $\frac1{n^s} = e^{-s\ln n} = n^{-\sigma}\left(\cos(t\ln n) - i\sin(t\ln n)\right)$ по модулю равно $n^{-\sigma}$, поэтому ряд сходится при $\sigma > 1$. Риман продолжил $\zeta$ на всю комплексную плоскость, кроме точки $s = 1$, где у неё полюс, и нашёл её главное свойство.
Функция $\xi(s) = \pi^{-s/2}\,\Gamma\!\left(\frac s2\right)\zeta(s)$ удовлетворяет равенству $\xi(s) = \xi(1 - s)$. Здесь $\Gamma$ — гамма-функция Эйлера, продолжение факториала: $\Gamma(n) = (n - 1)!$; она нигде не обращается в ноль, а в точках $0, -1, -2, \dots$ у неё полюсы.
Идея доказательства и почему целиком его здесь нет
Риман записал $\pi^{-s/2}\Gamma(s/2)n^{-s}$ как интеграл $\int_0^\infty e^{-\pi n^2 x}x^{s/2 - 1}\,dx$, сложил по всем $n$ и получил интеграл от «тета-функции» $\theta(x) = \sum_{n \in \mathbb Z} e^{-\pi n^2 x}$. У неё есть собственная симметрия $\theta\!\left(\frac1x\right) = \sqrt x\,\theta(x)$ — она следует из формулы суммирования Пуассона, родственницы рядов Фурье. Разрезав интеграл в точке $x = 1$ и применив симметрию к одному куску, получают выражение, которое не меняется при замене $s \to 1 - s$ и имеет смысл при всех $s \ne 0, 1$. Аккуратное доказательство занимает несколько страниц и требует гамма-функции и комплексного анализа; его можно найти в книге Г. Эдвардса «Дзета-функция Римана» или в монографии Э. Ч. Титчмарша.
Из уравнения видно, где у $\zeta$ нули. При $s = -2, -4, -6, \dots$ множитель $\Gamma(s/2)$ бесконечен, а $\xi(s) = \xi(1 - s)$ конечно — значит, $\zeta(s) = 0$. Это тривиальные нули. Справа от прямой $\operatorname{Re}s = 1$ нулей нет.
При $\operatorname{Re}s > 1$ функция $\zeta(s)$ в ноль не обращается. При $\operatorname{Re}s < 0$ её нули — только $-2, -4, -6, \dots$ Остальные нули лежат в полосе $0 \le \operatorname{Re}s \le 1$, симметрично относительно действительной оси и относительно прямой $\operatorname{Re}s = \frac12$.
При $\operatorname{Re}s > 1$ по тождеству Эйлера $\zeta(s)\prod_{p \le P}\left(1 - p^{-s}\right) \to 1$. Будь $\zeta(s) = 0$, левая часть была бы равна нулю при всех $P$. При $\operatorname{Re}s < 0$ имеем $\operatorname{Re}(1 - s) > 1$, так что $\zeta(1 - s) \ne 0$, $\Gamma\!\left(\frac{1 - s}{2}\right)$ конечна и не равна нулю, и $\xi(1 - s) \ne 0$. Значит, $\xi(s) \ne 0$, и $\zeta(s)$ обращается в ноль только там, где множитель $\Gamma(s/2)$ бесконечен, — в точках $-2, -4, \dots$
Симметрия. Если $\zeta(\rho) = 0$ и $0 \le \operatorname{Re}\rho \le 1$, то $\xi(\rho) = 0$ (гамма-множитель здесь конечен), значит, $\xi(1 - \rho) = 0$ и $\zeta(1 - \rho) = 0$. Кроме того, у ряда $\sum n^{-s}$ действительные коэффициенты, поэтому $\zeta(\bar s) = \overline{\zeta(s)}$ при $\operatorname{Re}s > 1$, а по теореме единственности и всюду. Значит, $\bar\rho$ и $1 - \bar\rho$ — тоже нули. Точки $\rho$, $\bar\rho$, $1 - \rho$, $1 - \bar\rho$ расположены симметрично относительно оси и прямой $\operatorname{Re}s = \frac12$.
Нетривиальные нули дзета-функции — её нули в критической полосе $0 \le \operatorname{Re}s \le 1$. Прямую $\operatorname{Re}s = \frac12$ посреди полосы называют критической прямой.
Первые нетривиальные нули: $\frac12 + 14{,}1347i$, $\frac12 + 21{,}0220i$, $\frac12 + 25{,}0109i$, $\frac12 + 30{,}4249i$, $\frac12 + 32{,}9351i$ — и симметричные им снизу. Все на прямой $\operatorname{Re}s = \frac12$. Риман вычислил первые из них сам: в 1932 году Карл Людвиг Зигель нашёл эти расчёты в его бумагах вместе с формулой, которой Риман пользовался и которую никогда не публиковал.
Чему равна сумма $1 + 2 + 3 + 4 + \dots$?
При $s = -1$ ряд $\sum n^{-s} = 1 + 2 + 3 + \dots$ расходится. Значение $\zeta(-1) = -\frac1{12}$ даёт аналитическое продолжение — единственная голоморфная функция, которая совпадает с суммой ряда там, где ряд сходится (глава 34). Складывать при этом ничего не складывают.
Музыка простых
Чтобы увидеть, как нули управляют простыми, удобнее считать простые числа с весами. Эту функцию ввёл Пафнутий Чебышёв.
Функция Чебышёва $\psi(x)$ — сумма $\ln p$ по всем степеням простых $p^k \le x$. Например, $\psi(10) = 3\ln2 + 2\ln3 + \ln5 + \ln7 \approx 7{,}832$: двойка входит за $2, 4, 8$, тройка — за $3, 9$.
Каждое простое $p$ весит $\ln p$, а частота простых около $t$ примерно $\frac1{\ln t}$, так что «в среднем» каждое число прибавляет к $\psi$ единицу, и $\psi(x) \approx x$. Нетрудно показать, что $\frac{\psi(x)}{x} \to 1$ тогда и только тогда, когда $\frac{\pi(x)}{x/\ln x} \to 1$: тяжёлых степеней простых мало. Риман нашёл формулу, которая говорит, чему равна ошибка. В 1895 году Ганс фон Мангольдт доказал её в таком виде.
Каждый нуль — нота, а простые числа — аккорд из бесконечного числа нот. Первые несколько волн рисуют плавную кривую, следующие вырезают из неё ступеньки. Для самой $\pi(x)$ у Римана есть похожая формула, чуть сложнее: вместо $x$ в ней стоит гладкая функция $R(x) = \sum_{n \ge 1}\frac{\mu(n)}{n}\operatorname{li}\!\left(x^{1/n}\right)$, где $\mu(n)$ — функция Мёбиуса (ноль, если $n$ делится на квадрат простого, иначе $+1$ или $-1$ при чётном или нечётном числе простых множителей), а каждая пара нулей тоже добавляет волну.
Теперь видно, почему важно, где лежат нули. Волна от пары нулей с действительной частью $\beta$ растёт как $x^\beta$. Если бы нашёлся нуль с $\beta = 1$, его волна росла бы как сам главный член $x$, и закон распределения мог бы не выполняться. В 1896 году Адамар и Валле-Пуссен доказали, что на прямой $\operatorname{Re}s = 1$ нулей нет, — и так закрыли вопрос, который Гаусс задал столетием раньше.
$\pi(x) \sim \operatorname{li}x \sim \frac{x}{\ln x}$, то есть отношения $\frac{\pi(x)}{\operatorname{li}x}$ и $\frac{\pi(x)}{x/\ln x}$ стремятся к $1$ при $x \to \infty$.
Идея доказательства и почему целиком его здесь нет
Прологарифмируем тождество Эйлера и продифференцируем: $-\frac{\zeta'(s)}{\zeta(s)} = \sum_{n}\frac{\Lambda(n)}{n^s}$, где $\Lambda(n) = \ln p$, если $n = p^k$, и $0$ иначе, — это «производная» функции $\psi$. Интеграл по вертикальной прямой в комплексной плоскости переводит эту функцию обратно в $\psi(x)$, а вычеты в полюсах $-\frac{\zeta'}{\zeta}$ — в полюсе $s = 1$ и в нулях $\zeta$ — дают явную формулу (вычеты, глава 34). Чтобы получить $\psi(x) \sim x$, нужно доказать, что на прямой $\operatorname{Re}s = 1$ нулей нет, и аккуратно оценить интегралы; даже самое короткое доказательство (Дональда Ньюмана, 1980) опирается на теорему Коши и занимает несколько страниц. В 1949 году Сельберг и Эрдёш нашли доказательство без комплексного анализа, но оно длиннее. Это и есть путь, обещанный в главе 3.
Вершина: гипотеза Римана
Волна от нуля тем выше, чем правее он лежит. Если все нули лежат на средней прямой, высота каждой волны не больше $\frac{2\sqrt x}{|\rho|}$, и ошибка в законе распределения — порядка корня из $x$. Таблица в начале главы подсказывает именно это.
Гипотеза Римана: все нетривиальные нули дзета-функции лежат на критической прямой $\operatorname{Re}s = \frac12$.
Сам Риман написал о ней одну фразу: «Весьма вероятно, что все корни действительны. Конечно, было бы желательно строгое доказательство; но я, после нескольких беглых безуспешных попыток, временно отложил его поиски» (действительные корни в его обозначениях — это нули на критической прямой). С тех пор поиски не прекращались. В 1900 году Давид Гильберт включил гипотезу в свой список важнейших проблем под номером восемь, в 2000 году Математический институт Клэя назначил за её решение миллион долларов.
Что известно наверняка. В 1914 году Годфри Харди доказал, что на критической прямой лежит бесконечно много нулей. Брайан Конри в 1989 году показал, что на ней лежит больше двух пятых всех нулей. Компьютеры проверили очень много: Дэвид Платт и Тимоти Траджиан в 2021 году доказали, что все нули с мнимой частью от $0$ до $3 \cdot 10^{12}$ лежат на прямой, — а таких нулей больше двенадцати триллионов. Ни одного нуля вне прямой не найдено.
Гипотеза Римана верна тогда и только тогда, когда $|\pi(x) - \operatorname{li}x| \le C\sqrt x\ln x$ для некоторой постоянной $C$ и всех $x \ge 2$.
Идея доказательства
В одну сторону — через явную формулу: если все $\beta = \frac12$, каждая волна не выше $\frac{2\sqrt x}{|\rho|}$, а нулей с $|\gamma| \le T$ около $\frac{T}{2\pi}\ln\frac{T}{2\pi}$. Оборвав сумму на подходящем $T$ и оценив остаток, получают ошибку порядка $\sqrt x\ln^2 x$ для $\psi$ и затем $\sqrt x\ln x$ для $\pi$. В другую — если ошибка так мала, то функция $\frac{\zeta'}{\zeta}$, выраженная через $\psi$ интегралом, продолжается без особенностей в полуплоскость $\operatorname{Re}s > \frac12$, и нулей там нет; по симметрии их нет и левее $\frac12$. Подробные оценки — в книгах Эдвардса и Титчмарша. Лоуэлл Шёнфельд в 1976 году нашёл явную постоянную: если гипотеза верна, то $|\pi(x) - \operatorname{li}x| < \frac{\sqrt x\ln x}{8\pi}$ при $x \ge 2657$. Для $x = 10^{18}$ это $1{,}65 \cdot 10^9$, а настоящая ошибка — $2{,}2 \cdot 10^7$.
Проверено больше двенадцати триллионов нулей, и все лежат на прямой. Можно ли считать гипотезу Римана доказанной?
Знаменитый пример — сама ошибка $\operatorname{li}x - \pi(x)$. Во всей таблице выше она положительна, и так при всех $x$, до которых дошли вычисления. Но Джон Литлвуд в 1914 году доказал, что она меняет знак бесконечно много раз. Где случится первая смена знака, точно неизвестно; известно лишь, что не позже примерно $1{,}4 \cdot 10^{316}$ — далеко за пределами любых вычислений.
Соседний хребет: эллиптические кривые
Древняя задача: какие натуральные числа бывают площадями прямоугольных треугольников с рациональными сторонами? У треугольника со сторонами $3, 4, 5$ площадь $6$. Леонардо Пизанский (Фибоначчи) около 1225 года нашёл треугольник площади $5$: $\frac32$, $\frac{20}{3}$, $\frac{41}{6}$. Ферма доказал, что площадь $1$ невозможна. Такие числа называют конгруэнтными, и задача сводится к кривой: число $n$ конгруэнтно тогда и только тогда, когда на кривой $y^2 = x^3 - n^2x$ есть рациональная точка с $y \ne 0$. Треугольнику $3, 4, 5$ соответствует точка $\left(\frac{25}{4};\ \frac{35}{8}\right)$ кривой $y^2 = x^3 - 36x$: проверьте, $\frac{15\,625}{64} - 225 = \frac{1225}{64}$.
Эллиптическая кривая — множество точек $(x;\,y)$, для которых $y^2 = x^3 + ax + b$, где $4a^3 + 27b^2 \ne 0$, вместе с ещё одной, «бесконечно удалённой» точкой $O$. Условие на коэффициенты исключает кривые с остриём или самопересечением: число $-(4a^3 + 27b^2)$ — дискриминант многочлена $x^3 + ax + b$, и он не равен нулю ровно тогда, когда у многочлена нет кратных корней.
С эллипсами эти кривые почти не связаны: имя досталось им от эллиптических интегралов, которыми считают длину дуги эллипса. Главное их свойство в том, что точки кривой можно складывать. Прямая через две точки кривой пересекает её в третьей: уравнение кривой на прямой превращается в кубическое, а у кубического уравнения с двумя известными корнями есть и третий.
Если $P$ и $Q$ — точки кривой $y^2 = x^3 + ax + b$ с $x_P \ne x_Q$, то прямая $PQ$ пересекает кривую ещё ровно в одной точке $R$, и $R = (x_{P+Q};\,-y_{P+Q})$ с $x_{P+Q}, y_{P+Q}$ из формулы выше.
Хитрость в том, чтобы вместо поиска точки пересечения решать кубическое уравнение, два корня которого уже известны, — хватит теоремы Виета.
Если прямая вертикальна, третьей точки на плоскости нет: считают, что прямая встречает кривую в бесконечно удалённой точке $O$, и $P + Q = O$. Точка $O$ играет роль нуля: $P + O = P$, а противоположная к $(x;\,y)$ точка — $(x;\,-y)$.
Точки эллиптической кривой вместе с $O$ образуют коммутативную группу относительно сложения по правилу хорд и касательных. Если коэффициенты $a, b$ рациональны, то рациональные точки образуют подгруппу.
Сумма не зависит от порядка слагаемых: прямая через $P$ и $Q$ — та же, что через $Q$ и $P$. Нуль и противоположные элементы описаны выше. Подгруппа: если координаты $P$ и $Q$ и коэффициенты рациональны, то рационален наклон $\lambda$ (в том числе в случае касательной), а с ним и координаты $P + Q$ по формуле сложения; противоположная точка $(x;\,-y)$ тоже рациональна. Остаётся ассоциативность, $(P + Q) + S = P + (Q + S)$, — самое трудное свойство. Её можно проверить прямым вычислением по формулам сложения, но выкладки огромны, и компьютерной алгебре тут доверяют больше, чем карандашу. Концептуальное доказательство использует теорему Кэли — Бахараха о кубических кривых на проективной плоскости и выходит за рамки курса; его можно найти в книге Дж. Силвермена и Дж. Тейта «Рациональные точки на эллиптических кривых».
На кривой $y^2 = x^3 - x + 1$ сложите точки $P = (-1;\,1)$ и $Q = (1;\,1)$.
Прямая через $P$ и $Q$ горизонтальна: $y = 1$, $\lambda = 0$. Подставив, получаем $x^3 - x + 1 = 1$, то есть $x(x - 1)(x + 1) = 0$: третья точка $R = (0;\,1)$. По формуле $x_{P+Q} = 0^2 - (-1) - 1 = 0$, $y_{P+Q} = 0 - 1 = -1$. Ответ: $P + Q = (0;\,-1)$ — отражение $R$.
Из двух рациональных точек сложение делает третью, из неё — следующую, и так можно получить бесконечно много рациональных точек. Сколько нужно исходных?
У эллиптической кривой с рациональными коэффициентами группа рациональных точек конечно порождена: найдутся точки $P_1, \dots, P_r$ и конечная подгруппа $T$ такие, что каждая рациональная точка равна $n_1P_1 + \dots + n_rP_r + t$ с целыми $n_i$ и $t \in T$.
Доказательство Луиса Морделла — развитие «метода спуска» Ферма (глава 18): у точек определяют «высоту» (размер числителей и знаменателей) и показывают, что из любой точки можно спуститься к точкам ограниченной высоты. Оно занимает главу в учебнике Силвермена и Тейта, и мы его примем. Число $r$ называют рангом кривой. Для кривой $y^2 = x^3 - 36x$ ранг равен $1$, для $y^2 = x^3 - x$ — нулю: её рациональные точки исчерпываются $O$, $(0;\,0)$ и $(\pm1;\,0)$, и поэтому $1$ не конгруэнтное число. Как по кривой найти её ранг, в общем случае неизвестно.
Как кривые доказали теорему Ферма
В главе 18 мы оставили Великую теорему Ферма — у уравнения $a^n + b^n = c^n$ при $n \ge 3$ нет решений в натуральных числах — с обещанием рассказать, что за кривые помогли её доказать. Путь был таким. В 1985 году Герхард Фрай заметил: если бы решение $a^p + b^p = c^p$ с простым $p \ge 5$ существовало, то кривая $y^2 = x(x - a^p)(x + b^p)$ была бы настолько странной, что вряд ли могла бы быть модулярной. Модулярность — глубокое свойство: числа $p + 1 - N_p$, которые считаются для кривой по каждому простому модулю, оказываются коэффициентами функции с огромной симметрией на комплексной верхней полуплоскости — модулярной формы. Гипотеза Таниямы — Симуры (1955–1957) утверждала, что модулярна любая эллиптическая кривая с рациональными коэффициентами.
В 1986 году Кен Рибет доказал, что кривая Фрая модулярной быть не может. Значит, из гипотезы Таниямы — Симуры следовала теорема Ферма. В июне 1993 года Эндрю Уайлс, семь лет работавший почти в одиночку, объявил в Кембридже доказательство модулярности для класса кривых, куда попадала и кривая Фрая. В доказательстве нашёлся пробел; в сентябре 1994 года Уайлс вместе со своим бывшим учеником Ричардом Тейлором его закрыл. Две статьи вышли в 1995 году в журнале Annals of Mathematics. Полную гипотезу Таниямы — Симуры доказали в 2001 году Бройль, Конрад, Даймонд и Тейлор. Все эти доказательства занимают сотни страниц и опираются на математику далеко за пределами курса; но в их центре — те самые кривые $y^2 = x^3 + ax + b$ и счёт их точек по модулю $p$.
Кривые в браузере
Формулы сложения работают в любом поле, где можно делить. Возьмём остатки по простому модулю $p$ (глава 42): деление — умножение на обратный по модулю. Кривая превращается в конечное облако точек, сложение переставляет их по невидимым правилам, а свойства группы сохраняются.
Число $N$ точек эллиптической кривой над $\mathbb Z_p$ (вместе с $O$) удовлетворяет неравенству $|N - (p + 1)| \le 2\sqrt p$.
Интуиция: для каждого $x$ правая часть $x^3 + ax + b$ — квадрат примерно в половине случаев и тогда даёт две точки, иначе ни одной; в среднем выходит около $p$ точек плюс $O$. Теорема говорит, насколько сильно «везение» может отклониться от среднего. Её доказательство (Хельмут Хассе, 1930-е годы) опирается на алгебраическую геометрию, и мы примем его без доказательства — зато проверим в виджете.
На кривой $y^2 = x^3 + 2x + 2$ над $\mathbb Z_{17}$ лежит точка $P = (5;\,1)$. Найдите $2P$.
Касательная: $\lambda = \frac{3 \cdot 5^2 + 2}{2 \cdot 1} = \frac{77}{2}$. По модулю $17$: $77 \equiv 9$, а обратный к $2$ — это $9$ ($2 \cdot 9 = 18 \equiv 1$), так что $\lambda \equiv 9 \cdot 9 = 81 \equiv 13$. Тогда $x_{2P} = 13^2 - 5 - 5 = 159 \equiv 6$, $y_{2P} = 13 \cdot (5 - 6) - 1 = -14 \equiv 3$. Ответ: $2P = (6;\,3)$. Проверка: $3^2 = 9$ и $6^3 + 2 \cdot 6 + 2 = 230 = 13 \cdot 17 + 9$.
Сложение точек стоит довести до автоматизма: хорда, касательная и то же самое по модулю $p$. Все тренажёры курса — на странице практики.
Обмен ключами Диффи — Хеллмана из главы 41 переносится на кривую дословно. Вместо степени $g^a$ — кратная точка $aG = G + G + \dots + G$: её быстро вычисляют удвоениями, как быстрое возведение в степень. Алиса выбирает секретное $a$ и отправляет $aG$, Боб — $b$ и $bG$. Алиса вычисляет $a(bG)$, Боб — $b(aG)$, и это одна и та же точка $abG$. Подслушивающему нужно по $G$ и $aG$ найти $a$ — это дискретный логарифм на кривой.
Эллиптическую криптографию независимо предложили в 1985 году Нил Коблиц и Виктор Миллер. Её преимущество — размер. Лучшие известные способы искать дискретный логарифм на хорошей кривой — вариации «шагов младенца и великана» и ро-метода Полларда — требуют около $\sqrt N$ операций. Для кривой над полем из примерно $2^{256}$ элементов это $2^{128}$ шагов, то есть та же стойкость, что у RSA с ключом в $3072$ бита, при ключе в двенадцать раз короче.
Вторая часть ответа. Когда вы открываете сайт банка, браузер и сервер по протоколу TLS 1.3 (2018) договариваются о ключе обменом Диффи — Хеллмана на эллиптической кривой — чаще всего на кривой Curve25519 Даниэля Бернштейна (2006) или на кривой P-256 из стандарта NIST. Подслушавший видит общую точку и обе кратные, но чтобы получить ключ, ему нужно решить задачу дискретного логарифма на кривой, а для неё неизвестно способа быстрее примерно $2^{128}$ шагов. Квантовый компьютер с алгоритмом Шора эту защиту сломал бы (глава 41), поэтому с 2024 года браузеры всё чаще добавляют к обмену на кривой постквантовый алгоритм ML-KEM, стойкость которого держится на других задачах.
Простые числа распределены почти как случайные, и точность закона Гаусса определяется нулями одной функции: гипотеза Римана — это утверждение, что ошибка не больше, чем у честной случайности, порядка $\sqrt x$. Кривые третьей степени превращают точки в числа, которые можно складывать; эта арифметика доказала теорему Ферма и защищает интернет.
Куда дальше
Мы всё время говорили о простых как о чём-то почти случайном: частота $\frac{1}{\ln t}$, ошибка порядка $\sqrt x$, как у суммы случайных слагаемых, нули, похожие на спектры случайных матриц. Но чтобы говорить о случайности всерьёз, нужно начинать с самого простого: уметь считать варианты. Почему при трёх игральных костях сумма $10$ выпадает чаще суммы $9$, хотя обе складываются шестью способами? Сколькими способами может выпасть…? С этого вопроса начинается следующая глава.