Нужно доказать, что
Статья ориентирована на студентов, заинтересованных граждан и просто зевак. У нас защита информации была на пятом курсе в институте. На лекциях по защите информации было много историй о нелегкой судьбе русских программистов в шальные девяностые: как им платили за работу пельменями, которые делались на цокольном этаже предприятия, где они работали, как делается самогон и т.п. А оставшееся время лекции посвящалось собственно аспектам защиты информации. На лекциях давалось очень много теории по темам, хоть как-то связанным с алгоритмами шифрования. На экзамене в каждом билете было пара вопросов по теории и одна задачка.
За день до нашего экзамена ребята с параллельной группы скинули одну задачку(описана в начале статьи), решить которую не смогли. Сидела я на работе, думала, как ее решить, около часа. Какие идеи и первые мысли по решению были у меня в голове на тот момент, я не скажу, уже несколько лет прошло. Кстати мне на экзамене попалась задачка такого же типа. Ниже покажу доказательство двух типовых задачек. Если вы знаете, как доказать по-другому, отпишитесь в комментариях.
Итак, приступим. Доказательство построено с использованием теоремы Эйлера.
Еще раз повторю задание. Нужно доказать, что
делится на 12 для всех простых x > 3.x и 12 — взаимно простые, тогда по т.Эйлера,
делится на 12, т.е. остаток от деления равен 0 (в теореме единица перенесена в правую часть равенства, сделаем так же):
Для числа 12 существует четыре меньших него и взаимно простых с ним чисел (1, 5, 7, 11), поэтому функция Эйлера принимает значение четыре:
Перенесем единицу из правой части равенства влево и воспользуемся формулой из школы, разложим на множители разность квадратов:
Сокращаем на
:
Что и требовалось доказать.
А теперь вот вам еще одна типовая задачка, которая попалась мне на экзамене. Когда решение было показано преподу, он почему-то был удивлен, поскольку, как он потом сказал, было бы достаточно просто посчитать в лоб, возвести в степень и показать, что одно число делится на другое. А решение, которое я ему показала, он видит впервые. Вот всегда думаешь, что для доказательства нужно применить теоремы, следствия, аксиомы, а оказывается «можно было просто в лоб посчитать».
Доказать, что число
делится на 105.Если число делится нацело, то остаток 0. Числа 73 и 105 – взаимно простые => по т. Эйлера:
Вычисляем функцию Эйлера. Поскольку перебирать все числа меньше 105 и искать взаимно простые со 105 долго, разложим 105 на множители и найдем функцию Эйлера для каждого из них, а после просто перемножим:
Переносим единицу влево и раскладываем на множители:
Сокращаем на
:
Разложим на множители и сократим еще раз:
Остаток от деления
на 105 — ноль, деление нацело. Ч.т.д.Возможно, кому-то пригодится это решение, но, надеюсь, что у вас на ЗИ будет что-то поинтереснее.
Комментарии (31)
skiedr
17.12.2016 17:40+6Я скажу больше. x*x — 1 делится на 24 для всех простых x > 3
Sayonji
18.12.2016 00:37+1У меня такое ощущение, как будто тут какой-то флешмоб: все зашли и стали обсуждать статью с примером из задавальника по дискрану первого курса. Мало того, как вы заметили, облегченным примером. Дальше будет статья про то почему простых чисел бесконечно,
Sencho_Pens
17.12.2016 18:31+8Мне кажется, доказать можно проще:
- Раскладываем на
- Т.к.
— простое и нечетное, то
и
— четные =>
? 4
- Среди n подряд идущих натуральных чисел существует единственное ? n (одно из свойств делимости натуральных чисел). Возьмем 3 подряд идущих:
.
? 3
? 3;
skiedr
17.12.2016 18:43+4Из двух соседних четных одно обязательно делится на 4. То есть (x-1)(x + 1) ? 8
saluev
18.12.2016 00:30Вот и я удивился, когда упоминание теоремы Эйлера увидел.
(Простите, это ответ Sencho_Pens.)
- Раскладываем на
artskep
17.12.2016 19:46+12А у меня одного возникает вопрос — какое отношение это имеет к защите информации?
AnROm
17.12.2016 19:51+4У нас много было задачек по теории чисел, полиномам и др. Многие аспекты из теории чисел используются в алгоритмах шифрования.
Karpion
18.12.2016 00:11+5Конкретно эти задачи — никакого отношения к защите информации не имеют. Однако, в системах шифрования очень часто используется операция «остаток от деления» (можно сказать «функция от двух аргументов»), и поэтому программист, работающий с шифрованием данных, должен знать свойства этой операции. А подобные задачи хорошо учат и позволяют проверить уровень теоретической подготовки.
Ну, это примерно как в МИСиС преподавали курс химии, подавляющая часть которого к металлургии никак не относится.masai
18.12.2016 02:18А на экзамене по предмету, связанному с металлургией, вам давали задачки из этого курса химии? Просто тут речь о том, что на экзамене по безопасности задача могла бы быть более приближенной к криптографии, например. Впрочем, это дело преподавателя.
jehy
18.12.2016 11:55+1У нас на защите информации будет шестичасовая bug bounty на специально сделанной для этого уязвимой площадке. Нужно будет при помощи Kali Linux заниматься брутфорсом, XSS атаками, SQL injections и так далее. Дальше рассказать не могу, поскольку являюсь преподавателем этой дисциплины и не хочу спойлерить :) Может, потом напишу сюда отдельным постом.
MooNDeaR
18.12.2016 22:03+2Мне так грустно читать про это, потому что я закончил универ, как раз по направлению ИБ и откровенно говорю, что я дерьмовый спец, просто потому, что не было таких вот мероприятий. В какой-то момент я просто положил болт на учебу, в которой была только тупая теория, и занялся прокачкой своих С++ навыков. Теперь работаю разочарованым в российском образовании программистом…
jehy
19.12.2016 07:08+1Вы не поверите, но ближайшее будущего российского образования — это мы, разочарованные в нём студенты, которые хотят сделать что-то немного лучше. У меня вот договор с работодателем, что я ухожу на день в неделю преподавать. Себе в убыток, зато следующее поколение будет чуть менее разочарованным.
shurupkirov
19.12.2016 09:23странное условие
возьмите x=4, согласно вашего условия
4>3 true
(4*4-1 mod 12)=0 falseAnROm
19.12.2016 09:51+1Условие: для всех простых x > 3
4 — составное число, помимо как на 1 и 4 оно делится еще и на 2
kmu1990
Поправьте меня, если я что-то пропустил, но не нужно ли перед тем как сокращать x^2 + 1 показать, что он взаимно прост с 12?
AnROm
Нужно, спасибо, что поправили
kmu1990
Незачто. Кажется что для этой задачи есть гораздо более простое решение без теоремы Эйлера, а пользуясь только школьными знаниями: рассмотрим 3 числа p-1, p и p+1. Одно из них точно делится на 3, и по-условию это не p, кроме того p-1 и p+1 — оба четные. Собираем все вместе (p-1)(p+1) делится на 3 и на 2^2, т. е. делится на 12.
Stiver
Совершенно верно, эта задачка из старых олимпиадных для младших классов.
PapaBubaDiop
также решается без вычислений
105 = 3 * 5 * 7,
1) деление на 3 доказывается вашим способом, поскольку 73^6 — не делится на 2 и 3.
2) деление на 5 простое возведение в степень разряда единиц 3^2 = 9, 9^2 = 81, 1 в любой степени 1, вычитаем 1 = искомое число кратно 10, то есть делится на 5
3) деление на 7 — 73^3+1 делится на 7 поскольку куб суммы (70+3)^3 = все члены разложения делятся на 7 кроме 3^3=27, но ведь +1)) = 28 тоже чики.
shlemisto
можно ещё степень пошагово понижать:
73^12 = 32^12 = 1024^6 = 26^6 = 2^6 * 13^6 = 2^6 * 64^3 = 2^24 = 1024^2 * 2^4 = 26^2 * 2^4 = 2^2 * 13^2 * 2^4 = 2^2 * 64 * 2^4 = 2^12 = -26 * 2^2 = -104 = 1 (все действия по (mod 105))
итого
1 = 1 mod 105
kmu1990
Вы просто написали, что x^2 + 1 взаимно просто с 12, но не объяснили почему — это как-то странно. Мне вот например, не очевидно почему это так.
mikhaelkh
Очевидно, что не взаимно просто, т.к. простое x>3 нечётное, x^2+1 — чётное.
galaxy
А он и не взаимно прост: как минимум делится на 2 (тем не менее, можно доказать, что не делится на 3 или 4)
kmu1990
И правда, как я сразу не заметил, взаимная простота здесь не обязательна, тем не менее показать, что x^2+1 не кратно 12 все равно нужно, иначе не понятно на каком основании был отброшен множитель x^2+1. Так что для полноты картины покажем, что x^2+1 не делится на 4.
Очевидно, что если x — простое, то x^2 — нечетное, значит x^2-1 и x^2+1 — соседние четные числа, значит одно из них делится на 4, а другое нет. Нужно показать, что на 4 делится именно x^2-1. x^2-1 = (x-1)(x+1), как (x-1) так и (x+1) — оба четные, значит x^2-1 — делится на 4, а x^2+1 ничего не остается кроме как не делиться на 4, а значит и на 12. Все верно?
kmu1990
Нет не верно, взаимная простота все равно нужна.
Errandir
Для x = 5: x? + 1 = 26. А так как 12 и 26 имеют общий делитель (2), они не взаимно простые ? взаимная простота не нужна.
kmu1990
Вы показали ровно то, что она не нужна для x == 5, но есть еще бесконечное количество других x, для которых это тоже нужно показать. Справедливости ради отмечу конечно, что рассматривать бесконечное число всех простых чисел не нужно, потому что мы все равно работаем по модулю 12, но тем не менее нужно рассмотреть больше чем один случай x == 5, чтобы доказать это утверждение.
Взаимная простота гарантирует, что существует обратный по умножению, и значит на него можно домножить левую и правую части равенства и тем самым избавиться от множителя. Так что в общем случае, чтобы сократить взаимная простота необходима. В данном случае может быть можно обойтись и без нее, но это еще тоже нужно доказать.