Comments 32
Поправьте меня, если я что-то пропустил, но не нужно ли перед тем как сокращать x^2 + 1 показать, что он взаимно прост с 12?
Нужно, спасибо, что поправили
Незачто. Кажется что для этой задачи есть гораздо более простое решение без теоремы Эйлера, а пользуясь только школьными знаниями: рассмотрим 3 числа p-1, p и p+1. Одно из них точно делится на 3, и по-условию это не p, кроме того p-1 и p+1 — оба четные. Собираем все вместе (p-1)(p+1) делится на 3 и на 2^2, т. е. делится на 12.
Совершенно верно, эта задачка из старых олимпиадных для младших классов.
73^12 — 1 делится на 105?
также решается без вычислений
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 тоже чики.
Вы просто написали, что x^2 + 1 взаимно просто с 12, но не объяснили почему — это как-то странно. Мне вот например, не очевидно почему это так.
А он и не взаимно прост: как минимум делится на 2 (тем не менее, можно доказать, что не делится на 3 или 4)
И правда, как я сразу не заметил, взаимная простота здесь не обязательна, тем не менее показать, что 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. Все верно?
Очевидно, что если 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. Все верно?
Нет не верно, взаимная простота все равно нужна.
Для x = 5: x² + 1 = 26. А так как 12 и 26 имеют общий делитель (2), они не взаимно простые ⇒ взаимная простота не нужна.
Вы показали ровно то, что она не нужна для x == 5, но есть еще бесконечное количество других x, для которых это тоже нужно показать. Справедливости ради отмечу конечно, что рассматривать бесконечное число всех простых чисел не нужно, потому что мы все равно работаем по модулю 12, но тем не менее нужно рассмотреть больше чем один случай x == 5, чтобы доказать это утверждение.
Взаимная простота гарантирует, что существует обратный по умножению, и значит на него можно домножить левую и правую части равенства и тем самым избавиться от множителя. Так что в общем случае, чтобы сократить взаимная простота необходима. В данном случае может быть можно обойтись и без нее, но это еще тоже нужно доказать.
Взаимная простота гарантирует, что существует обратный по умножению, и значит на него можно домножить левую и правую части равенства и тем самым избавиться от множителя. Так что в общем случае, чтобы сократить взаимная простота необходима. В данном случае может быть можно обойтись и без нее, но это еще тоже нужно доказать.
Я скажу больше. x*x — 1 делится на 24 для всех простых x > 3
Мне кажется, доказать можно проще:
- Раскладываем на
- Т.к.
— простое и нечетное, то
и
— четные =>
⋮ 4
- Среди n подряд идущих натуральных чисел существует единственное ⋮ n (одно из свойств делимости натуральных чисел). Возьмем 3 подряд идущих:
.
⋮ 3
⋮ 3;
Из двух соседних четных одно обязательно делится на 4. То есть (x-1)(x + 1) ⋮ 8
Вот и я удивился, когда упоминание теоремы Эйлера увидел.
(Простите, это ответ Sencho_Pens.)
(Простите, это ответ Sencho_Pens.)
UFO just landed and posted this here
А у меня одного возникает вопрос — какое отношение это имеет к защите информации?
У нас много было задачек по теории чисел, полиномам и др. Многие аспекты из теории чисел используются в алгоритмах шифрования.
А у меня другой вопрос: неужели только я не понимаю, как это решать?
Конкретно эти задачи — никакого отношения к защите информации не имеют. Однако, в системах шифрования очень часто используется операция «остаток от деления» (можно сказать «функция от двух аргументов»), и поэтому программист, работающий с шифрованием данных, должен знать свойства этой операции. А подобные задачи хорошо учат и позволяют проверить уровень теоретической подготовки.
Ну, это примерно как в МИСиС преподавали курс химии, подавляющая часть которого к металлургии никак не относится.
Ну, это примерно как в МИСиС преподавали курс химии, подавляющая часть которого к металлургии никак не относится.
У нас на защите информации будет шестичасовая bug bounty на специально сделанной для этого уязвимой площадке. Нужно будет при помощи Kali Linux заниматься брутфорсом, XSS атаками, SQL injections и так далее. Дальше рассказать не могу, поскольку являюсь преподавателем этой дисциплины и не хочу спойлерить :) Может, потом напишу сюда отдельным постом.
Обязательно пишите! Буду ждать ))
Мне так грустно читать про это, потому что я закончил универ, как раз по направлению ИБ и откровенно говорю, что я дерьмовый спец, просто потому, что не было таких вот мероприятий. В какой-то момент я просто положил болт на учебу, в которой была только тупая теория, и занялся прокачкой своих С++ навыков. Теперь работаю разочарованым в российском образовании программистом…
странное условие
возьмите x=4, согласно вашего условия
4>3 true
(4*4-1 mod 12)=0 false
Могу предложить своё решение с перебором.
Рассмотрим 6 последовательностей: типа 6*k, 6*k+1, 6*k+2, 6*k+3, 6*k+4, 6*k+5. В общем виде 6*k+A, где A — постоянно.
Первая будет 6,12,18,24… вторая 7,13,19,25… и так далее.
Предполагаем, что есть такое значение k, что (6*k+A)^2=12*N+1, т.е. дает 1 по модулю 12.
Тогда по индукции, следующее значение в той же последовательности будет 6*(k+1)+A = 6*k+A+6 также будет давать в квадрате 1 по модулю 12.
(6*k+A+6)^2 = (6*k+A)^2 + 12(6*k+A)+36=12(6*k+A)+36 +12*N+1
Объединение всех последовательностей покрывают все натуральные числа. При этом 6*k, 6*k+2, 6*k+4 — четные, а 6*k+3 — делятся на 3.
Таким образом нужно проверить лишь последовательности 6*k+1 и 6*k+5.
первая проверяется числом 7, вторая числом 5.
7*7 = 49 =12*4+1
5*5 = 25 =12*2+1
Рассмотрим 6 последовательностей: типа 6*k, 6*k+1, 6*k+2, 6*k+3, 6*k+4, 6*k+5. В общем виде 6*k+A, где A — постоянно.
Первая будет 6,12,18,24… вторая 7,13,19,25… и так далее.
Предполагаем, что есть такое значение k, что (6*k+A)^2=12*N+1, т.е. дает 1 по модулю 12.
Тогда по индукции, следующее значение в той же последовательности будет 6*(k+1)+A = 6*k+A+6 также будет давать в квадрате 1 по модулю 12.
(6*k+A+6)^2 = (6*k+A)^2 + 12(6*k+A)+36=12(6*k+A)+36 +12*N+1
Объединение всех последовательностей покрывают все натуральные числа. При этом 6*k, 6*k+2, 6*k+4 — четные, а 6*k+3 — делятся на 3.
Таким образом нужно проверить лишь последовательности 6*k+1 и 6*k+5.
первая проверяется числом 7, вторая числом 5.
7*7 = 49 =12*4+1
5*5 = 25 =12*2+1
Sign up to leave a comment.
Задание с экзамена по защите информации