Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Последовательности, функции и их кодирование на Верченко

Тема Межрегиональная им. И. Я. Верченко (криптография)

Последовательности, функции и их кодирование на Верченко

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела межрегиональная им. и. я. верченко (криптография)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#90278

a) перестановка $f$ чисел ${0,1,...,6}$ задана таблицей:


$x$	0	1	2	3	4	5	6

$f(x)$	3	2	4	0	5	6	1

Например, $f(2)= 4$ . Найдите две различные перестановки $g$ и $h$ такие, что для всех $x ∈{0,1,...,6}$ выполняется

f(x)≡ (g(x)+h(x))(mod7)

b) перестановка $f$ задана на чётном количестве чисел ${0,1,...,2n− 1}$ таблицей:


$x$	0	1	2	..	$2n− 2$	$2n− 1$

$f(x)$	$i0$	$i1$	$i2$	..	$i2n−2$	$i2n−1$

Здесь $(i0,i1,...,i2n−1)$ - перестановка чисел ${0,1,...,2n− 1}$ .

Докажите, что не существует перестановок $g$ и $h$ таких, что для всех $x∈ {0,1,...,2n− 1}$ выполняется $f(x)≡(g(x)+ h(x))(mod (2n))?$

Источники: Верченко - 2024, 11.3 (см. ikb.mtuci.ru)

Подсказки к задаче

Пункт а, подсказка 1

Просто пытаться найти перестановки функции перебором очень тяжело. Однако можно заметить, что если мы домножим каждое значение перестановки f(x) на число взаимно простое с 7 и возьмём от получившихся чисел остатки при делении на 7, то мы получим перестановку. Попробуйте найти такие перестановки, подходящие под условие.

Пункт а, подсказка 2

Нужно взять два числа, взаимно простых с 7, чтобы их сумма имела остаток 1 при делении на 7. Тогда, умножив f(x) на эти числа, мы получим перестановки g(x) и h(x). Они подходят под условие.

Пункт b, подсказка 1

Мы почти ничего не знаем про расположение элементов перестановки. Однако точно знаем, чему равна сумма значений перестановки. Ведь её значения - 0,1,...,2n-1. То же самое можно сказать про перестановки g(x) и h(x). Попробуйте доказать требуемое от противного, записав условие через сумму перестановки.

Пункт b, подсказка 2

Суммы значений всех трёх перестановок равны (2n+1)*n. Тогда, используя условие пункта b, получаем, что (2n+1)*n = (2n+1)*n+(2n+1)*n(mod 2n). Попробуйте получить противоречие, рассматривая по модулю 2n.

Показать доказательство

а) Так как $НОД (2,7) =НО Д(6,7)=1,$ то $g(x)≡ 2f(x)(mod7)$ и $h(x)≡ 6f(x)(mod7)$ являются перестановками. Но тогда, например, $g(x)=2f(x),h(x)=6f(x)$ и выполняется

g(x)+ h(x)=2f(x)+6f(x)≡f(x)(mod7)

b) Из условия получим

2∑n− 1 2n∑−1 f(x)= x = (2n+ 1)n =n(mod(2n)) i=0 i=0

С другой стороны, если указанное условии пункта b) представление существует, то

2∑n−1 2∑n− 1 2n∑−1 f(x)= g(x)+ h(x)=2(2n+ 1)n≡ 0(mod(2n)), i=0 i=0 i=0

а это доказывает невозможность указанного представления.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#68242

Имеется устройство, которое строит последовательность чисел $x,x ,x ,... 0 1 2$ следующим образом: первые два члена $x 0$ и $x 1$ мы задаем самостоятельно, а последующие члены устройство вычисляет так: $x2 =x0+ 13⋅(x1+ k1),x3 = x1+ 13 ⋅(x2+ k2),...$ Здесь $k1,k2,...$ — – некоторая фиксированная ключевая последовательность. При этом все числа $x0,x1,x2,...$ и $k1,k2,...$ являются целыми, лежащими в пределах от 0 до 32 включительно. (Если в процессе вычислений получится число, превосходящее 32, то результат будет заменен его остатком от деления на 33; например, $16+ 13 ⋅2 =9.)$ С помощью этого устройства построили две последовательности $a0,a1,a2,...$ и $b0,b1,b2,...,$ по первым членам $a0 =1,a1 = 3$ и $b0 =1,b1 =12.$ Верно ли, что найдётся ключевая последовательность $k1,k2,...$ и некоторое целое $t,$ большее 0, такие, что выполняются условия:

a) $bt = at,bt+1 =at+1?$

б) $bt = at+1?$

Решение обоснуйте.

