Условия выделимости весовых коэффициентов из сумм с членами последовательностей двух видов

Полный текст

Необходимость в обоснованности процессов шифрования — расшифрования конфиденциальных текстов с алгебраическими преобразованиями последовательно получаемых суммарных величин, слагаемые которых содержат свободные и весовые сомножители [1], требует соблюдения условий выделимости данных весовых сомножителей — целочисленных весовых коэффициентов. Указанные алгебраические преобразования совершаются с применением следующего соотношения: ∀g ∈ Ip−1 = 1, . . . , p − 1 : g bp−γ+2 cp−γ+2 /c∆+1 = b∆+1 + ϕ(∆); Φ− γ=1 p ∈ N\{1} — общее количество весовых коэффициентов; g — индекс шага, выполняемого в процессе последовательного нахождения этих коэффициентов; 91 А. И. Н и к о н о в Φ = Φ(p) — основная сумма, то есть число, присылаемое адресату-дешифровальщику; b, c — символы компонентов слагаемых — соответственно весовых коэффициентов и свободных множителей, произведения которых, имеющие вид bl cl , l = 1, . . . , p, образуют члены основной последовательности, причём bl ∈ N ∪ {0}, ∃bl = 0, cl ∈ R+ \{0}; (1) ϕ(∆) = Φ(∆)/c∆+1 ; величина ϕ(∆) называется относительным суммарным остатком (ОСО), содержащим, в свою очередь, компонент — безотносительный суммарный остаток ∆ bl cl ; Φ(∆) = l=1 ∆ = p − g — целочисленный аргумент последовательно формируемой величины ϕ(∆); ∆ ∈ Ip−1 ; величину c∆+1 назовём внешним (по отношению к остаточной последовательности bl cl , l = 1, . . ., ∆) членом. Последовательность cl , l = 1, . . ., p, или cl , l = 1, . . ., ∆, называется соответственно основной или остаточной последовательностью свободных множителей. Рассматриваемый ОСО по условию выделимости должен оставаться внутри интервала допустимых отклонений от целочисленных значений весовых коэффициентов. Его рамки задаются в общем случае слева путём указания числа δ− 0, а справа — числа δ+ 0. Ни одного g ∈ Ip−1 , для которого соответствующее условие выделимости не выполняется, быть не должно. Целью настоящей работы является нахождение условий выделимости как для знакопостоянных, так и для знакочередующихся слагаемых из основной суммы: членов геометрической прогрессии, а также членов цепочки одинаковых натуральных степеней натуральных чисел. Введём несколько типовых условий выделимости: 1) 0 < δ− , δ+ < 1; интервал допустимых отклонений — двузначный, а его протяжённость может превышать единицу; 2а) 0 < δ− + δ+ < 1; интервал допустимых отклонений — двузначный, а его протяжённость может быть уменьшена сравнительно с единицей; 2б) 0 δ+ < 1, δ− = 0 или 0 δ− < 1, δ+ = 0; значения точечных элементов интервала допустимых отклонений имеют одинаковый знак или нулевое значение, а протяжённость этого интервала снижена сравнительно с единицей. Если та или иная рассматриваемая нами последовательность подходит для реализации типовых условий выделимости 2б, то её следует признать также подходящей и для любого условия выделимости, относящегося к типам 1, 2а. Границы интервала допустимых отклонений для условия выделимости могут быть установлены более или менее удачно в зависимости от степени адекватности их задания возможным значениям, фактически присущим количественному представлению ОСО. Нахождение условий выделимости будем производить, выявляя характерные свойства ОСО (1), присущие их второму типу. Ниже будут формироваться относительные суммарные остатки с максимальными значениями весовых коэффициентов вида bl = bm > 1 [1]: ϕ+ (∆) = max ϕ(∆) = bm S∆ /c∆+1 ; B 92 ϕ+ (∆), S∆ /c∆+1 > 0; Условия выделимости весовых коэффициентов из сумм . . . ϕ− (∆) = min ϕ(∆) = bm S∆ /c∆+1 ; B ϕ− (∆), S∆ /c∆+1 < 0; ∆ B = {b1 , . . . , bp }, S∆ = cl . l=1 Здесь величина S∆ — суммарный остаток, относящийся соответственно к остаточной последовательности свободных множителей cl , l = 1, . . . , ∆. Величины ϕ+ (∆), ϕ− (∆) образуют множество, элемент которого обозначим через ex ϕ(∆). Сами же значения суммарных остатков могут быть найдены при использовании в качестве основной последовательности геометрической прогрессии — с помощью известного выражения суммы её членов [2], а при использовании в указанном качестве последовательности равных друг другу натуральных степеней натуральных чисел — с помощью либо непосредственного выражения их суммы, либо известного комбинаторного способа [3, 4]. Заключительный момент в рассмотрении условия выделимости представляется решением двойного неравенства, выражающего это условие; его левая и правая части определяются заданными границами интервала допустимых отклонений, а центральная часть является записью выражения анализируемого ОСО. Теперь объясним подробнее правила индексации относительных суммарных остатков. Надстрочные индексы ОСО указывают на следующее: первый — на знак данного ОСО; второй, если он окажется необходимым, — на вид используемой основной или остаточной последовательности (г — геометрическая прогрессия, р — последовательность с натуральными равностепенными членами). Подстрочные индексы ОСО указывают на следующее: первый — на характер используемой последовательности (п — знакопостоянная, ч — знакочередующаяся); второй, если он окажется необходимым, — на нечётность либо чётность числа ∆ (o — нечётное, e — чётное). Кроме того, положим, что после символа ϕ указывать в скобках символ ∆ не обязательно. Сделанные нами замечания относятся к относительным суммарным остаткам, соответствующим как знакопостоянным, так и знакочередующимся основным и остаточным последовательностям и соответствующим им суммам, причём объём замечаний достаточен для того, чтобы начать выработку условий выделимости, связанных со знакопостоянными последовательностями. Получим сперва условие выделимости, использующие остаточную последовательность, которая представляется знакопостоянной геометрической прогрессией (2) cl = cг = q l = (am )l , l = 1, . . . , ∆; пl q — знаменатель прогрессии и её же первый член aг ; a ∈ R+ \{0}, m ∈ N. п1 Нижний и верхний буквенные индексы величин cг , aг имеют уже объясп1 пl нённый смысл: п — знакопостоянная последовательность; г — геометрическая прогрессия. Первый вариант представления условия выделимости имеет вид двойного неравенства 0 ϕ+г (∆) < δ+ , ∆ ∈ {1, . . . , p − 1}. п Числитель ОСО, располагаемый в центральной части этого неравенства, есть сумма членов геометрической прогрессии, а член c∆+1 занимает именно внеш93 А. И. Н и к о н о в нее положение относительно прогрессии (2). Следовательно, рассматриваемое условие выделимости может быть выражено как 0 ϕ+г (∆) = b+ /(q − 1) п m (q ∆ − 1)/q ∆ < 1, b+ = bm /δ+ . m Если положить q − 1 > 0, то будем иметь 0 < (q ∆ − 1)/q ∆ < 1. Далее получаем двойное неравенство 0 b+ /(q − 1) < 1, откуда следует появление m требования q > b+ +1. Обеспечение этого требования и позволяет реализовать m рассматриваемый первый вариант условия выделимости. Если положить q − 1 < 0, то в рамках такого допущения потребуется, чтобы 0 b+ (1/q) (1/q)∆ − 1 / ((1/q) − 1) < 1. Здесь для каждого допустимого m значения g < p, p 2, уровень ϕ+г (∆) превышает единицу, и поэтому с прип нятием предположения q < 1 рассматриваемый случай условия выделимости следует признать неосуществимым. Второй вариант задания условия выделимости как 0 δ− < 1, δ+ = 0, которому соответствует первый член геометрической прогрессии aг = −q и п1 её знаменатель q, имеет следующий конкретизированный вид: −δ− < ϕ−г (∆) п 0⇒0 −ϕ−г (∆) < δ− , п ∆ ∈ {1, . . . , p − 1}. Тогда первый и второй варианты задания условий выделимости с учётом равнозначности первых членов используемых ими остаточных последовательностей можно объединить следующим образом: 0 δ+ → ϕ+г (∆), п −г δ− → ϕп (∆). |ex ϕг (∆)| < п Решение одного или другого варианта этого неравенства при указании в нём одной из величин δ+ или δ− соответствует решению, уже полученному нами для представленного выше первого варианта условия выделимости со знакопостоянной геометрической прогрессией. Условие выделимости, связанное с остаточной знакопостоянной последовательностью равных друг другу натуральных степеней натуральных чисел, может быть получено и проанализировано исходя из следующих соображений. Применительно к ОСО ∆ lν /(∆ + 1)ν , ϕ+р (∆) = bm п (3) l=1 определённому на множестве {∆; g = 1, . . . , p − 1} и принимающему положительные значения, построим сопутствующую функцию (её верхний индекс c) x ϕc (x) п (l + χ)ν /(∆ + 1 + χ)ν , = bm (4) l=1 где 1 x ∆, 0 χ = x − χ < 1, ν ∈ N. Критерием такого построения является реализация фактов принадлежности определённых значений 94 Условия выделимости весовых коэффициентов из сумм . . . функции (4) области значений исходной функции (3), аргументом которой выступает целочисленная величина ∆. Нашу сопутствующую функцию можно дифференцировать по аргументу x. Преобразуем соотношение (4): x ϕc (x) п (l + χ)ν /( x + 1 + χ)ν . = bm l=1 Выражение производной d (ϕc (x)) /dx = ϕc (x) п п находится здесь согласно известному правилу [5] с учётом равенства dx = dχ: x ϕc (x) = bm ν п ν−1 φl (x + 1 − l − χ)/(x + 1)2ν ; l=1 φl = (l + χ)(x + 1). Учитывая соотношение x = x + χ, получаем x ϕc (x) = bm ν п (l + χ)ν−1 ( x + 1 − l)/(x + 1)ν+1 . l=1 Поскольку x l, для любого x ∈ Ix∆ = [1, ∆] величина ϕc (x) > 0, то п есть в интервале Ix∆ величины ϕc (x), ϕc (x) имеют сплошь положительные п п значения. Аналогичные построения и преобразования могут быть произведены и применительно к функциям ϕ−р (∆), −ϕc (x), которые воспроизводят вырап п жения (3), (4) со знаками, обратными применённым выше, и имеют, таким образом, отрицательные значения. Величину ϕ+р (∆) с областью значений из R+ \{0} и величину ϕ−р (∆) с п п областью значений из R− \{0} будем обозначать просто как ϕ+р и ϕ−р . Соп п ответственно, элемент множества {ϕ+р , ϕ−р } может быть представлен в вип п де ex ϕр . Установленный выше характер знака производной сопутствующей п функции по аргументу x позволяет прояснить то обстоятельство, что уровень max{∆} ϕ+р , соответствующий максимуму положительной величины на п интервале Ix∆ , приходится на максимальное значение ∆ = p − 1. В симметричном по знаку случае отрицательных значений величины ϕ−р минимальное п значение данной величины min{∆} ϕ−р на том же интервале Ix∆ приходится п на то же значение ∆ = p − 1. Итак, если в процессе вычислений ϕ+р или ϕ−р при задаваемых изменеп п ниях факторов p, ν окажется, что для какого-либо найденного ∆ = p−1 абсолютная величина соответствующего ОСО уже не превышает установленного порога δs (s ∈ {−, +}), то достигнутые значения p, ν и будут обеспечивать удовлетворение заявленного условия выделимости. Чтобы перейти к выработке условий выделимости целочисленных весовых коэффициентов основных последовательностей со знакочередующимися членами, сделаем несколько дополнений к нашим прежним замечаниям общего характера. 95 А. И. Н и к о н о в В частности, рассмотрим остаточные последовательности свободных множителей с чётной и нечётной индексацией членов, имеющие соответственно все положительные или отрицательные члены: + lm П+ п = c2l−1 , l = + 1, . . . , lm + →S = c2l−1 ; l=1 − lm П− п = −c2l , l = − 1, . . . , lm − →S =− c2l ; l=1 S+, S− — суммы членов соответственно положительных и отрицательных подпоследовательностей П+ и П− , то есть соответственно положительный и отп п + рицательный суммарные остатки. Подстрочный индекс • обозначений S• и − , используемых далее, будет указывать на последний член, находящийся в S• подпоследовательности П+ или П− и нумеруемый как член последовательноп п сти Пп , объединяющий П+ и П− ; члены П+ и П− , образующие объединённую п п п п последовательность Пп , поочерёдно выбираются из них. Через П+ или П− п◦ п◦ обозначим модификацию подпоследовательности П+ или П− , в которой на п п местах её членов размещаются нули, то есть содержимое множества качественных признаков из П+ или П− составляет нуль. п◦ п◦ Всевозможные комбинации знаков суммарных остатков вида S• и внешних членов c∆+1 , то есть комбинации верхних индексов их обозначений, пред− + ставлены в нижеприведённой таблице. Число вида lm или lm , указанное в этой таблице и обозначающее количество членов соответствующей подпоследовательности П+ или П− , определяется из следующих равенств: п п − 2lm◦ = ∆ − 1; − 2lme = ∆; + 2lm◦ − 1 = ∆; + 2lme − 1 = ∆ − 1. (5) Знак S/ его нижний индекс • Знак c∆+1 Знак или значение c∆ Знак или значение c∆−1 + Значение lm − или lm Нечётность или чётность ∆ Разновидность ОСО −/∆ − 1 −/∆ +/∆ +/∆ − 1 − + − + 0 → П+ п◦ − + 0 → П− п◦ − 0 → П+ п◦ 0 → П− п◦ + − lm = (∆ − 1)/2 − lm = ∆/2 + lm = (∆ + 1)/2 + lm = ∆/2 o e o e ϕ+ ч◦ ϕ− чe ϕ− ч◦ ϕ+ чe + − Переход от подстрочной индексации в обозначениях сумм S• и S• к подстрочной индексации этих же сумм как величин, соответствующих подпоследовательностям П+ и П− , может быть осуществлён согласно равенствам (5). п п Для последовательности, расширенной за счёт внешнего члена, позицию ex которого мы обозначим как lm , количественное определение этой позиции в случаях положительности либо отрицательности всех членов данной расширенной последовательности может быть произведено по соотношениям ex− 2lm = ∆ + 1, ex+ 2lm − 1 = ∆ + 1. Член c∆+1 проявляет свой внешний характер в отношении последовательности П+ или П− и может быть обозначен соответственно как c+ или c− . п п ∆+1 ∆+1 96 Условия выделимости весовых коэффициентов из сумм . . . В правой колонке нашей таблицы помещены обозначения следующих разновидностей относительных суммарных остатков: ϕ+ , ϕ+ — функции вида ч◦ чe + − соответственно bm S∆−1 /c− , bm S∆−1 /c+ ; ϕ− , ϕ− — функции вида соотчe ч◦ ∆+1 ∆+1 − + ветственно bm S∆ /c− , bm S∆ /c+ . ∆+1 ∆+1 Надстрочные индексы этих функций отвечают соотношениям: плюс — совпадение между собой знаков величин S и c∆+1 ; минус — несовпадение между собой таких знаков. Пусть в качестве остаточной последовательности свободных множителей выступает знакочередующаяся геометрическая прогрессия с первым членом q и знаменателем −q: cl = cг = (−1)l+1 q l , чl l = 1, . . . , ∆. Среди слагаемых, относящихся к суммарным остаткам, будем собирать такие, которые имеют одинаковые знаки и, следовательно, образуют величи− + ны S• , S• . Если положить q > 1, то в случае, когда все ненулевые относительные суммарные остатки, связанные с указанной последовательностью, отрицательны, учитывая данные вышеприведённой таблицы, имеем при ∆ ∈ Ip−1 : ϕ−г = − bm q/(q 2 − 1) (q ∆ − 1)/q ∆ ; чe ϕ−г ч◦ 2 = − (bm q) / q − 1 (q ∆+1 − 1)/q ∆+1 (6) (7) . Отсюда, следуя принятому нами способу решения двойного неравенства −δ− < ϕ−г ч (8) 0 с ОСО в его центральной части, выражаемым с помощью суммы геометрической прогрессии: 0 < (q ∆ − 1)/q ∆ < 1, −b− q/(q 2 − 1) > −1. m 0 < (q ∆+1 − 1)/q ∆+1 < 1; Продолжив решение, находим q > 0,5 b− + (b− )2 + 4 m m 1/2 . Переходя теперь к случаю использования знакочередующейся геометрической прогрессии, когда все ненулевые относительные суммарные остатки положительны, и учитывая данные вышеприведённой таблицы, вырабатываем следующее представление разновидностей положительного ОСО: ϕ+г = bm /(q 2 − 1) (q ∆−1 − 1)/q ∆−1 , ч◦ ϕ+г чe 2 ∆ ∆ = − bm /(q − 1) (q − 1)/q , ∆ ∈ Ip−1 \{1}; ∆ ∈ Ip−1 . (9) (10) Затем, решая двойное неравенство 0 ϕ+г < δ+ , ч (11) получаем 0 < (q ∆−1 − 1)/q ∆−1 < 1, 1/2 Отсюда q > (b+ + 1) m 0 < (q ∆ − 1)/q ∆ ; 0 b+ /(q 2 − 1) < 1. m . 97 А. И. Н и к о н о в Теперь количественное заключение о допустимых значениях q > 1, при которых выполняется поставленное условие выделимости, можно представить как 1/2 q > max 0,5 b− + (b− )2 + 4 , (b+ + 1)1/2 . m m m Далее положим 0 < q < 1, и, в случае отрицательности всех ненулевых значений относительных суммарных остатков, обратившись к сооношениям (6), (7) при решении двойного неравенства (8), получим: ϕ−г = −b− η(η 2 − 1)−1 (η ∆ − 1); чe m (12) ϕ−г = −b− η(η 2 − 1)−1 (η ∆+1 − 1); ч◦ m η = (1/q) > 1, ∆ ∈ Ip−1 . (13) Учтём, что для натуральных p 2 и g ∈ Ip−1 действует равенство min(max ∆) = 1, p и поэтому ни одна из величин вида (12), (13) не удовлетворяет неравенству (8): каждое из чисел η, bm превышает единицу. Даже в случае ∆ = 1 абсолютная величина (12) должна удовлетворять неравенству b− η/(η + 1) < 1 ⇒ η(b− − 1) < 1, m m но поскольку η > 1 и bm 2, выполнить такое требование невозможно. Тем более это оказывается невозможным и для всех других значений числа ∆ из области его определения применительно к неравенству (8). Продемонстрируем неосуществимость неравенства (11) применительно ко всем относительным суммарным остаткам вида (9) и (10), когда положительное q < 1. Здесь полагаем, что в выражении (9) число ∆ имеет значение не меньшее двух, и рассмотрим величину η ∆−1 для выражения (9) и величину η ∆ для выражения (10), которые в данных выражениях теперь более всего благоприятствуют реализации двойного неравенства (11). Тогда для реализации (11) уже при ∆ = 2 в (9) и ∆ = 1 в (10) должны соблюдаться неравенства 0 b+ η 2 /(η + 1) < 1 ⇒ η(b+ η − 1) < 1. m m Однако η > 1, bm 2, и неравенство (11) не может быть здесь выполнено. Итак, при любых значениях ∆, соответствующих области значений 0 < q < 1, условия выделимости (8), (11) оказываются невыполнимыми. ОСО, использующий знакочередующуюся последовательность, содержащую члены — равные натуральные степени натуральных чисел, может быть выражен следующим образом: s lm ϕsp ч ε+ξ = (−1) s (2l − ε)ν / (2lm + ξ)ν , bm l=1 где верхний индекс s ∈ {−, +} указывает на знак «минус» или «плюс»; ε= 98 − 0 → П − → S• , п + +; 1 → П п → S• Условия выделимости весовых коэффициентов из сумм . . . − lm → ε = 0, + lm → ε = 1; значения ξ могут определяться в зависимости от пары знаков s1 , s2 ∈ {−, +}, которыми — в качестве верхних индексов — снабжаются обозначения суммарs ных остатков и внешних членов вида S• 1 , cs2 : ∆+1  0 : (s1 , s2 ) = (+, −),  ξ = 1 : (s1 , s2 ) = (−, +) ∨ (+, +),  2 : (s , s ) = (−, −). 1 2 Кроме того, можно указать следующие соотношения, которые связывают между собой знаковые индексы и символы ε, ξ: s→ +: −: (s1 , s2 ) = (+, +) ∨ (−, −) → ε + ξ = 2, (s1 , s2 ) = (−, +) ∨ (+, −) → ε + ξ = 1. Функция, сопутствующая данному ОСО, имеет вид x ϕsc (x) ч ε+ξ = (−1) (2l − ε + 2χ)ν /(2 x + ξ + 2χ)ν ; bm l=1 0 χ = x − x < 1, s x = lm . s В пределах области своего определения [1, lm ] сопутствующая функция имеет производную s dϕsc (x)/dx = (−1)ε+ξ 2νbm Ax / (2lm + ξ + 2χ)2ν ; ч (14) s lm s Ax = (2lm + ξ + 2χ)ν−1 s (2l − ε + 2χ)ν−1 (2lm − 2l + ξ + ε) . l=1 Нетрудно видеть, что справедливым оказывается неравенство Ax > 0, и знак выражения (14) определяется лишь показателем степени (−1)ε+ξ . Когда этот показатель равен двум, сопутствующая функция имеет вид ϕ+c (x), ч а когда он равен единице — вид −ϕ−c (x). Следовательно, при увеличении x ч первая из указанных функций в области своего определения является возрастающей, а вторая — убывающей. Сужая ϕsc (x) до ОСО ϕ+p или ϕ−p , то есть беря значение ϕsc (x) в точках ч ч ч ч s вида x = x , убеждаемся в том, что с ростом lm , а следовательно, с ростом ∆ положительные значения ϕ+p увеличиваются, а отрицательные значения ч ϕ−p уменьшаются, поэтому максимум ϕ+p или минимум ϕ−p соответствует ч ч ч максимуму ∆ = p − 1 или же минимуму g = 1. То есть число ∆ может быть обоснованно выбрано как значение аргумента ОСО, участвующее в его проверке на соблюдение выработанного условия выделимости.

Об авторах

Александр Иванович Никонов

Самарский государственный технический университет

Email: nikonovai@mail.ru
(д.т.н., проф.), профессор, каф. электронных систем и информационной безопасности Россия, 443100, Самара, ул. Молодогвардейская, 244

Список литературы

Дополнительные файлы