• XSS.stack #1 – первый литературный журнал от юзеров форума

Задачи по математике и критпографии

Отслеживать

AKella

(L2) cache
Пользователь
Регистрация
30.12.2004
Сообщения
410
Реакции
15
1. Найдите две последние цифры числа 3 в степени 2005.

2. (Устойчивость к перебору-2) Для подтверждения своих полномочий в компьютерной системе, пользователь должен ввести свое имя и пароль, состоящий из семи букв русского алфавита с исключенными Ё и Ь. Файл с паролями пользователей хранится на сервере в зашифрованном виде. Для их зашифрования использовался следующий способ. Буквам алфавита сопоставлены числа от 0 до 30: А - 0, Б - 1, , Я - 30. При зашифровании пароля каждую его букву заменяют остатком от деления на 31 значения выражения 4a3+3a2+9a+28, где а - число, соответствующее заменяемой букве.

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

љАлиса хочет войти в систему под чужим именем, а соответствующий этому имени пароль не знает. Она написала программу, которая в случайном порядке перебирает пароли. Какой из двух паролей - КОСИНУС или ТАНГЕНС - <устойчивее> к действию этой программы?

3. На каждой из трех осей установлено по одной вращающейся шестеренке и неподвижной стрелке. Шестеренки соединены последовательно. На первой шестеренке 10 зубцов, на второй - 8, на третьей - 7. На каждом зубце первой, второй и третьей шестеренок в порядке возрастания по часовой стрелке написаны цифры от 0 до 9, от 0 до 7 и от 0 до 6 соответственно. Когда стрелка первой оси указывает на цифру, стрелки двух других осей так же указывают на цифры. Найти период последовательности, полученной следующим образом. Выписывается наибольшая цифра из тех, на которые указывают стрелки, затем первая шестеренка поворачивается на 36 градусов по часовой стрелке, выписывается наибольшая цифра и т.д.

4. (Диск Альберти-4) Для зашифрования текста использовался вращающийся диск, центр которого находится на оси, закрепленной на неподвижном основании. Диск разделен на 33 равных сектора, в которые в неизвестном порядке вписаны все буквы русского алфавита (по одной в каждый сектор). На основании, по одной напротив каждого сектора, выписаны буквы в алфавитном порядке по часовой стрелке. Каждое положение диска, получающееся из исходного поворотом на угол, кратный величине угла сектора, задает соответствие между буквами на диске и на основании. При зашифровании очередной буквы текста, ее заменяли соответствующей ей буквой при текущем положении диска, после чего диск поворачивался на один сектор по часовой стрелке. Найдите наименьшую длину такой последовательности букв, что если нам станет известен результат ее зашифрования, мы сможем однозначно восстановить расположение букв на диске.

5. Шалтай-Болтай предлагает Алисе при зашифровании текста с помощью диска Альберти (задача N4) после каждой буквы поворачивать диск не на один, а на семь секторов. Стоит ли Алисе принять это предложение? (Ответ обосновать).
 
1. Найдите две последние цифры числа 3 в степени 2005.
ответ - 3 , (3^401)^5
на каждую четвертую степень тройки в конце - 1. Еще одна стпень - 3. еще на 5 - 3...

4a3+3a2+9a+28 - полином или просто многочлен нулевой степени?
 
Хммм вот немного подумал:

3^2005 = 81^500 * 243
Самая последняя по-любому 3
предпоследняя 3x + 4, где x - предпоследняя в 81^500
для восьмерки можно посчитать что через каждые 4 степени будет 0 предпоследней.
значит ответ - 43
если я где-то ошибся - поправьте :unsure:
 
4*a^3+3*a^2+9*a+28 - полином, иначе немного неправильно всё получается
Для их зашифрования использовался следующий способ. Буквам алфавита сопоставлены числа от 0 до 30: А - 0, Б - 1, Я - 30. При зашифровании пароля каждую его букву заменяют остатком от деления на 31 значения выражения 4*a^3+3*a^2+9*a+28, где а - число, соответствующее заменяемой букве.
Выпишем все буквы в алфавите и пронумеруем их исключив Ё и Ь:
2.gif