Источники: Верченко-2023 (см. v-olymp.ru)

Подсказки к задаче

Пункт а), подсказка 1

У вас есть равенство двух членов одной последовательности двум другим. А как можно выразить, например предыдущий член последовательности через два соседних? Попробуйте так прийти к противоречию)

Пункт б), подсказка 1

Мы понимаем, что последовательности устроены одинаковым образом, так еще и ключевая последовательность у них одинаковая. Что можно сделать, чтобы вообще исключить эту последовательность?

Пункт б), подсказка 2

Вычесть одну последовательность из другой! По факту, в этой последовательности тогда нужно будет понять, есть там единица, или нет. В таком случае посмотрите на первые члены и на то, по какому модулю у нас все происходит и придите к противоречию)

Показать ответ и решение

а) Для всех $t≥1$

at+1 = at− 1+13(at+ kt),at−1 =at+1− 13(at+kt)

Поэтому, если $bt = at,bt+1 =at+1$ , то $bt−1 =at−1,...b1 = a1,b0 = a0$ , что противоречит условию.

б) Удобно перейти к разностям полублоков $zt = bt− at$ (везде далее действия с полублоками (умножение, сложение и вычитание) производятся по модулю $M$ ) и выяснить, может ли 1 появиться в ${z} t$ . Из уравнения шифрования

bt+1 = bt−1+ 13(bt+kt),t≥ 1

a =a + 13(a +k ),t≥ 1 t+1 t−1 t t

получаем после вычитания

zt+1 = zt−1+ 13zt,t≥1,

что последовательность разностей не зависит от ключа $kt$ . По условию $(z0,z1)= (0,9),(z0,z1,M )= 3$ , поэтому все члены последовательности будут делиться на $3$ , и единицы там не будет.

Ответ:

а) нет

б) нет

Ошибка.
Попробуйте повторить позже

Задача 3#71011

Дана последовательность $a,b ,a ,b,...,a,b 1 1 2 2 k k$ , состоящая из $0$ и $1.$ Пусть $N$ — количество чисел $i$ от $1$ до $k$ таких, что $a = 0 i$ и $bi = 1.$ Докажите, что число последовательностей указанного вида, для которых $N$ нечетно, находится по формуле $2k−1 k−1 2 − 2 .$

Источники: Верченко-2022 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

В задаче есть параметр k, учитывая который строятся последовательности. Увеличив k, несложно построить новую последовательность, не "сломав" старую. Попробуем решить задачу индукцией по k! Докажем, что если утверждение выполняется при k-1, но оно выполняется и при k.

Подсказка 2

Если последовательность из 2k элементов удовлетворяет условию, то какой тогда будет эта последовательность без последнего пары a_k, b_k? Что будет с четностью N?

Подсказка 3

Нам подходят такие последовательности длины 2(k-1), где N четно, а_k = 0 и b_k = 1. А если N нечетно, то какой может быть пара (a_k;b_k)?

Показать доказательство

Применим метод математической индукции по параметру $k$ . При $k= 1$ формула очевидна. Докажем, что если она верна при $k − 1$ , то верна и при $k.$

Искомое число равно числу последовательностей

a1,b1,a2,b2,...,ak−1,bk−1,

(1)

в которых количество $i= 1,2,...k− 1,$ таких, что $ai = 0$ и $bi = 1$ четно (в этом случае пара $(ak,bk)$ может быть только $(0,1))$ плюс количество последовательностей вида (1) в которых количество чисел $i= 1,2,...k− 1,$ таких, что $ai = 0$ и $bi = 1$ нечетно, умноженному на 3 (так как пара $(ak,bk)$ может быть любой из пар $(0,0),(1,0),(1,1)).$ В итоге по предположению индукции нужное число последовательностей будет удовлетворять равенству

( ( )) ( ) 22(k−1)− 22(k−1)−1 − 2k−2 + 3 22(k−1)−1− 2k−2 =22k−1− 2k−1

Ошибка.
Попробуйте повторить позже

Задача 4#71013

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

$PIC$

За один такт устройство считывает с ленты с позиций $μ1,μ2,μ3$ (на первом такте $μ1 = 1$ ) три значения $x,y,z$ . Если $x+ y+z ≥2,$ то устройство на новой ленте печатает 1 , иначе — 0 . Затем устройство сдвигается на одну позицию вправо, и процедура повторяется. Найдите разности $d1 = μ2− μ1$ и $d2 = μ3− μ2,$ если известно, что $d1 +d2 ≤ 10,$ а на новой ленте было напечатано следующее: $0001000010111111000111010111011010101001 ...$ (для примера на рисунке изображен случай $d1 = 3,d2 =5).$

