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

Тема Верченко (криптография)

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

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

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

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

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

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

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

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

Задача 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.$ )

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

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

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

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

Подсказка 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$ .

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

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

Подсказка 1

Заметим, что для всех x вектор h(x) содержит четное число единиц. Сколько всего существует векторов, в которых единиц чётное число?

Подсказка 2

Конечно, 2ⁿ⁻¹. Значит, нам нужно улучшить нашу оценку всего на 1. Если встретятся все векторы с чётным число единиц, то встретится и нулевой. Какие векторы с чётным числом нулей могут перейти в него?

Подсказка 3

Если n нечётное, то подойдёт только сам нулевой вектор. Если же n чётное, то есть вектор из всех единиц. Тогда, используя идею чередования, можно найти 2 вектора, которые переходят в (1, 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.

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

Задача 8#123667

Для зашифрования осмысленного слова его буквы переводят в числа $x ,x ,...,x 1 2 n$ по таблице. Затем выбирают натуральные числа $x 0$ и $k.$ Далее число $x0$ приписывают в начало последовательности $x1,x2,...,xn,$ а число $n+4 xn+1 =x0+ 19$ (где $n−$ длина слова) — в ее конец. Получившаяся в результате последовательность $x0,x1,...,xn,xn+1$ затем преобразуется в последовательность $y0,y1,...,yn,yn+1$ по формуле $( 3 ) yi = r32 xi+ 6xi⋅k + k ,i= 0,1,...,n+ 1,$ где $r32(a)−$ остаток от деления числа $a$ на $32.$ Затем числа $y0,y1,...,yn+1$ заменяют буквами согласно таблице. В результате получили вот что: КЙЫЦНБНЦЛ. Какое слово было зашифровано?


А	Б	В	Г	Д	Е Ё	Ж	3	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Ш	Ъ	Ы	Ь	Э	Ю	Я

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	31

Источники: Верченко - 2020, 11.2

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

Подсказка 1

Да, условие и правда очень мудрёное и не совсем понятно за что ухватиться. Для начала наверное будет хорошо выписать всё, что можем найти. Как насчёт n и последовательности y?

Подсказка 2

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

Подсказка 3

Попробуйте рассмотреть остаток от деления от разности последней и первой букв. Может, так получится оценить k?

Подсказка 4

Опробуйте значение k, используйте правило шифрования в обратную сторону и посмотрите, получилось ли осмысленное слово. Если нет, то может стоит попробовать другое значение k?

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

В слове КЙЫЦНБНЦЛ $9$ букв, значит $n= 9− 2= 7.$ Найдеём остаток

11 25 5 33 3 r32(19 )= r32((19 )⋅19)= r32(9⋅19)= r32((3 ) ⋅57)= r32((− 5) ⋅(−7))= r32(3⋅25)=11

Преобразуем зашифрованный текст в последовательность чисел:

y0 = 10, y1 =9, y2 = 27, y3 = 22, y4 = 13, y5 = 1, y6 =13, y7 = 22, y8 = 11

Из условия следует, что $x8− x0 = 11.$ Рассмотрим разность

r32(y8− y0)=r32(x8+ 6x8⋅k3 +k − x0− 6x0⋅k3 − k)=

= r32((1 +6k3)⋅(x8− x0))= r32(11⋅(1+ 6k3))

Имеем:

r32(11⋅(1+ 6k3))= 1

Заметим, что $r32(3⋅11)= 1.$ Откуда находим $r32(1+ 6k3)= 3.$ Значит,

1+ 6k3 = 3+32t

3 3k =1+ 16t

3 33k = 11+ 11⋅16t

Значит, $r16(33k3)= r16(k3)= 11.$ В итоге

3 k =11+ 16p

При $p= 1$ получим $k3 =27.$ Отсюда $k =3.$ Опробуем полученное значение.

Согласно правилу зашифрования

y = 9= r (x + 6x ⋅27+ 3)= r (x ⋅3+ 3) 1 32 1 1 32 1

3x1+ 3= 9+32t

3x1 =6+ 32t

Т.е. $r32(3x1)= 6,$ тогда $r32(x1)= 2.$ Продолжая дальше получим:

y2 = 27= r32(x2+ 6x2⋅27+3)= r32(x2⋅3+3)

3x2+3 =27+ 32t

3x2 = 24+ 32t

Т.е. $r32(3x2)= 24,$ тогда $r32(x2)= 8.$ В итоге получим слово ВИСОКОС.

Ответ:

ВИСОКОС

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

Задача 9#123668

Каждому из четырех абонентов $A ,A ,A ,A 1 2 3 4$ надо выдать по два уравнения вида $aw +bx+ cy++dz = t,$ где $a,b,c,d,t,w,x,y,z ∈{0,1}.$ Значения секретных битов $w,x,y,z$ одинаковы для всех абонентов и им заранее неизвестны. Приведите хотя бы один пример уравнений, которые надо выдать этим четырем абонентам, чтобы каждая пара ${A1,A3},{A1,A4},{A2,A3}$ могла достоверно вычислить $w,x,y,z,$ но чтобы при этом: $1)$ ни одна другая пара абонентов не могла бы достоверно вычислить более одного секретного бита; $2)$ ни один абонент в одиночку не был в состоянии достоверно вычислить даже один секретный бит. Например, если абонент $A1$ получит уравнения ${w +x +y+ z = 1;w + x+ 0⋅y+0 ⋅z =1},$ а $A2$ — ${w+ 0⋅x+ y+0 ⋅z =0;w+ x+ 0⋅y+ +z = 0}.$ Тогда, объединившись, из имеющихся в их распоряжении четырех уравнений они однозначно найдут, что $w = 1,x =0,y = 1,z =1.$ При этом будем говорить, что пара абонентов ${A1,A2}$ может достоверно вычислить секретные биты $w,x,y,z.$ Здесь традиционно полагается, что $1+ 1= 0.$

