Восстановление пути в дереве Барнинга–Холла

В 1963 г. Ф. Дж. М. Барнинг и в 1970 г. А. Холл описали систематическую процедуру порождения всех примитивных пифагоровых троек с помощью умножения минимальной пифагоровой тройки $[3,4,5]$, рассматриваемой как вектор, на последовательность матриц, выбираемых из фиксированного трехэлементного множества унимодулярных матриц. Тем самым на множестве примитивных пифагоровых троек задается структура бесконечного тернарного корневого помеченного дерева. В данной работе представлен алгоритм, который по заданной примитивной пифагоровой тройке (ППТ) строит путь в этом дереве, ведущий от корня к этой тройке. Так как тройка может лежать очень глубоко, эффективность алгоритма имеет первостепенное значение. Представленный алгоритм имеет полиномиальную временную сложность относительно длины входа, которая соответствует логарифму некоторой величины, характеризующей размер ППТ.