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

Рассмотрена реализация операций в конечных полях на комбинационных схемах линейной сложности — одномерных каскадах конструктивных модулей (ОККМ). На основании предложенных алгоритмов совместной разделительной декомпозиции систем частичных булевых функций сформированы нижние и верхние оценки количест...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Системні дослідження та інформаційні технології
Datum:	2006
Hauptverfasser:	Тарасенко, В.П., Тесленко, А.К.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2006
Schlagworte:	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/42174
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Реализация операций в конечных полях на одномерном каскаде конструктивных модулей / В.П. Тарасенко, А.К. Тесленко // Систем. дослідж. та інформ. технології. — 2006. — № 2. — С. 7–27. — Бібліогр.: 6 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-42174
record_format	dspace
spelling	Тарасенко, В.П. Тесленко, А.К. 2013-03-11T11:39:13Z 2013-03-11T11:39:13Z 2006 Реализация операций в конечных полях на одномерном каскаде конструктивных модулей / В.П. Тарасенко, А.К. Тесленко // Систем. дослідж. та інформ. технології. — 2006. — № 2. — С. 7–27. — Бібліогр.: 6 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/42174 638.322 Рассмотрена реализация операций в конечных полях на комбинационных схемах линейной сложности — одномерных каскадах конструктивных модулей (ОККМ). На основании предложенных алгоритмов совместной разделительной декомпозиции систем частичных булевых функций сформированы нижние и верхние оценки количества боковых выводов модулей каскада, которые позволяют определить реализуемость операций в конечных полях на ОККМ с заданными конструктивными ограничениями, в том числе и массовых операций. Эффективность этой методики продемонстрирована на примере базисных массовых операций, применяемых в современных несимметричных криптографических преобразованиях. Розглянуто реалізацію операцій у скінченних полях на комбінаційних схемах лінійної складності — одновимірному каскаді конструктивних модулів (ОККМ). На основі запропонованих алгоритмів спільної розподільної декомпозиції систем частково визначених булевих функцій сформовані нижні та верхні кількості бокових виводів модулів каскаду, які дозволяють визначити можливість реалізації операцій в скінченних полях на ОККМ із заданими конструктивними обмеженнями, у тому числі і масових операцій. Ефективність цієї методики показано на прикладі базисних масових операцій, що використовуються у сучасних несиметричних криптографічних перетвореннях Realization of operations in finite fields with combination schemes of linear complexity as one-dimension cascades of constructive modules (OCCM) has been considered. Lower and upper evaluations for lateral pins of modules in a cascade have been formed on the base of proposed algorithms for joint dividing decomposition of systems of partial Boolean functions. The evaluations make it possible to determine the possibility of operations realization including mass operations in finite fields with OCCM of the given constructive limitations. As an example, the efficiency of the proposed method has been demonstrated on the basic mass operations used in the modern asymmetric cryptographic transformations. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Реалізація операцій у скінченних полях на одновимірному каскаді конструктивних модулів Realization of operations in finite fields with one-dimension cascade of constructive modules Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Реализация операций в конечных полях на одномерном каскаде конструктивных модулей
spellingShingle	Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Тарасенко, В.П. Тесленко, А.К. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
title_short	Реализация операций в конечных полях на одномерном каскаде конструктивных модулей
title_full	Реализация операций в конечных полях на одномерном каскаде конструктивных модулей
title_fullStr	Реализация операций в конечных полях на одномерном каскаде конструктивных модулей
title_full_unstemmed	Реализация операций в конечных полях на одномерном каскаде конструктивных модулей
title_sort	реализация операций в конечных полях на одномерном каскаде конструктивных модулей
author	Тарасенко, В.П. Тесленко, А.К.
author_facet	Тарасенко, В.П. Тесленко, А.К.
topic	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
topic_facet	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
publishDate	2006
language	Russian
container_title	Системні дослідження та інформаційні технології
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
format	Article
title_alt	Реалізація операцій у скінченних полях на одновимірному каскаді конструктивних модулів Realization of operations in finite fields with one-dimension cascade of constructive modules
description	Рассмотрена реализация операций в конечных полях на комбинационных схемах линейной сложности — одномерных каскадах конструктивных модулей (ОККМ). На основании предложенных алгоритмов совместной разделительной декомпозиции систем частичных булевых функций сформированы нижние и верхние оценки количества боковых выводов модулей каскада, которые позволяют определить реализуемость операций в конечных полях на ОККМ с заданными конструктивными ограничениями, в том числе и массовых операций. Эффективность этой методики продемонстрирована на примере базисных массовых операций, применяемых в современных несимметричных криптографических преобразованиях. Розглянуто реалізацію операцій у скінченних полях на комбінаційних схемах лінійної складності — одновимірному каскаді конструктивних модулів (ОККМ). На основі запропонованих алгоритмів спільної розподільної декомпозиції систем частково визначених булевих функцій сформовані нижні та верхні кількості бокових виводів модулів каскаду, які дозволяють визначити можливість реалізації операцій в скінченних полях на ОККМ із заданими конструктивними обмеженнями, у тому числі і масових операцій. Ефективність цієї методики показано на прикладі базисних масових операцій, що використовуються у сучасних несиметричних криптографічних перетвореннях Realization of operations in finite fields with combination schemes of linear complexity as one-dimension cascades of constructive modules (OCCM) has been considered. Lower and upper evaluations for lateral pins of modules in a cascade have been formed on the base of proposed algorithms for joint dividing decomposition of systems of partial Boolean functions. The evaluations make it possible to determine the possibility of operations realization including mass operations in finite fields with OCCM of the given constructive limitations. As an example, the efficiency of the proposed method has been demonstrated on the basic mass operations used in the modern asymmetric cryptographic transformations.
issn	1681–6048
url	https://nasplib.isofts.kiev.ua/handle/123456789/42174
citation_txt	Реализация операций в конечных полях на одномерном каскаде конструктивных модулей / В.П. Тарасенко, А.К. Тесленко // Систем. дослідж. та інформ. технології. — 2006. — № 2. — С. 7–27. — Бібліогр.: 6 назв. — рос.
work_keys_str_mv	AT tarasenkovp realizaciâoperaciivkonečnyhpolâhnaodnomernomkaskadekonstruktivnyhmodulei AT teslenkoak realizaciâoperaciivkonečnyhpolâhnaodnomernomkaskadekonstruktivnyhmodulei AT tarasenkovp realízacíâoperacíiuskínčennihpolâhnaodnovimírnomukaskadíkonstruktivnihmodulív AT teslenkoak realízacíâoperacíiuskínčennihpolâhnaodnovimírnomukaskadíkonstruktivnihmodulív AT tarasenkovp realizationofoperationsinfinitefieldswithonedimensioncascadeofconstructivemodules AT teslenkoak realizationofoperationsinfinitefieldswithonedimensioncascadeofconstructivemodules
first_indexed	2025-11-26T09:13:46Z
last_indexed	2025-11-26T09:13:46Z
_version_	1850617259760812032
fulltext	© В.П. Тарасенко, А.К. Тесленко, 2006 Системні дослідження та інформаційні технології, 2006, № 2 7 TIДC ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ, ВИСОКОПРОДУКТИВНІ КОМП’ЮТЕРНІ СИСТЕМИ УДК 638.322 РЕАЛИЗАЦИЯ ОПЕРАЦИЙ В КОНЕЧНЫХ ПОЛЯХ НА ОДНОМЕРНОМ КАСКАДЕ КОНСТРУКТИВНЫХ МОДУЛЕЙ В.П. ТАРАСЕНКО, А.К. ТЕСЛЕНКО Рассмотрена реализация операций в конечных полях на комбинационных схе- мах линейной сложности — одномерных каскадах конструктивных модулей (ОККМ). На основании предложенных алгоритмов совместной разделительной декомпозиции систем частичных булевых функций сформированы нижние и верхние оценки количества боковых выводов модулей каскада, которые по- зволяют определить реализуемость операций в конечных полях на ОККМ с за- данными конструктивными ограничениями, в том числе и массовых операций. Эффективность этой методики продемонстрирована на примере базисных мас- совых операций, применяемых в современных несимметричных криптографи- ческих преобразованиях. ВВЕДЕНИЕ В компьютерной инженерии, например, в помехоустойчивом кодировании, криптографических преобразованиях и т.д., широко применяются специали- зированные устройства для выполнения операций в конечных полях, что подтверждает актуальность исследования эффективных методов их практи- ческой реализации. Развитие компьютерных сетей, повсеместное внедрение электронного документооборота повышают значение такого критерия эф- фективности, как скорость преобразования информации. В то же время [1] выполнение операций в конечных полях, которые используются, например, в асимметричных криптографических преобразованиях, по скорости суще- ственно уступает симметричным преобразованиям, что приводит к ограни- чению областей применения ассиметричных преобразований, несмотря на ряд потенциальных преимуществ. Один из традиционных методов ускорения преобразования информа- ции — реализация их на комбинационных схемах, что находит применение в современной технологии ПЛИС [2]. Однако экспоненциальный рост слож- ности комбинационных схем с ростом числа независимых переменных n является здесь сдерживающим фактором и в общем случае исключает прак- тическую реализацию на комбинационных схемах массовых операций (т.е. определенных для некоторого ряда значений n ). Асимметричные крипто- графические преобразования и есть примерами массовых операций, кото- рые, кроме того, на практике характеризуются довольно большими значе- В.П.Тарасенко, А.К.Тесленко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 8 ниями n . Поэтому исследования методов реализации операций в конечных полях на комбинационных схемах с полиномиальной, в частности линейной, зависимостью сложности от числа n разрядов двоичного представления ис- ходных данных вызывают несомненный интерес. К таким методам относится реализация операций на одномерных кас- кадах конструктивных модулей (ОККМ), в которых каждый конструктив- ный модуль (КМ) и каскад в целом являются комбинационными схемами (рис. 1 и рис. 2). Следует отметить, что ряд типовых операций вычислительной техники (сложение, вычитание, поразрядная логика и т.д.), используемых и в крип- тографических преобразованиях, реализуется средствами, которые можно считать частными случаями ОККМ. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОСТАНОВКА ЗАДАЧИ Рассмотрим произвольную операцию ),,...,,( 21 PXXXFZ m= в конечном поле характеристики p и порядка )1( ≥= wpP w . Будем считать, что эле- Рис. 1. Структура ОККМ fj 0010 ... pxx m fn-1 1)1()1(1 ... −−− nnmn pxx f1 1111... pxx m f0 0010 ... pxx m Комбинационная схема К ом би на ци он на я сх ем а К омбинационная схема fj r r r r jmjj pxx1 Рис. 2. Структура отдельного КМ Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Системні дослідження та інформаційні технології, 2006, № 2 9 менты конечного поля кодируются целыми числами от 0 до 1−P , т.е. }1,...,1,0{,...,,, 21 −∈ PXXXZ m . Тогда операция ),,...,,( 21 PXXXFZ m= может быть реализована системой булевых функций ),,...,,(,...),,,...,,(),,,...,,( 211211210 PXXXfPXXXfPXXXf mnmm − , каждая из которых определяет значения разрядов с номером j 1)0,1,...,( −= nj двоичного представления результата операции =Z ),,...,,( 21 PXXXF m= . Здесь 〉〈= −110 ,...,, niiii xxxX , ),2,1,( mi …= , =P 〉〈= −110 ,...,, niii ppp — кортежи булевых переменных, определяющих значе- ния разрядов с номером j двоичного представления iX и P , [ log] 2 Pn = , ( []u — ближайшее к u большее целое число). В дальнейшем кортежем бу- левых переменных (или кортежем булевых функций) будем называть после- довательность таких переменных (функций), упорядоченную по возраста- нию номеров разрядов. Реализация операций на ОККМ обусловливает следующие конструк- тивные ограничения. На первичные входы КМ каскада поступают разряды iX и P с одинаковыми номерами, а на первичном выходе КМ реализуются значения разрядов результата с тем же номером. Для обеспечения возмож- ности увеличения разрядности iX и P путем присоединения к ОККМ до- полнительных модулей потребуем, чтобы при переходе от одного КМ кас- када к другому номера разрядов изменялись в порядке возрастания или убывания. Ограничим число боковых входов и выходов каждого КМ по ка- ждому из направлений (как в сторону старших, так и в сторону младших разрядов) некоторым целым значением r . Общее число КМ в ОККМ равно n , а каждый КМ имеет номер, соответствующий номеру разряда. С учетом принятых ограничений условие реализуемости некоторой массовой операции на ОККМ есть cr < , где c — константа, при любых значениях n из ряда возможных значений. В частности cr < при ∞→n . Отсюда возникает задача определения возможных значений количества бо- ковых выводов КМ для реализации на ОККМ операции …,,( 21 XXFZ = ),, PX m… . ОБЩАЯ МЕТОДИКА РЕШЕНИЯ ЗАДАЧИ Примем следующие обозначения. Пусть = abiX , 〉〈 + baa iii xxx ,...,, 1 , ),1,2,( mi …= , 〉〈= + baa iiiab pppP ,...,, 1, , 11 ,...,,,,..., 11, ++ 〈= aaaa mamab xxpxxU , 〉+ bma pxxp bb ,,...,, 11 — кортежи булевых переменных, определяемые значе- ниями iX и P из диапазона номеров разрядов от a до b включительно )( ba ≤ , nab <, . Пусть =),,...,,( 21, PXXXF mab ),,...,,(,...),,,...,,(),,,...,,( 2121121 PXXXfPXXXfPXXXf mbmama += В.П.Тарасенко, А.К.Тесленко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 10 кортеж булевых функций, определяемых значениями разрядов результата с номерами от a до b . При принятых обозначениях aainii PxPPXX an ,ai0,1 p ,X , , aa,0,1 ≡〉〈〉〈≡≡≡ −− , ),,...,,(f),,...,,(F 21a21aa, PXXXPXXX mm 〈≡ , ≡≡− ),,...,,(,,,...,, 21210,1 PXXXFPXXXU mmn )(),,...,,( 0,10,1210,1 −−− ≡≡ nnmn UFPXXXF . Произвольный набор значений булевых переменных из кортежа abiX , обозначим как abig , 1),1,2,( −…= ni , а из кортежа abP , как abs , . Пусть abq , — вектор ),,...,,( ,21 ,,, abm sggg ababab значений переменных из abU , , а abQ , — множество всевозможных векторов abq , . Разделим множество разрядов двоичного представления аргумен- тов iX , P и результата операции Z на два непустых подмножества: младшее (разряды с номерами от 0 до j ) и старшее (от 1+j до 1−n ), 2),,1,0( −…= nj . Основываясь на этом, будем анализировать совместную разделитель- ную декомпозицию [3] функций из кортежа ),,...,,( 211,1 PXXXF mjn +− при отделении аргументов из кортежа 0,jU , а также функций из кортежа ),,...,,( 210, PXXXF mj при отделении аргументов из кортежа 1,1 +− jnU , т.е. ))(,()( 0,21,110,11,1 jjnnjn UFUFUF +−−+− = , ))(,()( 1,140,30,10, +−− = jnjnj UFUFUF , 2),1,2,( −…= nj , где минимально возможное число функций в кортежах 2F и 4F определя- ется свойствами булевых функций и в конечном итоге свойствами операции ),,...,,( 21 PXXXFZ m= . Определим на множестве векторов 0,jQ отношение равенства. Векторы 0,0,0, , jjj Qrq ∈ находятся в отношении равенства, если равны кортежи функций ),( 0,1,11,1 jjnjn qUF +−+− и ),( 0,1,11,1 jjnjn rUF +−+− . Два кортежа функ- ций равны, если число функций в кортежах одинаково, а булевы функции, находящиеся на одних и тех же позициях в кортежах, равны. Очевидно, что отношение равенства кортежей функций является отношением эквивалент- ности, которое разбивает множество 0,jQ на классы эквивалентности, число которых составляет 0,jd . Аналогично 1,1 +− jnd обозначим число классов эк- вивалентности, на которое разбивается множество 1,1 +− jnQ по отношению равенства кортежей )( 0,1,10, jjnj UqF +− . Очевидно, что число функций в кор- Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Системні дослідження та інформаційні технології, 2006, № 2 11 теже 2F не меньше, чем [ log] 0,2 jd , а в кортеже 4F — не меньше, чем [ log] 1,12 +− jnd . Согласно [4], для реализации системы булевых функций ),,...,,( 21 PXXXF m на ОККМ необходимо и достаточно, чтобы r jd 20, ≤ и r jnd 21,1 ≤+− для всех 2,1,,0 −…= nj . Отметим, что этот результат может быть использован только тогда, когда булевы функции определены на всех значениях аргументов, например, в случае конечных полей характеристи- ки 2. В этом случае число n модулей ОККМ однозначно определяет значе- ние nP 2= , а функции из кортежа ),...,,( 21 mXXXF определены на всех значениях аргументов из iX mi ,1,2,…= . В случае же конечных полей ха- рактеристики 2>p булевы функции из ),,...,,( 21 PXXXF m являются час- тично определенными даже при фиксированном значении const)( =PP . Ес- ли же переменные из кортежа P определяются не величиной порядка поля, а одним из возможных неприводимых нормированных многочленов степени n , то функции из ),,...,,( 21 PXXXF m будут частично определенными даже для полей характеристики 2. Однако методы оптимальной (по заданному критерию) реализации час- тичных булевых функций по сравнению с методами реализации полностью определенных функций в общем случае более сложны и трудоемки. Поэто- му для оценки возможности реализации систем частично определенных бу- левых функций на ОККМ целесообразно использовать нижние и верхние границы боковых выводов КМ. Нижней оценкой будем называть такое число боковых выводов КМ по каждому из направлений (в стороны как старших, так и младших разрядов), которое не превышает их фактического значения, полученного соглас- но [4] при любом доопределении булевых функций из кортежа ),,...,,( 21 PXXXF m . Верхней оценкой будем называть число боковых вы- водов КМ по каждому из направлений, которое не меньше их фактического значения, полученного согласно [4] хотя бы для одного из возможных до- определений. Приведенные определения нижней и верхней оценок упрощают анализ реализаций произвольной операции ),,...,,( 21 PXXXFZ m= на ОККМ. Действительно, некоторая операция принципиально не может быть реализо- вана на ОККМ с числом боковых выводов модулей, меньшим, чем нижние оценки. В то же время достоверно существуют реализации операции на ОККМ с числом боковых выводов модулей, равным верхней оценке. В слу- чае массовых операций, если хотя бы одна из нижних оценок — возрастаю- щая функция от n , ее реализация на ОККМ невозможна. Если обе верхние оценки не являются возрастающими функциями от n , то массовая операция реализуема на ОККМ. Для определения верхних и нижних оценок числа боковых выводов КМ рассмотрим совместную разделительную декомпозицию систем частичных булевых функций. При этом на множестве векторов значений отделяемых В.П.Тарасенко, А.К.Тесленко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 12 аргументов (например, 0,jQ ) в общем случае нельзя установить отношение равенства кортежей функций из-за неполного определения функций в кор- тежах. Можно лишь определить отношение совместимости кортежей функ- ций. Два кортежа функций являются совместимыми, если они содержат одинаковое число функций, и совместимы функции, находящиеся на одина- ковых позициях в кортежах. В свою очередь, две функции совместимы, если они равны на всех тех наборах значений аргументов, где они определены. Векторы значений отделяемых аргументов, порождающие совместимые кортежи функций, назовем совместимыми. В дальнейшем, для упрощения изложения, отношение равенства будем рассматривать как частный случай отношения совместимости, что не противоречит определению этих отноше- ний. АЛГОРИТМЫ ОЦЕНКИ ЧИСЛА ВЫВОДОВ МОДУЛЕЙ ОККМ В общем случае отношение совместимости на множестве векторов значений отделяемых переменных не является отношением эквивалентности. Это приводит к постановке задачи определения покрытия множества векторов значений отделяемых переменных минимально возможным числом под- множеств совместимых векторов — задачи определения кратчайшего по- крытия. Известен алгоритм (далее Алгоритм 1) решения такой задачи [5], заключающийся в выполнении всевозможных совмещений (склеиваний) векторов, формировании тупиковых покрытий и выборе среди них крат- чайшего. Необходимо отметить, что Алгоритм 1 в общем случае формирует ту- пиковые покрытия, в которых подмножества покрытия могут пересекаться. Применительно к совместной декомпозиции систем частичных булевых функций это означает, что на векторах, входящих в подмножества пересече- ния, доопределение булевых функций не является однозначным. Однако любое возможное доопределение булевых функций на этом подмножестве векторов не изменит количества подмножеств тупикового покрытия и мо- жет быть использовано для оптимизации реализации функций по дополни- тельным критериям. Кроме того, любое возможное доопределение кортежей булевых функций на векторах, входящих в подмножества пересечения под- множеств покрытия, фактически приводит к разбиению исходного множе- ства векторов на непересекающиеся подмножества. Тем не менее, с учетом приведенных замечаний в дальнейшем будем использовать термин «покры- тие», а термин «разбиение» соотносить, как это принято, с отношениями эквивалентности. Укажем на следующие, важные для дальнейшего изложения, свойства тупиковых покрытий: • Любые два вектора, входящие в одно и то же подмножество тупико- вого покрытия, совместимы. • Два любых подмножества тупикового покрытия содержат, по край- ней мере, по одному несовместимому вектору (в противном случае покры- тие не будет тупиковым). Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Системні дослідження та інформаційні технології, 2006, № 2 13 • Каждому подмножеству покрытия совместимых векторов соответст- вует подмножество совместимых кортежей функций. В результате совме- щения кортежей функций из такого подмножества происходит доопределе- ние функций в кортежах на всех или на части значений аргументов, где они не были определены. Этот процесс в дальнейшем будем называть доопреде- лением функций в кортежах или доопределением кортежей, а сформирован- ный кортеж — характеристическим кортежем подмножества покрытия. • Характеристические кортежи подмножеств тупикового покрытия попарно не совместимы. • Кратчайшему покрытию соответствует наименьшее число попарно не совместимых характеристических кортежей. Пусть 0,jd и 1,1 +− jnd — числа подмножеств кратчайшего покрытия множества 0,jQ и 1,1 +− jnQ , соответственно, полученные при независимом анализе для каждого значения n . Поскольку никакие доопределения функций из двух несовместимых кортежей не преобразуют кортежи в совместимые, то значения [ log] 0,2 jd и [ log] 1,12 +− jnd позволяют определить нижние оценки числа боковых выводов КМ в ОККМ: ( )[ log]max )( 0,2 jdnL =← — в сторону старших разрядов, ( )[ log]max )( 1,12 +−→ = jndnL — в сторону млад- ших разрядов, 2,1,,0 −…= nj . Для формирования верхних оценок введем понятие непротиворечиво- сти покрытий множеств векторов. Согласно изложенному выше, подмноже- ству покрытия соответствует подмножество совместимых кортежей функ- ций. При совмещении таких кортежей происходит доопределение функций в кортежах. Если доопределения любой функции из ),,...,,( 21 PXXXF m , вызванные покрытиями двух различных множеств векторов baQ , и dcQ , , являются одинаковыми, то такие покрытия будем называть непротиворечи- выми. Отсюда следует, что некоторые покрытия (не обязательно тупиковые) множеств 1,1 +− jnQ и 0,jQ , ( 2,1,,0 −…= nj ) являются непротиворечивыми, если существует, по крайней мере, одно доопределение функций из кортежа ),,...,,( 21 PXXXF m , в результате которого любые два вектора из любого подмножества покрытия останутся совместимыми (напомним, что отноше- ние равенства рассматривается как частный случай отношения совместимо- сти). Обозначим 0,je и 1,1 +− jne числа подмножеств непротиворечивых по- крытий множеств 0,jQ и 1,1 +− jnQ ( 2,1,,0 −…= nj ). Эти числа позволяют определить верхние оценки числа боковых выводов модулей ОККМ: ( )[e log]max )( 0,2 jnH =← — в сторону старших разрядов и =→ )(nH ( )[e log]max 1,12 +−= jn — в сторону младших разрядов, 2,1,,0 −…= nj . Для определения верхних оценок рассмотрим свойства частичных бу- левых функций из кортежа ),,...,,( 21 PXXXF m . Их особенностью является неопределенность всех функций кортежа для одних и тех же векторов зна- чений аргументов. Легко видеть, что таким же свойством обладают любые В.П.Тарасенко, А.К.Тесленко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 14 кортежи ),( 0,1,11,1 jjnjn qUF +−+− и )( 0,1,10, jjnj UqF +− где 0,0, jj Qq ∈ , 1,11,1 +−+− ∈ jnjn Qq ( 2,1,,0 −…= nj ). Это обусловливает следующую классификацию отношений совместимости кортежей частично определенных функций: отношения псевдоравенства, одностороннего и двустороннего доопределений. Отношение псевдоравенства будем обозначать символом ≅ , на- пример, 0,0, jj ba ≅ , где 0,0,0, , jjj Qba ∈ или ≅+−+− ),( 0,1,11,1 jjnjn aUF ),( 0,1,11,1 jjnjn bUF +−+−≅ . При данном отношении множество векторов значе- ний не отделяемых аргументов (в рассматриваемом примере 1,1 +− jnQ ) раз- бивается на два подмножества. На первом из них функции из обоих корте- жей определены и равны, на втором — не определены. Если первое из подмножеств пустое, то функции в обоих кортежах не определены при всех значениях аргументов. Если второе подмножество пустое, то функции из различных кортежей определены и равны на всех значениях аргументов, т.е. отношение равенства — частный случай отношения псевдоравенства. Легко видеть, что отношение псевдоравенства является отношением эквивалент- ности. При совмещении векторов значений отделяемых переменных дооп- ределение функций в кортежах может быть произвольным, но одинаковым для функций в различных кортежах (неоднозначное доопределение). Данное отношение будем называть отношением совместимости ранга 1. Отношение одностороннего доопределения будем обозначать символом ⇒ , например, 0,0, jj ba ⇒ , где 0,0,0, , jjj Qba ∈ или ⇒+−+− ),( 0,1,11,1 jjnjn aUF ),( 0,1,11,1 jjnjn bUF +−+−⇒ . При данном отношении множество векторов значений не отделяемых аргументов (в рассматриваемом примере 1,1 +− jnQ ) разбивается на три подмножества. На первом из них (оно может быть пус- тым) функции из обоих кортежей определены и равны, на втором (оно не может быть пустым) функции кортежа слева от знака ⇒ не определены, а справа — определены, на третьем из них (оно тоже может быть пустым) функции из обоих кортежей не определены. Вектор 0,ja и кортеж ),( 0,1,11,1 jjnjn aUF +−+− будем называть поглощаемыми. Отношение од- ностороннего доопределения обладает свойством транзитивности (из 0,0, jj ba ⇒ и 0,0, jj cb ⇒ следует 0,0, jj ca ⇒ ), но не обладает свойствами симметричности и рефлексивности (из 0,0, jj ba ⇒ не следует 0,0, jj ab ⇒ и не верно 0,0, jj aa ⇒ ). Здесь и в дальнейшем будем считать, что в процессе совмещения кортежей функций, для которых существует рассматри- ваемое отношение, происходит доопределение функций из кортежа ),( 0,1,11,1 jjnjn aUF +−+− только значениями функций из кортежа ),( 0,1,11,1 jjnjn bUF +−+− (однозначное доопределение). На векторах из третье- го множества (если оно не пустое) функции в обоих кортежах остаются не определенными. Такое доопределение обозначим =+−+− :),( 0,1,11,1 jjnjn aUF ),( 0,1,11,1 jjnjn bUF +−+−= . Очевидно, что в результате совмещения создается Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Системні дослідження та інформаційні технології, 2006, № 2 15 кортеж, совпадающий с имеющимся кортежем ),( 0,1,11,1 jjnjn bUF +−+− , т.е. новый кортеж не создается. Отношение одностороннего доопределения бу- дем называть отношением совместимости ранга 2. Между поглощенным и поглощаемым вектором (кортежем функций) в результате выполнения со- вмещения устанавливается отношение псевдоравенства. Отношение двустороннего доопределения (отношение совместимости ранга 3) будем обозначать символом ⇔ , например, 0,jij ba ⇔ или ),(),( 0,1,11,10,1,11,1 jjnjnjjnjn bUFaUF +−+−+−+− ⇔ . При данном отношении множество векторов значений аргументов (в рассматриваемом примере 1,1 +− jnQ ) разбивается на четыре подмножества. На первом из них (оно мо- жет быть пустым) функции из обоих кортежей определены и равны, на вто- ром (оно не может быть пустым) функции кортежа слева от знака ⇔ не оп- ределены, а справа — определены, на третьем (оно не может быть пустым) — функции кортежа слева от знака ⇔ определены, а справа — не определены, на четвертом (оно тоже может быть пустым) — функции из обоих кортежей не определены. Отношение двустороннего доопределения обладает свойством симметричности (например, из 0,jij ba ⇔ следует 0,0, jj ab ⇔ ), но не обладает свойством рефлексивности и транзитивности. Здесь и далее будем считать, что процесс совмещения кортежей функций, для которых существует отношение двустороннего доопределения, состоит только во взаимном доопределении функций в кортежах на втором и треть- ем подмножествах аргументов. На векторах из четвертого множества (если оно не пустое) функции в обоих кортежах остаются не определенными. При этом может создаваться ранее отсутствующий кортеж. Например, в случае совмещения кортежей ),( 0,1,11,1 jjnjn aUF +−+− и ),( 0,1,11,1 jjnjn bUF +−+− может создаваться кортеж, которого не было в перечне кортежей, порождаемых всеми векторами из множества 0,jQ . Между кортежем, созданным в ре- зультате совмещения, и исходными кортежами устанавливается отношение одностороннего доопределения. Поскольку в кортежах булевых функций ),,...,,( 21 PXXXF m , реали- зующих операции в конечных полях, при любых значениях аргументов все функции определены или все функции не определены, то между любыми векторами множества 0,jQ (или множества 1,1 +− jnQ ), 2,1,,0 −…= nj , может существовать одно из перечисленных отношений совместимости, т.е. при- веденная классификация исчерпывает все возможные отношения совмести- мости векторов и соответствующих им кортежей функций. Среди рассмотренных отношений совместимости отношение ранга 1 является отношением эквивалентности. Оно разбивает множество 0,jQ (и 1,1 +− jnQ ), 2,1,,0 −…= nj , на классы эквивалентности — подмножества со- вместимых векторов (ранга 1), т.е. такое разбиение является некоторым по- крытием (в общем случае не тупиковым) исходного множества непересе- кающимися подмножествами совместимых векторов. Легко видеть, что В.П.Тарасенко, А.К.Тесленко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 16 такие покрытия множеств 0,jQ и 1,1 +− jnQ , 2,1,,0 −…= nj , являются непро- тиворечивыми. Действительно, для этого достаточно доопределить все час- тичные функции из ),,...,,( 21 PXXXF m на всех тех векторах значений ар- гументов, где они не определены, одним и тем же значением (например, 0). Следовательно, число классов эквивалентности по отношению совместимо- сти ранга 1 множеств векторов 0,jQ и 1,1 +− jnQ , 2,1,,0 −…= nj , может слу- жить для определения верхних оценок числа боковых выводов модулей ОККМ, реализующего систему частичных булевых функций. Такие верхние оценки назовем оценками по псевдоравенству. В общем случае они могут быть весьма завышенными, поскольку не учитывают отношения совмести- мости рангов 2 и 3. Тем не менее, оценки по псевдоравенству могут свиде- тельствовать о принципиальной возможности реализации на ОККМ массо- вых операций. Рассмотрим Алгоритм 2 определения верхних оценок на основе отно- шений совместимости рангов 1 и 2 (оценок по одностороннему доопределе- нию). 1. Для каждого 2,1,,0 −…= nj выполнить пп. 2 и 4. 2. Определить список классов разбиения множеств векторов 0,jQ по отношениям совместимости ранга 1. 3. Вычеркнуть из списка классы, векторы которых поглощаются хотя бы одним вектором из 0,jQ . 4. Определить значение e j,0 количества классов, оставшихся не вы- черкнутыми. 5. Определить оценку [)log(]max)( 0,2 jenO = ← . Выполнить пп. 1…4 для множеств 1,1 +− jnQ и определить оценку ( )[ log]max )( 1,12 +−→ = jnenO . В общем случае из-за отсутствия свойств симметричности и рефлек- сивности отношений одностороннего доопределения может существовать несколько вариантов поглощения векторов из некоторого класса. Вследст- вие множественности вариантов поглощения векторов некоторого класса может существовать несколько вариантов результирующего покрытия мно- жеств 0,jQ и 1,1 +− jnQ подмножествами совместимых векторов по отношени- ям совместимости рангов 1 и 2. Однако число подмножеств таких покрытий неизменно и равно соответственно 0,je и 1j1,-ne + . Это следует из свойства транзитивности отношений одностороннего доопределения, а также из того, что при совмещении кортежей функций, находящихся в отношении ранга 2, новые кортежи не создаются. Действительно, величина e j,0 определяет максимальное число попарно несовместимых векторов множества 0,jQ по отношению совместимости рангов 1 и 2, и она не может измениться в ре- зультате любого совмещения векторов, находящихся в отношении ранга 1 или 2. Покажем, что среди всевозможных вариантов результирующего покры- тия множеств 0,jQ и 1,1 +− jnQ ( 2,1,,0 −…= nj ) в соответствии с Алгорит- мом 2 всегда существуют непротиворечивые покрытия. Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Системні дослідження та інформаційні технології, 2006, № 2 17 Утверждение 1. Для любого покрытия множества 0,bQ , порождаемого Алгоритмом 2, существуют непротиворечивые покрытия, порождаемые этим же алгоритмом, для множества 0,cQ 02 ≥>≥− bcn . Рассмотрим произвольный вектор 0,0, cc Qc ∈ . Представим =0,cc ),( 0,1, bbc cc += . Пусть существует по крайней мере один вектор 0,0,1,0, ),( cbbcc Qddd ∈= + такой, что 0,0, cc dc ⇒ )),(),(( 0,1,0,1, bbccbc ddcc ++ ⇒ и 0,0, bb dc ⇒ . Тогда или ),(),( 0,1,0,1, bbcbbc dccc ++ ⇒ , или ≅+ ),( 0,1, bbc cc ),( 0,1, bbc dc +≅ . В первом случае для вектора ),( 0,1,0, bbcc ccc += существует альтернативный вариант совместимости ранга 2, а именно вектор ),( 0,1, bbc dc + , не противоречащий совмещению векторов 0,bc и 0,bd . Во втором случае совмещение векторов 0,bc и 0,bd не приводит к до- определению функций из кортежа ),,( 0,1,1,11,1 bbccncn ccUF ++−+− . Если же век- тор 0,cc поглощается каким-либо вектором из 0,cQ , то этим же вектором может быть поглощен и вектор 0,1, , bbc dc + , что приводит к одинаковому доопределению функций в кортежах ),( 0,1,11,1 bbnbn cUF +−+− и ),( 0,1,11,1 bbnbn dUF +−+− . Пусть ни одного вектора 0,cd с указанным свойством не существует. Однако это означает, что вектор 0,bc не поглощается ни одним вектором из множества 0,bQ , а также функции из кортежа ),( 0,1,11,1 bbnbn cUF +−+− не были доопределены ни на одном векторе из 1,1 +− bnQ . В этом случае никакие дооп- ределения функций из кортежа ),( 0,1,11,1 bbnbn cUF +−+− в результате любых поглощений векторов во множестве 0,cQ не изменят свойств вектора 0,bc поглощать векторы из множества 0,bQ , если таковые имелись. Аналогично изложенному доказывается справедливость Утверждения 2. Утверждение 2. Для любого покрытия множества 1,1 +− cnQ , порождае- мого Алгоритмом 2, существуют непротиворечивые покрытия, порождае- мые этим же алгоритмом, для множества 1,1 +− bnQ ( 02 ≥>≥− bcn ). Утверждение 3. Любые покрытия множеств 0,bQ и 1,1 +− cnQ , порож- даемые Алгоритмом 2, являются непротиворечивыми ( 02 ≥>≥− bcn ). Для доказательства рассмотрим два произвольных вектора ∈0,0, , bb ba 0,bQ∈ таких, что 0,0, bb ba ⇒ и два произвольных вектора ∈+−+− 1,11,1 cncn dc 1,1 +−∈ cnQ таких, что 1,11,1 +−+− ⇒ cncn dc . Покажем, что поглощение вектора 0,ba не может привести к несовместимости векторов 1,1 +− cnc и 1,1 +− cnd . Из принятых условий следует ),,(),( 0,1,1,10,0,1,1,10, bbccncbbccnc UUdFUUcF ++−++− ⇒ , (1) В.П.Тарасенко, А.К.Тесленко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 18 ),,(),( 0,1,1,11,10,1,1,11,1 bbccnbnbbccnbn bUUFaUUF ++−+−++−+− ⇒ . (2) Обозначим 1,1 +− bnT такое непустое по определению подмножество век- торов множества 1,1 +− bnQ , где функции в кортеже ,( 1,11,1 +−+− cnbn UF ), 0,1, bbc aU + не определены, а в кортеже ),,( 0,1,1,11,1 bbccnbn bUUF ++−+− оп- ределены. Если не существует ни одного вектора 1,11,1,1 ),( +−++− ∈ bnbccn Ttt такого, что 1,11,1 +−+− = cncn ct , то доопределение функций в кортеже ),,( 0,1,1,11,1 bbccnbn aUUF ++−+− не может изменить отношение ⇒+− 1,1 cnc 1,1 +−⇒ cnd . Пусть существует хотя бы один вектор ∈++− ),( 1,1,1 bccn tt 1,1 +−∈ bnT такой, что 1,11,1 +−+− = cncn ct . Тогда кортеж значений функций ),,( 0,1,1,11, bbccnbc btcF ++−+ определен и согласно (1) равен кортежу значений функций ),,( 0,1,1,11, bbccnbc btdF ++−+ . В результате поглощения вектора 0,ba вектором 0,bb ),,(:),,( 0,1,1,11,0,1,1,11, bbccnbcbbccnbc btcFatcF ++−+++−+ = или ),,(),,( 0,1,1,11,0,1,1,11, bbccnbcbbccnbc btcFatcF ++−+++−+ = . Если кортеж значений функций ),,( 0,1,1,11, bbccnbc atdF ++−+ определен, то согласно (2) он равен кортежу значений функций ),,( 0,1,1,11, bbccnbc btdF ++−+ . Если не определен, то вектор 1,11,1,1 ),( +−++− ∈ bnbccn Ttd , и в результате погло- щения вектора 0,ba вектором 0,bb ),,(:),,( 0,1,1,11,0,1,1,11, bbccnbcbbccnbc btdFatdF ++−+++−+ = . Отсюда следует ),,(),,( 0,1,1,11,0,1,1,11, bbccnbcbbccnbc btdFatdF ++−+++−+ = , что не противоречит совместимости векторов 1,1 +− cnc и 1,1 +− cnd . Аналогич- но можно показать, что поглощение вектора 1,1 +− cnc не может привести к несовместимости векторов 0,ba и 0,bb . Утверждения 1…3 показывают, что среди всевозможных покрытий множеств 0,jQ и 1,1 +− jnQ ( 2,1,,0 −…= nj ), порождаемых Алгоритмом 2, существуют непротиворечивые покрытия, и поэтому оценки )(nO← и )(nO→ являются верхними оценками, которые далее будем называть верх- ними оценками по одностороннему доопределению. Предположим, что существует такое значение tj = , когда в результате вычеркивания векторов из поглощаемых классов множества 0,tQ между лю- быми двумя оставшимися векторами не существует отношения двусторон- него доопределения. В этом случае любое из покрытий этого множества, Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Системні дослідження та інформаційні технології, 2006, № 2 19 порождаемых Алгоритмом 2, является кратчайшим. Действительно, выбе- рем по одному вектору из каждого не вычеркнутого класса. Согласно при- нятому условию, они будут попарно не совместимы, следовательно, покры- тия множества 0,tQ тупиковые. С другой стороны, если среди векторов из вычеркнутых классов были векторы с отношениями двустороннего доопре- деления как между собой, так и с векторами из не вычеркнутых классов, то в результате их совмещения число характеристических кортежей может толь- ко увеличиться. Следовательно, покрытия множества 0,tQ , порождаемые Алгоритмом 2, при принятом условии будут и кратчайшими. Если же 0,te не меньше любых e j,0 ( 2,1,,0 −…= nj ), то согласно определению, оценка )(nO← будет и нижней оценкой. Это доказывают следующие утверждения. Утверждение 4. Если среди множеств 0,jQ с максимальными значе- ниями e j,0 существует хотя бы одно, где среди векторов из не вычеркнутых классов отсутствуют отношения двустороннего доопределения, то оценка )n(O← , полученная с помощью Алгоритма 2, является нижней. Аналогич- но для оценки )n(O→ . Утверждение 5. Если среди множеств 1,1 +− jnQ с максимальными зна- чениями 1j1,-ne + существует хотя бы одно, где среди векторов из не вы- черкнутых классов отсутствуют отношения двустороннего доопределения, то оценка )n(O→ , полученная с помощью Алгоритма 2, является нижней. Заметим, что трудоемкость реализации Алгоритма 2 существенно ни- же по сравнению с Алгоритмом 1. В то же время Алгоритм 2 непосредст- венно не выделяет необходимые покрытия и, соответственно, не формирует доопределения функций из ),,...,,( 21 PXXXF m . Для этой цели применяется Алгоритм 3. 1. Разбить множество векторов 0,0Q по отношению псевдоравенства. Произвольно выполнить поглощение всех поглощаемых векторов и доопре- деление функций в поглощаемых кортежах. 2. Последовательно для значений 2,,2,1 −…= nj выполнить следую- щие действия. 2.1. Разбить множество векторов 0,jQ по отношению псевдоравен- ства с учетом предшествующих доопределений функций из ),,...,,( 21 PXXXF m . 2.2. Выполнить поглощение всех векторов из поглощаемого класса векторами одного и только одного поглощающего класса. Выбор по- глощающего класса произвольный. Доопределить функции в погло- щаемых кортежах. 3. Разбить множество векторов 1,1 −− nnQ по отношению псевдора- венства с учетом предшествующих доопределений функций из ),,...,,( 21 PXXXF m . Произвольным образом выполнить поглощение всех поглощаемых векторов и доопределить функции в поглощаемых кортежах. В.П.Тарасенко, А.К.Тесленко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 20 4. Последовательно для значений 0,1,,4,3 …−−= nnj выполнить сле- дующие действия: 4.1. Разбить множество векторов 1,1 +− jnQ по отношению псевдора- венства с учетом предшествующих доопределений функций из ),,...,,( 21 PXXXF m . 4.2. Выполнить поглощение всех векторов из поглощаемого класса векторами одного и только одного поглощающего класса. Выбор по- глощающего класса произвольный. Доопределить функции в погло- щаемых кортежах. Достоверность Алгоритма 3 следует из доказательств Утвержде- ний 1…3. ПРИМЕРЫ Практическое значение полученных результатов проиллюстрируем реализа- цией на ОККМ одноместных и двуместных операций в конечных полях ха- рактеристики 2>p при 1=w (т.е. pP = ), которые используются в асим- метричных криптографических преобразованиях. Рассмотрим реализацию операции определения значения Z из уравне- ния PXZ mod2 = , которую назовем операцией деления на 2 (сдвига впра- во) в кольце неотрицательных вычетов по модулю P . Аналитически значе- ние Z определяется по следующему алгоритму: 2. div : else 2 div )(: then 1 2) mod ( If XZPXZX =+== Функции из кортежа ),( PXF не определены на всех тех значениях ар- гументов, где P X ≥ , а также где P четно, а X нечетно. Обозначим ,2 mod ,2 mod ,2 mod 1 0, 1 ,0 1 0, −−− === j j j j j j PPXXZZ 1 11, 1 1,1 1 1,1 2 div P ,2 div ,2 div + +− + +− + +− === j jn j jn j jn PXXZZ , ( 2,1,,0 −…= nj ). Определим список классов эквивалентности по отношению псевдора- венства для множеств 0,jQ , ( 2,1,,0 −…= nj ). Класс 1L , где 0,jX нечетное, а 0,jP четное. Функции из кортежей ),( 0,1,11,1 jjnjn qUF +−+− , где 10, L∈jq , не определены на всех значениях аргу- ментов. Класс 2L , где 0,jX и 0,jP нечетные, 0,0, jj PX < , а 1 0,0, 2 +<+ j jj PX . Функции из кортежей ),( 0,1,11,1 jjnjn qUF +−+− ( 20, L∈jq ) определены как 2div)( 1,11,11,1 +−+−+− += jnjnjn PXZ на всех тех значениях аргументов, где 1,11,1 +−+− ≤ jnjn PX . Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Системні дослідження та інформаційні технології, 2006, № 2 21 Класс 3L , где 0,jX и 0,jP нечетные, 0,0, jj PX ≥ , а 1 0,0, 2 +<+ j jj PX . Функции из кортежей ),( 0,1,11,1 jjnjn qUF +−+− ( 30, L∈jq ) определены как 2div)( 1,11,11,1 +−+−+− += jnjnjn PXZ на всех тех значениях аргументов, где 1,11,1 +−+− < jnjn PX . Класс 4L , где 0,jX и 0,jP нечетные, 0,0, jj PX < , а 1 0,0, 2 +≥+ j jj PX . Функции из кортежей ),( 0,1,11,1 jjnjn qUF +−+− ( 40, L∈jq ) определены как 2div)1( 1,11,11,1 ++= +−+−+− jnjnjn PXZ на всех тех значениях аргументов, где 1,11,1 +−+− ≤ jnjn PX . Класс 5L , где 0,jX и 0,jP нечетные, 0,0, jj PX ≥ , а 1 0,0, 2 +≥+ j jj PX . Функции из кортежей ),( 0,1,11,1 jjnjn qUF +−+− ( 50, L∈jq ) определены как 2div)1( 1,11,11,1 ++= +−+−+− jnjnjn PXZ на всех тех значениях аргументов, где 1,11,1 +−+− < jnjn PX . Класс 6L , где 0,jX четное, 0,0, jj PX < . Функции из кортежей ),( 0,1,11,1 jjnjn qUF +−+− ( 60, L∈jq ) определены как 2div)( 1,11,1 +−+− = jnjn XZ на всех тех значениях аргументов, где 1,11,1 +−+− ≤ jnjn PX . Класс 7L , где 0,jX четное, 0,0, jj PX ≥ . Функции из кортежей ),( 0,1,11,1 jjnjn qUF +−+− ( 70, L∈jq ) определены как 2div)( 1,11,1 +−+− = jnjn XZ на всех тех значениях аргументов, где 1,11,1 +−+− < jnjn PX . Определим список классов эквивалентности по отношению псевдора- венства для множеств 1,1 +− jnQ , ( 2,1,,0 −…= nj ). Класс 1H , где 1,11,1 +−+− > jnjn PX . Функции из кортежей ),( 0,1,10, jjnj UqF +− , где 11,1 H∈+− jnq , не определены на всех значениях аргументов. Класс 2H , где 1,11,1 +−+− = jnjn PX и 0)2mod( 1,1 =+− jnX . Функции из кортежей ),( 0,1,10, jjnj UqF +− , ( 21,1 H∈+− jnq ) определены как 2div0,0, jj XZ = , если 0,jX четное, 2div)( 0,0,0, jjj PXZ += , если 0,jX нечетное, на всех тех значениях аргументов, где 0,0, jj PX < , 0,jP нечетное или 0,jX четное. Класс 3H , где 1,11,1 +−+− = jnjn PX и 1)2mod( 1,1 =+− jnX . Функции из кортежей ),( 0,1,10, jjnj UqF +− , ( 31,1 H∈+− jnq ) определены как 2div)2( 0, 1 0, j j j XZ += + , если 0,jX четное, 2div)( 0,0,0, jjj PXZ += , если 0,jX нечетное, В.П.Тарасенко, А.К.Тесленко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 22 на всех тех значениях аргументов, где 0,0, jj PX < , 0,jP нечетное или 0,jX четное. Класс 4H , где 1,11,1 +−+− < jnjn PX , 0)2mod)(( 1,11,1 =+ +−+− jnjn PX и 0)2mod( 1,1 =+− jnX . Функции из кортежей ),( 0,1,10, jjnj UqF +− , ( ∈+− 1,1 jnq 4H∈ ) определены как 2div0,0, jj XZ = , если 0,jX четное, 2div)( 0,0,0, jjj PXZ += , если 0,jX нечетное, на всех тех значениях аргументов, где 0,jP нечетное или 0,jX четное. Класс 5H , где 1,11,1 +−+− < jnjn PX , 1)2mod)(( 1,11,1 =+ +−+− jnjn PX и 0)2mod( 1,1 =+− jnX . Функции из кортежей ),( 0,1,10, jjnj UqF +− , ( ∈+− 1,1 jnq 5H∈ ) определены как 2div0,0, jj XZ = , если 0,jX четное, 2div)2( 1 0,0,0, +−+= j jjj PXZ , если 0,jX нечетное и 1 0,0, 2 +≥+ j jj PX , 2div)2( 1 0,0,0, +++= j jjj PXZ , если 0,jX нечетное и 1 0,0, 2 +<+ j jj PX , на всех тех значениях аргументов, где 0,jP нечетное или 0,jX четное . Класс 6H , где 1,11,1 +−+− < jnjn PX , 0)2mod)(( 1,11,1 =+ +−+− jnjn PX и 1)2mod( 1,1 =+− jnX . Функции из кортежей ),( 0,1,10, jjnj UqF +− , ( ∈+− 1,1 jnq 6H∈ ) определены как 2div)2( 0, 1 0, j j j XZ += + , если 0,jX четное, 2div)( 0,0,0, jjj PXZ += , если 0,jX нечетное, на всех тех значениях аргументов, где 0,jP нечетное или 0,jX четное. Класс 7H , где 1,11,1 +−+− < jnjn PX , 1)2mod)(( 1,11,1 =+ +−+− jnjn PX и 1)2mod( 1,1 =+− jnX . Функции из кортежей ),( 0,1,10, jjnj UqF +− , ( ∈+− 1,1 jnq 7H∈ ) определены как 2div)2( 0, 1 0, j j j XZ += + , если 0,jX четное, 2div)2( 1 0,0,0, +−+= j jjj PXZ , если 0,jX нечетное и j jj PX 20,0, ≥+ , 2div)2( 1 0,0,0, +++= j jjj PXZ , если 0,jX нечетное и j jj PX 20,0, <+ , на всех тех значениях аргументов, где 0,jP нечетное или 0,jX четное. Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Системні дослідження та інформаційні технології, 2006, № 2 23 Из изложенного следует, что 4 0,0 =e (классы L ,L 32 и 4L пустые), 610 =e (класс 2L пустой), а при 1>j 70, =je . Аналогично 71,1 =+− jne ( 2,1,,0 −…= nj ). Тогда верхние оценки по псевдоравенству =← )(nH 3)[log](max)()[log](max 0,20,2 ==== → jj enHe и не зависят от n , что сви- детельствует о принципиальной возможности реализации на ОККМ опера- ции деления на 2 в кольце неотрицательных вычетов. Для получения верхних оценок по одностороннему доопределению ис- пользуем Алгоритм 2. Легко убедиться, что при 1>j векторы из класса 1L поглощаются векторами из любого иного класса, векторы из класса 3L по- глощаются векторами из класса 2L , векторы из класса 5L — векторами из класса 4L , а векторы из класса 7L — векторами из класса 6L . В соответст- вии с Алгоритмом 2 не вычеркнутыми останутся классы 2L , 4L и 6L , т.е. 30, =je . При 1=j не вычеркнутыми останутся классы 2L , 4L и 7L , т.е. 30, =je . При 0=j не вычеркнутыми останутся классы 5L и 6L , т.е. 20, =je . Следовательно, 2)( =← nO . Аналогично векторы из класса 1H по- глощаются векторами из любого иного класса, векторы из класса 2H — векторами из класса 4H , а векторы из класса 3H — векторами из класса 6H , и не вычеркнутыми останутся классы 4H , 5H , 6H и 7H , т.е. 41,1 ≤+− jne и 2)( =→ nO . Следовательно, рассматриваемая массовая опера- ция реализуема на ОККМ с 2=r . Легко проверить, что любые два вектора, взятые из различных классов 2L , 4L и 6L , не совместимы, а также любые два вектора, взятые из различных классов 4H , 5H , 6H и 7H , не совмести- мы. Следовательно, в соответствии с Утверждениями 4 и 5 приведенная оценка количества боковых выводов модулей ОККМ, реализующего опера- цию деления на 2 в кольце неотрицательных вычетов, является не только верхней, но и нижней оценкой, т.е. не существует доопределений булевых функций из кортежа ),( PXF , при которых 2<r . В случае конечных полей характеристики p и 1=w порядок поля P — простое число, которое для ОККМ с n КМ должно находиться в диа- пазоне nn P 22 1 <<− . Такие ограничения на возможные значения P сущест- венно увеличивают число векторов значений переменных, где функции из ),( PXF не определены, что предположительно может привести к уменьше- нию полученных оценок. В действительности же изменение оценок не про- исходит, поскольку при любом конкретном простом P из указанного диапа- зона всегда существуют значения X , при которых будут выполняться все соотношения, используемые как в определениях классов, так и в определе- ниях значений функций в соответствующих кортежах. Отсюда также следу- ет, что минимальное число боковых выводов модулей по обоим направле- ниям будет равно двум даже в случае, когда const=P . В.П.Тарасенко, А.К.Тесленко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 24 В работе [6] показано, что операции PZXZ mod)( += и =Z PZX mod)( −= в кольце неотрицательных вычетов реализуются на ОККМ со значением 2=r при условии конкретного доопределения булевых функ- ций из ),( PYXF , которое основывалось на следующем доопределении опе- раций — при любых YX , и P в диапазоне от 0 до 12 −n в случае сложения )( YXZ += , если PYX <+ )( и )( PYXZ −+= , если PYX ≥+ )( , а в слу- чае вычитания )( YXZ −= , если YX ≥ и )( PYXZ +−= , если YX < . Согласно изложенному, приведенный в работе [6] результат определяет верхнюю оценку числа боковых выводов модулей ОККМ при реализации операций сложения и вычитания в конечных полях характеристики 2>p при 1=w . В конечных полях функции из ),( PYXF определены на наборах аргументов, соответствующих простым значениям P в диапазоне nn P 22 1 <<− , а также значениям PYX <, . В связи с этим актуальным явля- ется доказательство существования (или отсутствия) доопределений функ- ций из ),( PYXF , позволяющих уменьшить эту оценку. Для доказательства воспользуемся Алгоритмом 2. Легко проверить, что множество векторов 0,jQ разбивается на следующие классы эквивалентности по отношению псевдоравенства: Класс 1L , где значение 0,jP не является остатком от деления простых P из заданного диапазона значений на 12 +j . Функции из кортежей ),( 0,1,11,1 jjnjn qUF +−+− , где ∈0,jq 1L не определены на всех значениях аргу- ментов. Класс 2L , где +0,jX <0,jY 0,jP . Класс 3L , где 0,0, jj XP ≤ + 1 0, 2 +< j jY , 0,0, jj PX < , 0,0, jj PY < . Класс 4L , где 0,0, jj XP ≤ + 1 0, 2 +< j jY , 0,0, jj PX ≥ , 0,0, jj PY < . Класс 5L , где 0,0, jj XP ≤ + 1 0, 2 +< j jY , 0,0, jj PX < , 0,0, jj PY ≥ . Класс 6L , где 0,0, jj XP ≤ + 1 0, 2 +< j jY , 0,0, jj PX ≥ , 0,0, jj PY ≥ . Класс 7L , где 0, 1 0,0, 1 22 j j jj j PYX +<+≤ ++ , 0,0, jj PX < , 0,0, jj PY < . Класс 8L , где 0, 1 0,0, 1 22 j j jj j PYX +<+≤ ++ , 0,0, jj PX ≥ , 0,0, jj PY < . Класс 9L , где 0, 1 0,0, 1 22 j j jj j PYX +<+≤ ++ , 0,0, jj PX < , 0,0, jj PY ≥ . Класс 10L , где 0, 1 0,0, 1 22 j j jj j PYX +<+≤ ++ , 0,0, jj PX ≥ , 0,0, jj PY ≥ . Класс 11L , где 0,0,0, 12 jjj j YXP +≤++ . Множество векторов 1,1 +− jnQ разбивается на следующие классы экви- валентности по отношению псевдоравенства: Класс 1H , где значение 11 +− j,nP не является частным от деления про- стых P из заданного диапазона значений на 12 +j . Функции из кортежей Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Системні дослідження та інформаційні технології, 2006, № 2 25 ),( 0,1,10, jjnj UqF +− , где 11,1 Hq jn ∈+− не определены на всех значениях аргу- ментов. Класс 2H , где <+ +−+− )1(),1(1,1 jnjn YX 11,1 −+− jnP . Класс 3H , где =+ +−+− )1(),1(1,1 jnjn YX 11,1 −+− jnP . Класс 4H , где =+ +−+− )1(),1(1,1 jnjn YX 11 +− j,nP , <+− 1,1 jnX 11 +− j,nP , <+− )1(),1( jnY 11 +− j,nP . Класс 5H , где =+ +−+− )1(),1(1,1 jnjn YX 11 +− j,nP , =+− 1,1 jnX 11 +− j,nP , 0)1(),1( =+− jnY . Класс 6H , где =+ +−+− )1(),1(1,1 jnjn YX 11 +− j,nP , 01,1 =+− jnX , =+− )1(),1( jnY 1,1 +−= jnP . Класс 7H , где >+ +−+− )1(),1(1,1 jnjn YX 11 +− j,nP , 1,11,1 +−+− < jnjn PX , <+− )1(),1( jnY 11 +− j,nP . Класс 8H , где >+ +−+− )1(),1(1,1 jnjn YX 11 +− j,nP , =+− 1,1 jnX 11 +− j,nP , <+− )1(),1( jnY 11 +− j,nP . Класс 9H , где >+ +−+− )1(),1(1,1 jnjn YX 11 +− j,nP , <+− 1,1 jnX 11 +− j,nP , =+− )1(),1( jnY 11 +− j,nP . Класс 10H , где >+ +−+− )1(),1(1,1 jnjn YX 11 +− j,nP , =+− 1,1 jnX 11 +− j,nP , =+− )1(),1( jnY 11 +− j,nP . При 0<j векторы из класса 1L поглощаются векторами из любого иного класса, векторы из классов 4L , 5L и 6L поглощаются векторами из класса 3L , векторы из классов 8L , 9L и 10L — векторами из класса 7L . Не вычеркнутыми останутся классы 2L , 3L , 7L и 11L т.е. 40, =je . При 0=j классы 3L , 6L , 7L , 8L и 9L пустые, векторы из класса 1L поглощаются, т.е. 0,0e также равно 4. Следовательно 2)( =← nO . При 2−< nj векторы из класса 1H поглощаются векторами из любого иного класса, векторы из классов 5H и 6H — векторами из класса 4H , век- торы из классов 8H , 9H и 10H — векторами из класса 7H . Не вычеркну- тыми останутся классы 2H , 3H , 4H и 7H , т.е. 41,1 =+− jne . При 2−= nj классы 2H , 4H , 7H , 8H и 9H пустые, а векторы из класса 1H поглощаются, т.е. 1,1 −− nne также равно 4. Следовательно, 2)( =→ nO . Легко убедиться, что любые два вектора, взятые из различных классов 2L , 3L , 7L и 11L при 0>j не совместимы, а также любые два вектора, взятые из различных классов 2H , 3H , 4H и 7H не совместимы. Следова- тельно, согласно Утверждениям 4 и 5, приведенные оценки количества бо- ковых выводов модулей являются не только верхними, но и нижними оцен- ками. В.П.Тарасенко, А.К.Тесленко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 26 Поэтому при реализации на ОККМ операции PYXZ mod )( += в ко- нечных полях характеристики 2>p при 1=w не существует доопределе- ний функций из ),( PYXF , при которых 2<r . Это же касается и случая const=P . В то же время вследствие большого числа вариантов поглощения векторов из классов 1L и 1H в соответствии с Алгоритмом 3 существует много вариантов доопределения функций из ),( PYXF , обеспечивающих 2=r , что может служить источником дальнейшей оптимизации по другим критериям. Аналогичные результаты можно получить и для операции =Z PYX mod )( −= . В работе [6] рассмотрена также реализация операции умножения PYXZ mod )( ∗= на основе ОККМ, реализующих операции =Z PYX mod )( += и PXZ mod )(2= . Альтернативным методом реализации операции PYXZ mod )(= является метод, базирующийся на операции PYXZ mod )(2 += . Воспользовавшись Алгоритмом 2, можно установить следующее. Чис- ло классов разбиения множества векторов 0,jQ по отношению псевдоравен- ства при любом 2,...,1,0 −= nj не превышает 22, а число классов, остав- шихся не вычеркнутыми, не превышает 12 ( 120, ≤je ). При всех значениях j , где 120, =je , векторы, входящие в любые два не вычеркнутые классы не совместимы. Отсюда следует, что 4)()[log](max)( 0,2 === ←← nLenH j . Аналогично число классов разбиения множества векторов 1,1 +− jnQ по отно- шению псевдоравенства при любом 2,...,1,0 −= nj не превышает 20, а число классов, оставшихся не вычеркнутыми, не превышает 10 ( 101,1 ≤+− jne ). При всех значениях j , где 101,1 =+− jne , векторы, входящие в любые два не вычеркнутые класса, не совместимы. Отсюда следует, что =→ )(nH 4)()[log](max 1,12 === →+− nLe jn . Это позволяет утверждать, что массовая операция PYXZ mod )(2 += в конечных полях характеристики 2>p при 1=w реализуема на ОККМ cо значением 4=r , причем не существует до- определений функций из ),( PYXF , позволяющих уменьшить значение r . ВЫВОДЫ Предложенные выше методика и алгоритмы совместной разделительной декомпозиции систем частично определенных булевых функций позволяют сформировать нижние и верхние оценки числа боковых выводов модулей ОККМ. Эти оценки определяют возможность реализации операций в конеч- ных полях на ОККМ с заданными конструктивными ограничениями относи- тельно их числа входов – выходов. Для массовых операций рассмотренная методика позволяет аналитическим путем (даже без использования компью- терных средств) определять возможность их реализации как комбинацион- Реализация операций в конечных полях на одномерном каскаде конструктивных модулей Системні дослідження та інформаційні технології, 2006, № 2 27 ных схем линейной сложности, и тем самым обеспечивать свойство нара- щиваемости структур, выполненных как ОККМ. Теоретические выкладки подтверждены конкретными примерами реализации массовых операций в конечных полях на ОККМ. Полученные результаты могут быть использова- ны при реализации любых преобразований ),...,,( 21 mXXXFZ = , в которых все разряды значений не определены на подмножестве значений аргументов. Рассмотренный конструктивный алгоритм определения внутренних структур отдельных КМ обусловливает возможность дальнейших исследо- ваний по их оптимизации относительно критериев сложности или быстро- действия. ЛИТЕРАТУРА 1. Березовский А.И., Задирака В.К., Шевчук Л.Б. О тестировании быстродействия алгоритмов и программ вычисления основных операций несимметричной криптографии // Кибернетика и системный анализ. — 1999. — № 5. — C. 59–66. 2. Палагин А.В., Опанасенко В.Н., Сахарин В.Г. Особенности проектирования цифровых устройств на современных кристаллах ПЛИС фирмы Xilinx // Проблемы управления и информатики. — 2001. — № 1 — C. 105–119. 3. Тесленко А.К. Совместная декомпозиция логических функций // Вестник Киевского политехн. ин-та. Серия автоматики и электроприборострое- ния. — 1975. — Вып.12. — C. 59–61. 4. Корнейчук В.И., Тарасенко В.П., Тесленко А.К. Исследование сложности реали- зации функций на одномерном каскаде модулей // Автоматика и вычисли- тельная техника. — 1977. — № 5. — C. 5–11. 5. Журавлев Ю.И. Алгоритмы построения минимальных дизъюнктивных нор- мальных форм для функций алгебры логики // В кн.: Дискретная математи- ка и математические вопросы кибернетики. Т.1. — М.: Наука, 1974. — С. 67–97. 6. Тарасенко В.П., Тесленко А.К. Реализация основных арифметических операций над остатками на одномерных каскадах конструктивных модулей // УСиМ. — 2003. — № 3(185) — C. 29–42. Поступила 15. 06. 2005

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

Institution

Ähnliche Einträge