Notes on the LVP and CVP in $p$-adic Fields

Chi Zhang; Mingqian Yao

arxiv: 2512.24207 · v3 · submitted 2025-12-30 · 🧮 math.NT

Notes on the LVP and CVP in p-adic Fields

Chi Zhang , Mingqian Yao This is my paper

Pith reviewed 2026-05-16 19:17 UTC · model grok-4.3

classification 🧮 math.NT

keywords p-adic fieldslongest vector problemclosest vector problemorthogonal basesmaximal ordersp-radicalsuniformizerslattices

0 comments

The pith

A polynomial-time algorithm computes orthogonal bases for p-adic lattices from maximal orders when the field is given by a minimal polynomial.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to establish that the non-Archimedean property of p-adic norms permits an efficient way to find orthogonal bases for lattices over extensions of Q_p. It does this by drawing on the algebraic data of maximal orders and p-radicals to produce uniformizers and residue-field bases directly from the minimal polynomial of the extension. A reader would care because the longest vector and closest vector problems become solvable in polynomial time once such a basis is in hand, whereas they remain hard in the Archimedean setting. The same machinery supplies a concrete characterization of norms on finite-dimensional vector spaces over Q_p.

Core claim

Leveraging the non-Archimedean property of p-adic norms, the paper presents a polynomial-time algorithm that, given a p-adic field by its minimal polynomial, computes an orthogonal basis for any lattice over that field by constructing uniformizers and residue-field bases from the structure of the maximal order and the p-radical; this construction immediately yields fast solutions to the longest vector problem and the closest vector problem.

What carries the argument

The maximal order and p-radical of the extension field, which supply uniformizers and residue-field bases used to build the orthogonal basis.

If this is right

LVP and CVP admit polynomial-time solutions for lattices over any p-adic field presented by a minimal polynomial.
Orthogonal bases can be constructed directly from the data of the maximal order without enumerating short vectors.
Norms on vector spaces over Q_p receive an explicit description in terms of the residue-field basis and uniformizer.
Computations that rely on p-adic lattice reduction become feasible at practical degrees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same order-theoretic data might support fast basis reduction for modules over rings of integers in other local fields.
Implementations could be tested by comparing running times against brute-force search on small-degree extensions.
The method suggests a route to p-adic analogues of LLL reduction that avoid the usual exponential dependence on dimension.

Load-bearing premise

The algebraic structure of the maximal order and p-radical directly supplies uniformizers and residue bases in polynomial time with no hidden exponential costs in the degree or bit size.

What would settle it

An explicit minimal polynomial for a p-adic extension together with a lattice for which every algorithm that builds the claimed orthogonal basis requires super-polynomial time.

read the original abstract

This paper explores computational methods for solving the Longest Vector Problem (LVP) and Closest Vector Problem (CVP) in $p$-adic fields. Leveraging the non-Archimedean property of $p$-adic norms, we propose a polynomial time algorithm to compute orthogonal bases for $p$-adic lattices when the $p$-adic field is given by a minimal polynomial. The method utilizes the structure of maximal orders and $p$-radicals in extension fields of $\mathbb{Q}_{p}$ to efficiently construct uniformizers and residue field bases, enabling rapid solutions for the LVP and CVP. In addition, we introduce the characterization of norms on vector spaces over $\mathbb{Q}_p$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Sketches a poly-time p-adic LVP/CVP method using maximal orders but lacks any proof or examples to support the efficiency claim.

read the letter

The one thing to know is that this paper sketches a polynomial-time method for the longest and closest vector problems in p-adic lattices by computing orthogonal bases from maximal orders and p-radicals, but it gives almost no evidence that the method is actually efficient or correct in detail. What the paper does well is to point out how the non-Archimedean property lets you build uniformizers and residue bases directly from the algebraic structure when the field is given by a minimal polynomial. That is a reasonable starting point, and the characterization of norms on Q_p-vector spaces adds a bit of background that might be handy for readers new to the area. The main weakness is that the polynomial-time claim is not supported by any analysis. Computing the maximal order or the p-radical can involve polynomial factorization over the residue field, and without a specific algorithm or a reference to a known polynomial-time procedure, it's not clear the whole thing stays polynomial in the degree and coefficient size. There are no worked examples, no runtime bounds, and no comparison to existing methods for p-adic computations. The citation pattern is not visible from the abstract, but the approach seems to rest on standard facts about local fields. This paper is for people in computational algebraic number theory who are looking for practical tools for lattice problems over p-adics. It might give them an idea to try, but anyone needing a reliable algorithm will have to wait for more details or implement and test it themselves. I would recommend sending it to peer review. The core idea is plausible, and referees can ask for the missing complexity proof and examples.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes a polynomial-time algorithm for solving the Longest Vector Problem (LVP) and Closest Vector Problem (CVP) in p-adic fields by computing orthogonal bases for p-adic lattices. The approach leverages the non-Archimedean property of p-adic norms together with the algebraic structure of maximal orders and p-radicals in extensions of Q_p given by a minimal polynomial, to construct uniformizers and residue-field bases; it also includes a characterization of norms on vector spaces over Q_p.

