Числа Маркова в Zp

Современные алгоритмы шифрования используют сложность обращения элементов в группах конечных полей Z_p. Например, алгоритм RSA использует группу умножения поля, а более современная эллиптическая криптография — группу точек эллиптической кривой над конечным полем. Для расшифровки сообщения на него действуют открытым ключом — элементом группы, обратным закрытому ключу.

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

Все целочисленные решения этого уравнения образуют ветвящееся дерево, в каждой вершине которого сходится по три ребра. По теореме Виета вершине-решению (x, y, z) можно сопоставить решения (x, y, 3xy − z), (x, 3xz − y, z) и (3yz - x, y, z). В конечных полях это дерево сворачивается в причудливые конечные графы, математического описания которых мне найти не удалось. Например, если вдумчивый читатель выпишет число различных (с точностью до симметрии) решений уравнения при разных p, то получит последовательность, отсутствующую в энциклопедии последовательностей целых чисел Слоэна.

На картинке внизу приведены решения для поля из пяти элементов (p = 5). Изменяя число элементов поля и число переменных в уравнении Маркова, можно построить другие графы с числом вершин, не превосходящим 100. Можно далее улучшить получающиеся картинки, поменяв «пружинный» алгоритм размещения вершин в используемой библиотеке рисования графов, или перетащив неудачно расположенные вершины мышкой.

Модуль p =     Число переменных n =