Функции и координатная плоскость

Этот урок необязателен

Этот урок — подготовка к CRYPTO-09 (Эллиптические кривые). Если вы помните, что такое функция и координатная плоскость, смело переходите к CRYPTO-01: Модулярная арифметика. Вернитесь сюда перед CRYPTO-09, если чувствуете необходимость.

Вспомните

Прежде чем читать дальше, попробуйте ответить:

1. Что такое функция? Чем f(x) = x^2 отличается от f(x) = 2x + 1 визуально?

2. Что такое наклон (slope) прямой?

3. Если точка (3, 5) лежит на кривой, симметричной относительно оси x, какая ещё точка на этой кривой?

Если ответили уверенно — вы готовы к эллиптическим кривым. Если нет — за 15 минут вспомним всё, что нужно.

Функции как отображения

Функция f: X -> Y сопоставляет каждому элементу из множества X (область определения, domain) ровно один элемент из множества Y (кодомен, codomain).

Ключевое слово: ровно один. Для каждого входа существует единственный выход.

Попробуйте:

• Переключитесь между f(x) = 2x+1, f(x) = x^2 и f(x) = x mod 7
• Посмотрите, как таблица значений меняется
• Обратите внимание на свойства: инъективность и сюръективность

Аналогия для разработчика: чистая функция в TypeScript: (x: number) => number. Один и тот же вход всегда дает один и тот же выход, без побочных эффектов.

# Функция в Python -- это то же самое:
def f(x):
    return 2 * x + 1

# Чистая функция: один вход -> один выход, всегда
assert f(5) == 11
assert f(5) == 11  # вызов повторно -- результат тот же

Инъективность и сюръективность

Эти свойства функций напрямую связаны с криптографией:

Инъективность (one-to-one)

Разные входы всегда дают разные выходы:

f(a) = f(b) => a = b

Пример: f(x) = 2x + 1 — инъективна (если 2a+1 = 2b+1, то a = b). Контрпример: f(x) = x^2 — не инъективна (f(-2) = f(2) = 4).

В крипто: идеальная хеш-функция стремится к инъективности — разные входы должны давать разные хеши. На практике коллизии возможны (входов больше, чем выходов), но найти их должно быть вычислительно сложно.

Сюръективность (onto)

Каждый элемент кодомена является выходом хотя бы для одного входа:

Для каждого y из Y существует x из X, такой что f(x) = y

Пример: f(x) = x mod 7 — сюръективна на Z_7 (каждое число 0-6 достижимо). Контрпример: f(x) = x^2 — не сюръективна на Z (отрицательные числа не выходы).

Биекция (bijection)

Функция, которая одновременно инъективна и сюръективна. Это идеальное отображение — для каждого выхода существует ровно один вход.

В крипто: шифрование с ключом должно быть биекцией — каждому открытому тексту соответствует ровно один шифротекст, и наоборот (иначе расшифрование невозможно).

# Биекция: шифрование XOR с ключом
def encrypt(plaintext, key):
    return plaintext ^ key

def decrypt(ciphertext, key):
    return ciphertext ^ key

# encrypt -- биекция: каждый вход дает уникальный выход
# decrypt -- обратная функция
assert decrypt(encrypt(42, 137), 137) == 42

Координатная плоскость

Координатная плоскость — это способ визуализировать функции. Каждая точка задается парой координат (x, y):

• x — горизонтальная ось (вправо = больше)
• y — вертикальная ось (вверх = больше)

Попробуйте:

• Режим “Точки”: наведите мышь для координат
• Режим “y = 2x + 1”: обратите внимание на треугольник rise/run
• Режим “y = x^2”: параболу не перепутаешь с прямой
• Режим “y^2 = x^3 + 7”: это кривая secp256k1 над вещественными числами!

Наклон прямой (slope)

Наклон показывает, насколько круто поднимается (или опускается) прямая:

slope = rise / run = (y2 - y1) / (x2 - x1)

Для прямой y = 2x + 1:

• Точки: (0, 1) и (2, 5)
• rise = 5 - 1 = 4
• run = 2 - 0 = 2
• slope = 4 / 2 = 2

В CRYPTO-09 вы будете вычислять наклон прямой, соединяющей две точки на эллиптической кривой. Этот наклон — ключевая часть операции сложения точек (point addition), основной операции криптографии на эллиптических кривых.

# Наклон прямой через две точки:
def slope(x1, y1, x2, y2):
    return (y2 - y1) / (x2 - x1)

print(slope(0, 1, 2, 5))  # 2.0 -- наклон y = 2x + 1

Симметрия

Симметрия относительно оси x: если точка (x, y) принадлежит фигуре, то и точка (x, -y) тоже принадлежит ей. Отражение “переворачивает” знак y-координаты.

В эллиптических кривых это критически важно:

• Кривая y^2 = x^3 + ax + b всегда симметрична относительно оси x
• Для каждой точки P = (x, y) на кривой существует точка -P = (x, -y)
• Это свойство используется для определения обратного элемента в группе точек кривой
• Операция P + (-P) дает “точку на бесконечности” O — нейтральный элемент группы

# Симметрия: если (x, y) на кривой y^2 = x^3 + 7,
# то и (x, -y) тоже на кривой
x = 1
y_squared = x**3 + 7  # 8
y = 8 ** 0.5           # 2.828...

# Проверка: оба варианта удовлетворяют уравнению
assert abs(y**2 - (x**3 + 7)) < 1e-10
assert abs((-y)**2 - (x**3 + 7)) < 1e-10  # (-y)^2 = y^2
print(f"Точки: ({x}, {y:.3f}) и ({x}, {-y:.3f})")

Кривая y^2 = x^3 + 7

Это уравнение кривой secp256k1 — той самой, которую используют Bitcoin и Ethereum. Над вещественными числами она выглядит как плавная кривая (переключитесь на режим “y^2 = x^3 + 7” в диаграмме выше).

Но в CRYPTO-09 вы увидите эту же кривую над конечным полем GF(p) — и она выглядит совершенно иначе: как разбросанные точки без видимой структуры. Несмотря на хаотичный вид, все алгебраические свойства (сложение, симметрия, групповой закон) сохраняются.

import math

# Точки на кривой y^2 = x^3 + 7 (вещественные числа)
for x in range(-1, 6):
    rhs = x**3 + 7
    if rhs >= 0:
        y = math.sqrt(rhs)
        print(f"x={x}: y = +/-{y:.3f}")
    else:
        print(f"x={x}: нет вещественных y (x^3 + 7 = {rhs} < 0)")

Где вы это встретите

Что дальше?

Вы вспомнили все необходимые математические основы! Теперь переходите к CRYPTO-01: Модулярная арифметика — первому уроку основного курса. Если по ходу курса встретите незнакомый термин, в каждом уроке есть ссылки обратно на эти refresher-уроки.