Источники: Верченко-2022 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

Да, можно и перебрать d_1 и d_2, но это будет долго) Попробуем сократить перебор! Что мы вообще умеем делать? Мы умеем брать конкретные элементы ленты и считать их сумму, если расстояния между ними это d_1 и d_2. Какие "удобные" элементы хочется взять?

Подсказка 2

Рассмотрим систему неравенств, которая соответствует выходных знакам вида 1...1 на расстоянии d_1. С помощью нее мы сможем дать ограничения на элементы, находящиеся на расстоянии d_1. Таким образом мы сможем перебрать и методом "пристального взгляда на ленту" найти d_1. Аналогично с d_2!

Показать ответ и решение

Число возможных вариантов $d 1$ и $d :10+ 9+ ⋅⋅⋅+1 =55 2$ , можно для каждого варианта проверять, что соответствие входных и выходных символов, а можно предложить более быстрый способ, заключающийся в нахождении сначала $d1$ (максимум 10 вариантов), а затем $d2$ . Для этого достаточно заметить следующее.

Если рассмотреть систему, соответствующую выходным знакам на расстоянии $d1$ вида $1...1$ в произвольном такте работы $μ1 :$

xμ1 + xμ1+d1 − xμ1+d1+d2 ≥ 1,

xμ1+d1 +xμ1+2d1 − xμ1+2d1+d2 ≥ 1,

то если $x = 0 μ1+d1$ , то $x = 1,x = 1. μ1 μ1+2d1$

Это позволяет отбраковать опробуемый вариант $d . 1$ Устанавливаем, что $d = 2. 1$

Аналогично, если рассмотреть систему, соответствующую выходным знакам на расстоянии $d2$ вида $0...1$ в произвольном такте работы $μ1 :$

xμ1 + xμ1+d1 − xμ1+d1+d2 ≤ 0,

xμ1+d2 +xμ1+d1+d2 − xμ1+d1+2d2 ≥1,

тогда если $xμ1+d1+d2 = 0,$ то $xμ1+d1 = 0,xμ1+d1+2d2 = 0.$

Это позволяет отбраковать опробуемый вариант $d 2$ (с учётом найденного ранее $d =2). 1$ Находим $d = 6. 2$

Ответ:

$d = 2,d =6 1 2$

Ошибка.
Попробуйте повторить позже

Задача 5#71370

Знаками открытого и шифрованного текстов являются пары целых от 0 до 31. Для зашифрования используется секретный ключ $k$ (целое число от 0 до 31), заданная таблично функция $h,$ а также функция $g(c,d),$ которая паре целых чисел $(c,d)$ ставит в соответствие пару $(d,c+ h(d+k))$ (причем если число $d +k$ или $d+ h(d+ k)$ превышает 31 , то их заменяют остатком от деления на 32 $).$ Знак шифрованного текста $(b1,b2)$ получается из знака открытого текста $(a1,a2)$ путем 128-кратного применения функции $g :$

(b1,b2)= g128(a1,a2)= g(...g(g(a1,a2)))

Известно, что знак открытого текста $(21,0)$ преобразовался в знак зашифрованного текста $(15,25),$ знак $(7,3)$ преобразовался в $(29,5),(0,17)$ — в $(25,4)$ и, наконец, $(5,21)−$ в $(22,9).$ Найдите ключ $k.$


$i$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

$h(i)$	9	1	30	4	24	12	8	23	18	7	16	15	21	26	10	17	19	22	13	28	14


21	22	23	24	25	26	27	28	29	30	31

11	2	29	3	6	27	0	5	25	31	20

Источники: Верченко-2022 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

Применять 128 раз одну и ту же функцию очень сложно...поэтому было бы хорошо, если мы сразу могли понимать, а что у нас получается на каждой итерации? Может ли в итоге у двух разных пар получиться один и тот же знак?

Подсказка 2

Если две пары отличаются одним применением функции, то и их знаки тоже отличаются одним применением функции. Как это связать с условием?

Подсказка 3

Попробуем найти такие пары чисел, которые удовлетворяют утверждению из подсказки 2. Теперь мы знаем, какие пары отличаются применением функции g! Несложно найти k)

Показать ответ и решение

Необходимо заметить, что из равенств

128 (b1,b2)= g (a1,a2)

( ′ ′) 128( ′ ′) b1,b2 = g a1,a2

(a′,a′)= g(a,a ) 1 2 1 2

следует равенство

(b′,b′)= g(b,b ) 1 2 1 2

