Криптография и свобода

Масленников Михаил

Такие подстановки естественно назвать логарифмическими, а точку х_{, при которой П(х) = logФр – выколотой точкой логарифмической подстановки П.}

Здесь и всюду далее нам будут встречаться два разных типа арифметических операций сложения и вычитания: в кольце Z/N и в поле GF(N+1). Операции в кольце Z/N будем обозначать обычными символами “+” и “-“, а операции в поле GF(N+1) – o и соответственно.

Теорема 1.

Пусть П – логарифмическая подстановка, х₁х₂,

х₁,х₂ ЄZ/N, i – произвольный ненулевой элемент кольца Z/N.

Тогда если ни одна из точек х₁+i,x₁,х₂+i,x₂ не является выколотой, то П(х₁+i)- П(x₁) П(х₂+i)- П(x₂).

Доказательство.

Предположим, что П(х₁+i)- П(x₁)= П(х₂+i)- П(x₂), тогда Ф^{П(х1+i)- П(x1)}=Ф^{П(х2+i)- П(x2)}.

Поскольку все точки не являются выколотыми, то отсюда вытекает, что (Ф^х1+i+roр)(Ф^х2+roр)=(Ф^х2+i+roр)(Ф^х1+roр).

Раскрывая скобки и сокращая одинаковые члены в левой и правой частях равенства, получаем

р (Ф^x1+i+roФ^x2+r)= р(Ф^x2+i+roФ^x1+r)

Поскольку р – ненулевой элемент, то отсюда вытекает, что

Ф^x1+r(Фⁱ 1)= Ф^x2+r(Фⁱ 1)

Поскольку i – произвольный ненулевой элемент Z/N, а Ф – примитивный элемент GF(N+1), то Фⁱ1, откуда вытекает, что х₁=х₂.

Теорема 2. Пусть П – логарифмическая подстановка.

Тогда для любого ненулевого значения iЄZ/N\{0} из условия, что ни одна из точек x, x+i не является выколотой вытекает, что П(х+i)- П(x) i.

Доказательство.

Пусть П(х+i)- П(x) = i. Тогда Ф^{П(х+i)- П(x)}= Фⁱ, откуда Ф^x+r+ioр=Фⁱ(Ф^x+roр), следовательно, р=рФⁱ. Отсюда следует, что i=0.

Раскинулось поле широко! Операции возведения в степень и логарифмирования в конечном поле позволили ловко избавиться от неопределенности в разности значений подстановки и легко, просто элементарно решить задачу построения матрицы P(П) с минимальным числом нулей. Заметим, что если в определении логарифмических подстановок отказаться от условия, что р – произвольный ненулевой элемент поля GF(N+1), то при р=0 мы получаем обычные линейные подстановки, у которых число нулей в P(П) максимально!

Осталось совсем чуть-чуть: разобраться с выколотой точкой.

Для произвольного ненулевого фиксированного iЄZ/N рассмотрим отображение множества Z/N в Z/N вида:

M_i(х) = П(х+i)- П(х),

где П – логарифмическая подстановка. Тогда, в силу теоремы 1, количество различных значений в множестве {M_i(х), xЄZ/N\{x_{,x– i}}равно мощности этого множества, т.е.N-2, причем, в силу теоремы 2, это множество в точности совпадает с {Z/N\{i}}. В частности, при любом iN/2 существует такое значение х, xЄZ/N\{x,x– i},}

что M_i(х)=N/2.

Теорема 3. Пусть П – логарифмическая подстановка.

Тогда если при некотором iN/2 в i-ой строке матрицы P(П) справедливо p_iN/2>1, то эта строка не содержит нулевых элементов.

Доказательство.

В силу теоремы 2 достаточно доказать, что p_ii0. Условие p_iN/2>1означает, что либо M_i(х_{)=N/2, либо Mi(х– i)=N/2. Зафиксируем то, которое равно N/2, а другое оставшееся значение обозначим через M. Суммируя, как и ранее мы уже делали в этой книге, значения Mi(х) по всем xЄZ/N, получаем:}

N/2(N-1) – i + M + N/2 = 0.

Отсюда вытекает, что M=i, следовательно, p_ii0.

По коням! Пора заняться средней строчкой.

Начнем с самого любимого элемента – p_N/2,N/2. Ранее мы уже отмечали, что этот элемент должен быть всегда четным (рассуждения для случая N=2ⁿ легко обобщаются для произвольного четного N). Следовательно, в логарифмической подстановке возможны только два значения p_N/2,N/2: 0 или 2. Допустим, что p_N/2,N/2=2. В силу теоремы 2 эти значения может давать только выколотая точка x₀ и x_{+N/2, т.е.}

П(х_{+N/2)- П(х)= П(х+N/2+N/2)- П(х+N/2)= П(х)- П(х+N/2)=N/2.}

Отсюда вытекает, что 2П(х_{+N/2)=2П(х).}

Рассмотрим два случая.

1. р=1, следовательно, П(х_{)=0. Тогда П(х+N/2)=N/2. Имеем:}

Ф^П(х0+N/2)= Ф^N/2 Ф^x0+N/2+roр=Ф^N/2 Ф^N/2(1 Ф^x0+r)= р Ф^N/2(1oр)= р 2Ф^N/2 = 1.

Возводя обе части последнего равенства в квадрат и учитывая, что Ф^N=1, получаем такое равенство возможно только в тривиальном поле из 3 элементов.

2. р1, следовательно, П(х_{) =N/2, П(х+N/2)=0, откуда}

Ф^П(х0+N/2)= 1 Ф^x0+N/2+roр=1 р(1 Ф^N/2)= 1 Ф^N/2= 1 р^{– 1}.

Возводя это равенство в квадрат, получаем значение р:

р=2^{– 1}

С учетом условия П(х_{) =N/2 получаем: logФ2^{– 1} = N/2, откуда 2^{– 1} =Ф^N/22^{– 2} =1. Такое также возможно только в тривиальном поле из 3 элементов.}

Следовательно, во всех реальных практически значимых случаях p_N/2,N/2=0. Тогда найдется по крайней мере одна строка i, в которой p_N/2,i2, и по теореме 3 в ней не будет нулей. Общее число нулей в такой матрице, с учетом уже упоминавшейся ее симметричности, будет равно N-3. Это минимально возможное количество нулей и оно оказалось достижимым!