Источники: Верченко - 2020, 11.3

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

Подсказка 1

Для начала подумайте, как спрятать один конкретных бит z от всех абонентов, кроме конкретной пары.

Подсказка 2

Можно выбрать один конкретный бит и выдать его первому абоненту (уравнением a = p). А второму выдать уравнение a + z = q. Тогда они смогут угадать секретный бит z. Но как спрятать его от остальных? Каким выбрать a?

Подсказка 3

Попробуйте сделать так, чтобы a зависел от других секретных битов.

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

"Спрятать"один бит, например, $z,$ от всех абонентов, но сделать его доступным для пары ${A ,A } i j$ можно следующим общим способом: выбрать некоторый бит $a,$ пусть $a= p,$ выдать это уравнение $Ai,$ а уравнение $Aj$ — уравнение $a+ z = q (p,q ∈{0,1}$ — произвольные, но зафиксированные значения). Ни $Ai,$ ни $Aj$ не могут достоверно получить значение бита $z$ из имеющихся у них уравнений, но вместе они смогут его вычислить: $a+a +z =z =p+ q.$

Применительно к задаче, в качестве бита $a$ можно использовать сумму других двух секретных бит. Выдадим абоненту $A2$ уравнение $x +y = p1$ а $A1$ — уравнение $x+ y+ z = q1,$ тогда, сложив эти уравнения вместе, пара абонентов ${A1,A2}$ найдет $z = p1+q1.$ Выдадим абоненту $A2$ также уравнение $x+z =p2,$ тогда они найдут бит $y = p2 +q1.$ Очевидно, что при таком способе, если пара абонентов находит $2$ бита, то она найдет и третий, так как он будет присутствовать хотя бы у одного абонента в линейной комбинации: $x =p1+ p2+q1.$

Этот способ можно распространить и на пары абонентов ${A1,A3},{A1,A4},$ проверяя при этом, что пары абонентов ${A2,A3},{A2,A4},{A3,A4}$ не смогут найти ни одного бита.

Ответ:

Например,

$A1 :w+ x= w0+ x0,x+y =x0+ y0$

$A2 :w+ x= w0+ x0,x+y +z = x0+ y0+z0$

$A3 :y+ z = y0+z0,w+ x+ y = w0+ x0 +y0$