Необходимым условием выполнения равенств $(a′1,a′2)= g(a1,a2),(b′1,b′2)= g(b1,b2)$ являются равенства $a′1 = a2,b′1 = b2.$ Среди приведенных в задаче пар знаков открытого и шифрованного текстов есть знаки, удовлетворяющие этому условию: одна пара $(21,0),(0,17)$ и вторая пара $(29,5),(5,21).$ То есть

(15,25)=g128(21,0)

(25,4)= g128(0,17)

Из условия задачи возможность найти ключ — воспользоваться равенствами

(0,17)= g(21,0), (25,4)= g(15,25)

Убедимся, что при этих условиях оба равенства дают одинаковое значение ключа $k.$

$PIC$

Получаем, что $k= 19.$

Ответ: 19

Ошибка.
Попробуйте повторить позже

Задача 6#99583

Целое число $s∈ {0,...,30}$ может быть преобразовано следующим образом. Пусть, например, $s= 9.$ Представим его в двоичной системе счисления пятизначным числом: $s= 9= 010012.$ Теперь выберем какое-нибудь целое число $c≥ 0$ и сдвинем получившуюся строку $01001$ циклически на $c$ позиций влево. Например, при $c= 1$ получится строка 10010, представляющая собой двоичную запись числа 18. Значит, сдвигом на одну позицию из числа 9 получается число $18;$ будем это записывать так: $9 ⋘ 1= 18.$

(Если $01001$ сдвинуть влево на две позиции, то получится $00101,$ то есть $9 ⋘ 2= 5.$ )

Итак, $s≪ c$ — это число, получившееся сдвигом числа $s$ на $c$ позиций влево.

Для зашифрования осмысленного слова выбирается секретный ключ — набор из $64$ чисел

k1,...,k32 ∈{0,...,30} и c1,...,c32 ∈{0,1,2,3}.

Затем с каждой буквой слова (по отдельности) проделывается следующее.

Букву заменяют числом $a$ по таблице

$|---|---|---|---|----|---|----|---|---|---|----|---|----|---|---|---|----|---|---|----|---|---|---|----|----|---|----|---|---|----|----| |А--|Б--|-В-|-Г-|-Д--|Е--|Ж---|З--|И--|-К-|-Л--|М--|-Н--|О--|-П-|-Р-|-C--|Т--|У--|-Ф--|Х--|Ц--|-Ч-|-Ш--|-Щ--|-Б-|-Ы--|-Б-|-Э-|-Ю--|-Я--| -0----1---2---3---4---5----6---7----8---9---10--11---12--13--14---15---16--17--18---19---20--21---22---23---24---25---26--27---28---29---30--$

и последовательно вычисляют

a1 = (a+ k1)⋘ c1,a2 =(a1+ k2)⋘ c2,...,a32 =(a31+k32)⋘ c32.

Исходную букву затем заменяют на букву, соответствующую числу $a32.$

(Если в процессе вычислений получается число, превышающее $30,$ то оно заменяется остатком от деления на $31.$ Так, сумму $20+ 17$ следует заменить на $6.$ )

В результате зашифрования получился набор букв ЯГКЫНИ.

Найдите исходное слово, если известно, что при зашифровании на этом ключе буква Ъ переходит в букву Ь, а буква П — в Е.

Подсказки к задаче

Подсказка 1

В таких задачах, где идёт сложный процесс, хорошей идеей будет посмотреть на первые несколько шагов. Вдруг обнаружится цикличность, или можно будет заметить явную закономерность и вывести общую формулу. Попробуйте посмотреть, как меняется для чисел, которые записываются в виде пяти знаков (может быть с нулями в начале) в двоичной системе счисления, значение при операции левого циклического сдвига (то есть при с=1).

Подсказка 2

Заметим, что s « 1 = 2s (mod 31) (для этого надо разобрать два случая, чему равна первая цифра в двоичной системе счисления). Тогда s « c = 2^c * s (mod 31). А это значит, что мы стали чуть больше понимать, как работает процесс. Однако, все ещё не представляется возможным решить задачу, потому что даже сейчас непонятно, как явным образом ввести ограничения на k_i и c_i. Каким свойством обладает преобразование s « c? А что будет, если сделать не s « c, а (k + n) « c? Чему равно такое выражение?

Подсказка 3

Преобразование линейно, а значит и композиция преобразований тоже линейна. Значит оно записывается в виде kx + b. Что тогда можно сказать про k и b, если у нас есть значения на двух разных аргументах?

Показать ответ и решение

Покажем, что

c (s ≪ c)= r31(s⋅2 ).

Заметим, что достаточно доказать для $c= 1.$ Пусть $s= (s4s3s2s1s0) . 2$ Если $s4 = 0$ , то равенство ( $∗)$ очевидно. Если $s4 = 1,$ то