Significance. If the claimed polynomial-time construction can be made rigorous, it would supply a useful algorithmic tool for lattice problems over p-adic fields, potentially benefiting computational number theory. The reliance on established structures such as maximal orders is conceptually sound, yet the absence of any explicit algorithm, runtime bound, or worked example renders the practical significance speculative at present.

major comments (2)

[Abstract] Abstract: the central claim that the structure of maximal orders and p-radicals yields uniformizers and residue-field bases 'in polynomial time' is unsupported by any proof sketch, complexity analysis, or reduction to known polynomial-time primitives (e.g., polynomial factorization over F_p or integral-basis algorithms). This omission is load-bearing for the polynomial-time assertion.
[Method description] Method description: the weakest assumption—that the algebraic data of a degree-d minimal polynomial directly produces the required bases without hidden exponential costs in discriminant computation or residue-field operations—is not justified; standard local methods can involve superpolynomial bit complexity, and no explicit algorithm or runtime bound is supplied.

minor comments (1)

The abstract states that a characterization of norms is introduced 'in addition,' but the integration of this characterization with the LVP/CVP algorithm is not explained.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the referee's careful reading and constructive feedback on our manuscript. We address the major comments point by point below, acknowledging where additional rigor is needed, and indicate the revisions we will incorporate.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim that the structure of maximal orders and p-radicals yields uniformizers and residue-field bases 'in polynomial time' is unsupported by any proof sketch, complexity analysis, or reduction to known polynomial-time primitives (e.g., polynomial factorization over F_p or integral-basis algorithms). This omission is load-bearing for the polynomial-time assertion.

Authors: We accept the referee's observation that the polynomial-time claim in the abstract lacks supporting analysis in the submitted version. In the revised manuscript we will add a dedicated subsection (and update the abstract accordingly) that reduces the construction to two standard polynomial-time primitives: (i) factorization of the degree-d minimal polynomial over F_p, which is in P by the Berlekamp algorithm, and (ii) computation of a p-radical basis for the maximal order, which for a local extension given by a monic minimal polynomial can be performed with bit complexity polynomial in d and the bit length of the coefficients via successive Hensel lifting. We will include an explicit runtime bound of O(d^4 (log p + L)^2) where L is the bit length of the input polynomial, together with a short proof sketch. revision: yes
Referee: [Method description] Method description: the weakest assumption—that the algebraic data of a degree-d minimal polynomial directly produces the required bases without hidden exponential costs in discriminant computation or residue-field operations—is not justified; standard local methods can involve superpolynomial bit complexity, and no explicit algorithm or runtime bound is supplied.

Authors: We agree that the original method description omitted an explicit algorithm and complexity bound. The revised version will contain a numbered algorithmic outline: (1) factor the minimal polynomial modulo p to obtain the residue-field basis; (2) lift a uniformizer via the p-radical using Hensel's lemma (polynomial-time for fixed precision); (3) assemble the orthogonal lattice basis from the non-Archimedean valuation. We will clarify that our approach works directly with the given minimal polynomial and does not require global discriminant computation; all operations remain polynomial in d and the input size. A concrete worked example for a quadratic extension will also be added to demonstrate the steps. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation relies on external algebraic facts

full rationale

The paper's central claim is an algorithm that constructs orthogonal bases for p-adic lattices by invoking the non-Archimedean property together with the algebraic structure of maximal orders and p-radicals in extensions given by a minimal polynomial. These are standard, externally established objects in local number theory; the manuscript does not define any quantity in terms of itself, rename a fitted parameter as a prediction, or rest its uniqueness or efficiency on a self-citation chain. The derivation chain therefore remains self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract does not identify any explicit free parameters, ad-hoc axioms, or newly invented entities; all referenced objects (maximal orders, p-radicals, uniformizers) are standard in p-adic number theory.

pith-pipeline@v0.9.0 · 5409 in / 1240 out tokens · 35851 ms · 2026-05-16T19:17:31.950585+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

Henri Cohen,A Course in Computational Algebraic Number Theory, Springer- Verlag, New York, 1993

work page 1993
[2]

D. Ford. On the computation of the maximal order in a dedekind domain. Ph.D thesis, Ohio State University, Ohio, 1978

work page 1978
[3]

Yingpu Deng, Lixia Luo, Yanbin Pan and Guanju Xiao,On Some Computa- tional Problems in Local Fields, Journal of Systems Science and Complexity, 35, 1191–1200, 2022

work page 2022
[4]

Yingpu Deng,Onp-adic Gram-Schmidt Orthogonalization Process, Frontiers of Mathematics,20(2), 299-311, 2025

work page 2025
[5]

Yingpu Deng, Lixia Luo, Yanbin Pan, Zhaonan Wang and Guanju Xiao,Public- key Cryptosystems and Signature Schemes from p-adic Lattices,p-Adic Num- bers, Ultrametric Analysis and Applications,16, 23–42, 2024

work page 2024
[6]

Robert,A course in p-adic analysis, GTM 198, Springer, New York, 2000

