Теория чисел

p-адические числа

Переполнение int32 в C - это не ошибка, а арифметика в Z_{2^32}. p-адические числа - формализация этой идеи. Ряд 1+2+4+8+... = -1 строго сходится в 2-адической топологии. NTRU криптосистема, альтернатива RSA в постквантовом мире, работает именно в Z_p.

  • NTRU криптография: постквантовая альтернатива RSA работает в кольцах Zp
  • Переполнение integer: арифметика int32 в CPU - это Z_{2^32} арифметика
  • Лемма Хензеля: подъём решений уравнений mod p - алгоритм аналитического продолжения
  • Алгебраические числа: p-адические числа в доказательстве теоремы Ферма
  • Криптографические протоколы: p-адические экспоненты в конструкциях на кривых
  • Численный анализ: p-адическая интерполяция для L-функций Дирихле

Бесконечный ряд 1+2+4+8+... сходится к -1 в Z₂ - и это не парадокс, а строгая математика. p-адические числа переворачивают интуицию: «большие» степени p - это малые числа. Это не экзотика: переполнение int32, NTRU криптография, тактики оптимизации компиляторов - всё это Z₂ в действии.

**О чём этот урок на самом деле:** есть разные способы «измерять расстояние» на ℚ. Обычное: |a-b|. p-адическое: |a-b|ₚ. Каждое даёт другое пополнение: ℝ или Qₚ. Теорема Островского: это все возможные нормы. p-адические числа - такой же законный анализ, как вещественный, просто с другой геометрией.

p-адическая норма vs обычная

Ультраметрическое неравенство: все треугольники равнобедренные

В p-адической метрике: если |a|ₚ ≠ |b|ₚ, то |a+b|ₚ = max(|a|ₚ, |b|ₚ). Это строго сильнее обычного неравенства треугольника. Следствие: в p-адическом пространстве каждая точка внутри шара является его центром. Это принципиально другая геометрия.

**p-адические числа в современных системах** От математики до production-криптографии • TLS 1.3 / ECDH: Арифметика над Fp связана с Qp. Curve25519 использует поле F_{2^255-19}. 2^255-19 - простое число, арифметика над ним напрямую связана с 2-адической теорией через лемму Хензеля. • NTRU / Kyber (NIST PQC): Лемма Хензеля для декодирования. NTRU (стандартизован NIST 2022) использует подъём Хензеля. Kyber основан на Module-LWE над кольцами Z_q[x]/(xⁿ+1) - p-адическая структура. • Компиляторы (GCC/LLVM): Целочисленные оптимизации. Умножение на константу через сдвиги: n*5 = n*4+n = n<<2+n. Это арифметика в Z₂. Анализ переполнения: Z/2^k Z. • Алгоритмы теории чисел: Подъём Хензеля для целочисленного факторинга. Dixon, Quadratic Sieve, General NFS используют p-адические методы для factorization. Подъём решений mod p к mod p^k.

p-адическая валюация: другое понятие близости

Каждое HTTPS-соединение использует эллиптические кривые над полями, связанными с p-адической арифметикой. TLS 1.3 по умолчанию - ECDH на Curve25519. Лежащая в основе математика: **p-адические числа**, где «близость» определяется делимостью на p. 1024 ближе к нулю, чем 3 - потому что 1024 = 2^10 делится на 2^10, а 3 не делится на 2 вообще.

Вычислите v₃(54) и |54|₃. Почему 54 ближе к нулю в 3-адической метрике, чем 5?

Поля Qp: пополнение Q по p-адической норме

Вещественные числа ℝ - это пополнение ℚ по обычной норме |·|. p-адические числа Qₚ - это пополнение ℚ по p-адической норме |·|ₚ. Теорема Островского: всего существуют |·|, |·|₂, |·|₃, |·|₅, ... - и это **все** нормы на ℚ. Разные нормы, разные геометрии, разная математика.

Элемент Zₚ (p-адическое целое) записывается как бесконечная сумма a₀ + a₁p + a₂p² + ..., где aᵢ ∈ {0,...,p-1}. Это «числа в базе p, идущие влево бесконечно». Обычные целые числа включены: 7 = 7 (конечная запись). Число -1 = (p-1) + (p-1)p + (p-1)p² + ... (бесконечная запись, аналог 0.999...=1).

**Теорема Островского (1916):** каждая нетривиальная норма на ℚ эквивалентна либо обычной |·|, либо p-адической |·|ₚ для некоторого простого p. Это значит, что все возможные «понятия близости» для рациональных чисел - это одна обычная и бесконечно много p-адических. ℝ и Qₚ - равноправные пополнения ℚ.