Теперь найдем числа которыми заменяется каждая буква:
1) A -> 0 = (4*0^3 + 3*0^2 + 9*0 + 28) mod 31 = 28 mod 31 = 28; A -> 28
2) Б -> 1 = (4*1^3 + 3*1^2 + 9*1 + 28) mod 31 = 44 mod 31 = 13; Б -> 13
...
Написав пару строк на с++ я получил производные позиции всех букв:
1.gif

Теперь рассмотрим первое слово: КОСИНУС
К -> 16, O -> 0, C -> 23, Н -> 15 , У -> 16, C -> 23
Посчитаем совпадения позиций в шифрованом алфавите из получившегося слова: 16 встречается 3 раза, 0 3 раза, 23 два раза, 15 один, 16 три и 23 два. Т.е. количество возможных значений 3*3*2*1*3*2 = 108.

Теперь рассмотрим слово: ТАНГЕНС
Аналогично ТАНГЕНС -> 0,28,16,4,28,16,23. Где количество совпадений 3,3,3,1,3,3,2 соответственно. Количество возможных паролей 3*3*3*1*3*3*2 = 486.

Отношение ТАНГЕНС:КОСИНУС = 486/108 = 4,5.
Вывод: ТАНГЕНС лучше КОСИНУСА :)


А первая задачка, то вообще в 9 классе проходится вроде))) Модульная арифметика называется :)
Вот решение:
Представим 3^2005 как 3^5*3^2000. Разложим 2000 на простые множители: 2,2,2,2,5,5,5. Чтобы получить последние две цифры, нам нужно 3^2005 mod 100 :)
Объясню кто незнает правила умножения по модулю. Например 11^6 mod 100 = (11^2 mod 100)^3 mod 100;
1) 11^2 mod 100 = 121 mod 100 = 21
2) 21^3 mod 100 = 9621 mod 100 = 61 - как нам и нужно было, последние две цифры. Если хотите проверьте 11^6 = 1771561. Т.е. действия с небольшими числами.

Тепер рассмотрим наш случай :). ((3^5 mod 100)*((((((((3^2) mod 100))^2 mod 100)^2 mod 100)^2 mod 100)^5 mod 100)^5 mod 100)^5)
На вид что-то страшное и непонятное :) Разберемся по действиям:
1) 3^2 mod 100 = 9
2) 9^2 mod 100 = 81
3) 81^2 mod 100 = 61
4) 61^2 mod 100 = 21
5) 21^5 mod 100 = 1
6) 1^5 mod 100 = 1
7) 1^5 mod 100 =1
8) 3^5 mod 100 = 43
9) 43*1 mod 100 = 43
Последние две цифры числа 3^2005 -> 43. Dude03, ты правильно решил задачу, но запутанно немного :)





Как остальные сделаю, выложу решение )
 
А первая задачка, то вообще в 9 классе проходится вроде))) Модульная арифметика называется :)
Вот решение:
Представим 3^2005 как 3^5*3^2000. Разложим 2000 на простые множители: 2,2,2,2,5,5,5. Чтобы получить последние две цифры, нам нужно 3^2005 mod 100 smile.gif
Объясню кто незнает правила умножения по модулю. Например 11^6 mod 100 = (11^2 mod 100)^3 mod 100;
1) 11^2 mod 100 = 121 mod 100 = 21
2) 21^3 mod 100 = 9621 mod 100 = 61 - как нам и нужно было, последние две цифры. Если хотите проверьте 11^6 = 1771561. Т.е. действия с небольшими числами.

Тепер рассмотрим наш случай smile.gif. ((3^5 mod 100)*((((((((3^2) mod 100))^2 mod 100)^2 mod 100)^2 mod 100)^5 mod 100)^5 mod 100)^5)
На вид что-то страшное и непонятное :) Разберемся по действиям:
1) 3^2 mod 100 = 9
2) 9^2 mod 100 = 81
3) 81^2 mod 100 = 61
4) 61^2 mod 100 = 21
5) 21^5 mod 100 = 1
6) 1^5 mod 100 = 1
7) 1^5 mod 100 =1
8) 3^5 mod 100 = 43
9) 43*1 mod 100 = 43
Последние две цифры числа 3^2005 -> 43. Dude03, ты правильно решил задачу, но запутанно немного :)
Угу=( не догадался на 100 поделить
 
admin


Напишите ответ...
  • Вставить:
Прикрепить файлы
Верх