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



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


T ³ НОК(T1,…,Tn)/НОД(T1,…,Tn).

 

Доказательство. Делимость НОК(T1,…,Tn) на T следует из утверждений 6.1 и 6.2. Без ущерба для общности докажем нижнюю оценку для п=2.

Пусть T1=t, T2=t, НОД(t,t)=d. Тогда t=p×d, t=q×d, НОК(t,t)=p×q×d, где (p,q)=1.

Предположим, что j(xi,1,xi,2)=j(xi+T,1,xi+T,2) для всех i, где T<p×q. Так как T/p×q×d, то при сделанном предположении T=p×x×d, где p/p, x/q, d/d, причём, равенства p=p и x=q не выполнены одновременно, иначе было бы T³p×q.

Пусть для определённости p<p. Тогда в последовательности Y® имеют место повторы через каждые q членов, где q=p×q×d (так как T/q). Следовательно, для всех натуральных i

j(xi,1,xi,2)=j(xi+q,1,xi+q,2).

 Так как t/q, то для всех i верно

xi+q,2=xi,2, и последнее равенство принимает вид:

 

j(xi,1,xi,2)=j(xi+q,1,xi,2).                                                 (6.1)

По условию (p,q)=1, значит и (p,q)=1. Поэтому t не делит q, то есть, xi,1¹xi+q,1 для некоторых i. Последнее неравенство несовместимо с (6.1) при биективности отображения j по первой переменной. Следовательно, T³p×q.                                        ¨

6.2. Граф отображения

Пусть имеется отображение j:X®Y, где X и Y - конечные множества мощности n и m соответственно, n,m>1. Отображению j поставим в соответствие  ориентированный двудольный граф G(j)=(XÈY,U), где XÈY - множество

вершин, U - множество дуг, и пара (x,y)ÎU Û xÎX, y=j(x)ÎY. Граф G(j) называют графом отображения j.

Из однозначности отображения j следует, то полустепень исхода любой вершины xÎX

равна 1 и êUê=êXê=n.

Полустепень захода py вершины y

графа G(j) равна числу прообразов элемента y относительно отображения j, 0£py£п. При этом

=п.




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