Deterministic and Efficient Ideal Arithmetic via Two-Element Representations
June 25, 2026
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)\), let \(K={\mathbb{Q}}[x]/(f)\) be the number field, and \(O_K\) be the integral closure. Our algorithm works when the norm of the input ideal is co-prime to the index \([O_K:{\mathbb{Z}}[x]/f]\). In particular, it handles all ideals for monogenic \(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 [1], 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 [2]–[4]. A large number of algorithms are proposed, including NewHope [5], Crystals-Kyber [6] and LAC [7]. These applications call for efficient implementation of ideal arithmetic, an important topic in computational number theory that was first studied in [8], [9], 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 [9] 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 = M O_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 [10] 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 [11]. 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 [13]. 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 [14]–[16]. 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 = a O_K + r O_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}\) into factors which are co-prime to each other. This allows us to split the input ideal. We then work on each factor ideal separately.
A degenerate case, when \({\cal N} = N^e\) is a perfect power, must be handled separately. For this case, we run the Euclidean algorithm on \(a(x)\) and \(b(x)\) over \({\mathbb{Z}}/{N}\) (rather than over \({\mathbb{Z}}/{\cal N}\)), producing an ideal of form \[\label{eq:onegennotN} (N^e, a_1 (x), N d_1(x), N d_2(x), \cdots ),\tag{1}\] where only one generator is not a multiple of \(N\). We add \(f(x)\) into the ideal, and it guarantees that \(a_1(x)\) is a factor of \(f(x)\) over \({\mathbb{Z}}/N\).
In the end, we factor the input ideal into a product of factors in special forms: \[({\cal N}, a(\alpha), b(\alpha))= \prod_{i=1}^t (N_i, a_i (x)) \prod_{i=t+1}^s (N_i^{e_i}, a_i (x), N_i d_{ 1 i}(x), N_i d_{ 2 i}(x), \cdots).\]
Stage 2 The second stage of our algorithm will handle ideals in the form of (1 ). One can clearly read off a factor \((N, a_1(\alpha))\) from the ideal that is in two-element representation. The other factors will also likely contain \(N\). How do we multiple \((N, a_1(\alpha)) (N, a_2(\alpha))\) into a two-element form? Preferably the product is \((N^2, a_1(\alpha) a_2(\alpha))\), but this is not always true.
Example 1. Consider the 8-th cyclotomic field with ring of integers \({\mathbb{Z}}[x]/(x^4+1)\). The ideals \((65, x^2 + 268)\) and \((65, x^2 - 268)\) are primes, and their product is \((65)\), but \[(65^2, (x^2+268)(x^2-268)) = (65^2, -71825) = (65^2, -17 * 65^2) = (65^2).\] If we add some multiplies of \(65\) to the second generator, \[(65, x^2 + 268)=(65, x^2+8), (65, x^2 - 268) = (65, x^2-8),\] then \[(65^2, (x^2+8)(x^2-8)) = (65^2, -65) = (65).\] The main innovation of our paper is to find the desirable second generator so that ideal arithmetic can be done efficiently.
In the work of Pohst-Zassenhaus, when the integer generator \(N\) is a prime, a special type of two-element representations was found so that multiplication can be done in a straight forward way: \[(p, \beta_1) (p, \beta_2) = (p^2, \beta_1 \beta_2 ).\] Their algorithm is not available when \(N\) is not a prime, since it requires prime ideal factorization. Our main technical contribution is to derive such a form for a composite \(N\) with unknown prime factorization, overcoming the inefficiency in [13]. See Section 4 and 5.
Stage 3 After the second stage, the algorithm splits the input ideal uniformly: \[({\cal N}, a(x), b(x)) = \prod_{i=1}^s (N_i, a_i (x)),\] where all the \(N_i\)’s are pairwise co-prime to each other. Multiplying them together into a single ideal in two-element representation can be accomplished in a standard way by Chinese Remainder Theorem, which is the goal in the final stage. See Lemma 2.
Theorem 1. (Main) There is an algorithm solving the two-element representation problem for a monogenic field of degree \(n\) in time \(poly(n, \log {\cal N})\). When \({\cal N}\) has no repeated prime factor, the algorithm runs in time \(O(n^2 \log {\cal N} \omega({\cal N}))\), where \(\omega ({\cal N})\) denotes the number of distinct prime factors of \({\cal N}\).
Our algorithm shows that neither randomness nor prime ideal factorization is necessary to find two-element representation for an ideal. In fact, finding a factor of \({\cal N}\) only slows down our algorithm. Our algorithm is practical, since the basic operation is arithmetic on polynomials rather than integral matrices that is much more expensive. Note that \(\omega({\cal N})\) is less than \(\log {\cal N}\), and has average order \(\log\log {\cal N}\)[17]. Thus when \({\cal N}\) is square-free, the complexity is comparable to randomized algorithm. Our algorithm works for all ideals in monogenic fields, covering cyclotomic fields—the most important case for ideal-based cryptography. It also works for non-monogenic fields if the norm of I is relatively prime to the index of \(O_k\) over \({\mathbb{Z}}[x]/(f)\). Moreover, if the algorithm fails, it will provide a certificate that \(f(x)\) is not monogenic.
2 Mathematical Preparation↩︎
It is well-known [8] that a prime ideal containing \(p\) has two-element representation \((p, t(x))\) if \(p\) does not divide the index of \([O_K:{\mathbb{Z}}[x]/(f)]\). Here \(t(x)\) is an irreducible factor of \(f(x)\) over \({\mathbb{F}}_p\).
In the section, we present a few facts about ideals in number fields. They are known in different forms in literature. We include some proofs here for completeness.
2.1 The minimal positive integer in an ideal↩︎
Given an ideal \(I\) in \(O_K\), we denote the minimal positive integer in the ideal by \(MPI(I)\). It divides the norm and can be computed by Hermite Normal Form of the lattice corresponding to \(I\). If the number field is monogenic and the ideal is principal \((a(x))\), it can be also computed by more efficient Euclidean algorithm. First we find the inverse of \(a(\alpha)\) in the field, by running the Euclidean algorithm on \(f(x)\) and \(a(x)\) in \({\mathbb{Q}}[x]\). The inverse must be in the form \(b(\alpha)\) for some polynomial in \(b(x) \in {\mathbb{Q}}[x]\). Let the number \(i\) be the smallest positive integer such that \(i b(x) \in {\mathbb{Z}}[x]\). It can be shown that \(i = MPI (a(\alpha))\). If an ideal is generated by a few elements \(\alpha_1, \alpha_2, \cdots\), we can set \({\cal N}\) to be \(gcd(MPI((\alpha_1)), MPI((\alpha_1)), \cdots)\).
2.2 When integer generators are relatively prime↩︎
We now show that factorization of an integer generator of an ideal leads to factorization of the ideal.
Lemma 1. Let \(I\) be an ideal in \({\mathbb{Z}}[x]\). Suppose that an integer \({\cal N}\) factors as \({\cal N} = N_1 N_2\), with \((N_1, N_2) = 1\). Then the ideal factors as \[{\cal N} {\mathbb{Z}}[x] + I = (N_1 {\mathbb{Z}}[x]+ I) (N_2 {\mathbb{Z}}[x] + I)\]
Proof. Since \[(N_1 {\mathbb{Z}}[x]+ I) (N_2 {\mathbb{Z}}[x] + I) = N_1 N_2{\mathbb{Z}}[x] + N_1 I {\mathbb{Z}}[x] + N_2 I {\mathbb{Z}}[x] + I^2,\] it is clear that \(RHS \subseteq LHS\). To see that \(LHS \subseteq RHS\), we observe that for any \(f(x) \in I\), \(f(x) \in f(x) N_1 {\mathbb{Z}}[x] + f(x) N_2 {\mathbb{Z}}[x]\). ◻
Lemma 2. Assume that two positive integers \(N_1, N_2\) are relatively prime. Let \[M_1 = N_1^{-1} \pmod{N_2 }\;and \;M_2 = N_2^{-1} \pmod{N_1 }.\] Then two ideals in \({\mathbb{Z}}[x]\) can be multiplied in polynomial time as \[(N_1, f_1(x)) (N_2, f_2(x)) = (N_1 N_2, g(x) ),\] where \(f_1(x), f_2(x)\) are in \({\mathbb{Z}}[x]\), and \(g(x) = N_2 M_2 f_1(x) + N_1 M_1 f_2(x)\).
Proof. Essentially we find a polynomial \(g(x)\) so that \(g(x) \pmod{N_1} = f_1(x)\) and \(g(x) \pmod{N_2} = f_2(x)\), using the Chinese Remainder Theorem. Then we apply Lemma 1. ◻
3 An Euclidean algorithm for integral polynomials↩︎
First we rephrase the Euclidean algorithm for polynomials over \({\mathbb{Z}}/N{\mathbb{Z}}\) as ideal normalization in \({\mathbb{Z}}[x]\).
Lemma 3. Let \(N\) be a positive integer, and \(a(x), b(x)\) are two integral polynomials, neither of which is a multiple of \(N\). There is a polynomial time algorithm that either finds a nontrivial factor of \(N\), or two polynomials \(c(x)\) and \(d(x )\) in \({\mathbb{Z}}[x]\) such that \[a(x){\mathbb{Z}}[x] + b(x){\mathbb{Z}}[x] = c(x){\mathbb{Z}}[x] + N d(x){\mathbb{Z}}[x].\] In addition, in this case the algorithm also find three polynomials \(a'(x), b'(x), t(x)\) such that \[a(x) a'(x) + b(x) b'(x) + N t(x) = c(x).\]
Proof. If \(N\) is a perfect power, we can find its non-trivial factor in polynomial time. Now assume that \(N\) is not a perfect power.
If any coefficients of \(a(x), b(x)\) is a non-trivial zero divisor in \({\mathbb{Z}}/N\), we can find a non-trivial factor of \(N\). Otherwise we separate the terms of \(a(x), b(x)\): \[a(x)=a_1 (x) + N a_2(x), b(x) = b_1(x) + N b_2(x),\] where the leading coefficients of \(a_1(x), b_1(x)\) are in \(( {\mathbb{Z}}/N )^*\). W.l.o.g, assume that \(\deg(a_1(x)) \geq \deg (b_1(x)).\) Then in \(Z/N[x]\), we can divide \(a_1(x)\) by \(b_1(x)\), and let \(q(x) \in {\mathbb{Z}}[x]\) be the quotient. It implies that there exists a polynomial \(r(x) \in {\mathbb{Z}}[x]\) such that \[a(x) = q(x) b(x) + r(x),\] and \(r(x) = r_1(x) + N r_2(x)\), \(deg(r_1 (x)) < deg(b_1 (x))\). As ideals in \({\mathbb{Z}}[x]\), we have \[a(x) {\mathbb{Z}}[x] + b(x) {\mathbb{Z}}[x] = b(x) {\mathbb{Z}}[x] + r(x) {\mathbb{Z}}[x],\] since \(r(x)\) is in the LHS ideal and \(a(x)\) is in the RHS ideal.
At this point, if any coefficient of \(r(x)\) is a non-trivial zero divisor of \({\mathbb{Z}}/N\), then we find a non-trivial factor of \(N\). Otherwise we divide \(b(x)\) by \(r(x)\), and continue an Euclidean-style algorithm, until the remainder polynomial is \(0 \pmod{N}\). This concludes the proof. ◻
The algorithm is basically the Euclidean algorithm in \({\mathbb{Z}}/N[x]\), which is implemented in many software packages such as Sagemath. If the algorithm terminates without encountering a non-trivial zero divisor in \({\mathbb{Z}}/N\), then we solve the two-element representation problem for the ideal \((N, a(\alpha), b(\alpha))\): \[N O_k + a(x) O_k + b(x) O_k = N O_K + c(x) O_k.\] What if a non-trivial zero divisor in \({\mathbb{Z}}/N\) is found? We also need to take care of a degenerate case, when \(N\) is a perfect power. The following theorem shows that we can always factor and normalize the input ideal:
Theorem 2. There is a polynomial time algorithm that, given two integral polynomials \(a(x )\) and \(b(x )\), a positive integer \(N\) that is not a perfect power, and a positive integer \(e\), factors the ideal \((N^e, a(x), b(x)) \subseteq {\mathbb{Z}}[x]\) into a product as \[(N^e, a(x), b(x)) = \prod_{i} (N_i^{e_i}, a_i(x), N_i d_i (x))\] such that none of \(N_i\)’s is a perfect power, and for any \(i \not= j\), \(gcd(N_i, N_j) = 1\).
Proof. Run the algorithm from Lemma 3 on \(a(x), b(x)\) and \(N\) ( rather than \(N^e\) ). If we find \(c(x)\) and \(d(x)\) such that \(a(x){\mathbb{Z}}[x] + b(x) {\mathbb{Z}}[x] = c(x){\mathbb{Z}}[x] + N d(x) {\mathbb{Z}}[x],\) then \[(N^e, a(x), b(x)) = (N^e, c(x), N d(x)).\] Otherwise we find a factorization of \(N\), then \[(N^e, a(x), b(x)) = (N_1^{e_1}, a(x), b(x)) (N_2^{e_2}, a(x), b(x)).\] Here \(N_1, N_2\) are co-prime. We then recursively work on each of the factors, ultimately obtaining the desired factorization. ◻
We can add \(f(x)\) into the ideal, run the algorithm from Lemma 3 on \(a_i(x)\), \(f(x)\) and \(N\), and derive a corollary:
Corollary 1. There is a polynomial time algorithm that, given two integral elements \(a(\alpha )\) and \(b(\alpha)\) in \(O_K\), a positive integer \(N\) that is not a perfect power, and a positive integer \(e\), factors the ideal \((N^e, a(\alpha), b(\alpha)) \subseteq O_K\) into a product as \[\label{eq:5} (N^e, a(\alpha), b(\alpha)) = \prod_{i} (N_i^{e_i}, a_{ i }(\alpha), N_i I_i)\qquad{(1)}\] such that none of \(N_i\)’s is a perfect power; \(I_i = (d_{i1} (\alpha), d_{i2} (\alpha))\) is an ideal in \(O_K\); and for any \(i \not= j\), \(gcd(N_i, N_j) = 1\); and \(a_{i}(x)\) is a polynomial dividing \(f(x)\) in \({\mathbb{Z}}/N_i[x]\).
The first stage of the algorithm will factor the input ideal as in Equation ?? , and is described in pseudo-code in Algorithm 1. Note that we may write \(a_{i} (x)\), in many ways, as a monic polynomial dividing \(f(x)\) over \({\mathbb{Z}}/N_i\), plus a multiple of \(N_i\) in \({\mathbb{Z}}[x]\). This flexibility plays an essential role in later stages of the algorithm. For details see Theorem 3. For a factor in the RHS of Equation ?? with \(e_i =1\), it is already in the two-element form. While other factors in the RHS with \(e_i > 1\) is not in two-element representation, we can immediately read off a factor \((N_i, a_{i}(\alpha))\) with two generators. If \(a_{i}(\alpha) = 1\pmod{N}\), then \((N_i^{e_i}, a_{ i }(\alpha), N_i I_i)\) is the entire ring \(O_K\), according to the following lemma.
Lemma 4. If \(A \in ( {\mathbb{Z}}/N )^*\), then for any \(g(x)\), \(A+N g(x)\) is a unit in \({\mathbb{Z}}/N^s [x]\) for any positive integer \(s\).
Proof. Let \(B \in {\mathbb{Z}}\) be an inverse of \(A\), namely, there exists an \(C\in {\mathbb{Z}}\) such that \(A B = 1 + N C\). We have \[\begin{align} 1/(A + N g(x)) =& B/ ( A B + N B g(x))\\ =& B/ ( 1 + N (B g(x) + C) )\\ =& B ( 1 - N (B g(x) + C) + (N (B g(x) + C))^2 \\ & \cdots + (- N (B g(x) +C))^{s-1} ) \pmod{N^s } \end{align}\] ◻
If \(a_{i}(\alpha) \not= 1 \pmod{N_i}\), we need to compute \((N_i^{e_i}, a_{ i }(\alpha), N_i I_i)/(N_i, a_{i}(\alpha))\). In the next two sections, we show how to find a proper member in \(a_{i} (x) + N_i {\mathbb{Z}}[x]\) so that ideal division, multiplication and powering behave nicely.
4 Generalized Dedekind’s criterion↩︎
Let \(f(x)\) be monogenic. Let \(a_1(x ) \in {\mathbb{Z}}[x]\) be a monic factor of \(f(x)\) over \({\mathbb{Z}}/N\), where \(N\) is not a perfect power. We can write \[\label{eq:1} f(x) = f_1 (x) N^s + a_1^e (x) A(x),\tag{2}\] such that \(f_1(x) \not= 0 \pmod{N}\), and \(a_1(x)\) does not divide \(A(x)\) (which is also monic) over \({\mathbb{Z}}/N\).
Lemma 5. If \(e\geq 2\), we must have \(s =1\). Moreover, if running the algorithm from Lemma 3 on \(f_1(x), a_1(x)\) and \(N\) does not throw an exception of finding a non-trivial factor of \(N\), then \((f_1(x), a_1(x), N) =1\) in \({\mathbb{Z}}[x]\).
Proof. If \(s \geq 2\), or if \(a_1 (x)\) shares factors with \(f_1(x)\) over \({\mathbb{Z}}/N\), then it violates the Dedekind’s criterion [[18]][19] at \((p, a'(x))\), where \(p\) is a prime factor of \(N\), and \(a'(x)\) is an irreducible factor of \(a_1(x) \pmod{p}\). In other words, \((p, a'(x))\) is a maximal ideal corresponding to a singular point on the arithmetic curve \(f(x)\) over \({\mathbb{Z}}\). ◻
The above lemma is basically a generalized version of Dedekind’s criterion. We will use it to prove the core technical lemma of this paper.
Lemma 6. Assume that \(e=1\). In polynomial time, we can either find a non-trivial factor of \(N\), or find two monic integral polynomials \(a_2 (x)\) and \(a_3 (x)\), such that \(f(x)\) can be rewritten as \[\label{eq:2} f(x) =f_2(x) N^{s_2} + a_2 (x) a_3 (x) A(x);\qquad{(2)}\] \(a_1 (x)=a_2 (x) a_3 (x) \pmod{N}\); \((a_3 (x), f_2(x))_N =1\); \(a_2(x)\) divides \(f_2(x)\) over \({\mathbb{Z}}/N\); and \((a_2(x), A(x), N) = 1\) in \({\mathbb{Z}}[x]\).
Proof. Starting from Equation (2 ), we run the algorithm from Lemma 3 on
\((a_1(x), f_1 (x))\) and \(N\). If \(a_1(x)\) divides \(g(x)\), or the gcd is 1, then we are done. Otherwise, we obtain a
factorization of \(a_1(x)\) over \({\mathbb{Z}}/N\), and rewrite \(f(x)\) as \[f(x) = f_3(x) N^{s_3} + a_4 (x) a_5 (x)
A(x).\] Note that \(f_3(x)\) may differ from \(f_1(x)\). We run the algorithm from Lemma 3 on \(a_4(x), f_3(x), N\) and \(a_5(x), f_3(x), N\), and continue to find factors of \(a(x)\) over \({\mathbb{Z}}/N\). We terminate
the process when \[f(x) = f_2 (x) N^{s_2} + ( \prod_i a_{i2}(x)) (\prod_i a_{i3} (x)) A(x),\] each of \(a_{i2}(x)\) divides \(f_2 (x)\) over \({\mathbb{Z}}/N\), and each of \(a_{i3}(x)\) is co-prime to \(f_2 (x)\) over \({\mathbb{Z}}/N\). Since \(a_1 (x)\) can be split into at most \(\deg(a_1(x))\) factors, the algorithm will terminate eventually. The lemma follows by setting \[a_2(x) = \prod a_{i2} (x), a_3(x)
= \prod a_{i3}(x).\] Note that \(a_2(x)\) can not share a factor with \(A(x)\) by the generalized Dedekind’s criterion. This is crucial for the proof. ◻
Although we have found some factors of \(a_1 (x)\) over \({\mathbb{Z}}/N\), there is in general no efficient way to factor polynomials when \(N\) is not a prime. In fact, even taking square roots modulo \(N\) is as hard as factoring \(N\).
Theorem 3. Let \(a(x)\) be a factor of \(f(x)\) over \({\mathbb{Z}}/N\). In polynomial time, we can either find a non-trivial factor of \(N\), or find a monic integral polynomials \(\tilde{a} (x)\) such that \(f(x)\) can be written as \[\label{eq:3} f(x) =\tilde{f_1}(x) N + \tilde{a}(x) \tilde{A}(x),\qquad{(3)}\] so that \(a(x)=\tilde{a} (x) \pmod{N}\), and \((\tilde{a} (x), \tilde{f_1}(x), N)=1\) in \({\mathbb{Z}}[x]\).
Proof. The case of \(e\geq 2\) is covered by Lemma 5. Now assume that \(e=1\). We first find \(a_2(x)\) and \(a_3(x)\) in Equation (?? ). If \(s\geq 2\), then by Lemma 5, \(a_2(x) a_3(x)\) can not share a factor with \(A(x)\), so we write \[f(x) = (f_2(x) N^{s-1} - A(x)) N + ( a_2 (x) a_3 (x)+ N ) A(x),\] and set \(\tilde{a}(x) = a_2 (x) a_3 (x)+ N\) and \(\tilde{f_1}(x) = f_2(x) N^{s-1} - A(x)\). If \(s= 1\), we have \[f(x) = (f_2(x) - a_3(x) A(x)) N + ( a_2 (x) + N ) a_3 (x) A(x),\] and set \(\tilde{a}(x) = ( a_2 (x) + N ) a_3 (x)\) and \(\tilde{f_1}(x) = f_2(x) - a_3(x) A(x)\). In either case it can be verified that the resulting form satisfies the requirements in the theorem. ◻
5 Powering/Multiplying ideals in two-element representations↩︎
We now return to an ideal factor in the RHS of Equation (?? ). We will omit the subscription for convenience, and denote it by \(J = (N^e, a(\alpha), N I )\). Recall that \(N\) is not a perfect power. We find \(\tilde{a}(x)\) satisfying the condition in Equation (?? ), and read off a factor \((N, \tilde{a} (\alpha))\) from \(J\). We also find \(g(\alpha)\) so that \(a(\alpha) = \tilde{a}(\alpha) + N g(\alpha)\). According to Theorem 3, we may write \[\label{eq:4} f(x) = f_1 (x) N + \tilde{a} (x) A(x).\tag{3}\] with \((f_1(x), \tilde{a}(x), N) = 1\) in \({\mathbb{Z}}[x]\) (which implies that \(f_1(x) \not= 0 \pmod{N}\) ). We will show that the condition will enable fast ideal arithmetic.
Example 2. In Example 1, we can see that it is easier to multiply when using \(a(x) = x^2+8\), rather than \(x^2 + 268\), as the second generator, even though \((65, x^2 + 8) = (65, x^2 + 268)\). It is because that \[f(x)= x^4+1 = (x^2+8) (x^2-8)+65\] so \(x^2+8\) satisfies the conditions in Equation (3 ), whereas \(x^2+268\) does not, as \[f(x) = x^4+1 = (x^2+268) (x^2-268)+65^2*17.\]
Lemma 7. For any positive integer \(s\), \(N \in (N^s, \tilde{a}(\alpha) )\).
Proof. Since \((\tilde{a}(x), f_1 (x), N ) = 1\), there must exist integer polynomials \(a'(x), f_1'(x)\) and \(t(x)\) such that \[\tilde{a}(x) a'(x) + f_1(x) f_1'(x) + N t(x) = 1.\] We also have \[f_1 (\alpha) N + \tilde{a}(\alpha) A(\alpha) =0\] so \[f_1'(\alpha) f_1 (\alpha) N + f_1'(\alpha) \tilde{a}(\alpha) A(\alpha) =0\] \[(1 - \tilde{a}(\alpha) a'(\alpha) - N t(\alpha)) N + f_1'(\alpha) a(\alpha) A(\alpha) =0\] \[(1 - N t(\alpha)) N = \tilde{a}(\alpha) a'(\alpha) N - f_1'(\alpha) \tilde{a} (\alpha) A(\alpha)\] \[(1 - N t(\alpha)) N = \tilde{a}(\alpha) ( a'(\alpha) N - f_1'(\alpha) A(\alpha) )\] The statement follows from the fact that \[1- N t(\alpha)\] is a unit in \({\mathbb{Z}}[\alpha]/(N^{s})\). ◻
By setting \(\bar{a}(\alpha) = (a'(\alpha) N - f_1'(\alpha) A(\alpha))/(1 - N t(\alpha)) \in O_K\), we conclude:
Corollary 2. For \(\tilde{a} (x)\) in Equation 3 , we can find \(\bar{a}(\alpha)\) in deterministic polynomial time such that \[\tilde{a}(\alpha) \bar{a}(\alpha) = N \pmod{N^s}\] for any \(s\geq 2\). Moreover \[(N, \tilde{a}(\alpha)) (N, \bar{a}(\alpha)) = N\]
Now we are ready to calculate \(J/ (N, \tilde{a}(\alpha))\)
Lemma 8. Let \(\tilde{a} (x)\) satisfy the conditions in Equation 3 . Given an ideal \(J = (N^e, \tilde{a}(\alpha) + N g(\alpha), N I)\), where \(I = (d_1 (\alpha), d_2(\alpha), \cdots, d_k (\alpha))\), there is a polynomial time algorithm that either finds a non-trivial factor of \(N\), or calculate \(J/ (N, \tilde{a}(\alpha))\), and normalize it into a form \((N^e, a' (\alpha) , N I'),\) where \(a' (x)\) is a factor of \(f(x)\) over \({\mathbb{Z}}/N\), and \(I'\) has at most \(k+2\) generators.
Proof. We have \[\begin{align} &J/ (N, \tilde{a}(\alpha))\\ =& (N, \bar{a}(\alpha))(N^e, \tilde{a}(\alpha) +N g(\alpha), N I)/N\\ =& (N^{e+1}, N \tilde{a}(\alpha) +N^2 g(\alpha), N^2 I, N^{e} \bar{a}(\alpha), \tilde{a}(\alpha) \bar{a}(\alpha)+ N g(\alpha)\bar{a}(\alpha), \bar{a}(\alpha) N I)/N\\ =& (N^{e}, \tilde{a}(\alpha) +N g(\alpha), N I, N^{e-1} \bar{a}(\alpha), ( \tilde{a}(\alpha) \bar{a}(\alpha) )/N + g(\alpha)\bar{a}(\alpha), \bar{a}(\alpha) I)\\ =& (N^{e}, \tilde{a}(\alpha) +N g(\alpha), ( \tilde{a}(\alpha) \bar{a}(\alpha) )/N + g(\alpha)\bar{a}(\alpha), \bar{a}(\alpha) I, N^{e-1} \bar{a}(\alpha)) \end{align}\] Now we run the algorithm from Lemma 3 on the polynomial generators that are not multiples of \(N\), and normalize the above ideal into a form \((N^e, a'(\alpha) , N I')\) where \(I'\) has at most \(k+2\) generators. ◻
We could, of course, reduce the number of generators in \(I'\), but it may not be worth the computation effort. We should continue producing ideal factors and put them in the preferred form. The following theorem provides a simple algorithm to multiply them into one ideal in two-element representation.
Theorem 4. If \(\tilde{a}_1(x), \tilde{a}_2(x), \cdots, \tilde{a}_k(x)\) all satisfy the conditions in Equation (3 ), then \[(N, \tilde{a}_1(\alpha)) (N, \tilde{a}_2 (\alpha)) \cdots (N, \tilde{a}_k(\alpha)) = (N^k, \tilde{a}_1(\alpha)\tilde{a}_2(\alpha)\cdots \tilde{a}_k(\alpha))\]
Proof. Every term in the expansion of LHS has a form \(N^{k-s} \tilde{a}_{i_1}(\alpha) \tilde{a}_{i_2}(\alpha) \cdots \tilde{a}_{i_s}(\alpha)\). For each \(N\) in the product, we apply Lemma 7, replace it by an term in \[\{ \tilde{a}_1(\alpha), \tilde{a}_2(\alpha), \cdots, \tilde{a}_k(\alpha)\} - \{ \tilde{a}_{i_1}(\alpha), \tilde{a}_{i_2}(\alpha), \cdots, \tilde{a}_{i_s}(\alpha)\}\] and derive: \[N^{k-s} \tilde{a}_{i_1}(\alpha) \tilde{a}_{i_2}(\alpha) \cdots \tilde{a}_{i_s}(\alpha) \in (N^k, \tilde{a}_1 (\alpha)\tilde{a}_2(\alpha)\cdots \tilde{a}_k(\alpha))\] ◻
Note that we do not require \(\tilde{a}_i(x)\) to be relatively prime to each other over \({\mathbb{Z}}/N\). This theorem provides mathematical foundation for stage 2 of our algorithm. For pseudo-code, see Algorithm 2.
Corollary 3. For any positive integer \(s\), we have \[(N, \tilde{a}(\alpha))^s = (N^s, \tilde{a}(\alpha)^s)\]
6 Put the algorithm together↩︎
The third stage of our algorithm, described in Algorithm 3, is a straight-forward application of Lemma 2. Given an input ideal, we run Algorithm 1, Algorithm 2 and Algorithm 3 in sequence, obtaining two elements that generate the input. The building block of our algorithm is the Euclidean algorithm for integral polynomials over \({\mathbb{Z}}/N\), where \(N\) is a factor of \({\cal N}\) and is not a perfect power. To analyze the complexity, we count the number of gcd calculations. Since small prime factors of \({\cal N}\) have been taken care efficiently by the Pohst-Zassenhaus algorithm, we focus on \({\cal N}\) free of small prime factors. The most time-consuming part of the algorithm involves handling perfect powers. In the generic case when \({\cal N}\) is free of repeated factors, the algorithm will need at most \(\omega({\cal N})\) gcd calculations —which is on average \(\log\log {\cal N}\)— resulting in a complexity of \(O (n^2 \log {\cal N} \omega({\cal N}) )\). Even when \({\cal N}\) has repeated factors, the algorithm may not discover them as an exception and may thus achieve similar complexity.
7 Conclusion and open problems↩︎
In this paper, we present an efficient implementation of ideal arithmetic for monogenic polynomials. Cyclotomic polynomials are monogenic, making our algorithms directly applicable to the most important case for cryptography based on ideal lattices. Our algorithm may be viewed as a generalization of the Pohst-Zassenhaus algorithm to composite integers.
For a polynomial \(f\) that is not monogenic, the field \({\mathbb{Q}}[x]/f\) may still be monogenic. An open problem is to find such a monogenic polynomial for the field in polynomial time. Due to the existence of inessential discriminant divisors, we may not be able to find a monogenic polynomial for every field, however, a question can certainly be raised about finding a polynomial \(f'\) efficiently to minimize the index \([O_K:{\mathbb{Z}}[x]/f']\). Because inessential discriminant divisors are in general very small, resolving this question could lead to substantial gains in computational efficiency.