Модулярная арифметика

Зачем это блокчейну?

Каждый раз, когда вы отправляете Bitcoin-транзакцию, ваш кошелек выполняет десятки операций модулярной арифметики в 256-битном простом поле. Приватный ключ умножается на точку эллиптической кривой по модулю огромного простого числа p = 2^256 - 2^32 - 977. Цифровая подпись ECDSA вычисляет обратный элемент по модулю порядка кривой.

Без модулярной арифметики невозможны ни ключи, ни подписи, ни адреса. Давайте разберемся, как это работает — начиная с простых часов.

# Вот что делает ваш кошелек при каждой транзакции:
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
private_key = 42  # ваш секретный ключ
k = 123456789     # случайное число для подписи

# Обратный элемент по модулю — ключевая операция подписи
k_inv = pow(k, -1, p)
print(f"k^(-1) mod p = {k_inv}")

Интуитивное объяснение: аналогия с часами

Представьте обычные часы. Сейчас 10 часов. Через 5 часов будет… 3 часа (не 15!). Часы «оборачиваются» после 12. Это и есть модулярная арифметика:

10 + 5 = 15 = 3 (mod 12)

Числа «живут» на круге, а не на прямой. Когда мы достигаем модуля, мы начинаем сначала.

Попробуйте:

• Установите N = 12, нажмите на 10, затем на 5 — результат 3
• Установите N = 7, нажмите на 4 и 5 — результат 2
• Установите N = 2 — это двоичная арифметика (0 или 1)

Алгоритмический уровень: Python

В Python оператор % выполняет операцию по модулю:

# Базовые операции
print(10 + 5)       # 15
print((10 + 5) % 12) # 3 — как на часах

# Модулярная арифметика в поле Z_7
a, b, p = 4, 5, 7
print((a + b) % p)   # 2 — сложение
print((a - b) % p)   # 6 — вычитание (не -1!)
print((a * b) % p)   # 6 — умножение

Обратный элемент по модулю

В обычной арифметике обратный элемент для a — это 1/a. В модулярной арифметике обратный элемент a^(-1) — это число x, такое что a * x = 1 (mod p).

# Python 3.8+ поддерживает модулярный обратный:
p = 7
a = 3
a_inv = pow(a, -1, p)  # = 5, потому что 3 * 5 = 15 = 1 (mod 7)
print(f"{a} * {a_inv} = {a * a_inv} = {(a * a_inv) % p} (mod {p})")

# Проверка: все ненулевые элементы Z_p имеют обратные
for x in range(1, p):
    x_inv = pow(x, -1, p)
    assert (x * x_inv) % p == 1
    print(f"{x}^(-1) = {x_inv} (mod {p})")

Используйте калькулятор ниже для экспериментов с различными операциями:

Модулярное возведение в степень

Вычисление a^b mod n — одна из самых частых операций в криптографии. Наивный подход (умножить a само на себя b раз) слишком медленный для 256-битных чисел.

Алгоритм «возведение в квадрат и умножение» (Square-and-Multiply)

Идея: разложить показатель степени в двоичную форму и обрабатывать бит за битом.

def fast_modpow(base, exp, mod):
    """O(log n) вместо O(n) — разница между секундами и вечностью"""
    result = 1
    base = base % mod

    while exp > 0:
        if exp % 2 == 1:       # Если текущий бит = 1
            result = (result * base) % mod  # Умножаем
        exp = exp >> 1          # Сдвиг: следующий бит
        base = (base * base) % mod  # Квадрат

    return result

# Пример: 3^13 mod 17
print(fast_modpow(3, 13, 17))  # 12
print(pow(3, 13, 17))          # 12 — встроенная функция делает то же самое

Почему это важно? В Bitcoin показатель степени — это 256-битное число. Наивный подход потребовал бы 2^256 умножений (больше, чем атомов во Вселенной). Square-and-multiply делает это за ~256 шагов.

Попробуйте пошагово пройти алгоритм:

1. Нажмите «Далее» для каждого шага
2. Обратите внимание на двоичное представление показателя
3. На каждом шаге: квадрат, и если бит = 1, дополнительное умножение

Математический уровень

Конгруэнция

Два числа конгруэнтны по модулю n, если их разность делится на n:

a ≡ b (mod n)  ⟺  n | (a - b)

Примеры: 15 ≡ 3 (mod 12), потому что 12 | (15 - 3) = 12.

Малая теорема Ферма

Если p — простое число и gcd(a, p) = 1, то:

a^(p-1) ≡ 1 (mod p)

Следствие: a^(-1) ≡ a^(p-2) (mod p). Именно так Python вычисляет pow(a, -1, p):

p = 17
a = 3
# Два способа найти обратный элемент — дают одинаковый результат:
print(pow(a, -1, p))    # через расширенный алгоритм Евклида
print(pow(a, p - 2, p)) # через малую теорему Ферма

Теорема Эйлера (обобщение)

Для любого n (не обязательно простого) и gcd(a, n) = 1:

a^φ(n) ≡ 1 (mod n)

где φ(n) — функция Эйлера (количество чисел от 1 до n, взаимно простых с n).

Для простого p: φ(p) = p - 1, что дает малую теорему Ферма как частный случай.

Где это используется в блокчейне

Практика

Закрепите знания в Jupyter notebook: выполните упражнения по модулярной арифметике, реализуйте расширенный алгоритм Евклида и докажите малую теорему Ферма для малых простых чисел.

Notebook: labs/crypto/notebooks/01-modular-arithmetic.ipynb

Что дальше?

В следующем уроке мы перейдем от отдельных операций к алгебраическим структурам — группам и конечным полям. Вы увидите, почему числа по модулю простого числа образуют поле, и почему это критично для эллиптических кривых Bitcoin.