$A4 :w+ x+ y = w0+ x0+ y0,x+ y+ z = x0+y0+ z0$

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

Задача 10#123669

Саша решил отправить Маше записку. Для этого каждую букву сообщения он заменил комбинацией из $0$ и $1$ согласно таблице (А— $00000,$ Б— $00001,...,$ Я — $11111).$ Взяв день "Д"и номер месяца "М"своего рождения Саша вычислил $2 2 u1 = Д +M ,u2 = Д ⋅M, u3 = Д− M.$ Далее Саша вычислил четвертое $u4 = r32(u1+ u2u3),$ пятое $u5 = r32(u2+ u3u4),...,$ $n$ -ое число $un =r32(un−3 +un−2un−1),$ где $r32(a)−$ остаток от деления числа $a$ на $32.$ К $i$ -му биту символу исходного сообщения $(0$ или $1)$ он прибавил число $ui$ и взял остаток от деления на $2.$ Полученную последовательность из $0$ и $1$ он вновь преобразовал в буквы по таблице и получил следующее сообщение: ЖДУЛЩБШЛТВШЦЧ. Помогите Маше прочитать его.


A	Б	B	Г	Д	E	Ж	3	И	Й	K	Л	М	H	0	П	P	C	T	У	Ф	X	II	Y	Ш	Ш	T	Ы	Б	9	I0	Я

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1

0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1

0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1

0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Источники: Верченко - 2020, 11.4

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

Подсказка 1

Подумайте, как удобнее воспринимать условие «к i-ому биту символу исходного сообщения Петя прибавил u_i и взял остаток от деления на 2»

Подсказка 2

Поскольку результат зависит только от того, четное u_k или нет, то u_i достаточно смотреть на все сравнения по mod 2 вместо mod 32

Подсказка 3

Как четность u_k зависит от четности Д и М?

Подсказка 4

Записка должна нести осмысленное послание. Исключите неподходящие варианты дешифровок.

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

По условию, числа $u k$ прибавляются к битам открытого текста, а результат заменяется остатком от деления на 2. Заменим на остатки сразу: $uk = 0,$ если четное, и $uk = 1,$ если нечетное. Это не помешает нам вычислить остаток от деления на 32, так как если число четное, остаток будет четным, иначе — нечетным.

Посмотрим, какие последовательности мы получим в зависимости от четности чисел Д и М:

1.: Числа Д, М — нечетные. Тогда $u1 = 0,u2 = 1,u3 = 0,...$
2.: Числа Д, М имеют разную четность. Тогда $u1 = 1,u2 = 0,u3 = 1,...$
3.: Числа Д, М — четные. Тогда $u1,u2,...,u32 = 0.$ В этом случае текст Машиной записки остался бы без изменения, что, очевидно, не так.

Далее необходимо в первых двух случаях полностью вычислить последовательность ${un},$ вычесть ее из зашифрованного текста (ЗТ) и убедиться, что читаемый вариант получается во втором случае (см. таблицу).

$PIC$

Ответ:

СКОРОПЕРЕМЕНА

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

Задача 11#123671

Рассмотрим девять чисел $k,...,k , 1 9$ где $k ∈{0,1,2}. i$ При этом хотя бы одно число $k i$ отлично от нуля. С помощью этих чисел вырабатывают последовательность $u1,u2,...,u2019$ по формулам: $u1 = k1,u2 = k2,...,u9 =k9,ui+9 = r3(ui+ ui+1),$ $i= 1,2,...,2010,$ где $r3(a)$ — остаток от деления числа $a$ на $3.$ Найдите такое наименьшее натуральное число $l,$ что какие бы исходные числа $k1,...,k9$ мы ни взяли, в последовательности $u1,u2,...,ul$ каждое из чисел $0,1$ и $2$ гарантированно встретится хотя бы один раз.

Источники: Верченко - 2020, 11.6

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

Подсказка 1

Нам никто не говорил, какой конкретный набор для k будет дан. Давайте разбирать все варианты, которые могут возникнуть и мы уже решим задачу! Какой будет самым простым для нас?

Подсказка 2

