FLINT3.7.0-dev
/
Overview

p-adic arithmetic in FLINT

FLINT has two independent implementations of \mathbf{Q}_p. The original modules padic, padic_poly, padic_mat and qadic work with any prime p, store elements as fmpz integers and use a fixed precision per variable. The newer padic_radix works for word-size p, stores the unit in a radix p^e representation, tracks an error term for every element, and implements the generic ring interface, so that polynomials, matrices and power series over it are available through gr_poly, gr_mat and gr_series.

Modules and representations#

ModuleElementsPrecision modelp
padicp^v u, u an fmpzfixed absolute precision N per variable, inputs exactany
padic_polyp^v f(X), f \in \mathbb{Z}[X]one v and one N for all coefficientsany
padic_matp^v M, M an fmpz_matone v and one N for all entriesany
qadicp^v g(X) \bmod f in \mathbf{Q}_q = \mathbf{Q}_p[X]/(f)as padic_polyany
padic_radixp^v u + O(p^N), u a radix_integer_tball with its own N; context caps on absolute and relative precisionword-size

In the fixed-precision modules every function computes the exact result for the stored inputs and reduces it modulo p^N for the output; no loss of precision is detected. In padic_radix every function applies the precision rules of Precision of arithmetic operations to the error terms, and exact elements remain exact when the result fits the context precision. Both models are described in Precision and representation of p-adic numbers. Unramified extensions exist only in the fixed-precision model (qadic); ramified extensions are not implemented.

The storage differs as well. An fmpz unit needs \lceil (N - v)\log_2 p \rceil bits, and reduction modulo p^{N - v} is a division by an integer. A radix_integer_t stores the base-p^e digits, with p^e chosen as large as possible (for example 7^{22} on a 64-bit machine), so reduction modulo a power of p^e is a truncation, valuations are found by inspecting the lowest digit, and no conversion from binary is needed for printing.

Algorithms#

OperationMethodFunctionsDetails
Inverse of a unitextended Euclid modulo p, Newton lifting z \gets 2z - uz^2padic_inv, _padic_inv, qadic_inv, padic_radix_invInverses
Square rootroot modulo p (or Artin–Schreier modulo 8 for p = 2 in \mathbf{Z}_q), lifting of the inverse square rootpadic_sqrt, qadic_sqrt, padic_radix_sqrt, padic_radix_rsqrtSquare roots
Exponentialrectangular splitting, or bit-burst splitting with binary splittingpadic_exp*, qadic_exp*, padic_radix_exp*The p-adic exponential and logarithm
Logarithmrectangular splitting, product decomposition with binary splitting, or the Satoh–Skjernaa–Taguchi reductionpadic_log*, qadic_log*, padic_radix_log*The p-adic exponential and logarithm
Teichmüller liftNewton iteration for t^q - tpadic_teichmuller, qadic_teichmullerTeichmüller lifts
Frobenius \Sigma^eNewton lifting of \Sigma^e(X), composition by rectangular splittingqadic_frobeniusFrobenius automorphism and Teichmüller lifts in unramified extensions
Trace in \mathbf{Q}_qpower sums by Newton's identitiesqadic_traceTrace
Norm in \mathbf{Q}_qSylvester determinant, or \exp(\operatorname{Tr}\log x)qadic_norm, qadic_norm_resultant, qadic_norm_analyticNorm
Products of polynomials and matricesexact products over \mathbb{Z}, then reductionpadic_poly_mul, padic_mat_mul, qadic_mulMultiplying polynomials over Z
Dot products, matrix productsdelayed carries over radix limbspadic_radix_dot, gr_mat_mul over padic_radix

padic_poly_mul and padic_mat_mul multiply the integer parts with fmpz_poly_mul and fmpz_mat_mul and reduce once; the valuations simply add. padic_poly_inv_series lifts a power series inverse by Newton iteration over \mathbb{Z}/p^{N}\mathbb{Z}. Polynomial and matrix algorithms not listed here (division, GCD, factorisation, linear solving) are not implemented in the fixed-precision modules; over padic_radix the generic algorithms of gr_poly and gr_mat apply, with the precision loss tracked by the ball arithmetic.

Choosing a module#

  • For new code with word-size p, padic_radix is faster and reports the precision of every result; it is the only choice if precision loss must be detected, and the only module with polynomials and matrices that support division and linear algebra (through the generic rings).
  • For multiword primes, for unramified extensions, and for code that needs padic_poly, padic_mat or the Frobenius map, the fixed-precision modules are needed. Their results are exact functions of the stored inputs, so the caller has to bound the precision loss by the rules of Precision and representation of p-adic numbers.

Referenced from#

Cite this page

The FLINT team, “p-adic arithmetic in FLINT,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/p-adic/overview.html (generated 2026-10-20).