Простые числа и делимость

Вспомните

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

1. Что такое делитель числа? Сколько делителей у числа 12? А у числа 13?

2. Что такое НОД (наибольший общий делитель)? Чему равен НОД(12, 8)?

3. Что значит “два числа взаимно просты”?

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

Делимость

Говорят, что a делит b (записывается a | b), если b делится на a без остатка:

a | b  означает  b % a == 0

# Python:
def divides(a, b):
    return b % a == 0

# Делители числа 12:
n = 12
divisors = [d for d in range(1, n + 1) if n % d == 0]
print(divisors)  # [1, 2, 3, 4, 6, 12] -- 6 делителей

# Делители числа 13:
n = 13
divisors = [d for d in range(1, n + 1) if n % d == 0]
print(divisors)  # [1, 13] -- только 2 делителя (это простое число!)

Простые числа и решето Эратосфена

Простое число — это число больше 1, у которого ровно два делителя: 1 и оно само.

Аналогия разработчика: Простые числа — это “атомы” арифметики. Как атомы нельзя разложить на более простые вещества, так простые числа нельзя представить как произведение меньших чисел.

Самый древний алгоритм поиска простых — Решето Эратосфена (III век до н.э.). Пошагово вычёркиваем составные числа:

Нажимайте “Далее”, чтобы увидеть, как решето отсеивает составные числа. Обратите внимание:

• Достаточно проверить делители до sqrt(50) ≈ 7
• После вычёркивания кратных 2, 3, 5, 7 — все оставшиеся числа простые

# Проверка на простоту (наивный способ):
def is_prime(n):
    if n < 2:
        return False
    for d in range(2, int(n**0.5) + 1):
        if n % d == 0:
            return False
    return True

# Первые 25 простых:
primes = [n for n in range(2, 100) if is_prime(n)]
print(primes[:25])
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
#  53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Основная теорема арифметики

Каждое целое число больше 1 можно единственным образом представить как произведение простых чисел:

360 = 2^3 * 3^2 * 5

Это называется каноническое разложение (prime factorization).

Попробуйте:

• Введите 360 — классический пример (2^3 * 3^2 * 5)
• Введите 2 или 17 — простые числа не имеют разложения
• Введите 256 (2^8) — чистая степень двойки
• Введите 997 — большое простое число

Почему это важно для криптографии: если бы мы могли быстро разложить большие числа на множители, RSA-шифрование было бы взломано. Безопасность RSA основана на том, что разложение числа n = p * q (где p и q — большие простые) — вычислительно неосуществимая задача.

# Разложение на множители:
def factorize(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

print(factorize(360))  # {2: 3, 3: 2, 5: 1}
# Читаем: 360 = 2^3 * 3^2 * 5^1

НОД (наибольший общий делитель)

НОД(a, b) — наибольшее число, которое делит и a, и b.

Пример: НОД(12, 8) = 4, потому что 4 — самый большой делитель, общий для 12 и 8.

Алгоритм Евклида — один из древнейших алгоритмов (ему 2300 лет!). Идея проста: НОД(a, b) = НОД(b, a mod b).

Нажимайте “Далее”, чтобы увидеть каждый шаг алгоритма Евклида. Обратите внимание на прямоугольники: каждый шаг “отрезает” квадраты размером b от прямоугольника a x b, пока не останется квадрат — это и есть НОД.

import math

# Встроенный:
print(math.gcd(252, 105))  # 21

# Своя реализация:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(252, 105))  # 21
# Шаги: 252 = 2*105 + 42, 105 = 2*42 + 21, 42 = 2*21 + 0
# НОД = 21

Взаимно простые числа

Два числа взаимно просты (coprime), если их НОД равен 1:

gcd(a, b) = 1 -- значит a и b не имеют общих делителей кроме 1

import math

# Примеры:
print(math.gcd(15, 28))  # 1 -- взаимно просты
print(math.gcd(15, 25))  # 5 -- НЕ взаимно просты

# Проверка:
def coprime(a, b):
    return math.gcd(a, b) == 1

print(coprime(7, 13))   # True (оба простые, разные)
print(coprime(8, 15))   # True (8=2^3, 15=3*5, нет общих множителей)
print(coprime(6, 9))    # False (оба делятся на 3)

Почему это важно: модулярный обратный элемент a^(-1) mod n существует только если a и n взаимно просты. Это ключевое условие для вычисления ECDSA-подписей (CRYPTO-11) и ключей RSA (CRYPTO-08).

Функция Эйлера phi(n)

phi(n) — количество чисел от 1 до n, взаимно простых с n.

Формулы:

• Для простого p: phi(p) = p - 1 (все числа от 1 до p-1 взаимно просты с p)
• Для произведения двух простых: phi(p * q) = (p - 1) * (q - 1)

import math

def euler_totient(n):
    """Вычисляет phi(n) напрямую"""
    return sum(1 for k in range(1, n + 1) if math.gcd(k, n) == 1)

# Примеры:
print(euler_totient(7))    # 6 (простое: 7-1=6)
print(euler_totient(10))   # 4 (числа 1,3,7,9 взаимно просты с 10)
print(euler_totient(12))   # 4 (числа 1,5,7,11)

# Для RSA: n = p * q
p, q = 61, 53
n = p * q                  # 3233
phi_n = (p - 1) * (q - 1)  # 3120
print(f"phi({n}) = {phi_n}")  # phi(3233) = 3120

Где встретите: phi(n) появляется в теореме Эйлера (CRYPTO-01): a^phi(n) ≡ 1 (mod n). Это обобщение малой теоремы Ферма и основа для RSA-шифрования (CRYPTO-08), где d = e^(-1) mod phi(n).

Таблица “Нотация = Python”

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

Что дальше?

В следующем уроке мы вспомним множества и операции — язык, на котором описываются группы и поля. После этого урока вы будете готовы к CRYPTO-02.