Множества и операции

Вспомните

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

1. Что такое множество? Чем множество отличается от списка в Python?

2. Что такое объединение и пересечение множеств?

3. Что значит “операция замкнута на множестве”?

Если на все три ответили — просто пробегитесь по диаграммам. Если нет — разберёмся за 15 минут.

Множества

Множество — это набор уникальных элементов без определённого порядка.

Аналогия разработчика: множество = Python set. Нет дубликатов, нет порядка.

# Python:
A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}

# Принадлежность (in / not in):
print(3 in A)       # True   -- в математике: 3 ∈ A
print(6 in A)       # False  -- в математике: 6 ∉ A

# Пустое множество:
empty = set()       # в математике: ∅

# Подмножество:
C = {1, 2, 3}
print(C < A)        # True   -- в математике: C ⊂ A
print(C.issubset(A))  # True

Математическая запись:

Операции над множествами

Четыре основных операции над множествами — и у каждой есть прямой аналог в Python:

Попробуйте каждую операцию и обратите внимание, какие области Venn-диаграммы подсвечиваются:

A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}

print(A | B)   # {1, 2, 3, 4, 5, 6, 7}  -- объединение
print(A & B)   # {3, 4, 5}              -- пересечение
print(A - B)   # {1, 2}                 -- разность
print(A ^ B)   # {1, 2, 6, 7}           -- симметрическая разность

Бинарные операции

Бинарная операция берёт два элемента и возвращает один.

Аналогия разработчика: это метод, который принимает два аргумента одного типа и возвращает тот же тип:

// TypeScript: бинарная операция
type BinaryOp<T> = (a: T, b: T) => T;

// Примеры:
const add: BinaryOp<number> = (a, b) => a + b;
const mul: BinaryOp<number> = (a, b) => a * b;
const modAdd: BinaryOp<number> = (a, b) => (a + b) % 5;

# Python: бинарная операция
def mod_add(a: int, b: int) -> int:
    return (a + b) % 5

# Это бинарная операция на Z_5 = {0, 1, 2, 3, 4}:
print(mod_add(3, 4))  # 2  (потому что 7 % 5 = 2)

Свойства операций

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

Попробуйте переключить структуру и посмотрите, какие свойства выполняются:

• Z_5, + (mod 5) — все 5 свойств выполняются (это группа!)
• Z_5, x (mod 5) — замкнутость есть, но не у всех элементов есть обратные (0 не имеет обратного)
• Z*_7, x (mod 7) — все свойства выполняются (это тоже группа, и коммутативная!)

Замкнутость (closure)

Результат операции всегда остаётся в множестве.

# Z_5 с + (mod 5): замкнуто
Z5 = {0, 1, 2, 3, 4}
assert all((a + b) % 5 in Z5 for a in Z5 for b in Z5)

# Аналогия: если сложить два uint8, получим uint8 (с переполнением)

“a + b всегда даёт целое, если a и b — целые.” В модулярной арифметике (a + b) % n всегда в диапазоне {0, ..., n-1}.

Коммутативность (commutativity)

Порядок аргументов не важен: a * b = b * a.

# Сложение коммутативно:
assert 3 + 5 == 5 + 3  # True

# Умножение матриц НЕ коммутативно:
# A @ B != B @ A (в общем случае)

Ассоциативность (associativity)

Скобки не важны: (a * b) * c = a * (b * c).

# Сложение ассоциативно:
assert (2 + 3) + 4 == 2 + (3 + 4)  # True: 9 = 9

# Вычитание НЕ ассоциативно:
assert (10 - 3) - 2 != 10 - (3 - 2)  # 5 != 9

Нейтральный элемент (identity)

Элемент e, который не меняет другие элементы: a * e = a.

# Для сложения: e = 0 (потому что a + 0 = a)
# Для умножения: e = 1 (потому что a * 1 = a)
# Для модулярного сложения mod 5: e = 0
# Для модулярного умножения mod 7: e = 1

Обратный элемент (inverse)

Для каждого a существует a^(-1) такой, что a * a^(-1) = e.

# Для сложения: обратный к 3 -- это -3, потому что 3 + (-3) = 0
# Для модулярного сложения mod 5:
# обратный к 3 -- это 2, потому что (3 + 2) % 5 = 0

# Для модулярного умножения mod 7:
# обратный к 3 -- это 5, потому что (3 * 5) % 7 = 1
print(pow(3, -1, 7))  # 5

Чтение формальных определений

Теперь вы готовы прочитать формальное определение. Переведём по словам:

∀ a, b ∈ G: a * b ∈ G

По-русски: “Для любых двух элементов a и b из G, их произведение a * b тоже принадлежит G.”

В Python: all(a * b in G for a in G for b in G)

Ещё пример:

∀ a ∈ G, ∃ a^(-1) ∈ G: a * a^(-1) = e

По-русски: “Для каждого элемента a из G существует обратный элемент a^(-1) в G, такой что их произведение равно нейтральному элементу.”

В Python: all(any(op(a, b) == e for b in G) for a in G)

От множества к группе — превью

Множество + операция + четыре свойства = группа:

Если группа ещё и коммутативна (ab = ba), она называется абелевой группой.

Аналогия разработчика: группа — это интерфейс с 4 ограничениями. Множество “реализует” этот интерфейс, если все 4 свойства выполняются.

// Группа как интерфейс:
interface Group<T> {
  elements: Set<T>;
  operation: (a: T, b: T) => T;  // замкнутость + ассоциативность
  identity: T;                     // нейтральный элемент
  inverse: (a: T) => T;           // обратный элемент
}

Именно это CRYPTO-02 будет разбирать подробно — группы, кольца и конечные поля. Теперь у вас есть словарь, чтобы понять тот урок с первого раза.

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

Что дальше?

Вы вспомнили три фундамента:

1. Числа и нотация — язык математики
2. Простые числа и делимость — “атомы” арифметики
3. Множества и операции — “интерфейсы” алгебры

Теперь вы готовы к CRYPTO-01: Модулярная арифметика, где всё это объединится в конкретные криптографические конструкции. Удачи!