досліджується операція зсув-композиції дискретних функцій, що виникає при гомоморфізми кінцевих регістрів зсуву. Для довільної функції над кінцевим полем описані всі можливі уявлення у вигляді зсув-композиції двох функцій, права з яких лінійна. Крім того, вивчена можливість подання довільної функції над кінцевим полем зсув-композицією трьох функцій, в якій обидві крайні функції лінійні. Доведено, що в разі простого поля для лінійних функцій, а також для квадратичних функцій, лінійних по крайней змінної, поняття приводимість і лінійної приводимість збігаються.

Анотація наукової статті з математики, автор наукової роботи - Чередник Ігор Володимирович


Linear decomposition of discrete functions in terms of shift-composition operation

We investigate the shift-composition operation of discrete functions that arises under shift register'S homomor-phisms. For an arbitrary function over a finite field, all right linear decompositions are described in terms of shift-composition. Moreover, we study the possibility for representing an arbitrary function by a shift-composition of three functions such that both external functions are linear. It is proved that in the case of a simple field, the concepts of reducibility and linear reducibility coincide for linear functions and quadratic functions that are linear in the external variable.


Область наук:

  • Математика

  • Рік видавництва: 2019


    Журнал: Прикладна дискретна математика. додаток


    Наукова стаття на тему 'ЛІНІЙНЕ РОЗКЛАДАННЯ ДИСКРЕТНИХ ФУНКЦІЙ У термінах операцій ЗСУВ-КОМПОЗИЦИИ'

    Текст наукової роботи на тему «ЛІНІЙНЕ РОЗКЛАДАННЯ ДИСКРЕТНИХ ФУНКЦІЙ У термінах операцій ЗСУВ-КОМПОЗИЦІЇ»

    ?3. Carlet C. Vectorial Boolean Functions for Cryptography. Cambridge: Cambridge University Press, 2010. 93 p.

    4. Панкратова І. А. Властивості компонент деяких класів векторних булевих функцій // Прикладна дискретна математика. 2019. №44. С. 5-11.

    УДК 519.713.2 + 519.714.5 DOI 10.17223 / 2226308X / 12/21

    ЛІНІЙНЕ РОЗКЛАДАННЯ ДИСКРЕТНИХ ФУНКЦІЙ У термінах операцій ЗСУВ-КОМПОЗИЦІЇ

    І. В. Чередник

    Досліджується операція зрушення-композиції дискретних функцій, що виникає при гомоморфізми кінцевих регістрів зсуву. Для довільної функції над кінцевим полем описані всі можливі уявлення у вигляді зрушення-композиції двох функцій, права з яких лінійна. Крім того, вивчена можливість подання довільної функції над кінцевим полем зрушення-композицією трьох функцій, в якій обидві крайні функції лінійні. Доведено, що в разі простого поля для лінійних функцій, а також для квадратичних функцій, лінійних по крайней змінної, поняття приводимість і лінійної приводимість збігаються.

    Ключові слова: дискретні функції, кінцеві поля, регістр зсуву, зсув-композиція.

    Вступ

    Нехай Qq - кінцеве безліч з q елементів. У даній роботі будемо використовувати безліч змінних | x0, x ^ x2, ...}, а множина всіх функцій q-значної логіки від змінних x0, x ^ x2, ... будемо позначати через Fq. Довільну функцію f Е Fq завжди можна розглядати як функцію від відповідного допустимого набору змінних x0, x1, ..., xn. У роботах вітчизняних криптографов К. Г. Таболово, В. А. Башево, А. Я. Прососова, В. І. Солодовникова і ін. Була введена і досліджена (переважно в термінах гомоморфізмів регістрів зсуву) операція зрушення-композиції на безлічі всіх функцій Fq:

    f (xo,..., xn) <1 g (xo,..., Xm) = f (g (xo,..., Xm),..., G (xn,..., Xn + m)).

    У роботах перерахованих авторів в різному ступені спільності і спрямованості досить детально досліджена зв'язок між поданням функції f у вигляді зрушення-композиції f = g <h і існуванням гомоморфизма регістразсуву, відповідного функції f, на менший регістр зсуву, відповідний функції g (всі основні результати по даній тематиці єдиним чином викладені в [1]). Так, наприклад, в [2] описані всі можливі уявлення функції f над кінцевим полем Fq у вигляді f = l < g, де l - лінійна, що дозволило вказати всі можливі гомоморфізми регістразсуву зі зворотним зв'язком f на лінійні регістри зсуву.

    У даній роботі пропонується опис всіх можливих уявлень довільної функції f над кінцевим полем Fq у вигляді f = g < l, де l - лінійна. Крім того, вивчена можливість подання довільної функції f над кінцевим полем Fq у вигляді f = l1 <g <l2, де l1, l2 - лінійні. Доведено, що в разі простого поля для лінійних функцій, а також для квадратичних функцій, лінійних по крайней змінної, поняття приводимість і лінійної приводимість збігаються.

    1. Основні визначення та позначення

    У даній роботі, якщо не визначено інше, вважається, що д = р4, де р - просте,? Е М, а на безлічі задана структура поля, +, •). Відомо [3], що кожна функція f Е ^ представляється єдиним наведеними многочленом з [хо, х ^ ...], який для зручності будемо ототожнювати з функцією f. Для повноти і простоти викладу приклади в даній роботі розглядаються переважно в булевом випадку, при цьому операція додавання в поле виділяється символом «ф».

    Безліч всіх д-значних функцій, які биективное по першій (останньої) змінної, будемо позначати через * Гд безліч всіх д-значних функцій,

    які лінійні по першій (останньої) змінної, будемо позначати через (^ +); множину всіх функцій, що зберігають константу 0, будемо позначати%. При цьому природні похідні позначення

    = ^ П = п = * ^ п%, ...

    Як неважко переконатися, кожне з множин С С утворює напівгрупу щодо операції <1 з нейтральним елементом хо. При цьому нескладний приклад

    (Хо Ф Х1) < (Хо Ф Х1) = (хо ф Х1) < (Хо Ф Х1 ф 1)

    показує, що навіть в рамках моноїд <) Не завжди можливо виробляти

    праве скорочення в равенствах. Однак можливість правого і лівого скорочень все ж таки присутня в досить широких класах практично значущих функцій.

    Твердження 1. Безліч, *% * і, утворюють моноїд

    з можливістю лівого і правого скорочень.

    Будемо говорити, що функція д ділить справа функцію f, якщо існує така функція Н, для якої виконується рівність f = Н < д. Для кожної перестановки п елементів безлічі довільна функція f завжди ділиться справа на п (хо), п (/)-такі подільники функції f будемо називати невласними. Аналогічним чином визначаються відповідні поняття лівої подільності. Якщо у функції f існує власний правий, а отже, і власний лівий подільники, то будемо говорити, що функція f які приводилися.

    Зауваження 1. Нехай f е ^ і f (0, ..., 0) = Cf. Існує тісний зв'язок між що приводиться f в моноїд ( <) І наведені f = f - Cf в подмоноіде (%, <):

    f = д < Н ^^ / = (хо - Cf) < д < (Хо + сн) < Н, де (хо - Cf) < д < (Хо + СД Н Е%.

    Таким чином, дослідження приводимість в моноїд ( <) Багато в чому зводиться до дослідження приводимість в подмоноіде (%, <).

    2. Лінійне розкладання

    Безліч Ьд всіх функцій, які представлені лінійними, але не аффіннимі многочленами над

    згор xio + СГХ ХГХ + ... + сАкxifc:? про < ?1 < . . . < ?до, до е ^, cil,. . . , ^ До е ,

    утворює коммутативное кільце (Ьд, +, <), А відображення

    ^ 0х + cilх + ... + ^ кх '^ Ciо Хiо + Cil + ... + Cik х ^ до

    є изоморфизмом кілець [ж], +, •) і, +, <) [1, 2, 4]. Маючи на увазі цей ізоморфізм, далі будемо формулювати відомі поняття і використовувати відомі твердження про подільності многочленів стосовно лінійним функцій.

    Зі зрозумілих причин клас є важливим з практичної точки зору подмоноідом в (-, <) І виділення у довільній функції лівих або правих лінійних подільників видається природною і актуальним завданням. Функцію f Е - будемо називати лінійно приводиться справа, якщо у неї існує власний правий дільник 1 Є.В. іншому випадку функцію f будемо називати лінійно приводиться справа. Аналогічним чином визначається ліва лінійна приводимість функцій. Функцію називатимемо лінійно приводиться, якщо вона лінійно непри-водимо і праворуч, і ліворуч.

    В. І. Солодовников в [2] описав всі можливі ліві лінійні розкладання для довільної функції з .

    Теорема 1 [2]. Довільна функція f Е - однозначно представляється у вигляді

    J - V * / • < ха1

    J -? ^ 121, ... А; «°,« 1, ..., «до ^ хо хг1 • • • ХГК ,

    де 1Г1, ..., гк; а °, а1, ..., ак Е Ьд для всіх 1 ^? 1 < . . . < ?й, 0 < йо, «1, • • •,« й < ?.

    При цьому всі ліві лінійні подільники функції J вичерпуються делителями 1 - НОД (1Г1) ..., гк; а °, а1, ..., «до: 1 ^? 1 < • • • < ?й, 0 < йо, «1, • • •,« й < д). Зокрема, функція J лінійно непріводімим зліва в тому і тільки в тому випадку, коли 1 - ж0.

    Лінійну функцію виду ж0 + а1х ^ 1 + • • • + називатимемо унітарної по

    змінної ж0.

    Слідство 1 [2]. Довільна функція f Е - однозначно представляється у вигляді J - Ж5 < 1 <1 д, де Ж5 - крайня ліва змінна, від якої J залежить істотно; 1 Е - унітарна по змінної ж0; д - лінійно непріводімим зліва.

    Для опису правих подільників будуть потрібні додаткові позначення. Відомо [5, 6], що в разі д - р4, де р - просте, Ь > 1, ступінь нелінійності наведеного одночлена ж "Е Fq [ж], а < д, краще оцінювати не самим числом а, а його р-ічним вагою

    || а || р - а0 + • • • + а4_1, що визначаються з р-ічного уявлення

    а - а 0 + • • • + а4-1р4-1, 0 ^ а0, • • •, а4-1 < р ^

    У зв'язку з цим одночлен ж "часто розписують у вигляді ж" ° • • • ЖР 0,4-1, а довільний

    ^ 0 • • •

    наведений моном ха - ж "° • • • ж ^", де 0 ^ а0, • • •, ап < д і а ^ - а ^ 0 + • • • + а ^ 4-1р4 1,

    г Е {0, • • •, п}, - у вигляді

    хар - ха °° 1 1 х "п ° 1" п4-1

    х х0 • • • х0 • • • хга • • • хга ,

    маючи на увазі при цьому ар - (А00, • • •, а04-1, • • •, ап0, • • •, ап4-1).

    Ставлення градуированного лексикографічного порядку на індукує

    відношення порядку на безлічі наведених Мономах з Fq [ж0, • • •, жп]

    Хар ^ хЬР ^ ар ^ §Г1ех Ьр,

    при якому Мономах спочатку впорядковуються за ступенем нелінеіності, а Мономах одного ступеня нелінійності упорядковуються «лексикографічно» за умови

    р4-1 р4-1

    Хо > . . . > Хо > . . . > хП > . . . > хП •

    При простому д введене відношення порядку збігається зі стандартним градуйованим лексикографічним порядком на множині всіх наведених Мономах з

    ?д [Хо ,. . . , ХП].

    нехай

    хар _ Х «00 Хр 1а04-1« кю Хр АКГ-1 «кг 0 < < р

    л хг0 • • • хг0 • • • Лугк • • • ХГК ХГК > і ^ ікт ^

    тоді Мономах

    Х «00 ХР4 1а04-1 _РГ АКГ-1 ХРГ (« кг-1) ХРГ > 1

    Хг0. . . Хг0. . . »К. . . Х »до ХГК + 3, ^ ^ 1

    і тільки їх будемо називати лінійно пов'язаними з Мономах Хар.

    Теорема 2. Довільна функція f Е ^ однозначно представляється у вигляді

    т

    р

    f = С Сг Ха < /? (Хо, ...),

    ?= 0

    де з Е; хар > ... > хат -убивающая послідовність лінійно незв'язаних Мономах, і для кожного г Е {0, ..., т} коефіцієнт сг Е відмінний від 0, а / г (х0, ...) - лінійна функція, унітарна по змінної х0.

    При цьому якщо f істотно залежить від змінної х0, то всі праві лінійні подільники функції f вичерпуються делителями НСД (/ 0, ..., / т). Зокрема, функція f лінійно непріводімим справа в тому і тільки в тому випадку, коли НСД (/0,...,/т)= Х0.

    Слідство 2. Довільна функція f Е ^ однозначно представляється у вигляді f = х3 < д <1 /, де х3 - крайня ліва змінна, від якої f залежить істотно; д - лінійно непріводімим справа; / Е Ьч - унітарна по змінної х0.

    Зауваження 2. Подання, доведене в теоремі 2, істотно

    р4-1 4 - 1

    залежить від умов Х0 > . . . > Х0 > ...... > Х п > ... > ХП. Так, для функції

    f - ХД ~ Н ХдХ2 + Н Х0Х1 ~ Н Х0Х2

    над полем за умови х0 > х0 > Х1 > х1 > х2 > х2 справедливо розкладання

    f - Х0Х2 < (Х0 + Х1 + Х2) + Х1Х2 < (Х0 + Х1) + х0х1 < Х0,

    222 а за умови Х02 > Х0 > Х21 > Х1 > Х22 > Х2 - розкладання

    f - Х ^ 0 < (Х0 + Х2) + Х0Х2 < Х0 + х2х2 < Х0.

    3. Особливості двостороннього лінійного розкладу

    Теорема 3. Нехай д просте і функція f Е ділиться зліва на / 1 Е Ьд, а справа на / 2 Е Ьд. Тоді якщо / 1 та / 2 взаємно прості, то справедливо розкладання

    f = / 1 < д < / 2.

    Якщо, додатково, / 1 та / 2 - максимальні лівий і правий подільники функції f, то д - лінійно непріводімим.

    Зауваження 3. Умова простоти д є істотним в теоремі 3. Так, наприклад, якщо д = р4,? ^ 2 і а Е Fq \ Ер, то ар = а і, очевидно, лінійні функції х0 + АХ1, х0 + арх1 взаємно прості. Однак при цьому справедливі розкладання

    (Х0 + Архр) < х0 = хР + арх1 = х0 < (Х0 + АХ1) і легко переконатися в неможливості подання

    хр + арх1 = (х0 + Архр) < д <1 (х0 + АХ1).

    Зауваження 4. Умова взаємної простоти лівого і правого лінійних дільників є істотним в теоремі 3. Так, наприклад, для булевої функції

    f = (Х0 Ф Х1) < Х0Х1 < (Х0 Ф Х1) ф (Х0 Ф Х1) справедливі розкладання

    f = (Х0 Ф Х1) < (Х0Х1 ф Х0Х2 Ф Х1Х2 Ф Х0 Ф Х1) = (Х0 Ф Х1) < д1, f = (Х0Х1 Ф Х1Х2 Ф Х0) < (Х0 Ф Х1) = Д2 < (Х0 Ф Х1),

    але при цьому д1 - лінійно непріводімим справа, Д2 - лінійно непріводімим зліва, а тому неможливо уявлення

    f = (Х0 Ф Х1) < д < (Х0 Ф Х1).

    4. Квадратичні функції над простим полем

    З огляду на ізоморфізму кілець (Ьд, +, <) І, +, •) опис всіх лінійних подільників довільної функції f Е Ьд рівносильно визначенню канонічного розкладання відповідного многочлена.

    Для опису лінійних подільників довільної квадратичної функції можна використовувати результати теорем 2 і 3 і, як показує наступний результат, в разі лінійних по крайней змінної квадратичних функцій над простим полем це дозволяє описати взагалі всі можливі подільники.

    Теорема 4. Якщо д - просте число, то для композиції f <д довільних функцій f Е і д Е + та справедливі наступні твердження:

    1) deg (f < д) = 0 тоді і тільки тоді, коли deg f = 0;

    2) deg (f < д) = 1 тоді і тільки тоді, коли deg f = deg д = 1;

    3) deg (f < д) = 2 тоді і тільки тоді, коли або deg f = 1 і deg д = 2, або deg f = 2 і deg д = 1.

    Зауваження 5. Пункт 2 теореми 4 в окремому випадку д = 2 був доведений В. І. Соло-довніковим в 1978 р [1].

    Зауваження 6. Простий приклад

    (Х1Х4 Ф Х2Х3Х4) < (Х0 Ф Х1Х2 Ф Х2) = Х1Х4 Ф Х1Х5Х6 Ф Х1Х6 Ф Х3Х4 Ф Х3Х5Х6 Ф Х3Х6

    показує, що вже в разі кубічних функцій поняття приводимість стає ширше поняття лінійної приводимість.

    ЛІТЕРАТУРА

    1. Солодовников В. І. Регістри зсуву і криптоалгоритми на їх основі. LAP LAMBERT Academic Publishing 2017.

    2. Солодовников В. І. гомоморфізми регістрів зсуву в лінійні автомати // Дискретна математика. 2008. №4. C. 87-101.

    3. ЛідлР, Нідеррайтер Г. Кінцеві поля. М .: Мир, 1988.

    4. Солодовников В. І. гомоморфізми довічних регістрів зсуву // Дискретна математика. 2005. №1. C. 73-88.

    5. Кузьмін А. С., Нечаєв А. А., Шишкін В. А. Бент- і гіпербент-функції над кінцевим полем // Праці з дискретної математики. 2007. №10. C. 97-122.

    6. Черьомушкін А. В. Адитивний підхід до визначення ступеня нелінійності дискретної функції // Прикладна дискретна математика. 2010. №2. C. 22-33.

    519.7 DOI 10.17223 / 2226308X / 12/22

    Про взаємозв'язку між кватернарні І Булевой

    БЕНТ-ФУНКЦІЯМІ1

    А. С. Шапоренко

    Досліджуються кватернарні бент-функції виду f: ZJ ^ Z4. Показано уявлення коефіцієнтів Уолша - Адамара кватернарні функції через коефіцієнти двох булевих функцій. Отримано, що будь-яка кватернарні бент-функція є регулярною. Вивчається зв'язок кватернарні бент-функцій від однієї і двох змінних з булевими бент-функціями від двох і чотирьох змінних відповідно.

    Ключові слова: кватернарні функції, булеві функції, регулярні бент-функції.

    Нехай (ж, у) -скалярное твір векторів, де підсумовування проводиться по модулю 2, а ж.у - скалярний добуток векторів з підсумовуванням за модулем 4.

    Перетворенням Уолша - Адамара булевої функції f від n змінних називається целочисленная функція W / (ж), задана на безлічі ZJ рівністю

    Wf (ж) =? (-I)<x>y>® / (y). yezj

    Булева функція f від n (n - парне) змінних називається бент-функцією, якщо | Wf (ж) | = 2n / 2 для будь-якого ж е ZJ.

    Функція g: ZJ ^ Z4 називається кватернарні функцією від n змінних [1]. Перетворення Уолша - Адамара кватернарні функції g визначається наступним чином:

    Wg (ж) =? ix.y + g (y). yez n

    Тут «+» означає складання по модулю 4.

    Кватернарні функція g від n змінних називається бент-функцією, якщо | Wfl (ж) | = 4n / 2 для будь-якого ж е ZJ.

    1 Робота виконана за фінансової підтримки РФФД (проект №18-07-01394), Міністерства освіти і науки (Завдання №1.13559.2019 / 13.1 і Програма 5-100).


    Ключові слова: дискретної функції /ПРИКІНЦЕВІ ПОЛЯ /РЕГІСТР ЗСУВУ /ЗСУВ-КОМПОЗИЦІЯ /DISCRETE FUNCTIONS /FINITE FIELDS /SHIFT REGISTER /SHIFT-COMPOSITION

    Завантажити оригінал статті:

    Завантажити