dxdt.ru: занимательный интернет-журнал

Многие слышали про криптографию на эллиптических кривых. Но эллиптические кривые, которые давно являются мощным инструментом теории чисел, можно успешно применить к решению элементарной (по формулировке) арифметической задачки про бананы, яблоки и ананасы. Текст ниже – несколько сокращённая версия моего перевода ответа Quora.com, который дал Alon Amit (англ.).

В Сети нередко можно натолкнуться на различные задачи, сформулированные при помощи картинок, которые содержат какую-нибудь “арифметику” с фруктами (или другими объектами быта) и утверждения типа “Только 5% людей могут решить это”. Обычно, задачи довольно бестолковые, служащие для привлечения внимания к каким-нибудь онлайн-тестам.

(Найдите решение в целых положительных значениях для яблока, банана и ананаса.)

Однако эта задача только выглядит простой. Её можно решить (ниже мы разберём как), но решение оказывается сложным и требует специальных математических знаний. Может показаться, что если не удалось найти “формулы” для решения, то, так как это вроде бы простое уравнение и маленькое число 4, можно вооружиться практически любым языком программирования и поручить компьютеру перебор. Компьютеры нынче быстрые, поэтому ответ, возможно, найдётся практически тут же. Но это далеко не так. Грубый компьютерный перебор здесь просто оказывается бесполезен.

Перепишем задачу в привычных обозначениях. Мы хотим найти решения в целых положительных числах уравнения:

Прежде всего хорошо бы понять, к какому типу уравнений относится данное. Здесь требуется найти решения в целых числах (даже в натуральных). Похоже, это задача из области теории чисел. Выражение записано в рациональных функциях, но, домножив на общее кратное, можно легко получить многочлен, представляющий собой диофантово уравнение (диофантовыми называют уравнения с целыми коэффициентами, решения которых также ищут в целых или натуральных числах; пример диофанового уравнения: x^5 + y^5 = z^5 – АВ). Поиск решений в целых положительных числах делает задачу существенно более трудной, как мы убедимся ниже.

Сколько у нас переменных? На первый взгляд – три: a, b и c. Но намётанный глаз сразу обратит внимание на то, что уравнение однородное (степени всех одночленов, или мономов, равны – АВ). Поэтому, если (a, b, c) – решение, то и тройка (7a, 7b, 7c) – тоже решение. Любая такая кратная тройка будет решением, число 7 здесь взято только для примера. Умножение всех переменных на константу ничего не изменяет, так как константа сокращается:

Уравнение только кажется трёхмерным, на самом деле – оно двумерное. Геометрически, это двумерная поверхность. Именно такая поверхность определяется единственным уравнением с тремя переменными, например, x^2 = y + z^2. Более того, наша поверхность получается движением образующей линии, то есть, понять свойства поверхности можно при помощи изучения её сечения плоскостью. Такое сечение оказывается проективной кривой (грубо говоря, алгебраической кривой с присоединённой бесконечно удалённой точкой – АВ).

Данное наблюдение означает следующее. У нас есть тройки (кортежи) решений. Мы можем разбить все решения на классы, в соответствии со значением (например) переменной c: с = 0 и c ≠ 0. Первый класс решений (c = 0) фактически использует только две переменных: a и b. Решения из второго класса мы можем разделить на c и получить вариант с фиксированным значением c = 1. То есть, мы можем искать рациональные решения, где c = 1, а потом получить целые решения (a, b, c), умножив значения на общее кратное. То есть, целочисленные решения однородного уравнения соответствуют рациональным решениям некоторого неоднородного уравнения, размерность (число переменных) которого на единицу меньше.

Какова степень нашего уравнения? Степенью уравнения (многочлена) называют максимальную степень монома (то есть, элементарной части многочлена), которая определяется как сумма степеней входящих в него переменных. Например, степень a²bc⁴ равна 7, так как 7 = 2 + 1 + 4.

Свойства диофантовых уравнений существенно различаются в зависимости от степени:

• уравнения степени 1 – очень лёгкие;
• степени 2 – полностью изучены, и обычно поддаются простейшим методам;
• степени 3 – это огромный, глубоко теоретический, океан и куча нерешённых проблем;
• диофантовы уравнения степеней 4 и выше – очень и очень сложная область.

Наше уравнение имеет степень 3. В этом легко убедиться, умножив на общее кратное:

a(a + b)(a + c) + b(b + a)(b + c) + c(c + a)(c + b) = 4(a + b)(a + c)(b + c)

Не нужно раскрывать все скобки, чтобы увидеть, как получается третья степень: никакую из переменных не придётся умножать на саму себя более двух раз. У нас будут получаться a³, b²c и abc, но суммарная степень не превысит 3. Раскрыв скобки и упростив, получим следующее уравнение:

a³ + b³ + c³ – 3(a²b + ab² + a²c + ac² + b²c + bc²) – 5abc = 0

Вы можете возразить, что нельзя умножать на знаменатели, так как какой-то из них может быть равен нулю. Действительно, наше новое уравнение имеет несколько решений, которые не соответствуют исходному. Но так даже лучше. Дело в том, что такое преобразование улучшает ситуацию, упрощая работу с уравнением. Просто, если мы найдём какое-то решение, потребуется проверить, что оно не делает никакой из исходных знаменателей равным нулю.

Нетрудно найти корень нового уравнения. Например: a = -1, b = 1, c = 0 – рациональное решение, или рациональная точка. Это подсказывает, что наше кубическое уравнение на самом деле эллиптическая кривая.

Первое, что нужно сделать с уравнением эллиптической кривой, это привести его к форме Вейерштрасса:

