Первая серия задач
1.1. Проверьте, будет ли 2003 простым числом.
1.2. Под комбинаторной сложностью шифра понимается количество связанных с ним секретных ключей. Шифруемый текст, содержащий 64 буквы, построчно вписывается в таблицу 8x8. Криптограмма получается последовательным выписыванием букв по ходу некоторого маршрута шахматной ладьи, начинающегося из левой нижней клетки, - он и является ключом. Какова комбинаторная сложность этого перестановочного шифра?
1.3. Цифры обозначены буквами. Зная, что в фразе
И ВСЕ ЖЕ ОН НЕ ПРАВ
каждое слово является квадратом некоторого натурального числа, выпишите соответствие между цифрами и буквами.
1.4. Заданы четыре неотрицательных числа a, b, c, d, каждое из которых не превосходит 50000. Известно, что a<=x<=b, c<=y<=d. Напишите программу для определения наименьшего и наибольшего значений для x OR y.
1.5. Концевыми буквами слова называются его первая и последняя буквы. Выписано некоторое количество слов, причем у каждого слова концевые буквы разные и любые два слова отличаются хотя бы одной концевой буквой. Докажите, что из концевых букв этих слов по крайней мере две входят в одинаковое число слов.
Вторая серия задач
2.1. Докажите, что если числа p и 8p2+1 - простые, то число 8p2-1 тоже простое.
2.2. (RSA-155) В системе шифрования RSA используются натуральные числа, разложимые в произведение двух больших простых сомножителей. Перемножьте простые числа
102639592829741105772054196573991675900716567808038066803341933521790711307779
и
106603488380168454820927220360012878679207958575989291522270608237193062808643.
2.3. Буквы алфавита А, В, Д, Е, К, Л, Н, О, Р заменены знаками таким образом, что слова ВЕНА и ЛОРД шифруются соответственно как и
. Каким знаком естественно обозначить букву К?
2.4. Криптограмма C получается перестановкой букв открытого текста M длины n. Пусть P=p1p2...pn, где pi, 1<=i<=n, обозначает позицию в C, которую занимает i-я буква из M. Строится последовательность Q=q1q2...qn, в которой qi равно количеству pj, 1<=j< i , таких что pj>pi. Например, если M=БЕГИ и P=2,4,3,1, то C=ИБГЕ и Q=0,0,1,3. Имея C и Q, как можно восстановить M? В частности, расшифруйте криптограмму ВСУАИТИАИАРПМНМТЧДЕЫЛОИПК, зная, что Q=0,1,2,3,1,4,5,2,4,8,3,4,6,0,11,6,2,3,14,7,10,2,13,6,5.
2.5. Текст содержит 50 букв и имеет одинаковые начальную и конечную буквы. Можно ли вписать его ходами шахматного коня в квадрат 7x7, последним ходом вернувшись в исходную точку?
Третья серия задач
3.1. Докажите, что 15-ричное число 123456789ABCDE делится на 7.
3.2. Открытый текст записан в алфавите А, В, Д, Е, К, Л, Н, О, Р, С, Т, У, Ш. Нечетные буквы этого текста шифруются циклически сдвигом по алфавиту на k позиций вправо, а четные - циклическим сдвигом по алфавиту на k позиций влево. Расшифруйте криптограмму
ООЛО ТОВКН ВРАНУА СНРШВ КЕЕОВТУО,
зная, что одно из слов открытого текста начинается и кончается одной и той же буквой.
3.3. Решето Эратосфена находит все простые числа p, не превосходящие заданное натуральное число n. Выписываются числа 2, 3, 4, 5,..., n. Затем для k=2, 3,...[n1/2](целая часть) повторяется следующая процедура. Если k находится в списке, вычеркнуть из него все кратные: 2k, 3k, 4k, ... .Числа, оставшиеся в списке, и будут простыми. Напишите программу, реализующую этот алгоритм для n <=109.
3.4. В алфавите Е, Н, О, Т записаны слова НО, ОН, НЕ, ОТ. Придумайте алфавит с меньшим количеством букв для того, чтобы закодировать эти четыре слова. При этом должны соблюдаться следующие условия: 1) каждая буква старого алфавита заменяется одной определенной буквой нового алфавита; 2) любые два из четырех указанных слов различаются в новой записи. Сколькими существенно разными способами это можно сделать?
3.5. В условиях задачи 1.5 докажите, что если среди концевых букв выписанных слов только две входят в нечетное число слов, то эти буквы можно соединить цепочкой примыкающих слов (два слова называются примыкающими, если у них есть общая концевая буква).
Четвертая серия задач
4.1. 25 букв английского алфавита (j отождествляется с i) последовательно вписаны в некоторую таблицу, которая является ключом. На этом ключе открытый текст o! why zebra? шифруется как 5473428293221621 (знаки ! и ?, а также пробелы исключены). Найдите криптограмму для сообщения Olympiad in cryptography.
4.2. (RSA-21?) Разложите на простые множители число 414 030 798 119 522 429 281.
4.3. Расшифруйте криптограмму
ПА4БЕ(АБ)(АГ)(А2Г)ЕЛЕ(АЕ)(ЕА)(А2А2)А3Е(ААГ)С(АГА)А(ГАА)(АБГ)(А2Б)А(АА2)(БА)ЫЙ(ААБ)(ГА2)(АА3)Э(А2Г)(А3А)Г(ААА2)Б2АХ(АА2А)Г2Е(ГА2).
4.4. Составьте программу, которая в заданном целом числе n, 0<=n<=109, определит количество ненулевых двоичных разрядов.
4.5. В условиях задачи 3.5 докажите, что, если любые две концевые буквы соединимы цепочкой примыкающих слов, то для упомянутых двух особых букв можно построить соединяющую их цепочку указанного вида, которая будет содержать все выписанные слова.