Реплика: задача с делением и 25519

– Почему криптосистема называется X25519, откуда это 25519?
– Потому что там присутствует 2^255 и 19. Вот только “плюс” или “минус”? А, понятно, конечно, “минус”, поскольку 2^255+19 делится на 3, что очевидно.

Число, являющееся “модулем” в данной криптосистеме, должно быть простым. Соответственно, 2^255 – 19. Но выбор в большей степени обусловлен тем, что такое число имеет удобное двоичное представление: там много единичных битов подряд. Тем не менее, из наблюдения про 2^255 + 19 можно сделать задачу к Новому году: докажите, что 2^2023 + 2023 делится на три.

()

Похожие записки:



Далее - мнения и дискуссии

(Сообщения ниже добавляются читателями сайта, через форму, расположенную в конце страницы.)

Комментарии читателей блога: 5

  • 1. 7th December 2022, 17:42 // Читатель los-romka написал:

    Красивое! 8 лет не игрался в Алгебру. Задачку решаема менее чем за 10 минут в уме :D Оч крутая!

  • 2. 10th January 2023, 13:21 // Читатель Алена написал:

    А есть какой-то признак делимости на 3 для чисел в двоичной системе? Не подскажете, где он описывается? Или решение вашей задачи? Мне очень интересно.
    Если не хотите всем в комментариях показывать, то можно мне подсказку на почту?

  • 3. 10th January 2023, 14:16 // Александр Венедюхин ответил:

    Подсказка: чтобы вывести соответствующий признак делимости для двоичной системы, нужно, например, заметить, что остаток от деления основания 2 на 3 равен -1 (очень похоже на случай 11 для десятичной системы).

    Несколько проще, на мой взгляд, решать в шестнадцатеричной записи, потому что 16 == 3*5 + 1 (в десятичной – 10 == 3**2 + 1).

  • 4. 11th January 2023, 09:26 // Читатель Алена написал:

    Спасибо! С двоичной системой не получилось, а с шестнадцатеричной всё легко доказывается

  • 5. 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.

Написать комментарий

Ваш комментарий:

Введите ключевое слово "24Z67" латиницей СПРАВА НАЛЕВО (<--) без кавычек: (это необходимо для защиты от спама).

Если видите "капчу", то решите её. Это необходимо для отправки комментария ("капча" не применяется для зарегистрированных пользователей). Обычно, комментарии поступают на премодерацию, которая нередко занимает продолжительное время.