Поддержи Openmeetings

четверг, 29 июля 2010 г.

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

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

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

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

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

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

4 комментария :

Evgeniy комментирует...

Если не секрет - для визуализации графов что используется? Opensource или что-то свое?

Мне как раз для своей идеи тоже самое надо!!!
Подскажите плиз.

Мария комментирует...

Ссылка на библиотеку приведена в статье. Вот наша исправленная версия.

Rafael Sepeda комментирует...

Вопрос: а вы не пробовали привязывать к узлам графа ссылки. Хочу сделать на его основе дерево сайта, только вот со ссылками не разобрался: вместо ссылки вставляется код.

Maria Fedotova комментирует...

Пробовали привязывать ссылки, работает

Отправить комментарий