Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Общий секрет Миллы и Стеллы



Шифрование по таблице

Для зашифрования слова из 5 букв на русском языке его: 1) преобразовали с помощью таблицы (рис. 1) в цепочку чисел 2) выбрали (секретное) натуральное число и дописали сумму к цепочке справа, 3) в расширенной цепочке числа заменили числами по формулам: , если нечетное; , если четное, где еще одно (секретное) натуральное число и, наконец, 4) каждое заменили его остатком от деления на 31. В результате получили вот что: 28, 12, 5, 0, 11, 14. Найдите исходное сообщение.

Решение

Выпишем систему уравнений:

+ .

где

.

Сложив каждое четное уравнение системы, получим:

и

.

Из двух последних уравнений системы, находим:

.

Возьмем разность двух полученных уравнений, находим:

Теперь нетрудно установить, что:

 

В результате имеем:

У   И   А

А если отнять из второго уравнения системы четвертое, можно установить, что:

,

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

Ответ: УЛИКА.

Коммуникатор

Разблокировка коммуникатора осуществляется вводом 4-значного числового кода на сенсорном экране. На клавиатуре первоначальная расстановка цифр после ввода кода меняется в зависимости от случайного простого числа от 7 до 2017, и на месте цифры отображается значение равное последней цифре числа . Пользователь вводит цифры из левой колонки левой рукой, а остальные правой. Восстановите код блокировки, если известно, что при наборе кода пользователь вводил цифры следующим образом:

при : левой, правой, правой, правой;

при : правой, правой, левой, левой;

при : левой, левой, правой, правой;

при : правой, правой, левой, правой.

   

 

   

 

Решение

Из признаков делимости на 2 и на 5 следует, что простое число не может оканчиваться на четную цифру и на цифру 5. Следовательно, такое простое число может оканчиваться лишь на цифры 1, 3, 7, 9. Обозначим, через – последнюю цифру числа , тогда ясно, что выполняется свойство: . Поэтому раскладка клавиатуры определяются лишь указанными последними цифрами – 1, 3, 7, 9. Таким образом, возможны 4 варианта раскладки клавиатуры:

   

   

   

   

Теперь несложно понять, что в условиях задачи следует рассматривать все раскладки:

   

   

   

   

Первая цифра кода при находится в первом столбце, значит это 1, 4 или 7, при эта цифра лежит также в первом столбце – следовательно, она равна 7. Вторая цифра кода при лежит в первом столбце, значит это 7, 8 или 9. Во всех остальных раскладках она лежит в других столбцах (2 -ом или 3-ем). Как видно, таким свойством обладает только цифра 8. Аналогичным образом рассуждая, придем к тому, что единственной комбинацией, удовлетворяющей условиям задачи, будет 7832

Построение шифратора

Для записи текста используются только заглавные буквы, пробелы, точки и запятые – всего различных 36 символов. При зашифровании каждый символ заменили числом от 0 до 35 в соответствии с порядком в «расширенном» алфавите. Затем полученную последовательность чисел разбили на пары, а каждую пару заменили по правилу: пару заменили на пару , где – остаток от деления числа x на 36, а n, k и m – заранее выбранные целые числа от 0 до 35. Найдите все наборы чисел n, k и m, при которых разные пары переходят в разные (это необходимо для возможности расшифрования текста). Сформулируйте правило расшифрования для случая n = k = m = 17. Решение обоснуйте.

Решение

Условие задачи равносильно тому, что при «правильно» выбранных n, k и m система состоящая из уравнений ┤ имеет единственное решение при любой паре . В этом случае разные пары будут переходить в разные , иначе получим противоречие с единственностью решения такой системы при некоторой паре . Обратно, если разные пары переходят в разные пары , то при любой паре такая система либо имеет единственное решение, либо не имеет решений. Однако в то же время количество различных пар равно , а значит количество соответствующих им различных пар по крайней мере , но ясно, что их число не превосходит , а стало быть оно в точности равно . Отсюда следует, что для любой пары рассматриваемая система имеет решение и при том только одно. Можно показать, что уравнение имеет единственное решение при любом тогда и только тогда, когда n и 36 взаимнопросты. Следовательно, если n и 36 взаимнопросты, то из данного уравнения значение находится однозначно и тогда второе уравнение системы примет вид: . Аналогично, оно имеет единственное решение относительно при любом тогда и только тогда, когда m и 36 взаимнопросты, при этом значение параметра k на это свойство никак не влияет. Таким образом, однозначное расшифрование возможно при выборе взаимнопростых с 36 числах n, m и произвольном k. Пусть теперь n=k=m=17. Тогда для нахождения нужно решить систему уравнений: . Легко видеть, что . Отсюда легко проверить, что и .

Общий секрет Миллы и Стеллы

 

Милла и Стелла разговаривают по телефону и хотят выбрать секретное число