y² = x³ + ax + b

или (полная форма):

y²=x³ + ax² + bx + c

К форме Вейерштрасса можно привести всякое уравнение эллиптической кривой (исключения относятся к случаю полей малой характеристики, но нас этот момент сейчас не касается). Процесс преобразования существенным образом использует тот факт, что известна по крайней мере одна рациональная точка, и обычно оказывается трудоёмким, но это всего лишь механический процесс, который, к тому же, автоматически выполняют некоторые системы компьютерной алгебры. В нашем случае результат преобразования представляет собой пару пугающих формул:

Как только появились эти формулы, можно, путём пусть и утомительных, но очевидных алгебраических преобразований, получить следующее уравнение:

y² = x³ + 109x² + 224x (2)

Это уравнение выглядит совсем иначе, но, тем не менее, является верной моделью оригинального. Его график представлен ниже – типичная эллиптическая кривая с двумя вещественными компонентами.

Ласточкин хвост справа растёт до бесконечности и дальше. А замкнутая овальная часть слева – и есть самое интересное для нас место.

Решение (x,y) данного уравнения позволяет получить решение (a,b,c) исходного:

Отображения, которые мы построили из (a,b,c) в (x,y) и обратно, показывают, что два уравнения являются “одинаковыми” с точки зрения теории чисел: рациональные решения одного уравнения дают рациональные решения другого, то есть, между ними установлена бирациональная эквивалентность. Понятие бирациональной эквивалентности – одно из фундаментальных в алгебраической геометрии. Как отмечено выше, в нашем случае есть некоторые “исключительные” точки, а именно, те, в которых (a+b),(a+c) или (b+c) равны нулю. Обычное дело в бирациональной геометрии, но нам это никаких проблем не доставит.

Рассмотрим пример. Эллиптическая кривая (2) содержит привлекательную рациональную точку: x=-100, y=260. Найти её не так легко, как проверить, что значения – верные. Просто подставьте числа в уравнение и убедитесь, что обе части равны. Теперь мы можем проверить и значения a, b, c, соответствующие данной точке:

a=2/7
b=-1/14
c=11/14

Мы можем умножить на общее кратное, что даст целые числа:

a=4
b=-1
c=11

Подставляем в исходную задачу. Всё сходится:

Числа, составляющие этот ответ, целые, но не все они положительные, поэтому не подходят к исходной задаче. Нашу тройку чисел не так легко определить умозрительно, но, тем не менее, вполне реально подобрать вручную, не используя компьютер. Так что обещанная трудность задачи кроется в требовании решения в натуральных числах.

Как только у нас есть рациональная точка на кривой (2), мы можем получить другие рациональные точки, используя метод секущих и касательных для сложения точек. Начнём с точки P=(-100,260) и сложим её с самой собой. Это делается при помощи нахождения точки пересечения кривой и касательной к ней, проведённой в точке P. При этом, для определения суммы, точку нужно отразить относительно горизонтальной оси. (Принципы метода секущих и касательных показаны на рисунках ниже.)

(Удвоение точки.)

(Сложение двух точек.)

Результат удвоения точки P выглядит несколько более пугающим:

P + P = 2P = (8836/25, -950716/125)

Эта новая точка соответствует значениям a, b, c, которые так же походят к исходному уравнению:

(a, b, c) = (9499, -8784, 5165)

Можно с уверенностью сказать, что это решение непросто найти перебором вручную, но вполне реально при помощи простейшей программы на компьютере. Как бы там ни было, оно всё ещё не удовлетворяет требованию положительности.

Продолжим складывать точки и вычислим 3P=2P+P, соединив 2P и P прямой (секущей) и найдя пересечение с кривой. Снова определим a, b, c, и убедимся, что не все значения положительные. То же будет для 4P, 5P и так далее… пока мы не попадём в точку 9P.

9P=
-66202368404229585264842409883878874707453676645038225
 /
 13514400292716288512070907945002943352692578000406921,

 58800835157308083307376751727347181330085672850296730351871748713307988700611210
 /
 1571068668597978434556364707291896268838086945430031322196754390420280407346469

Эту точку совершенно точно нелегко было бы найти, но всё что потребовалось сделать при помощи нашего метода – это несколько раз применить простой геометрический алгоритм. Соответствующие значения a, b, c удивительны:

a=154476802108746166441951315019919837485664325669565431700026634898253202035277999,
b=36875131794129999827197811565225474825492979968971970996283137471637224634055579,
c=4373612677928697257861252602371390152816537558161613618621437993378423467772036

Это 80-значные числа. На практике невозможно найти 80-значные решения исходной задачи простым перебором на компьютере – это займёт слишком много времени. Удивительно, но при подстановке в наше исходное уравнение a/(b+c)+b/(a+c)+c/(a+b) найденные числа дают результат ровно 4. Оказывается, это наименьшее решение задачи. По мере того, как мы складываем точку P с самой собой, знаменатели уравнения продолжают расти. Доказать это не так просто, однако теория высот на эллиптических кривых позволяет показать, что эти астрономические числа, действительно, наименьшее решение исходной задачи.

Уже 80-значные числа в ответе – велики. Но если вместо 4 подставить 178, то для записи чисел решения потребуется 398605460 десятичных цифр. Нет, это не один из ответов, это лишь число знаков, которые потребуются, чтобы его записать. А для значения 896 запись решения потребует триллионы знаков.

Это впечатляющий пример того, что у диофантовых уравнений с маленькими коэффициентами могут быть огромные решения.

Источник: Quora.com

Адрес записки: https://dxdt.ru/2018/05/21/8520/