О порядке роста числа инъективных и сверхрастущих векторов и некоторых особенностях сильного модульного умножения

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 61+519. 7
О ПОРЯДКЕ РОСТА ЧИСЛА ИНЪЕКТИВНЫХ И СВЕРХРАСТУЩИХ ВЕКТОРОВ И НЕКОТОРЫХ ОСОБЕННОСТЯХ СИЛЬНОГО МОДУЛЬНОГО УМНОЖЕНИЯ
Д. М. Мурин
В 1978 г. Р. Меркль и М. Хеллман [1] предложили знаменитую ранцевую криптосистему. В ее основе лежит преобразование сверхрастущего вектора A = (ai, a2,…, an)
(a Е N, i = 1,…, n) с помощью сильного модульного умножения относительно нату/ n n
рального модуля m Е (^2 ai, 22 ai и натурального множителя t Е (1, m) в инъек-
i=1 i=1
тивный вектор B = (b1, b2,.. , bn) (bi Е N, i = 1,…, n), который служит открытым ключом.
В настоящей работе рассматриваются вопросы о том, какую часть от множества всех возможных векторов размерности n составляют инъективные и сверхрастущие векторы, и о равномерности покрытия множества упорядоченных инъективных векторов размерности n векторами, полученными из сверхрастущих векторов с помощью операции сильного модульного умножения и процедуры сортировки элементов вектора по возрастанию. Определения понятий упорядоченного (возрастающего), инъективного и сверхрастущего вектора, сильного модульного умножения можно найти в монографии [2].
О порядке роста числа инъективных и сверхрастущих векторов
Обозначим через F1(n, M) число упорядоченных инъективных векторов размерности n, максимальный элемент которых равен M, а через F2 (n, M) -число сверхрастущих векторов размерности n, максимальный элемент которых равен M.
Число векторов с максимальным элементом M, имеющих размерность n, равно
n n (M — 1) n-1
У2 cn (M — 1) n-k, из чего можно заключить, что F1(n, M) ^ -----: --, т. е. F1(n, M)
k=1 n!
при фиксированном n ограничено сверху некоторым полиномом степени n — 1 от M.
Оказывается, что справедлива следующая
Теорема. При фиксированном n ^ 2 и M ^ 2n-1 выполняется неравенство
F1(n, M) ^ F2(n, M) ^ P (M), где P (M) -некоторый полином (n — 1)-й степени от M.
ч (M — 2n-1 + 1 w M — 2n-1 + 1 n-2 1
Например, F2(n, M)^-------2^=2-------1Д------2™------/ при n2 и M^2n 1.
Это позволяет заключить, что функции F1(n, M) и F2(n, M) ведут себя подобно поли, M F1(n, M) F2(n, M)
номам степени n — 1 от M, а пределы lim ------------------, lim ----------------
M^ Е cn (m — 1) n-k? cn (m — 1) n-k
k=1 k=1
при фиксированном n существуют, конечны и не равны 0.
Отметим, что F2(n, M) = 0 при фиксированном n ^ 2 и M & lt- 2n-1.
О некоторых особенностях сильного модульного умножения
Рассмотрим множество сверхрастущих векторов размерности n, максимальный элемент которых строго меньше M. Операция сильного модульного умножения с модулем m ^ M с последующим применением процедуры сортировки элементов вектора по возрастанию отображает указанное множество во множество упорядоченных инъективных векторов размерности n, максимальный элемент которых строго меньше M.
Обозначим через F3(n, & lt- M) число упорядоченных инъективных векторов размерности n, максимальный элемент которых строго меньше M (т. е. мощность множества упорядоченных потенциальных векторов шифрования).
Обозначим через F4(n,& lt- M) число различных упорядоченных инъективных векторов размерности n, полученных с помощью сильного модульного умножения относительно модуля m и всех возможных множителей 1 & lt- t & lt- m из сверхрастущих векторов размерности n, максимальный элемент которых строго меньше M, при условии, что для каждого сверхрастущего вектора A = (ai,…, an) модуль m пробегает
n n
интервал (^ aj, min (2 a", M)]. Таким образом, F4(n, & lt- M) -мощность множества
i=1 i=1
упорядоченных действительных векторов шифрования.
Различные тройки (сверхрастущий вектор, модуль, множитель) могут определять один упорядоченный инъективный вектор. Число троек, определяющих один упорядоченный инъективный вектор, назовем числом представлений данного вектора.
Обозначим через F (n, & lt- M) отношение F4(n, & lt- M)/F3(n, & lt- M).
Проведенные вычислительные эксперименты позволяют выдвинуть следующую гипотезу.
Гипотеза. При фиксированном n? N значение F (n, & lt- M) достигает 0,9 при значениях M, близких к 22n.
Так, при n = 3 и 4 значение F (n, & lt- M) достигает 0,9 при M = 22n-2 + 2n — 1.
В ходе проведения компьютерных экспериментов установлено, что в результате применения к сверхрастущим векторам операции сильного модульного умножения (при выборе модуля и множителя описанным выше способом) с последующим применением процедуры сортировки элементов вектора по возрастанию чаще получаются векторы, имеющие малую евклидову длину. На рис. 1 приведены результаты одного из экспериментов для n = 3 и M = 34. Каждому натуральному числу на оси Ln соответствует упорядоченный инъективный вектор. Меньшим натуральным числам соответствуют векторы с меньшей евклидовой длиной. По оси Representation number отложено число представлений упорядоченного инъективного вектора.
Рис. 1. Число представлений упорядоченных инъективных векторов при п = 3, М = 34
ЛИТЕРАТУРА
1. Merkle R. C. and Hellman M. E. Hiding information and signatures in trap-door knapsacks // IEEE Trans. Inform. Theory. 1978. V. IT-24. P. 525−530.
2. Саломаа А. Криптография с открытым ключом. М.: Мир, 1995. 318 с.
УДК 512. 542. 74
ОПИСАНИЕ КЛАССА ПОДСТАНОВОК, ПРЕДСТАВИМЫХ В ВИДЕ ПРОИЗВЕДЕНИЯ ДВУХ ПОДСТАНОВОК С ФИКСИРОВАННЫМ ЧИСЛОМ МОБИЛЬНЫХ ТОЧЕК. II
А. Б. Пичкур
Пусть подстановка G Є Sn, T (G) С {1,…, N} - множество мобильных точек подстановки G, 2 ^ q ^ N, rN (q) = {G Є SN: |r (G)| = q} - множество всех подстановок степени N, имеющих ровно q мобильных точек.
В предшествующей работе (см. [1]) полностью описано строение множества rN (q) ¦ ГN (q) при 4 ^ q ^ N/2 и N ^ 8.
В данной работе описано множество всех подстановок из Tn (q) ¦ Tn (q +t) при t ^ 1. Этот результат имеет практические приложения в криптографии.
Сначала приведём результаты о строении множества Tn (q) ¦ Tn (q + 1). Утверждение 1. Если N ^ 6, 2 ^ q1 & lt- q2 & lt- N, то имеет место включение
Tn (qi) ¦ Tn (q2) С Tn (qi + 1) ¦ Tn (q2 + 1).
Теорема 1. Пусть N ^ 8, 3 ^ q ^ N/2, G Є SN. Если 1 & lt- |T (G)| ^ 2q — 1, то существуют подстановки H1 Є Tn (q), H2 Є Tn (q + 1), для которых выполняется равенство G = H1 ¦ H2.
Далее рассмотрим, какие подстановки из множеств Tn (2q +1), Гn (2q) принадлежат произведению Tn (q) ¦ Tn (q + 1).
Утверждение 2. Пусть N ^ 4, 2 ^ q & lt- N/2, подстановка G Є Tn (2q + 1) является произведением r неединичных циклов, длины которых равны m1, ш2,…, шг,
r
E Ші = 2q + 1. Подстановка G принадлежит множеству Tn (q) ¦ Tn (q + 1) в том и
i=1
только в том случае, когда существует такое подмножество {?1,…, г^} С {1,…, r}, что Ші1 ±+ Шік = q.
Утверждение 3. Пусть N ^ 4, 2 ^ q ^ N/2, подстановка G Є Tn (2q) является произведением r неединичных циклов, длины которых равны ш1, ш2, …, mr,
Г
ші = 2q. Подстановка G принадлежит множеству Tn (q) ¦ Tn (q + 1) в том и только
i=1
в том случае, когда выполнено условие: существует ?0 Є {1,…, r} и существует такое подмножество {?1,…, } С {1,…, r} {?0}, что ші0 & gt- 2 и q — ші1 + ші2 + ¦ ¦ ¦ + mik Є
Є {2,…, Шіо — 1}.
Итак, в теореме 1 и утверждениях 2 и 3 полностью описано строение множества Tn (q) ¦ Tn (q + 1) при 3 ^ q ^ N/2.
Наконец, приведем результаты о строении множества Tn (q) ¦ Tn (q +1), t ^ 2.
Теорема 2. Пусть N& gt- 10, 2 ^ t & lt- N — 2, 2 ^ q& lt- (N — t)/2 + 1, G Є SN. Если t ^ |T (G)| ^ 2q + t — 2, то существуют подстановки H1 Є Tn (q), H2 Є Tn (q + t), для которых выполняется равенство G = H1 ¦ H2.

ПоказатьСвернуть
Заполнить форму текущей работой