3 2 s= 16+ 2 ⋅s3+ 2 ⋅s2+2⋅s1+ s0.

Тогда

r31(s⋅2)= 24⋅s3+23⋅s2+ 22⋅s1+ 2⋅s0+ 1=(s≪ c),

и равенство $(∗)$ доказано. Следовательно,

a1 =((a+k1)≪ c1)=r31((a+ k1)⋅2c1)= r31(a⋅2c1 + k1⋅2c1).

То есть, на одном шаге шифрования — линейное преобразование числа $a.$ Так как композиция линейных преобразований есть линейное преобразование, то $a32 =(a⋅x+ k)$ , где $x$ и $k$ — неизвестные.

Воспользуемся тем, что на этом ключе буква Ъ переходит в букву Ь, а буква П — в Е:

27 ≡ (25⋅x +k), 5 ≡ (14⋅x+k) 31 31

Вычитая из первого равенства второе, получим: $22= 11⋅x.$ Отсюда $x= 2.$ Тогда

27 ≡ (25⋅2+ k) 31

и, следовательно, $k= 8.$ Окончательно получили:

a32 =(a⋅2+ 8)

Тогда

a= 2−1(a − 8)=16⋅a + 27 32 32

Последовательно подставляя буквы шифрованного текста ЯГКЫНИ, получим исходное слово МОСКВА.

Ответ:

МОСКВА

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#99591

Устройство принимает на вход и выдает на выход наборы из $n$ битов (причем $n ≥4$ ). Поданный на вход набор $x = (x ,...,x ) 1 n$ преобразуется в выходной набор

h(x)= (x1⊕ xn−1,x2 ⊕xn,x2⊕x3,x3⊕ x4,...,xn−2⊕ xn−1,x1⊕ xn),

где $⊕$ — стандартная операция сложения битов: $0⊕ 0= 1⊕1 =0,0⊕1 =1 ⊕0= 1$ .

Подав теперь этот набор $h(x)$ на вход, получим на выходе набор $h(h(x ))= h(2)(x)$ , который вновь подадим на вход и получим $h(3)(x)$ и т.д.

Докажите, что если все наборы

(2) (k) x,h(x),h (x),...,h (x)

оказались различными, то $k≤ 2n− 1− 1$ .

Показать доказательство

Заметим, что для всех $x$ вектор $h(x)$ содержит четное число единиц, так как

(x1⊕ xn−1)⊕(x2⊕ xn)⊕(x2⊕ x3)⊕ (x3 ⊕x4)⊕...⊕(xn−2⊕ xn− 1)⊕ (x1 ⊕xn)= 0.

Значит, в рассматриваемой последовательности

(2) (k) x,h(x),h (x),...,h (x)

все векторы, начиная со второго, имеют четное количество единиц. Количество всех векторов, имеющих четное количество единиц, равно $2n−1$ . Поэтому претендентом на самое большое количество различных векторов является последовательность (*), начинающаяся с вектора, содержащего нечетное количество единиц и продолжающаяся всеми векторами с четным количеством единиц. Количество векторов в такой последовательности будет $1+ 2n−1$ Таким образом,

n−1 k≤ 2 .

Для получения оценки $k≤ 2n−1− 1$ рассмотрим отдельно случай когда среди векторов последовательности (*) нет нулевого вектора $(0,0,...,0)$ и когда он есть.

Если в последовательности (*) нет вектора $(0,0,...,0)$ , то она содержит не более $1+ (2n−1− 1)= 2n− 1$ векторов и

k≤ 2n−1− 1.

Пусть теперь последовательность (*) содержит вектор ( $0,0,...,0$ ). Рассмотрим два случая.

1) Если $n$ — нечетное число, то

h(0,0,...,0)= h(1,1,...,1)=(0,0,...,0)

и других векторов, переходящих в нулевой нет. При этом не существует векторов $z$ таких, что

h(z)= (1,1,...,1)

Таким образом в этом случае последовательность (*) содержит максимум два вектора и

k≤ 2n−1− 1.

2) Если $n$ — четное число, то

h(0,0,...,0)= h(1,1,...,1)=(0,0,...,0)

и найдутся два вектора

a= (0,0,1,0,1,...,0,1,1) и b= (1,1,0,1,0,1,...,0,1,0,0),

содержащие четное число единиц такие, что

h(a)=h(b)= (1,1,...,1).

Последовательность (*) не может содержать одновременно векторы $a$ и $b$ , поэтому в этом случае она содержит не более $( n− 1 ) n−1 1+ 2 − 1 = 2$ векторов, так что

k≤ 2n−1− 1.

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел