Реплика: задача с делением и 25519
– Почему криптосистема называется X25519, откуда это 25519?
– Потому что там присутствует 2^255 и 19. Вот только “плюс” или “минус”? А, понятно, конечно, “минус”, поскольку 2^255+19 делится на 3, что очевидно.
Число, являющееся “модулем” в данной криптосистеме, должно быть простым. Соответственно, 2^255 – 19. Но выбор в большей степени обусловлен тем, что такое число имеет удобное двоичное представление: там много единичных битов подряд. Тем не менее, из наблюдения про 2^255 + 19 можно сделать задачу к Новому году: докажите, что 2^2023 + 2023 делится на три.
(Решение: записка и комментарии ниже.)
Адрес записки: https://dxdt.ru/2022/12/07/9355/
Похожие записки:
- Офтопик: знаки из точек, манускрипт и буква ë в английском
- "Авторизованный трафик" и будущее Интернета
- Бесконечные процессы как корни уравнений
- ML-KEM на тестовом сервере TLS
- Статья про защиту DNS-доступа
- Развитие автоматических "говорилок" (чат-ботов)
- Записки за февраль 2024
- Совпадения тегов ключей DNSSEC и парадокс дней рождения
- Записки за май 2024
- Совпадающие фрагменты текстов и манускрипты
- Обобщение ИИ и "кнопки на пульте"
Кратко этот сайт характеризуется так: здесь можно узнать про технологический прогресс, Интернет, математику, криптографию, авиацию, компьютеры, авиационные компьютеры, вооружения, роботов, вооружение роботов, армии мира, астрономию, космические исследования. И иногда о чём-то ещё (
Комментарии читателей блога: 5
1 <t> // 7th December 2022, 17:42 // Читатель los-romka написал:
Красивое! 8 лет не игрался в Алгебру. Задачку решаема менее чем за 10 минут в уме :D Оч крутая!
2 <t> // 10th January 2023, 13:21 // Читатель Алена написал:
А есть какой-то признак делимости на 3 для чисел в двоичной системе? Не подскажете, где он описывается? Или решение вашей задачи? Мне очень интересно.
Если не хотите всем в комментариях показывать, то можно мне подсказку на почту?
3 <t> // 10th January 2023, 14:16 // Александр Венедюхин:
Подсказка: чтобы вывести соответствующий признак делимости для двоичной системы, нужно, например, заметить, что остаток от деления основания 2 на 3 равен -1 (очень похоже на случай 11 для десятичной системы).
Несколько проще, на мой взгляд, решать в шестнадцатеричной записи, потому что 16 == 3*5 + 1 (в десятичной – 10 == 3**2 + 1).
4 <t> // 11th January 2023, 09:26 // Читатель Алена написал:
Спасибо! С двоичной системой не получилось, а с шестнадцатеричной всё легко доказывается
5 <t> // 27th January 2023, 08:35 // Читатель Сергей написал:
Начнем с простого: 2^2 = 1 (mod 3) (это малая теорема Ферма: для простого p и 0 < a 2^2023 (mod 3) = ((2^2)^1011) * (2^1) (mod 3) = (1^1011) * 2 (mod 3) = 2.
А значит, 2^2023 + 2023 (mod 3) = 2 + 2023 (mod 3) = 2025 (mod 3) = 0, т.е. 2^2023 + 2023 нацело делится на 3.
Написать комментарий