Deterministic and Efficient Ideal Arithmetic via Two-Element Representations
Qi Cheng · 2026
Read Deterministic and Efficient Ideal Arithmetic via Two-Element Representations by Qi Cheng (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26993.txt.
Introduction
Qi Cheng gives a fast, deterministic algorithm for a basic task in number theory with crypto stakes. An ideal in a number field is a structured set of algebraic integers. Many applications want just two elements that generate the whole ideal. Older methods are either randomised or too slow at cryptographic sizes, where lattice-based cryptography now lives.
Cheng's algorithm runs in polynomial time with no coin flips. It applies when the ideal's norm is coprime to a certain index measuring how far a simple ring sits inside the full integer ring. All ideals qualify for an important polynomial family that includes the cyclotomic polynomials of lattice cryptography. A broadened Dedekind test is the key tool. The result removes chance from a routine step in ideal math.
Catalog record
| CREATOR | Qi Cheng |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.26993
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Deterministic and Efficient Ideal Arithmetic via Two-Element Representations We thank the U. S. National Science Foundation for their support through the grant CCF-2530361 . Qi Cheng Abstract Given an ideal in a number field, it is desirable in many situations to find two elements that generate the ideal over the ring of the integers of the field. Existing algorithms are either randomized, or impractical at cryptographic sizes. In the paper, we present a deterministic polynomial time algorithm to find the two-element representation of an ideal. For a monic irreducible integral polynomial f ( x ) f(x) , let K = ℚ [ x ] / ( f ) K={\mathbb{Q}}[x]/(f) be the number field, and O K O_{K} be the integral closure. Our algorithm works when the norm of the input ideal is co-prime to the index [ O K : ℤ [ x ] / f ] [O_{K}:{\mathbb{Z}}[x]/f] . In particular, it handles all ideals for monogenic f ( x ) f(x) , a class that includes the cyclotomic polynomials widely used in lattice based cryptography. A key technical ingredient in our result is a generalized version of Dedekind criterion. 1 Introduction Due to the imminent threat of quantum algorithms to cryptosystems based on prime factorization and discrete logarithm [ 18 ] , cryptographers are motivated to design new cryptographic schemes that can resist quantum attacks. Hard ideal lattice problems underpin the security of the Ring Learning-With-Errors (RLWE) problem, a versatile and widely used primitive in post quantum cryptography [ 11 , 14 , 19 ] . A large number of algorithms are proposed, including NewHope [ 1 ] , Crystals-Kyber [ 3 ] and LAC [ 13 ] . These applications call for efficient implementation of ideal arithmetic, an important topic in computational number theory that was first studied in [ 4 , 5 ] , and the references therein. It is well-known that for a number field, two elements are sufficient to generate any fractional ideal as a module over its ring of integers. Several algorithms for finding such representation have been proposed, but they are either randomized or inefficient, due to expensive prime factorization. An ideal that admits a single generator is called principal. Interestingly there is no known efficient algorithm to decide the principality of an ideal, let alone to find a generator, even randomness is allowed. 1.1 Description of the problem Let f(x) be a monic irreducible polynomial over {\mathbb{Z}} of degree n . Let K={\mathbb{Q}}[x]/(f) be the number field. We denote by O_{K} the integral closure of {\mathbb{Z}}[x]/f(x) . It is a free {\mathbb{Z}}- module, but finding its integral basis is in general difficult, often requiring the prime factorization of the discriminant of f(x) . An ideal in O_{K} is also a free {\mathbb{Z}}- module. If space complexity is not a primary concern, then one [ 5 ] can represent an ideal by its {\mathbb{Z}}- basis, each of its elements being written in {\mathbb{Z}}- basis of O_{K} . This gives us an integral matrix (lattice) representation for an ideal. By sending x to one of the roots \alpha of f(x) in K , we establish an exact sequence of {\mathbb{Z}} -modules: 0\rightarrow(f(x))\rightarrow{\mathbb{Z}}[x]\rightarrow O_{K} If the index [O_{K}:{\mathbb{Z}}[x]/(f)] is 1, then the field— and the polynomial f(x) — are called monogenic; the ring of integers has a power basis \{1,\alpha,\alpha^{2},\cdots,\alpha^{n-1}\} ; and the sequence can be extended to 0 : 0\rightarrow(f(x))\rightarrow{\mathbb{Z}}[x]\rightarrow O_{K}\rightarrow 0. This short exact sequence allows us to lift an ideal in O_{K} back to an ideal in {\mathbb{Z}}[x] , and compute in {\mathbb{Z}}[x] , which is often more efficient than dealing with integral matrix representations of ideals. Moreover, ideals I\subseteq{\mathbb{Z}}[x] and I+f(x){\mathbb{Z}}[x]\subseteq{\mathbb{Z}}[x] will be mapped to the same ideal in O_{K} . It means that we may freely add f(x) into an ideal in {\mathbb{Z}}[x] , without changing its image in O_{K} . Note that {\mathbb{Z}}[x] has ideals that can not be generated by two elements (for instance (5,x)^{3} ). In general, the problem of finding two-element representation can be stated as follows: giving a_{1},a_{2},\cdots,a_{r} in O_{K} , to find b_{1},b_{2} in O_{K} so that a_{1}O_{K}+a_{2}O_{K}+\cdots+a_{r}O_{K}=b_{1}O_{K}+b_{2}O_{K} For example, if the ideal is given by its {\mathbb{Z}} -basis, then r=n . We can assume that r=3 , since a_{4},a_{5},\cdots can be absorbed into two elements recursively. We can find an integer in the input ideal and assign it to a_{1} . One of the two generators of the output ideal can also be an integer. So we should go one step further, and assume that both a_{1} and b_{1} are integers, and reformulate the problem as: Input: {\cal N}\in{\mathbb{Z}},a(x)\in{\mathbb{Z}}[x],b(x)\in{\mathbb{Z}}[x] Output: M\in{\mathbb{Z}},c(x)\in{\mathbb{Z}}[x] so that {\cal N}O_{K}+a(\alpha)O_{K}+b(\alpha)O_{K}=MO_{K}+c(\alpha)O_{K} In this paper, we focus on the most difficult case where {\cal N} is a large composite number free of small prime factors. Once we have an efficient algorithm for the above problem, ideal addition is straight-forward: (N_{1},a(x))+(N_{2},b(x))=(gcd(N_{1},N_{2}),a(x),b(x)) Ideal multiplication and powering are core subroutines in our algorithm, and they will be treated in Lemma 2 and Section 5 . 1.2 Previous works It has long been observed that two-element representations can speed up computation significantly. Pohst and Zassenhaus [ 17 ] utilized them to calculate class groups. Since their work dealt with ideals of small norms, they can afford to compute two-element representations by factoring ideals into small prime ideals. See also [ 9 ] . It is difficult to generalize their method to ideals of large norm, due to a few apparent difficulties here. First the norm of the ideal need to be factored into primes, which is hard. Second one must find prime ideals lying above a rational prime, which requires to factor polynomials over finite fields. It relies on randomized algorithms in the current state of the art [ 12 ] . Another deterministic algorithm was sketched in [ 2 , Subsection 6.3.2] . However, the time complexity was not analyzed, and the authors deemed it impractical if the ideal can not be factored. A simple randomized algorithm was proposed in [ 15 , 16 , 7 ] . The algorithm first finds a\in I , and then pick a random element r\in I/(a) . It can be proved that with high probability, I=aO_{K}+rO_{k} . 1.3 Our result Assume that the input ideal is ({\cal N},a(\alpha),b(\alpha)) . We address small prime factors of {\cal N} separately via the Pohst-Zassenhaus algorithm. Factoring polynomials in small finite fields does not require randomness. So we may assume that {\cal N} has no small prime factors (and is thus hard to factor). Stage 1 In the first stage of our algorithm, we factor the input ideal into a product of ideals in two-element representation, and ideals of a special form, described below. The basic idea is to try to compute gcd(a(x),b(x)) over {\mathbb{Z}}/{\cal N} using the Euclidean algorithm. If the computation succeeds, we find a polynomial c(x) , and obtain two-element representation {\cal N}O_{K}+c(\alpha)O_{K} . This should solve the problem for many inputs if {\cal N} is free of small prime factors. An obstacle in this step is a zero divisor in {\mathbb{Z}}/{\cal N} appearing as the leading coefficient of some polynomials. If additionally {\cal N} is not a perfect power, we split {\cal N}