В наборе k могут быть варианты: встречаются все три числа, набор состоит только из единиц или только из двоек, в наборе есть 1 и 2, но нет 0, в наборе есть только 1 и 0 и последний вариант - в наборе только 0 и 2. Для первых вариантов найти l не составляет проблем, осталось понять, что происходит в последних двух случаях!

Подсказка 3

Отдельного внимания стоит случай, где в k единицы не стоят рядом. Нам опять нужен перебор (посмотрим, что будет, если 1 стоит только на первой и/или последней позициях). Но не забудем, что мы решаем через полный перебор, поэтому остальные случаи тоже требует рассмотрения

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

Для каждого набора $k =(k ,...,k ) 1 9$ укажем такое минимальное $l$ , что в соответствующей последовательности $u ,u,...,u 1 2 l$ присутствует каждое из чисел 0, 1 и 2. Затем среди всех таких $l$ останется выбрать наибольшее — это и будет ответом в задаче.

1.

В наборе $k$ встречается каждое из чисел 0, 1 и 2. Тогда искомое $l$ не превосходит 9.

2.

Набор $k$ состоит только из 1. Тогда $u10 =...=u17 = 2$ и $u18 =0.$ Значит, $l= 18.$

Заметим, что случай « $k$ состоит только из 2» эквивалентен, так как если в последовательности ${un},$ отвечающей набору $2k =(2k1,2k2,...),$ заменить все 2 на 1, а 1 — на 2, то получится последовательность, соответствующая набору $k.$

3.

В наборе $k$ присутствуют и 1, и 2, но нет 0. Значит, среди чисел $u1,u2,...,u9$ есть два соседних $(us и us+1),$ одно из которых равно 1, а второе — 2. Тогда $us+9 = 0$ и $l≤ 17.$

4.

Набор $k$ состоит из 0 и 1.

Сразу заметим, что случай « $k$ состоит только из 0 и 2» эквивалентен, так как если в последовательности ${un},$ отвечающей набору $2k = (2k1,2k2,...),$ заменить все 2 на 1, а 1 — на 2, то получится последовательность, соответствующая набору $k.$

Теперь перейдем к разбору. Число 2 впоследствии дадут только две рядом стоящие 1. Поэтому рассматриваем варианты:

а) В $k$ есть рядом стоящие 1. Тогда $l≤19.$

б) В $k$ нет рядом стоящих 1.

Предположим, что 1 есть только на первой и/или последней позициях.

$∙$ Пусть $k = (1,0,...,0).$ В этом случае начало последовательности $u ,u ,... 1 2$ можно вычислить непосредственно:

{un} ={1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,2,1,0,...}

Тогда $l= 27.$

$∙$ Пусть $k = (1,0,...,0,1).$

{un}= {1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,2,1,0...}

Тогда $l= 18.$

$∙$ Пусть $k = (0,...,0,1).$

{un}= {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,2,1,0,...}

Тогда $l= 26.$

Итак, мы рассмотрели все случаи, когда 1 есть только на первой и/или последней позициях.

Иначе найдется номер $s$ такой, что $2≤ s≤ 8$ и $ks = 1.$ Рядом стоящих 1 нет, поэтому $ks− 1 =ks+1 = 0.$ Тогда $us+8 = us+9 = 1.$ Следовательно, $us+17 = 2$ и $l≤25.$

Ответ:

$l= 27$


A	Б	B	Г	Д	E	Ж	3	И	Й	K	Л	М	H	0	П	P	C	T	У	Ф	X	II	Y	Ш	Ш	T	Ы	Б	9	I0	Я

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1

0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1

0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1

0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1


A	Б	B	Г	Д	E	Ж	3	И	Й	K	Л	М	H	0	П	P	C	T	У	Ф	X	II	Y	Ш	Ш	T	Ы	Б	9	I0	Я

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1

0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1

0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1

0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1


A	Б	B	Г	Д	E	Ж	3	И	Й	K	Л	М	H	0	П	P	C	T	У	Ф	X	II	Y	Ш	Ш	T	Ы	Б	9	I0	Я

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1

0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1

0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1

0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1