Построение одного класса функций над конечными полями с использованием линейных рекуррент над кольцами Галуа | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/10

Построение одного класса функций над конечными полями с использованием линейных рекуррент над кольцами Галуа

Изучается класс функций над полем GF(q), построенных на основе линейных рекуррентных последовательностей (ЛРП) над кольцом GR(qn,pn) c отмеченным характеристическим многочленом. Порядок следования аргументов функций задаётся набором ЛРП над полем, а значения функций - усложнением ЛРП над кольцом. При выполнении некоторых условий, для близости исследуемых функций от m переменных к классу аффинных функций доказана оценка C(f) ^ ^ q(m+n-i)/2(pn-i - l)(q - l)i/2. Рассматриваются вопросы, связанные с мощностью класса функций и его автоматной реализацией.

Construction of a class of functions on finite fields using linear recurrences over galois rings.pdf Введение В [1,2] изучались свойства булевых функций, построенных на основе старших разрядных последовательностей отмеченных линейных рекуррент над кольцом R = Z2n. Получены оценки весов функций, вычислена их алгебраическая степень и доказана нижняя оценка нелинейности. В частности, показано, что этот класс функций достаточно удалён от класса аффинных булевых функций. Данная работа посвящена исследованию более широкого класса функций. Кроме того, класс функций рассматривается не только над полем из двух элементов, но и над произвольным конечным полем. Для этого приходится переходить от кольца вычетов по модулю 2n к произвольному кольцу Галуа. Достоинством рассматриваемого класса является возможность его построения с использованием линейного регистра сдвига над кольцом Галуа. 1. Определение класса функций Пусть p - простое число, q = p*, t Е N, P = GF(q) - конечное поле из q элементов, R = GR(qn,pn) - кольцо Галуа из qn элементов характеристики pn. Для кольца R фактор-кольцо R = R/pR является полем из q элементов. Далее для удобства изложения будем считать, что R = P, а операцию сложения в R и R будем обозначать одним символом +. Образ элемента а Е R при действии естественного эпиморфизма колец R ^ R обозначим через а. Естественный эпиморфизм колец R ^ R индуцирует эпиморфизм колец многочленов R[x] ^ R[x]. Образ многочлена A(x) = £ а^хг Е R[x] при этом эпиморфизме будем обозначать через A(x), где A(x) = £а^хг Е R[x]. Многочлен G(x) Е R[x] назовем унитарным, если его старший коэффициент равен единице, и реверсивным, если его свободный член обратим в R. Реверсивный многочлен G(x) G R[x] называется отмеченным, если периоды многочленов G(x) и G(x) равны. Известно, что для каждого реверсивного многочлена F(x) G P[x], не имеющего кратных корней в своем поле разложения, найдётся единственный отмеченный многочлен G G R[x], такой, что G(x) = F(x) [3, §4]. Способ построения отмеченного многочлена G(x), соответствующего многочлену F(x), основанный на применении алгоритма Гензеля, весьма сложен, но в случае p =2 существует достаточно простой рекурсивный способ его построения по F(x) [3]. Всюду далее F(x) G P[x], G(x) G R[x] - реверсивные многочлены, такие, что F неприводим над P, m = deg F = deg G, G(x) = F(x), T = T(G) = T(F) = qm - 1. Обозначим через Lr(G) множество всех ЛРП над кольцом R c характеристическим многочленом G(x) и через Lr(G)* -множество всех ЛРП v G Lr(G), для которых верно неравенство v = (0), где (0) -нулевая последовательность; v - последовательность, полученная из v действием естественного эпиморфизма R ^ R на каждый её элемент. Последовательность vv является ЛРП с характеристическим многочленом F(x) [3]. Пусть ф : R ^ P - произвольное отображение, v G LR(G)*, последовательности ui,... , um G Lp(F) максимального периода и линейно независимы над P, то есть равенство м1а1 + ... + umam = (0) выполняется только для нулевого вектора (а1,..., am). Определим последовательность u над Pm как u(i) = (u1(i),..., um(i)), i G No. Лемма 1. Последовательности u1,...,um линейно независимы над P тогда и только тогда, когда на цикле последовательности u появляются по одному разу все ненулевые векторы Pm. Рассмотрим функцию f = fu,v^ от m переменных, определённую по правилу: f (0, 0,..., 0)) = ф(0) и для всех i = 0,1,...,T - 1 f (u(i))= ф(v(i)). (1) Из леммы 1 следует, что правило (1) корректно задаёт функцию f. Таблицу функции можно построить с использованием регистров сдвига над кольцом R и m регистров сдвига над полем P. В наиболее интересном с практической точки зрения случае можно выбрать u1 = v, u2 = xv, ... , um = xm-1v, и тогда функция строится с использованием одного линейного регистра сдвига над кольцом R. Введём следующие обозначения для классов функций: D(F, u, ф) = U fu,v,^, D(F, ф) = U D(F, u, ф), vu где объединения берутся по всем возможным v и u, которые указаны в определении функции fu 2. Близость между дискретными функциями Пусть f, g : Pm ^ P - некоторые отображения. Для любого a G P через х« будем обозначать аддитивный характер поля P: trp (ax) / \ 2ni-P°--_ D Х« (x) = e p , x G P. Определим коэффициент кросс-корреляции между функциями f и g равенством C„(f,g)= E Xa(f (x) - g(x)), a G P\{0}. xep n Обозначим C(f,g)= max |Ca(/,g)|. «eP\{0} Пусть (a, x) -скалярное произведение векторов, g пробегает множество аффинных функций от n переменных над полем P, то есть g(x) = g(xi,..., xm) = (a, x) + b = aixi + a2X2 + ... + amxm + b, где a1,... , am, b - элементы из P. Далее будем использовать величину C(/) = max C(/, g) = max max |C«(/, g) | , 9 9 aeP\{0} которая характеризует «близость» / к классу всех аффинных функций от m переменных над полем P. 3. Свойства класса функций 3.1. Близость между функциями Приведём некоторые обозначения и результаты из теории колец Галуа [4, §2,3]. Введём p-адическое множество r(R) = {а Е R : = а}. Каждый элемент x кольца R может быть единственным образом представлен в виде p-адического разложения x = Yo (x) + PYi(x) + ... + pn-1Yn-i(x), где Yj : R ^ r(R), j Е {0,... , n - 1} - разрядные функции кольца R. Назовём отображение ф : R ^ P сбалансированным [5], если при каждом a Е P уравнение ^(x) = a имеет ровно |R|/|P| = qn-i решений относительно неизвестного x Е R. Теорема 1. Пусть фьф2 : R ^ P - сбалансированные функции, последовательность v линейно не выражается через xkv в кольце R. Тогда C(/u,v,^i ,/u,xk) ^ qm/2+n(pn i - 1). Будем говорить, что отображение ф биективно по старшему разряду, если его ограничение на любом подмножестве элементов кольца R с одинаковыми значениями n - 1 младших разрядов является биекцией. Частным случаем отображения, биективного по старшему разряду, является отображение, линейное по старшему разряду, то есть такое, что для каждого a Е R с p-адическим представлением a = a0 + pai + p2a2 + ... + pn-ian-i, a0, ai,..., an-i Е r(R), выполнено равенство ф^) = а an-i + n(a0, ai,..., an-2), (2) где а Е P\{0}; n : r(R)n-i ^ P - произвольное отображение. Отметим, что биективные по старшему разряду отображения являются сбалансированными. Следствие 1. Если функции фьф2 биективны по старшему разряду, то в условиях теоремы 1 верна оценка C(/u,^i,/u,x4^2) ^ qm/2+n(pn-i - i)(q - 1). Теорема 2. Пусть degF = m, f G D(F, ф). Если n = 1 и ф : R ^ P - произвольная функция, то верно равенство C(f) = qm и f - аффинная функция над полем P. Если n > 1 и функция ф биективна по старшему разряду, то для близости функции f к классу аффинных функций от m переменных верно неравенство C(f) ^ q(m+n-1)/2(pn-1 - 1)(? - i)1/2. Следствие 2. Пусть deg F = m, n > 1 и функция ф биективна по старшему разряду. Тогда при m ^ (2n - 2)/t + n в классе D(F, ф) нет аффинных функций, в частности не существует начального заполнения рекурренты v, такого, что (v(0),... , v(m - 1)) = (0,... , 0) и ф^) = (0). 3.2. Мощность класса и вес функций Утверждение 1. Пусть ф - сбалансированное отображение, deg F = m, тогда верна следующая оценка, достижимая сверху и снизу: qmn - q(n-1)m ^ |D(F,u,ф)| ^ qm - 1. Рассмотрим случай, когда n = 1, то есть R = GR(q,p) = GF(q) = P. Следствие 3. Если deg F = m, n = 1 и функция ф сбалансированная, то D(F, u, ф) = {(a, x) + ф(0) : a G Pm\(0,..., 0)}. Теорема 3. Пусть отображение ф биективно по старшему разряду, тогда при m ^ ^ 2(n - 1)/t+2n разным начальным заполнениям рекурренты v соответствуют разные функции класса D(F, u, ф) и имеют место равенства |D(F, u, ф)| = |Lr (G)*| = qnm - q(n-1)m. Прообраз элемента z при отображении f будем обозначать как f-1(z). Утверждение 2. Пусть ф - сбалансированное отображение, deg F = m, f G G D(F, ф), тогда для любого z G P верно ||f-1(z)| - qm-1| ^ qm/2+n-1(pn-1 - 1)(q - 1). 3.3. Случай произвольного разрядного множества Разрядным множеством кольца R называется любое его подмножество K = {ко, &1, . . . , kq-1}, такое, что все его элементы попарно несравнимы по идеалу pR [6, 7]. Например, множество r(R) является разрядным множеством кольца R [4, лемма 3]. Если K - разрядное множество кольца R, то каждый элемент a G R однозначно представим в виде a = ао + pa1 + ... + pn-1an-1, (3) где a^ G K, i G {0,... ,n - 1}. Равенство (3) называется разрядным представлением элемента a в множестве K; элемент a^ - i-м разрядом элемента a в множестве K, an-1 - старшим разрядом. Для каждого i G {0,... , n - 1} зададим разрядное отображение (a) = a^. Всюду далее K - произвольное разрядное множество кольца R. Обобщим понятие биективной по старшему разряду функции. Будем говорить, что отображение ф биективно по старшему разряду относительно разрядного множества K, если ограничение отображения ф на любом подмножестве элементов кольца R с одинаковыми значениями n - 1 младших разрядов в множестве K является биекцией. Утверждение 3. Если функция ф биективна по старшему разряду относительно некоторого разрядного множества K, то она биективна по старшему разряду относительно любого разрядного множества кольца R, в том числе относительно r(R). Следствие 4. Если функция ф биективна по старшему разряду относительно произвольного разрядного множества K, то верны следствие 1, теорема 2, следствие 2, теорема 3. Рассмотрим разрядные множества кольца R = Zpn. Будем говорить, что K образует арифметическую прогрессию, если K = (a, a + d,a + 2d,... ,a + (p - 1)d} для некоторых элементов a,d G R, a = 0 (mod p), (d,p) = 1. В этом случае будем использовать обозначение K = Ka,d. Важным примером разрядного множества, образующего арифметическую прогрессию, являетсяp-ичное разрядное множество K0,i = (0,1,... ,p- 1}. Рассмотрим случаи, когда R - Zpn и в равенстве (2) функция п тождественно равна 0. Следствие 5. Пусть deg F =