Как выглядит 3-адическое разложение числа -1 в Z₃? Каковы первые 4 коэффициента a₀, a₁, a₂, a₃?

Лемма Хензеля: подъём решений mod p к Zp

Лемма Хензеля - p-адический аналог метода Ньютона: если уравнение f(a) ≡ 0 (mod p) имеет «невырожденное» решение (f'(a) ≢ 0 mod p), то это решение **единственным образом поднимается** до решения mod p^k для любого k, и в пределе - до точного решения в Zₚ. Например, √2 существует в Z₇ (но не в Z₃).

При каком условии лемма Хензеля гарантирует единственность подъёма? Почему условие f'(a) ≢ 0 (mod p) критично?

p-адические числа в криптографии и CS

**Переполнение int32** в C/Java - это арифметика в Z/2^32Z, кольцо вычетов, являющееся фрагментом Z₂. INT_MAX + 1 = INT_MIN - математически корректное поведение в Z₂. **NTRU** - lattice-based шифрование (стандарт NIST PQC 2022) использует подъём Хензеля при декодировании. Каждый раз, когда компилятор оптимизирует целочисленное умножение - он использует p-адическую арифметику.

Объясните, почему поведение int32 при переполнении описывается кольцом Z/2^32Z. Как это связано с Z₂?

Число n|n|_∞ (обычная)|n|_2 (2-адическая)v₂(n)
1110
221/21
441/42
1024 = 2^1010241/1024 ≈ 0.00110
3310
12 = 4·3121/42

a = 5, b = 3 |a|_5 = 1/5 (v_5(5) = 1) |b|_5 = 1 (v_5(3) = 0) |a+b|_5 = |8|_5 = 1 (v_5(8) = 0) max(|a|_5, |b|_5) = max(1/5, 1) = 1 |a+b|_5 = 1 = max(1/5, 1) ✓ ультраметрика выполнена Обычное неравенство треугольника тоже: 1 ≤ 1/5 + 1 = 6/5 ✓ Но ультраметрика сильнее: 1 ≤ max(1/5, 1) = 1 (равенство!)

Упражнения

  1. Почему бесконечный ряд 1+2+4+8+... сходится в Z₂, но расходится в ℝ? — Сходимость = частичные суммы Cauchy в данной метрике В ℝ: |Sₙ|=2ⁿ-1→∞ - расходится В Z₂: |Sₙ-(-1)|₂ = |2ⁿ|₂ = 2^{-n} → 0 - сходится! Смена метрики меняет понятие сходимости - два разных мира
  2. Как лемма Хензеля связана с методом Ньютона? — Шаг: a_new = a - f(a)/f'(a), но mod p^(2k) Каждая итерация: точность mod p^k → mod p^(2k) (квадратичная сходимость) Условие: f'(a) ≢ 0 mod p - невырожденность (как в методе Ньютона) Разница: метод Ньютона в ℝ, Хензель в Zₚ - разные пополнения ℚ

Ключевые идеи

  • vₚ(n) = степень p в n; |n|ₚ = p^{-vₚ(n)} - большие степени p означают малую p-адическую норму
  • Ультраметрика: |a+b|ₚ ≤ max(|a|ₚ, |b|ₚ) - сильнее обычного треугольника
  • Zₚ = пополнение Z по |·|ₚ; элементы = бесконечные ряды Σaₖpᵏ, aₖ ∈ {0,...,p-1}
  • Теорема Островского: |·|, |·|₂, |·|₃, ... - все нормы на ℚ; ℝ и Qₚ равноправны
  • Лемма Хензеля: f(a)≡0 mod p, f'(a)≢0 mod p → единственный подъём до Zₚ (Ньютон в Zₚ)
  • int32 переполнение = Z/2^32Z; NTRU/Kyber (NIST PQC) используют Хензеля; v₂ = trailing zeros

Связанные темы

p-адические числа объединяют модулярную арифметику и алгебраическую теорию чисел

  • Эллиптические кривые — ECC над Fp связана с Qp; подъём Хензеля используется при вычислении точек кривой
  • Модулярная арифметика — Z/pᵏZ - конечные приближения Zₚ; подъём от mod p к mod pᵏ
  • Теорема Ферма - Уайлс — Доказательство использует деформации Галуа в p-адических представлениях

Связанные уроки

  • top-01
p-адические числа

0

1

Войти