так, чтобы оно осталось неизвестным постороннему, возможно подслушивающему

разговор. Для этого Милла подбирает натуральное число a ≤ 256 такое, что числа

r257( ai ) – различны при всех 1 ≤ i ≤ 256 и r257( a256 ) = 1, где r257( t ) – остаток от де-

ления числа t на 257. Затем Милла загадывает натуральное число x ≤ 256 , а Стелла–

натуральное число y ≤ 256. После этого Милла сообщает числа a и r257(ax ) Стелле, а

Стелла ей – число r257( ay ). Теперь они обе вычисляют их секретное число r257( axy ).

Найдите его, если известно, что r257(ax ) = 9, r257( ay ) = 256.

Решение

Обозначим через r257( x ) – остаток от деления на 257 числа x.

Так как r257(ax) = 9 = r257( 32 ) =r257(((r257(at))2)= r257(a2t ),

де 1 ≤ t ≤ 256, r257(at ) = 3. Тогда x = 2t или x = 2t - 256 = 2t’.

Тогда r257( axy ) = r257((256)x ) = r257(r257((-1)x ) ) = r257((-1)2t) = 1.

Переписка Кати и Юры

 

Для шифрования передаваемых сообщений Катя и Юра используют следующий способ. Юра заранее выбрал набор коэффициентов (2, 5, 8, 16), натуральное число u и сообщил их Кате. Для шифрования сообщения (x1,x2,x3,x4), состоящего из нулей и единиц, Катя вычисляет сумму S = 2x1 + +5x2+ 8x3 + 16x4, а затем находит остаток S′ от деления произведения Su на 32 и отсылает S′ Юре. Помогите Юре расшифровать сообщение S′ = 11, то есть найти соответствующую ему строку (x+++1,x2,x3,x4) , если известно, что остаток от деления числа 7u на 32 равен 1.

 

Решение

Обозначим через rM(b) - остаток от деления числа b на M. Запишем чему равно число S′ согласно определению деления натуральных чисел с остатком:

Поскольку известно, что остаток от деления 7u на M равен 1, то запишем:

Домножим обе части (1) на 7 и подставим в полученное равенство вместо 7u равенство (2). Имеем:

Заметим далее, что натуральное число

Поэтому полученное равенство (3) есть не что иное, как деление 7S′ с остатком на M и, кроме того, rM( 7S′) = S. Таким образом, найдя остаток от деления 7S′ на M , получим исходное число S.

В нашем случае, Теперь, зная S, осталось найти (x1,x2,x3,x4). Но это делается легко. Действительно, равенство x4 = 0 очевидно, поскольку S < 16. Дальше можно перебрать все возможные восемь вариантов, либо сразу заметить, что x2 = x3 = 1, x1 = 0(что просто угадывается), либо последовательно вычитать из S числа a3,a2, a1 пока не получим нуль, полагая при этом, что соответствующий xi = 1.

Восстановление бита

Известно, что три числа a1, a2, a3 были получены следующим образом. Сначала выбрали натуральное число A и нашли числа A1= [A]16, A2= [A/2]16, A3= [A/4]16, где [X]16 – остаток от деления целой части числа X на 16 (например, [53/2]16 = 10). Затем было выбрано целое число B такое, что 0 ≤ B ≤ 15 . Числа A1, A2, A3 и B записывают в двоичной системе счисления, т.е. представляют каждое из них в виде цепочки из 0 и 1 длины 4, приписывая слева необходимое число нулей. Такие цепочки условимся складывать посимвольно «в столбик» без переносов в следующий разряд согласно правилам: 1+1 = 0+0 = 0 и 1+0 = 0+1 = 1 , а саму операцию посимвольного сложения обозначим символом ⊕. Например, 3 ⊕ 14 = (0, 0, 1, 1) ⊕ (1, 1, 1, 0) = (1, 1, 0, 1) = 13. Положим a1 = A1⊕B, a2 = A2⊕B, a3 = A3⊕B. Найдите все возможные значения числа a3, если известно, что a1 = 4 , a2 = 10..

 

Ответ

13 и 5

Вскрытие RSA

Известно, что число 14197777 равно остатку от деления на 56887111 некоторого числа x, возведённого в куб. Числа x и 56887111 имеют общий делитель, отличный от 1, а число56887111 является произведением двух простых чисел. Найдите хотя бы одно такое числоx.

Решение

Пусть y=14197777, N=p·q =56887111, p,q – простые числа. По условиюНОД(x,N)=p>1 , то есть x=t·p, где t – натуральное число.

Так как y=rN(x3) - остаток от деления на N числа x3, то НОД(y,N)=p.Вычисляя НОД(14197777, 56887111), находим, что p=10667, тогда y=1331·p, аq=N/p=5333. Делим обе части уравнения

1331·p= rN((t·p)3)

на p, получаем:

1331= rN( t3· p2) = r5333( t3· 106672) = r5333( t3).

Поэтому t = ³√1331 = 11 и x = t·p = 11·10667 = 117337.

Ложь гномов

Для открытия подземелья в волшебной стране надо правильно назвать три целых числа a,b,c, служащих коэффициентами квадратичной функции f(x) = ax2 +bx +c.Представителям четырёх рас были переданы следующие значения функции: троллям –значение f(21), эльфам – f(24), гномам – f(25), оркам – f(28). Когда представители рас встретились, чтобы совместно найти a,b,c, и открыть подземелье, один из представителей, чтобы сорвать мероприятие, предъявил неверное значение. Выясните, кто это был, если известно, что тролли предъявили число 273, эльфы – 357, гномы – 391, орки – 497.

Решение

Разность значений квадратичной функции должна делиться на разность значений аргументов. Проверим выполнение этого факта для различных пар значений:

- для первого и второго: 357–273=84 делится на 3;

- для третьего и четвертого: 497–391=106 не делится на 3; следовательно, значение исказили или гномы, или орки;

- для первого и третьего: 391–273=118 не делится на 4, следовательно, значение исказили тролли или гномы;

- для второго и четвертого: 497–357=140 делится на 4.

Делимость-5

Делится ли число 422008+32009+1991-1 на 385?

Решение

385=5*7*11.

Делится, т.к. число 4k-1 делится на 5 тогда и только тогда, когда k кратно 2, на 7 - тогда и только тогда, когда k кратно 3, на 11 - тогда и только тогда, когда k кратно 5; показатель степени, очевидно, четен.

Далее, число 22008+32009+1991=22008-1+32009+1992 делится на 3, поскольку 2k-1 делится на 3 при четных k и 1992 делится на 3 по известному признаку делимости.

Числа 32009 и 22008 в десятичной записи оканчиваются на 3 и 6 соответственно, поэтому 22008+32009+1991 оканчивается на 0, т.е. делится на 5.

Аффинная перестановка

Для зашифрования сообщения на русском языке его записывают в одну строку без пробелов и знаков препинания. Заглавные буквы заменяются на строчные. В получившейся цепочке буквы нумеруются слева направо 1,2,...,L. Зашифрование происходит путем перестановки букв исходной цепочки по следующему правилу. Фиксируем два натуральных числа a и b. Буква с номером n в исходной цепочке должна в зашифрованной цепочке иметь номер, равный остатку от деления числа a·n+b на L (с одним исключением: если a·n+bнацело делится на L, то остаток полагается равным L). Например, если длина цепочки L=25 и a=9,b=11, то третья буква исходной цепочки будет тринадцатой в зашифрованной цепочке (т.к. 9·13+11=38, а число 38 дает остаток 13 при делении на 25). Известно, что в результате применения этого метода зашифрования к цепочке из 43 букв

светитнезнакомаязвездасновамыоторваныотдома

была получена цепочка

таытоеонсоовзмевтрадазедвмаянтоаысзаимнонвк

При этих же значениях a, b проведено зашифрование еще некоторой цепочки из 28 букв. Получилось вот что:

Видхьврлмаояооаоддсемдроиввоеозтообнзо

Найдите значения a и b и восстановите исходное сообщение.

Решение

Для начала найдём в открытом тексте две уникальные буквы (по возможности близкие). Это например К и Я, стоящие соответственно на 12 и 16 позициях в открытом тексте. В шифрованном тексте они стоят соответственно на 43 и на 28.

Составляем систему уравнений

{ 12a+b=43k
16a+b=28+43l

Вычитая, получаем уравнение 4a=28+43m , при m=0 находим a=7, из первого уравнения находим b=2.

Расшифровав второй текст, получим:

Морозвоеводадозоромобходитвладеньясвои

Делимость-4

Делится ли число 222007+32008-2009-1 на 1155?

Решение

Да, делится. Число вида 2k-1 делится на 3 тогда и только тогда, когда k четно, на 5 - тогда и только тогда, когда k кратно 4, на 7 - тогда и только тогда, когда kкратно 3, а на 11 - тогда и только тогда, когда k кратно 10.

Показатель степени 22007+32008-2009 делится на 4; он делится на 3, т.к.

22007+32008-2009= (22007-2006)+(32008-3)= (22007-2-2004)+(32008-3)= 2·(22006-1-1002)+(32008-3)

где 22006-1-1002 делится на 3. Поэтому в соответствии с первыми тремя критериями N делится на 3, 5 и 7. Числа 32008 и 22007 в десятичной записи оканчиваются на 1 и 8 соответственно, поэтому 22007+32008-2009 делится на 10. Таким образом, число N=222007+32008-2009-1 делится на 3·5·7·11=1155.

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.