Дидактические цели
Лаборатория для университета (первые курсы) или для продвинутого старшего класса, о кривой y² = x³ + ax + b. Она очень визуальна: почти всё происходит перетаскиванием точек по кривой и наблюдением за тем, как движется прямая, проходящая через них.
Центральная идея проста в формулировке и богата следствиями: прямая пересекает кубическую кривую в трёх точках, и если две из них рациональны, то и третья рациональна. Это правило вместе с отражением превращает рациональные точки кривой в группу: их можно складывать, умножать на целое число (n·P) и классифицировать. Отсюда возникают охота за рациональными точками (теорема Морделла: все они порождаются немногими) и кручение — точки, возвращающиеся к нейтральному элементу (теорема Мазура: возможно всего 15 вариантов). Лаборатория выходит к криптографии: та же кривая, но в модулярной арифметике (по модулю простого p), где вычислить n·P быстро, а восстановить n по n·P на практике неподъёмно. Именно эта асимметрия защищает сегодня безопасные соединения (TLS), WhatsApp и Bitcoin.
Чему учит лаборатория
- Видеть кривую y² = x³ + ax + b как форму, которая меняется вместе с a и b (одна ветвь или две), и распознавать, когда она перестаёт быть эллиптической кривой (дискриминант 4a³ + 27b² обращается в нуль).
- Определять сумму двух точек хордой и отражением, а сумму точки с собой — касательной; выводить и применять формулы сложения.
- Экспериментально убеждаться, что это сложение ассоциативно и коммутативно, то есть что рациональные точки кривой образуют группу с бесконечно удалённой точкой O в роли нейтрального элемента.
- Умножать точку на большое целое число способом «удвоить и сложить» (быстрое возведение в степень) вместо последовательного сложения.
- Искать рациональные точки кривой по высоте (знаменателю) и выражать их через комбинацию нескольких образующих (теорема Морделла).
- Распознавать кручение (точки конечного порядка) по критерию Нагеля — Лутц, проходить по семействам кривых с фиксированным кручением (нормальная форма Тейта) и знать все 15 возможных групп кручения над рациональными числами (теорема Мазура).
- Переносить ту же арифметику на вычисления по модулю простого p и понимать, почему умножить точку быстро, а обратить умножение (дискретный логарифм) настолько дорого, вплоть до обмена ключами Диффи — Хеллмана на эллиптической кривой вживую.
Ключевые математические идеи по блокам
A · Кривая. Форма y² = x³ + ax + b зависит от вещественных корней x³ + ax + b: две ветви, если корней три, одна — если корень один. Кривая особая (узел или остриё) ровно тогда, когда 4a³ + 27b² = 0; в этой точке она перестаёт быть эллиптической. Прямая пересекает кубику в трёх точках (с учётом кратности) или в двух плюс «одна в бесконечности», если прямая вертикальна.
B · Сложение и умножение. Если бы P + Q было третьей точкой пересечения P * Q, не нашлось бы нейтрального элемента; поэтому P + Q определяют как отражение P * Q. При таком определении P + (−P) = O и P + O = P. Ассоциативность (P + Q) + R = P + (Q + R) проверяется перетаскиванием точек и всегда выполняется, хотя это далеко не очевидно (на самом деле она опирается на девять точек Кэли — Бахараха). Умножение на n способом «удвоить и сложить» стоит порядка log₂ n операций вместо n: 13·P требует 5 операций (удвоить, сложить, удвоить, удвоить, сложить), а не 12.
C · Охота за рациональными точками. При рациональных коэффициентах хорда и касательная никогда не выходят за пределы Q: начав с рациональных точек, приходят только к рациональным точкам. Теорема Морделла утверждает, что группа рациональных точек — это E(Q) ≅ T ⊕ Zʳ: конечно порождённая группа с частью кручения T и рангом r образующих бесконечного порядка. Размер (высота, измеряемая числом цифр знаменателя) точки n·P растёт как n², из-за чего наивный перебор для больших n неосуществим. Конгруэнтные числа (площади прямоугольных треугольников с рациональными сторонами) — классический пример такой охоты: n конгруэнтно тогда и только тогда, когда y² = x³ − n²x имеет точку с y ≠ 0.
D · Кручение. Точки конечного порядка (возвращающиеся в O при умножении) имеют целые координаты и удовлетворяют критерию Нагеля — Лутц (y = 0 или y² делит 4a³ + 27b²), что позволяет находить их по конечной таблице кандидатов. Семейства Тейта показывают кривые, которые деформируются с параметром, не разрывая замкнутый многоугольник кручения. Теорема Мазура (1977) завершает классификацию: над Q существует только 15 возможных групп кручения, Z/n (n = 1…10, 12) и Z/2 × Z/2m (m = 1…4).
E · Криптография: обратный путь. Та же арифметика, теперь по модулю простого p (конечная группа): умножение n·P по-прежнему стоит недорого, порядка 2k операций для ключа из k бит. Обратить его — по Q = n·G найти n — задача разной природы в зависимости от того, где она поставлена:
- Над Q высота выдаёт n: поскольку размер n·P растёт как n², размер Q почти сразу подсказывает величину n.
- По модулю p подсказок нет: орбита G прыгает по решётке без всякой закономерности близости; быть «рядом» с Q ничего не говорит о том, близко ли n. Перебором найти n стоит порядка 2^k шагов против 2k шагов в прямом направлении: прямая против экспоненты.
- Лучшая из известных атак («шаг младенца — шаг великана», или ρ-метод Полларда) снижает число шагов с N до √N. При 256-битном ключе это √(2²⁵⁶) = 2¹²⁸ шагов, порядка 10²² лет при миллиарде шагов в секунду — дольше возраста Вселенной. Достаточно большой квантовый компьютер (с алгоритмом Шора) эту задачу бы всё же решил; отсюда интерес к постквантовой криптографии.
Зал «Прятки» проходит эту асимметрию в игре, прежде чем подкрепить её числами: над Q спрятанное число угадывают, потому что его выдаёт высота; в облаке точек по модулю p две соседние точки могут оказаться очень разными кратными, а два соседних кратных попадают в противоположные углы; а когда ученик прячет своё n, движок вычисляет n·G за несколько десятков операций, а чтобы найти его перебором, нужны сотни, и это при игрушечном простом числе. Зал заканчивается таблицей, сравнивающей путь туда с обратным путём.
Именно эту асимметрию — «дешёвый путь туда, немыслимо дорогой обратно» — использует протокол Диффи — Хеллмана: двое публикуют a·G и b·G и оба вычисляют одно и то же ab·G, а наблюдатель не может восстановить ни a, ни b.
F · Завершение. Детектив кривых (случайная кривая из проверенного списка, для которой нужно найти кручение и, если есть, точку бесконечного порядка) и калькулятор кривых без заданий, с точной арифметикой и видом по модулю p, который остаётся открытым для дальнейших исследований.
Источники
Лаборатория во многом следует книге Rational Points on Elliptic Curves Дж. Сильвермана и Дж. Тейта. Историческая мотивация начинается с задачи Баше (1621) и Диофанта (рациональные точки на кубике). Используются теорема Морделла (конечная порождённость группы рациональных точек), критерий Нагеля — Лутц, нормальная форма Тейта для семейств с фиксированным кручением и теорема Мазура (1977) о 15 возможных группах кручения. Блок о криптографии опирается на обмен ключами Диффи — Хеллмана и на криптографию эллиптических кривых, независимо предложенную Н. Коблицем и В. Миллером (1985).
Заметки для урока
- «Третья точка» и «Сложить — значит отразить» лучше смотреть подряд и с проекцией: это момент, когда сложение перестаёт быть формулой и становится картинкой, которую можно предсказать.
- «Сложение, которое можно перегруппировать» работает лучше, если сначала попросить класс предсказать результат, прежде чем отпускать точки: именно неожиданность того, что результат всегда совпадает, и держит идею группы.
- «Цифры растут взрывом» (парабола числа цифр знаменателя) наглядно показывает, почему перебор больших рациональных точек не работает.
- «Семейства с кручением» показывает, что один и тот же многоугольник кручения сохраняется, даже когда кривая деформируется вместе с ползунком u.
- «Прятки» — ключевой зал блока о криптографии: игра даёт прочувствовать асимметрию прежде, чем ей дадут имя, а итоговая таблица, сравнивающая прямую с экспонентой, — это весь аргумент в одной картинке.
- «Секрет у всех на виду» завершает блок о криптографии живым протоколом Диффи — Хеллмана: ученик играет за Ану против движка и расшифровывает сообщение, а весь класс может попробовать сыграть роль перехватчика.
Содержание по залам
Зал 1 · Форма кривой
Почему эти кривые важны (https, WhatsApp, Bitcoin, Великая теорема Ферма), и немного истории. Как нарисовать y² = x³ + ax + b, по шагам на примере y² = x³ − 4x: там, где x³ + ax + b отрицательно, кривой нет, а там, где положительно, есть две симметричные точки. Затем два ползунка: кривая симметрична относительно оси x и состоит из одной или двух частей в зависимости от вещественных корней x³ + ax + b.
Задания для ученика
- При b = 0: при каких a частей две (a < 0).
- При a = −2 двигать b, пока овал не отделится от ветви (открытие).
- Какое условие на a и b даёт две части (4a³ + 27b² < 0).
Зал 2 · Узлы и остриё
Когда овал касается ветви, появляется узел; при a = b = 0 — остриё. Разобранный пример: y² = x³ − 12x + 16 = (x − 2)²(x + 4) имеет узел в (2, 0) с двумя касательными. Критерий: 4a³ + 27b² = 0. Особые кривые не являются эллиптическими.
Задания для ученика
- Значение a, при котором y² = x³ + ax + 16 становится особой (−12).
- Сколько частей у y² = x³ − 3x + b при b = 1,9 и при b = 2,1 (две и одна).
- Где находится узел кривой y² = x³ − 3x + 2 ((1, 0)).
Зал 3 · Секущие прямые
Подстановка y = kx + c в уравнение кривой даёт уравнение третьей степени: разобранный пример с y = x + 1 и y² = x³ + 1, которые пересекаются в (−1, 0), (0, 1) и (2, 3). Затем прямую двигают и считают точки пересечения: 3 (считая касания дважды), либо 2 + «одна в бесконечности», если прямая вертикальна.
Задания для ученика
- Расположить прямую касательной к кривой.
- На y² = x³ − 3x + 6 — вторая точка пересечения горизонтальной касательной y = 2 в точке (1, 2) ((−2, 2)).
- Может ли невертикальная прямая вовсе не пересекать кривую (нет).
Зал 4 · Задача Диофанта
Рациональные точки, Диофант и Баше. Разобранный пример: касательная к y² = x³ + 17 в (−1, 4) даёт рациональную точку (137/64, 2651/512). Затем кривая Баше, y² = x³ − 2, с точкой (3, 5): касательная в (3, 5) даёт другую рациональную точку, (129/100, 383/1000) (Баше, 1621), а по симметрии и (129/100, −383/1000).
Задания для ученика
- Угловой коэффициент касательной в (3, 5) (27/10).
- Знаменатель новой x (100).
- Значение этой x (129/100).
Зал 5 · Третья точка
P ∗ Q: прямая через P и Q снова пересекает кривую в третьей точке. Разобранный пример на y² = x³ + 17 с P = (−2, 3) и Q = (−1, 4): наклон 1, x₃ = k² − x₁ − x₂ = 4 и P ∗ Q = (4, 9), без всяких квадратных корней.
Задания для ученика
- Довести точку до третьей точки для (2, 5) и (4, 9) ((−2, −3)).
- Не вычисляя, чему равно (2, 5) ∗ (−2, −3) ((4, 9): три точки на одной прямой меняются ролями).
Зал 6 · Сложить — значит отразить
Зачем отражать? Если бы P + Q было третьей точкой, не нашлось бы нейтрального элемента. Определение: P + Q = отражение P ∗ Q. Разобранный пример: (2, 5) + (8, 23) = (−1, 4).
Задания для ученика
- (−2, 3) + (−1, 4) по частям: наклон, x₃, y₃ и отражение ((4, −9)).
- Наоборот: при P = (−2, 3) и P + Q = (4, −9) найти Q ((−1, 4)).
Зал 7 · Бесконечно удалённая точка
Точка O: анимированный проективный вид. P + (−P) = O и P + O = P.
Задания для ученика
- Чему равно (2, 5) + (2, −5) (O).
- Чему равно −(4, 9).
Зал 8 · Точка плюс она же
P + P: хорда превращается в касательную по мере приближения Q к P (анимация скольжения). Наклон касательной: k = (3x² + a)/(2y). Разобранный пример с P = (−1, 4) на y² = x³ + 17: 2P = (137/64, −2651/512).
Задания для ученика
- На y² = x³ + 5x − 2 вычислить 2·(1, 2) по частям: k = 2, x₃ = 2, y₃ = 4 и отражение ((2, −4)).
- Почему 2P = O, когда y = 0 (вертикальная касательная).
Зал 9 · Сложение, которое можно перегруппировать
Эксперимент: двигать P, Q, R и наблюдать, как одновременно строятся (P + Q) + R и P + (Q + R); они всегда совпадают, хотя это далеко не очевидно (девять точек Кэли — Бахараха). Коммутативность: прямая через P, Q — та же, что через Q, P.
Задания для ученика
- Предсказать результат до того, как отпустить точки; выбор варианта о том, какое свойство увидено.
- При фиксированных P = (−2, 3) и Q = (4, 9) найти R, для которой P + Q + R = O ((−1, 4)).
Зал 10 · Умножение точки
n·P = P + P + …; орбита точки (3, 5) на y² = x³ − 2 прыгает по всей кривой, не повторяясь (бесконечный порядок). Удвоение и сложение по двоичной записи n: 13 = 1101₂ ⇒ удвоить, сложить, удвоить, удвоить, сложить (5 операций вместо 12).
Задания для ученика
- Какое n от 1 до 100 требует больше всего операций при удвоении и сложении (95 = 1011111₂: 6 удвоений + 5 сложений = 11).
- Построить 5·P за минимум шагов (2 удвоения + 1 сложение).
Зал 11 · Охотник за точками
Рациональные ⇒ рациональные: наклон, x₃ и y₃ вычисляются только сложением, вычитанием, умножением и делением. Высота точки (m/d², k/d³). Вручную на y² = x³ + 17: x = −1, −2 и 2 дают полные квадраты, x = 1 — нет. Затем автоматический поиск: ученик задаёт границу H, а движок перебирает все d и m; найденные точки загораются на кривой и в списке.
Задания для ученика
- Предложить целое x, отличное от −1, при котором x³ + 17 — полный квадрат (движок отвечает на каждую попытку).
- При H = 4 найти точку со знаменателем ((1/4, 33/8)).
Зал 12 · Всё из нескольких точек
Теорема Морделла (1922): все рациональные точки получаются сложением и вычитанием нескольких образующих; E(Q) ≅ T ⊕ Z^r, где r — ранг. На y² = x³ + 17 с G₁ = (−2, 3), G₂ = (2, 5) и кнопками ±G₁, ±G₂ и «удвоить» строят точки, опираясь на правило «три точки на одной прямой в сумме дают O».
Задания для ученика
- Построить (4, 9) (= G₁ − G₂).
- Построить (−1, 4) (= G₂ − 2G₁), узнав третью точку пересечения среди отмеченных.
Зал 13 · Цифры растут взрывом
График числа цифр знаменателя n·(3, 5): 1, 3, 5, 8, 15, 21, 28, 37, 48, 59 (n = 1…10). Растёт как n² (наложенная парабола).
Задания для ученика
- Предсказать, сколько цифр будет у знаменателя 20·P (≈ 4 × 59; ответ в диапазоне от 200 до 270).
- По квадратичному закону — наименьшее n, при котором в знаменателе больше 1000 цифр (42).
Зал 14 · Конгруэнтные числа
n конгруэнтно, если это площадь прямоугольного треугольника с рациональными сторонами (6 — у треугольника 3-4-5; 5 — у треугольника 3/2, 20/3, 41/6). Рассуждение Ферма в анимации по шагам: из 3-4-5 через два квадрата получаются три рациональных квадрата подряд и точка (25/4, 35/8) на y² = x³ − 36x. Обратные формулы: a = |x² − n²|/|y|, b = |2nx|/|y|, c = (x² + n²)/|y|. Удвоение точки превращает треугольник в другой той же площади (7/10, 120/7, 1201/70). В конце — число 157 (Загир).
Задания для ученика
- Точка (−4, 6) при n = 5 → катеты и гипотенуза треугольника (3/2, 20/3, 41/6).
- Точка кривой y² = x³ − 576x, соответствующая треугольнику 6-8-10 ((25, ±35)).
Зал 15 · Точки порядка 2
2P = O ⇔ y = 0. У y² = x³ − x их три: (−1, 0), (0, 0), (1, 0) → вместе с O, Z/2 × Z/2.
Задания для ученика
- Сколько точек порядка 2 у y² = x³ + 1 (1) и y² = x³ + 17 (0).
Зал 16 · Точки перегиба
3P = O ⇔ P — точка перегиба (касательная пересекает кривую в P трижды). Анимация «сплющивающейся» касательной. На y² = x³ + 1: (0, ±1). Орбита точки порядка n замыкается через n шагов; орбита точки бесконечного порядка, как (3, 5) на кривой Баше, не возвращается никогда.
Задания для ученика
- Найти перетаскиванием точку перегиба кривой y² = x³ − 9x + 9 ((3, ±3)).
Зал 17 · Фильтр Нагеля — Лутц
Точки кручения имеют целые координаты, и y = 0 либо y² | 4a³ + 27b²: это необходимое условие, но не достаточное. Разобранный пример с y² = x³ + 1 (4a³ + 27b² = 27, y ∈ {0, ±1, ±3}): пять кандидатов, все — точки кручения, вместе с O образующие Z/6.
Задания для ученика
- На y² = x³ + 9 отметить, какие из четырёх точек, прошедших фильтр, — точки кручения, глядя на их орбиты ((0, ±3); у (−2, ±1) бесконечный порядок).
- Сколько значений y > 0 проходит фильтр на y² = x³ − 2 (4, и ни одно не даёт целого x).
- Что можно сказать о (3, 5) на y² = x³ − 2, ничего не складывая (это не точка кручения: 25 не делит 108).
- На y² = x³ + 17 вычислить 2·(−2, 3) = (8, −23) и вывести, что у (−2, 3) бесконечный порядок, хотя фильтр она проходит.
Зал 18 · Семейства с кручением
Нормальная форма Тейта, y² + (1 − c)xy − by = x³ − bx², с P = (0, 0). Порядок n выбирают кнопками, а ползунок u деформирует кривую, но многоугольник орбиты P по-прежнему имеет n сторон.
Задания для ученика
- При n = 12 — порядок 3P (4).
- При n = 10 — какое кратное kP имеет порядок 2 (5P).
- При n = 9 — сколько из P, 2P, …, 8P имеют порядок 9 (6).
Зал 19 · Музей Мазура
Музей 15 возможных групп кручения над Q: Z/n (n = 1…10, 12) и Z/2 × Z/2m (m = 1…4). Витрина с одной кривой для каждой группы и её орбитой.
Задания для ученика
- Какую пару порядков не могут иметь две точки одной кривой (3 и 5: их сумма имела бы порядок 15).
- Группа кручения кривой с тремя точками порядка 2 и одной точкой порядка 3 (Z/2 × Z/6).
Зал 20 · Кривая по модулю p
Где это используется (https, WhatsApp, Bitcoin) и почему именно кривые: кривая на 256 бит защищает так же, как обычный модуль больше чем на 3000 бит. То же уравнение в арифметике по модулю простого p: кривая становится симметричным облаком точек на решётке (анимация: p растёт). Неравенство Хассе: |#E − (p + 1)| ≤ 2√p. Кручение сохраняется (6 делит #E для y² = x³ + 1).
Задания для ученика
- Вручную найти точки y² = x³ + 1 mod 5 по таблице квадратов (6, вместе с O).
- По оценке Хассе — сколько точек самое большее может быть у кривой по модулю 101 (122).
Зал 21 · Сложение по модулю p
Сложение работает так же: прямая уходит за край решётки и возвращается с другой стороны (как на торе) и по-прежнему проходит через 3 точки. Деление = умножение на обратный элемент по модулю p (мини-калькулятор обратных). Разобранный пример на y² = x³ + x + 1 mod 23: (9, 16) + (12, 4) = (18, 20).
Задания для ученика
- G + G для G = (3, 10) mod 23 по шагам: k = 6 (обратный к 20 — это 15), x₃ = 7, y₃ = 12.
- Если порядок G равен 28, чему равно 27·G, ничего не складывая ((3, 13)).
Зал 22 · Прятки
Один вопрос на весь зал: если дано n·G, можно ли найти n? Раунд 1, над Q (y² = x³ − 2, P = (3, 5)): движок прячет n от 1 до 20, и, сравнивая число цифр знаменателя (растёт как n²), его угадывают. Иллюстрация без баллов в облаке по модулю 1009: две соседние точки могут оказаться очень разными кратными, а два соседних кратных попадают в противоположные углы. Раунд 2, ученик прячет своё n (от 2 до 1012): движок вычисляет n·G удвоением и сложением, а затем ищет n перебором со счётчиком в реальном времени. В конце — таблица страха: для ключа из k бит путь туда ≈ 2k операций, перебор обратно ≈ 2^k, лучшая известная атака ≈ √(2^k).
Задания для ученика
- Раунд 1: угадать n по числу цифр знаменателя.
- Раунд 2: спрятать n и сравнить стоимость пути туда и обратного пути.
- Если в знаменателе n·P 130 цифр, в каком диапазоне лежит n (от 11 до 15).
- Выбор варианта: почему по модулю p не помогает приближаться понемногу.
- Сколько шагов в среднем потребует перебор, если в группе 1013 точек (~506).
Зал 23 · Шаги младенца, шаги великана
При m = ⌈√N⌉ — список из m «младенцев» (0·G, …, (m − 1)·G) и «великаны» Q, Q − mG, Q − 2mG…, пока один из них не совпадёт с младенцем. Анимация с G = (0, 425) и Q = (337, 940) mod 1009 (1013 точек, m = 32). Лучшая из известных атак снижает число шагов с N до √N. При 256 битах: √(2^256) = 2^128 ≈ 3,4·10^38 шагов, при 10^9 шагов в секунду ≈ 10^22 лет (возраст Вселенной — 1,4·10^10 лет). Честное замечание: достаточно большой квантовый компьютер (алгоритм Шора) эту задачу бы решил.
Задания для ученика
- Сколько шагов понадобилось в анимации (32 младенца + 24 великана = 56 против 776 при переборе).
- Сколько лет, по порядку величины (10^22).
Зал 24 · Секрет у всех на виду
Ана публикует a·G, Бруно — b·G, и оба вычисляют ab·G; перехватчику, который видит G, a·G и b·G, пришлось бы решать обратную задачу. Метафора смешивания красок, анимированная цветами на доске по модулю 23, затем настоящая версия с G = (3, 10) порядка 28 и таблицей её кратных. Ученик играет за Ану, движок — за Бруно.
Задания для ученика
- При a = 5 и b = 9 — общий секрет (ab mod 28 = 17 и 17·G = (18, 3)).
- Сыграть за Ану: выбрать секретное n, отправить n·G, вычислить секрет S по m·G, который присылает движок, и расшифровать при k = x(S) сообщение, зашифрованное шифром Цезаря.
- В роли перехватчика: при каком размере ключа можно восстановить a (5 и 10 бит — да, 256 бит — нет).
Зал 25 · Детектив кривых
Новая случайная кривая (из проверенного списка): ученик использует фильтр Нагеля — Лутц, орбиты и поиск точек малой высоты, чтобы назвать её кручение и точку бесконечного порядка, если она есть.
Задания для ученика
- Определить группу кручения кривой.
- Решить, есть ли у неё точки бесконечного порядка (ранг не меньше 1).
- Если есть, записать одну из них.
Зал 26 · Калькулятор кривых
Последний зал, без заданий и баллов: выбрать кривую (или ввести a и b), увидеть её точное кручение, искать рациональные точки до высоты H, складывать, вычитать, умножать, находить порядки и орбиты в точной арифметике и смотреть кривую по модулю p с оценкой Хассе. Зал остаётся открытым, чтобы к нему возвращаться.
Задания для ученика
- Без заданий: свободно исследовать другую кривую, другую точку или другое простое число.
Залы для показа
Самые наглядные для показа и обсуждения в классе.