About the numbers of the injective and of the super-increasing vectors and some particularities of the strong modular mu.pdf В 1978 г. Р. Меркль и М. Хеллман [1] предложили знаменитую ранцевую криптоси-стему. В ее основе лежит преобразование сверхрастущего вектора A = (а1, a 2 , . . . , an)(aj Е N, i = 1 , . . . , n) с помощью сильного модульного умножения относительно нату-/ n nрального модуля m Е I . aj , 2 . aj и натурального множителя t Е (1, m) в инъек-\i=1 i=1 Jтивный вектор B = (b1, b 2 , . . . , bn) (bj Е N, i = 1 , . . . , n), который служит открытымключом.В настоящей работе рассматриваются вопросы о том, какую часть от множествавсех возможных векторов размерности n составляют инъективные и сверхрастущиевекторы, и о равномерности покрытия множества упорядоченных инъективных век-торов размерности n векторами, полученными из сверхрастущих векторов с помощьюоперации сильного модульного умножения и процедуры сортировки элементов век-тора по возрастанию. Определения понятий упорядоченного (возрастающего), инъ-ективного и сверхрастущего вектора, сильного модульного умножения можно найтив монографии [2].О порядке роста числа инъективных и сверхрастущих векторовОбозначим через F1(n, M) число упорядоченных инъективных векторов размерно-сти n, максимальный элемент которых равен M, а через F2(n, M) -число сверхрасту-щих векторов размерности n, максимальный элемент которых равен M.Число векторов с максимальным элементом M, имеющих размерность n, равноn n( M - 1)n -1Y] С ? (M - 1 ) n - k , из чего можно заключить, что F1(n, M) ^ j , т. е. 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 - 2 n - 1 + 1 \( M - 2 n - 1 + 1 \ n - 2 1 Например, F2(n, M - 1Д 2^ ) при n^2 и M^2n - 1 .Это позволяет заключить, что функции F1(n, M) и F2(n, M) ведут себя подобно поли-1 M ! F1(n,M) r F2(n,M)номам степени n - 1 от M, а пределы lim - , lim -M Е c n ( M - 1 ) n - k ^ c n ( M - 1 ) n -kfc=1 fc=1при фиксированном n существуют, конечны и не равны 0.Отметим, что F2(n, M) = 0 при фиксированном n ^ 2 и M < 2n - 1.О некоторых особенностях сильного модульного умноженияРассмотрим множество сверхрастущих векторов размерности n, максимальныйэлемент которых строго меньше M. Операция сильного модульного умножения с мо-дулем m ^ M с последующим применением процедуры сортировки элементов векторапо возрастанию отображает указанное множество во множество упорядоченных инъ-ективных векторов размерности n, максимальный элемент которых строго меньше M.Обозначим через F3(n, < M) число упорядоченных инъективных векторов размер-ности n, максимальный элемент которых строго меньше M (т. е. мощность множестваупорядоченных потенциальных векторов шифрования).Обозначим через F4 ( n ,< M) число различных упорядоченных инъективных век-торов размерности n, полученных с помощью сильного модульного умножения от-носительно модуля m и всех возможных множителей 1 < t < m из сверхрастущихвекторов размерности n, максимальный элемент которых строго меньше M, при усло-вии, что для каждого сверхрастущего вектора A = (а1 , . . . , an) модуль m пробегаетn nинтервал (. a,, min(2 . a,,M)]. Таким образом, F4(n, < M) -мощность множества,=1 ,=1упорядоченных действительных векторов шифрования.Различные тройки (сверхрастущий вектор, модуль, множитель) могут определятьодин упорядоченный инъективный вектор. Число троек, определяющих один упоря-доченный инъективный вектор, назовем числом представлений данного вектора.Обозначим через F(n, < M) отношение F4(n, < M)/F3(n, < M).Проведенные вычислительные эксперименты позволяют выдвинуть следующую ги-потезу.Гипотеза. При фиксированном n . N значение F(n, < M) достигает 0,9 призначениях M, близких к 22n.Так, при n = 3 и 4 значение F(n, < M) достигает 0,9 при M = 22 n - 2 + 2n - 1.В ходе проведения компьютерных экспериментов установлено, что в результатеприменения к сверхрастущим векторам операции сильного модульного умножения(при выборе модуля и множителя описанным выше способом) с последующим при-менением процедуры сортировки элементов вектора по возрастанию чаще получаютсявекторы, имеющие малую евклидову длину. На рис. 1 приведены результаты одногоиз экспериментов для n = 3 и M = 34. Каждому натуральному числу на оси Lnсоответствует упорядоченный инъективный вектор. Меньшим натуральным числамсоответствуют векторы с меньшей евклидовой длиной. По оси Representation numberотложено число представлений упорядоченного инъективного вектора.Рис. 1. Число представлений упорядоченных инъективных векторов при n = 3, M = 34

Скачать электронную версию публикации