Ключевые слова

estimation of trigonometric sum, cross-correlation function, Galois ring, finite fields, complication of sequences, linear recurring sequences, оценка тригонометрической суммы, кросс-корреляционная функция, кольцо Галуа, конечные поля, усложнение последовательности, линейные рекуррентные последовательности

Авторы

ФИООрганизацияДополнительноE-mail
Бугров Алексей ДмитриевичМоскваBugrovalexey1@yandex.ru
Всего: 1

Ссылки

Кузьмин А. С., Нечаев А. А. Линейные рекуррентные последовательности над кольцами Галуа // Алгебра и логика. 1995. Т.34. №2. С. 169-189.
Камловский О. В. Частотные характеристики разрядных последовательностей линейных рекуррент над кольцами Галуа // Изв. РАН. Сер. матем. 2013. Т. 77. №6. С. 71-96.
Нечаев А. А. Код Кердока в циклической форме // Дискретная математика. 1989. Т. 1. №4. С. 123-139.
Погорелов Б. А, Сачков В. Н. Словарь криптографических терминов. М.: МЦНМО, 2006.
Нечаев А. А. Цикловые типы линейных подстановок над конечными коммутативными кольцами // Матем. сборник. 1993. Т. 184. №3. С. 21-56.
Былков Д. Н., Камловский О. В. Параметры булевых функций, построенных с использованием старших координатных последовательностей линейных рекуррент // Математические вопросы криптографии. 2012. Т. 3. №4. С. 25-53.
Былков Д. Н. Об одном классе булевых функций, построенных с использованием старших разрядных последовательностей линейных рекуррент // Прикладная дискретная математика. Приложение. 2014. № 7. С. 59-60.
 Построение одного класса функций над конечными полями с использованием линейных рекуррент над кольцами Галуа | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/10

Построение одного класса функций над конечными полями с использованием линейных рекуррент над кольцами Галуа | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/10