dxdt.ru: занимательный интернет-журнал

Разгадка к задаче про 2^255+19. В диалоге из “эпиграфа” к задаче говорится, что “очевидно, 2^255 + 19 делится на три”. Практически вся современная криптография так или иначе использует арифметику остатков. Поэтому понять, что 2^255 + 19 делится на три можно моментально: 2^255 при делении на 3 (mod 3) даёт остаток -1 (см. ниже); а 19 – это +1 (mod 3), потому что на 3 делится 18, соответственно, 19 == 6*3 + 1. Сумма остатков -1 + 1 == 0. Следовательно, число делится на три.

Почему 2^255 даёт остаток -1? Потому что 255 – нечётное число. Действительно, 2 в чётной степени будет давать остаток 1 (mod 3), а в нечётной остаток -1 (или 2, что здесь то же самое), так как 2 == 1*3 + (-1). Из этого можно вывести признак делимости на 3 для числа в двоичной записи, то есть, когда основание системы равно двум. А именно: биты со значением 1 (единица) на чётных позициях будут давать +1, на нечётных -1; если сумма (по единичным битам) делится на 3, то и само число делится. Пример (позиции считаем справа налево): 42 == 0b00101010; 1 + 1 + 1 == 3, следовательно, делится; 42 == 14*3; 43 == 0b00101011; 1 + 1 + 1 + (-1) == 2, следовательно, 43 не делится на 3.

Решение для 2^2023 + 2023. Доказываем, что делится на 3:
2^2023 (mod 3) == -1 (см. выше)
2023 = 2022 + 1; воспользуемся привычным признаком делимости для десятичной системы: 2 + 2 + 2 == 6, то есть, 0 (mod 3) => 2023 == 1 (mod 3)
-1 + 1 == 0

Естественно, возможны и другие, чем-то более привычные, способы. Например, в шестнадцатеричной системе, где 2^2023 это будет восьмёрка со множеством нулей, а 2023 == 0x07E7, поэтому в записи нашего числа, кроме нулей, встречаются только шестнадцатеричные цифры 8, 7, E и 7. В шестнадцатеричной системе действует тот же признак делимости на 3, что и в десятичной (“если сумма значений цифр делится на 3”), потому что основание системы 16 == 15 + 1, то есть, остаток 1. Шестнадцатеричное E это 14: 8 + 7 + 14 + 7 == 36; 36 == 12*3.

Адрес записки: https://dxdt.ru/2023/01/20/9460/