p-adic Numbers

What if 'closer to zero' means 'divisible by a high power of p' rather than 'small'? p-adic numbers flip our intuitions: the infinite series 1+2+4+8+... converges to -1. This same mathematics explains why integer overflow in C is not a bug but a rigorous algebraic system.

• **int32 overflow:** the behaviour `INT_MAX + 1 = INT_MIN` in C is arithmetic in Z/2^32Z, a special case of 2-adic numbers
• **Cryptography:** the NTRU algorithm uses Hensel lifting for decoding encrypted messages
• **Formal verification:** p-adic norms help prove correctness of algorithms over integers

Предварительные знания

• Modular Arithmetic

The p-adic Valuation

p-adic numbers underpin number-theoretic cryptography: the Weil pairing in BLS12-381 (used by Ethereum 2.0 for 500K+ validators) is defined over p-adic completions. The 2-adic valuation v_2(n) counts trailing zeros in binary - directly measuring cache-line alignment in systems programming.

vp(n) = max{k : p^k | n}. Examples: v2(12) = 2, v3(12) = 1, v5(12) = 0. Valuation of a product: vp(ab) = vp(a) + vp(b). Valuation of a sum: vp(a+b) >= min(vp(a), vp(b)), with equality when vp(a) ≠ vp(b).

The Ring of p-adic Integers Zp

The **p-adic integers** Zp are the completion of Z with respect to the p-adic metric. An element of Zp can be written as an infinite series a0 + a1*p + a2*p^2 + ..., where each coefficient ai is in {0, 1, ..., p-1}. Think of them as 'numbers in base p written infinitely to the left'.

1) Z ⊂ Zp: all ordinary integers embed naturally. 2) Any a with vp(a)=0 (i.e. gcd(a,p)=1) is invertible in Zp. 3) Zp is a local ring with unique maximal ideal pZp. 4) Qp = Zp[1/p] is the field of p-adic numbers, the p-adic analogue of the reals.

Hensel's Lemma

**Hensel's lemma** is a 'lifting' technique: if f(x) ≡ 0 (mod p) and f'(x) ≢ 0 (mod p), the solution can be uniquely lifted to a solution mod p^k for any k. This is the p-adic analogue of Newton's method.

Let f(x) be a polynomial with integer coefficients. If f(a) ≡ 0 (mod p) and f'(a) ≢ 0 (mod p), there exists a unique b ≡ a (mod p) with f(b) ≡ 0 (mod p^2). Applying iteratively yields a solution in Zp.

p-adic Numbers in CS

p-adic numbers appear in cryptography, algorithm analysis, and program verification. Most practically, integer overflow in C/Java is perfectly modelled by the ring Z/2^32Z: a quotient of Z2.

1) Integer overflow: arithmetic in int32 is Z/2^32Z, a quotient of Z2. 2) Hashing: p-adic methods yield uniform hash functions. 3) Formal verification: p-adic numbers are used when proving properties of programs over integers. 4) Hensel lifting underlies NTRU and some post-quantum lattice schemes.

Key Ideas

• **vp(n)**: exponent of p in n; defines the p-adic norm |n|_p = p^(-vp(n))
• **Zp**: completion of Z under the p-adic metric; elements are infinite series in powers of p
• **Hensel's lemma**: a solution f(x) ≡ 0 (mod p) lifts uniquely to Zp when f'(a) ≢ 0 (mod p)
• **In CS:** int32 overflow = arithmetic in Z/2^32Z; Hensel lifting is used in post-quantum cryptography

Related Topics

p-adic numbers bridge modular arithmetic, algebraic number theory, and modern cryptography:

• Modular Arithmetic — Z/p^kZ are finite approximations (truncations) of p-adic numbers
• Algebraic Number Theory — Zp is an example of the ring of integers of a p-adic field
• Post-Quantum Cryptography — Hensel lifting is employed in lattice-based schemes

Вопросы для размышления

• Why does the series 1 + 2 + 4 + 8 + ... converge in Z2 but diverge in the reals? What does this tell us about the notion of 'closeness'?
• How is Hensel's lemma related to Newton's method in numerical analysis? What is the key difference?
• If int32 overflow is modelled by Z/2^32Z, how does this affect code security: and how has it been exploited in real vulnerabilities?

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

• top-01