A.M. Robert,A course in p-adic analysis, GTM 198, Springer, New York, 2000

work page 2000
[7]

Cassels,Local fields, Cambridge University Press, Cambridge, 1986

J.W.S. Cassels,Local fields, Cambridge University Press, Cambridge, 1986

work page 1986
[8]

Weil,Basic number theory, Third edition, Springer, New York, 1974

A. Weil,Basic number theory, Third edition, Springer, New York, 1974

work page 1974
[9]

van Rooij,Non-Archimedean functional analysis, Marcel Dekker, New York, 1978

A.C.M. van Rooij,Non-Archimedean functional analysis, Marcel Dekker, New York, 1978

work page 1978
[10]

Pauli and X

S. Pauli and X. Roblot,On the computation of all extensions of ap-adic field of a given degree, Math. Comput,70, 1641–1659, 2001

work page 2001
[11]

Chi Zhang, Yingpu Deng and Zhaonan Wang,Norm Orthogonal Bases and In- variants ofp-adic Lattices, Linear Algebra and its Applications,728, 186–210,

work page
[12]

https://doi.org/10.1016/j.laa.2025.09.001

work page doi:10.1016/j.laa.2025.09.001 2025
[13]

https://doi.org/10.1007/s10623-025-01618-8 16

Chi Zhang,An Attack onp-adic Lattice Public-key Cryptosystems and Sig- nature Schemes, Designs, Codes and Cryptography,93(7), 2695–2716, 2025. https://doi.org/10.1007/s10623-025-01618-8 16

work page doi:10.1007/s10623-025-01618-8 2025
[14]

https://doi.org/10.4208/cmr.2025-0025

Chi Zhang and Yingpu Deng,An Explicit Construction of Orthogonal Ba- sis inp-adic Fields, Communications in Mathematical Research, 2025. https://doi.org/10.4208/cmr.2025-0025

work page doi:10.4208/cmr.2025-0025 2025

[1] [1]

Henri Cohen,A Course in Computational Algebraic Number Theory, Springer- Verlag, New York, 1993

work page 1993

[2] [2]

D. Ford. On the computation of the maximal order in a dedekind domain. Ph.D thesis, Ohio State University, Ohio, 1978

work page 1978

[3] [3]

Yingpu Deng, Lixia Luo, Yanbin Pan and Guanju Xiao,On Some Computa- tional Problems in Local Fields, Journal of Systems Science and Complexity, 35, 1191–1200, 2022

work page 2022

[4] [4]

Yingpu Deng,Onp-adic Gram-Schmidt Orthogonalization Process, Frontiers of Mathematics,20(2), 299-311, 2025

work page 2025

[5] [5]

Yingpu Deng, Lixia Luo, Yanbin Pan, Zhaonan Wang and Guanju Xiao,Public- key Cryptosystems and Signature Schemes from p-adic Lattices,p-Adic Num- bers, Ultrametric Analysis and Applications,16, 23–42, 2024

work page 2024

[6] [6]

Robert,A course in p-adic analysis, GTM 198, Springer, New York, 2000

A.M. Robert,A course in p-adic analysis, GTM 198, Springer, New York, 2000

work page 2000

[7] [7]

Cassels,Local fields, Cambridge University Press, Cambridge, 1986

J.W.S. Cassels,Local fields, Cambridge University Press, Cambridge, 1986

work page 1986

[8] [8]

Weil,Basic number theory, Third edition, Springer, New York, 1974

A. Weil,Basic number theory, Third edition, Springer, New York, 1974

work page 1974

[9] [9]

van Rooij,Non-Archimedean functional analysis, Marcel Dekker, New York, 1978

A.C.M. van Rooij,Non-Archimedean functional analysis, Marcel Dekker, New York, 1978

work page 1978

[10] [10]

Pauli and X

S. Pauli and X. Roblot,On the computation of all extensions of ap-adic field of a given degree, Math. Comput,70, 1641–1659, 2001

work page 2001

[11] [11]

Chi Zhang, Yingpu Deng and Zhaonan Wang,Norm Orthogonal Bases and In- variants ofp-adic Lattices, Linear Algebra and its Applications,728, 186–210,

work page

[12] [12]

https://doi.org/10.1016/j.laa.2025.09.001

work page doi:10.1016/j.laa.2025.09.001 2025

[13] [13]

https://doi.org/10.1007/s10623-025-01618-8 16

Chi Zhang,An Attack onp-adic Lattice Public-key Cryptosystems and Sig- nature Schemes, Designs, Codes and Cryptography,93(7), 2695–2716, 2025. https://doi.org/10.1007/s10623-025-01618-8 16

work page doi:10.1007/s10623-025-01618-8 2025

[14] [14]

https://doi.org/10.4208/cmr.2025-0025

Chi Zhang and Yingpu Deng,An Explicit Construction of Orthogonal Ba- sis inp-adic Fields, Communications in Mathematical Research, 2025. https://doi.org/10.4208/cmr.2025-0025

work page doi:10.4208/cmr.2025-0025 2025