Дискретная математика и криптология




СТРУКТУРА И ПЕРИОДЫ ПРЕОБРАЗОВАНИЙ - часть 14


 eх=jт(х)+jт+1(х)+…+jт+t-1(х),                                         (6.5)

есть неподвижный элемент преобразования j.

Доказательство. Так как преобразование j линейно, то

j(eх)=jт+1(х)+jт+2(х)+…+jт+t-1(х)+jт+t(х).

По утверждению 6.3 вершины ji(х) графа G(j) при i³т являются циклическими и лежат на цикле длины t, поэтому jт+t(х)=jт(х). Следовательно, j(eх)=eх.                      ¨                                   

Таким образом, каждому элементу хÎP(n)

соответствует неподвижный элемент линейного преобразования j, определяемый выражением (6.5), обозначим его eх,j.

Аффинные преобразования y1 и y2 пространства P(n) назовём а-параллельными, где а - ненулевой вектор пространства P(n), если y1(х)-y2(х)=а для всех хÎP(n). Заметим,  что а-параллельные преобразования y1 и y2 либо оба биективны, либо оба небиективны.

Теорема 6.9. Пусть j - биективное линейное преобразование пространства P(n) над полем Р характеристики p, и y есть а-параллельное ему аффинное преобразование. Тогда j и y оба либо являются, либо не являются преобразованиями максимального периода.

Доказательство. По условиям теоремы y(х)=j(х)+а для всех хÎP(n), где а¹и, и - нулевой вектор пространства P(n). Отсюда с использованием индукции по i несложно вывести равенство, верное для любого хÎP(n) и любого натурального i:

yi(х) = ji(х)+ji-1(а)+ji-2(а)+…+j(а)+а.                               (6.6)

По утверждению 6.3, последовательность {ji(а)}, i=1,2,…, является периодической с периодом tа,j, равным длине цикла, которому принадлежит вектор а. Тогда по утверждению 6.8 неподвижным элементом преобразования j является элемент eа,j=jl-1(а)+…+j(а)+а при l=tа,j.

По теореме 6.1 последовательность {ji(а)+…+j(а)+а}, i=0,1,2,…, является периодической с периодом t, где

t/d(eа,j)×tа,j                                                       (6.7)




Содержание  Назад  Вперед