close

Вход

Забыли?

вход по аккаунту

?

Сущность и математические свойства одного класса многомодульных преобразований.

код для вставкиСкачать
УДК 519.713
СУЩНОСТЬ И МАТЕМАТИЧЕСКИЕ
СВОЙСТВА ОДНОГО КЛАССА
МНОГОМОДУЛЬНЫХ
ПРЕОБРАЗОВАНИЙ
ГРИНЕНКО Т.А.
Предлагается и теоретически обосновывается алгоритм построения псевдослучайных последовательностей с требуемыми свойствами. Этот алгоритм основывается на применении многомодульных преобразований.
Рассматриваются сущность и математические свойства
многомодульных преобразований.
В ряде приложений необходимо применять псевдослучайные последовательности (ПСП) с требуемыми свойствами [1]. Основными из этих свойств, по
которым предъявляются сложные требования, являются: основание алфавита ? m, период повторения ?
L, восстанавливаемость, псевдослучайные свойства,
а также структурные свойства.
К настоящему времени разработан ряд алгоритмов
и средств формирования ПСП. Основной их особенностью является то, что они строятся для двоичного
основания, т.е. m=2. Известен также класс линейных
m-ичных последовательностей [2, 3]. Однако этот
класс последовательностей обладает неудовлетворительными структурными свойствами в смысле значительной зависимости появления символов в последовательности. Так, для определения закона формирования таких ПСП необходимо и достаточно
получить безошибочно 2l символов, где l ? база
линейного рекуррентного регистра [4]. Поэтому
весьма важной и необходимой является задача разработки математических алгоритмов и средств с
заведомо необходимыми свойствами и основанием
алфавита. К наиболее перспективному классу таких
преобразований, на наш взгляд, относится класс
многомодульных преобразований.
Рассмотрим сущность и свойства преобразования
элементов полей Галуа GF(p), которое в дальнейшем
будем называть многомодульным. Это преобразование может использоваться при создании средств
формирования ПСП.
Общее правило формирования последовательности многомодульного преобразования в поле GF(p)
имеет вид
ai
bi
ai 1 T Q mod P ,
a i mod P1, P2 ,..., Pn 1, Pn , m ,
(1)
где ai и ai-1 ? собственно i-й и (i-1)-й элементы
формируемой последовательности;TX ? Q-й первообразный элемент поля GF(p); P1,P2,},Pn ? промежуточные модули; m-основание алфавита.
В соотношении (1) должно выполняться условие
P !! P1 !! P2 !!! !! Pn !! m t 2 , (2)
причем Pn ? произвольное основание алфавита
символов формируемой ПСП.
Применение правила (1) позволяет, с одной стороны, существенно повысить кодовую устойчивость,
94
т.е. устойчивость против определения закона формирования ПСП, а с другой ? формировать последовательность элементов с требуемым основанием алфавита.
Прежде чем перейти к методам и средствам
формирования таких последовательностей и изучению их структурных и ансамблевых свойств, приведем ряд основных понятий и определений из теории
многомодульных преобразований, сформулировав
их в виде утверждений.
Определение. Показателем a по модулю m (будем
называть его Pm(a)) называется наименьший положительный показатель степени a, сравнимый с единицей по модулю m [2].
Согласно определению, Pm(a) означает положиP (a )
{ 1(mod m) , причем
тельное число, такое что a m
при всех r , таких что 1 d r d Pm (a ) , a r z 1(mod m) .
Утверждение 1. Если a по модулю m принадлежит
показателю Pm(a), то числа
1 a 0 , a 1 , ... , a Pm ( a ) 1
по модулю m несравнимы.
Учитывая определение и утверждение 1, можно
построить последовательность {X}={x1,x2,,xn} вида
xi
Rm T i , i
0,1, ..., Pm T ,
(3)
(TL) ? остаток от деления целого числа TL на m,
где Rm
который будет иметь период L = Pm(q ), причем
каждое значение xi на периоде L встречается только
один раз.
Для построения управляющей q-ичной ПСП
{B}={b1,b2, , bn} предлагается использовать следующее правило:
bi
Rq R m T i
Rq x i
, i = 0,1,..., Pm T ,
(4)
где 1 < q < m, q < Pm(q ).
Пусть m=pD , где p ? простое число, D ? любое
целое положительное число. Тогда существует первообразный элемент q по модулю m, который принадлежит показателю
(5)
Pm T M m p D 1 p 1 ,
где M(m)? функция Эйлера от m. Учитывая утверждение 1, правило формирования ПСП {B} можно
переписать в следующем виде:
bi
Rq Rm T i , 0 d i d p D 1 p 1 ,
Rq x i
(6)
pa
.
где 1 < q <
Частотой появления элемента a на отрезке периодической последовательности длиной в период будем называть отношение числа появления элемента
a, т.е. числа элементов отрезка, совпадающих с a, к
длине отрезка, т.е. числу элементов отрезка.
Определим частоту появления каждого из элементов 0,1,2,...,q1-1 на отрезке последовательности bi
(6) длиной M(pD).
Утверждение 2. Пусть pD = M1q+R1,
pD = M2q+R2,
где R1 Rq p D 1 , R2 Rq p D .
Тогда частота появления каждого из элементов
bi={0,1,2,...,q-1} на отрезке последовательности bi
длиной L =M(pD)= pD(p-1) равна либо М2-М1, либо
М2-М1+1, либо М2-М1-1.
РИ, 1999, № 2
Доказательство. Обозначим через N D упорядоp
ченное множество наименьших неотрицательных
вычетов по модулю pD, т.е.
N D
p
0,1,2 ,... , p D 1 .
(7)
Пусть N * D обозначает упорядоченное подмноp
жество в N D , состоящее из элементов взаимноp
простых с p, а N D ? упорядоченное подмножество
p
в N D , состоящее из элементов не взаимно-простых
p
с p. Для N D ,
p
N *D
p
, N D верны соотношения
p
N D = N* D * N D ,
p
p
p
N D
p
N D \ N *D ,
p
p
N* D N D
p
p
(8)
‡.
Перейдем в упорядоченном множестве N D к
p
остаткам по modq. Получившееся множество остатков обозначим через N D . Тогда
p ,q
N D
p ,q
­
Ѕ
°
°
, ,2,..., q 1,...,0,1,2,..., q 1,0,1,2,..., R2 1ѕ. (9)
®01
°
°
M2 ?????
Ї
ї
Таким образом, в N D элементы 0,1,2,...,R2-1
p ,q
встречаются М2+1 раз каждый, а элементы R2,R2+1,...,
q?1 встречаются М2 раз каждый.
Рассмотрим подмножество N D . Его элементы
p
имеют вид kp, k = 0 , 1 , 2, ..., pD-1?1 и подмножество
N D содержит pD-1 элементов.
p
Если p имеет при делении на q остаток r=0 (p и q
взаимно-простые), т.е. r Rq ( p) z 0 , то остатки элементов множества N D при делении на q совпадают
p
с остатками элементов последовательности вида {0,
r, 2r,..., (pa-1?1)r}, т.е.
­
°
N D
, r ,2r ,... , (q 1)r , ... ,0, r ,2r , ..., (q 1)r ,
®0
p ,q
°
M1 ?????
Ї
(10)
Ѕ
0, r,2r, ..., (R 1 -1)r ѕ ,
ї
где (r,q)=1, иначе НОД(r,q) делил бы простое число
p. Так что среди остатков элементов 0, r, 2r,..., (q-1)r
ровно по одному разу встречаются все остатки 0, 1,
2,..., q-1 (может быть в другом порядке), и все остатки
элементов 0, r, 2r,..., (R1-1)r различны. СледовательРИ, 1999, № 2
но, среди элементов множества N D
каждый
p ,q
остаток 0, 1, 2,..., q-1 встречается либо М1, либо М1+1
раз.
Если r Rq ( p D 1 ) 0 , то очевидно, что М1=0.
Так как, не обращая внимания на упорядоченность, имеет место соотношение
§ M pD 1 · °Ѕ
°­
ёѕ N D \ N D ,
®1, R D T , R D T 2 ,..., R D Ё T
p
p
p ©
p
p
№ °ї
°?
то, не обращая внимание на упорядоченность, имеет
место соотношение
­°
Ѕ°
®b0 , b1 , b2 , ..., b Ё§ D ё· ѕ
M © p № 1 °
°?
ї
N D \ N D . (11)
p ,q
p ,q
Из (11) следует справедливость утверждения 2, из
которого вытекают следующие следствия.
Следствие 1. Если r1 = r2 z 0, q < pD-1, то все
элементы последовательности {B}={b1,b2,,bn} будут
иметь одну и ту же частоту M2 - M1.
Действительно, пусть
pD
тогда q M 2 M1
M 2 q r2 , p D 1
p D p D 1
M 1q r1 ,
M p D и, следователь-
но, qЅM(p D). Но так как M(p D) есть период последовательности xn , то все элементы последовательности
bn имеют одну и ту же частоту.
Следствие 2. Если r1 = r2 z 0, pD-1 < q < pD, то в
последовательности bn имеют место две частоты M2
и M2 + 1. Действительно, пусть
p D M 2 q r2 , p D 1 M 1q r1 ,
так как pD-1 < q, то M1 = 0 и элементы 1,2, , r-1 будут
иметь частоту M2 + 1, а элементы r, r + 1,q - 1 ?
частоту M2.
Следствие 3. Если r1 z r2, 2 d q < pD , то в
последовательности bn имеют место по крайней мере
две частоты, одна из которых равна M2 - M1.
Определим наименьший положительный период
периодической последовательности bi .
Утверждение 3. Пусть последовательность bi определяется как
Rq §Ё R D T i ·ё , 0 d i d M p D ,
(12)
© p
№
где 2dqdpD, qzpz, z=0,1,},D-1.
Тогда последовательность bi будет иметь положительный период L =M(pD).
Доказательство. Если r1zr2, то (следствие 3) элементы последовательности bi будут иметь различные
частоты, одной из которых является частота M2 ?M1.
Пусть последовательность bi имеет период
bi
d d M p D , kd
M p D , тогда k должно делить все
частоты элементов 0, 1, 2,..., q-1. Но для любой пары
частот имеют место соотношения
M 2 M1 , M 2 M1 1 1 ,
M 2 M1 , M 2 M1 1
1.
Следовательно, M p D = kd 1 u d d .
Если в последовательности элементы имеют три
различные частоты, тогда
95
M 2 M 1 1, M 2 M 1 , M 2 M 1 1
и d
M p
D
1 ,
.
Если r1 = r2, pD-1 < q < pD, тогда (следствие 2) имеет
место соотношение M 2 1, M 2
но, d
1 и, следователь-
M pD .
Если r1 = r2, q < pD-1, то (следствие 1) все элементы
последовательности bi имеют одинаковую частоту
M2-M1.
Пусть последовательность bi имеет период
d d M p D , kd
M p D . Предположим, что последо-
вательность bi имеет четное количество периодов k.
Тогда, очевидно, b0 b § D · или
M Ё© p ё№
2
T 0 mod p D { T
MЁ§© pD ё·№
2
mod p D mod q .
Так как T ? первообразный элемент, а p ? простое
число, то
M §Ё© pD ·ё№
T
2
{ p D 1 mod p D .
Следовательно, можно записать
p D 1 { 1 mod ??? p D { 2 mod q .
УДК 658.52.011.56
ОБ ОДНОМ ОБОБЩЕНИИ ЗАДАЧИ
О НАЗНАЧЕНИЯХ
ПАНИШЕВ А.В., КОСТИКОВА М.В.,
СКАКАЛИНА Е.В.
Рассматриваются результаты изучения задачи о назначении. Предлагается использование теории паросочетаний для нахождения множества оптимальных решений задачи с заданными свойствами. Для ее решения
предлагается модифицированный алгоритм Кана-Мункреса.
Изложенные здесь результаты представляют попытку углубить знания об известной задаче о назначении, располагающей широким спектром практических приложений на транспорте.
Доказано, что задача о назначении эффективно
разрешима. При этом предполагается, что для достижения оптимума ее целевой функции достаточно
найти единственное решение задачи.
Однако в практических ситуациях возникает
потребность в нахождении множества оптимальных
решений с заданными свойствами. Результаты изучения задачи о назначении в подобной постановке
составляют содержание данной статьи. Они излагаются в терминах теории паросочетаний и связанной
с нею проблемой оптимизации на графах и сетях.
Используемые здесь определения и понятия заимствованы из [1].
96
Но, так как все элементы bi имеют одну частоту,
то q | M p D
или
p D1 p 1 { 0 mod q , откуда
p { 1 mod q . Тогда и p D { 1 mod q . Таким образом,
мы получили противоречие и, следовательно, последовательность bi имеет период L =M(pD).
Предположим, что последовательность bi имеет
нечетное количество периодов k.
Утверждение 3 доказано.
Таким образом, доказано, что используя выражение (6), можно построить m-ичные ПСП сколь
угодно большого периода. При этом также теоретически обосновано, что на всей длине периода появление любого числа из интервала [0, q ? 1] практически равновероятно, если выполняется условие (2).
Литература: 1. Завадская Л.А., Фаль А.М. Криптографически сильные генераторы псевдослучайных последовательностей // Безопасность информации.1997. №1. С.711. 2. Горбенко И.Д. Новые алгоритмы синтеза оптимальных дискретных сигналов // Радиотехника и электроника АН СССР, 1989. № 11. С.18-25. 3. Горбенко И.Д.
Свойства характеристических дискретных сигналов //
Радиотехника и электроника, 1990. № 2. С.11-20. 4.
Горбенко И.Д. Теория дискретных сигналов. Ч 1. Оптимальные дискретные сигналы с одно-двух- уровневой
ПФАК. Учебное пособие. МО СССР, 1983. С.55-69.
Поступила в редколлегию 07.06.99
Рецензент: д-р техн. наук Стасев Ю.В.
Гриненко Татьяна Алексеевна, инженер кафедры ЭВМ
ХТУРЭ. Научные интересы: криптографические методы
защиты информации в компьютерных системах. Адрес:
Украина, 61726, Харьков, пр. Ленина, 14, тел. 40-94-13.
Пусть S ? совершенное паросочетание в двудольном графе G=(V, E) с разбиением множества вершин
V=X‰Y, где X=Y, D
Y
m и Eij0
m
? заданная
матрица весов ребер графа G . Определим вес
паросочетания S как сумму весов его ребер xi , y j
xi Џ X , y i Џ Y :
US
¦ Eij0
xi , y j ЏS
.
Упорядочим по невозрастанию веса его ребер. В
результате получим последовательность
E1 S t E 2 S t ... t E m S .
Будем говорить, что последовательность весов
ре бер
сове рше нного
паросочетан ия
S E1 S t E 2 S t ... t E m S совпадает с последовательностью весов ребер совершенного паросочетания
S' E1 Sc t E 2 Sc t ... t E m Sc , если для всех i,
E i S E i Sc .
Для заданной матрицы E 0
ij
m
i 1, m ,
найдем паросочета-
ние S* с максимальным весом:
U S
max U S ,
SЏ p
(1)
p ? множество всех совершенных паросочетаний.
РИ, 1999, № 2
Документ
Категория
Без категории
Просмотров
5
Размер файла
244 Кб
Теги
одного, математические, свойства, класс, преобразование, многомодульных, сущность
1/--страниц
Пожаловаться на содержимое документа