Submitted exclusively to the London Mathematical Society
doi:10.1112/0000/000000

Algorithms on Ideal over Complex Multiplication order

arXiv:1602.09037v1 [cs.DS] 29 Feb 2016

Paul Kirchner
Abstract
We show in this paper that the Gentry-Szydlo algorithm for cyclotomic orders, previously
revisited by Lenstra-Silverberg, can be extended to complex-multiplication (CM) orders, and
even to a more general structure. This algorithm allows to test equality over the polarized ideal
class group, and finds a generator of the polarized ideal in polynomial time. Also, the algorithm
allows to solve the norm equation over CM orders and the recent reduction of principal ideals to
the real suborder can also be performed in polynomial time. Furthermore, we can also compute in
polynomial time a unit of an order of any number field given a (not very precise) approximation
of it.
Our description of the Gentry-Szydlo algorithm is different from the original and LenstraSilverberg’s variant and we hope the simplifications made will allow a deeper understanding.
Finally, we show that the well-known speed-up for enumeration and sieve algorithms for ideal
lattices over power of two cyclotomics can be generalized to any number field with many roots
of unity.

1. Introduction
Recently, an algorithmic study of lattices was made necessary by new cryptographic
proposals. Indeed, lattice-based cryptography has several advantages : it seems post-quantum
secure, allows to build a lot of cryptosystems and enjoys a worst-case/average-case reduction
over any lattice problem [1]. Yet, the schemes are slow and have large keys so that most
designers turned towards ideal-lattice based cryptography, based on the Ring-LWE [2].
However, ideal lattices are less studied and the added algebraic structure might allow significant
gains with respect to the same problem for a random lattice. Some suggested to remove a part
of the algebraic structure by choosing a polynomial with a large Galois group † .
We show that many algorithms previously discovered for cyclotomic fields can be generalized
to CM orders with little loss. In particular, a large part of the present paper is dedicated to the
Gentry-Szydlo algorithm [3]. This algorithm, given an ideal generated by some v ∈ Z[X]/(X n −
1) and the autocorrelation of v, finds v up to the (few) root of unity in polynomial time. It was
first used to break the NTRU signature scheme [3]. Lenstra and Silverberg [4] then extended
it to (essentially) product of cyclotomic rings, and made it rigorous. According to [4], Gentry
referred to Gentry-Szydlo’s algorithm as "a rather crazy, unusual combination of LLL with more
‘algebraic’ techniques", while Smart viewed it as magic. We hope the simplifications made to
the algorithms‡ , as well as our effort to see the exact conditions under which Gentry-Szydlo’s
algorithm can be run will help to removed this "dark magic" aspect.
This new algebraic structure extends the CM order, and can be applied to any order. We
give here a particular case of our main theorem Theorem 4 :

2000 Mathematics Subject Classification 00000.
† http://blog.cr.yp.to/20140213-ideal.html
‡ In a recent conference, no less than 9 hours and 33 minutes were dedicated to Gentry-Szydlo’s algorithm and
Lenstra-Silverberg’s modifications.

Page 2 of 17

PAUL KIRCHNER

Theorem 1. Under GRH or using randomness, we can test in polynomial time if (I, r) where
I is an ideal of a CM order is equal to some ((v), vv) for some invertible v and find such a v.
It has several applications, that we extend in section 4. The most useful is the reduction of
searching for short vectors in ideals over CM orders to ideals over their real suborder, which
is enough to attack the Smart-Vercauteren FHE scheme [5, 6], the GGH multilinear map
scheme [7], Soliloquy [8] and the Boneh-Freeman homomorphic signatures [9]. Remark that
a quantum algorithm was recently discovered which breaks all these schemes in polynomial
time [10]. This problem can be mitigated by switching to other number fields, since the attack
crucially relies on having a very orthogonal basis of the unit lattice [11]. It (usually) divides by
two the dimension of the lattice, which corresponds to reduce the running time to its square
root. For most cryptosystems based on ideal lattices, the ideals are not principal, so this
attack does notapply† . However, if it can be modified to attack Ring-LWE, which is decoding
q a
in the lattice
O2 for some uniform a ∈ O/q, this would break almost all published
0 1
design in practical time ‡ . Another application is to solve the norm equation, though not in
polynomial time. A last application is the heuristic ability to solve bounded distance decoding
in polynomial time over the unit lattice with approximation factor around nO(log(log n)) , even
though the unit lattice is not known. Note however that units may not be of size polynomial
in the discriminant. A recent attack against GGH uses Gentry-Szydlo’s algorithm in a similar
way, our extension allows it to work over any number field [12].
While CM orders and their polarized class group were introduced for the study of abelian
varieties, such as some elliptic curves, this paper does not use any algebraic geometry. Also,
this result may indicate that polarized class group are more tractable than the class group
from a computational point of view. In particular, given some generators of a subgroup of the
polarized class group, either we have an incremental multiset hash function [13] (or a hash
function), or there is an efficient bijection between this abelian group and its normal form.
Finally, testing equality in the polarized class group is related to isotopy of knots, see [14,
Knot theory].
In appendix, we show that for ideal lattices, we can accelerate standard algorithms for
searching the shortest vector by a polynomial factor with respect to their (exponential)
complexity on generic lattices.

2. Preliminaries
2.1. Basics
P
The norm of a vector or a matrix ||A|| is the Frobenius form, i.e. ||A||2 = i,j A2i,j . The
binary logarithm is denoted by log and ln is the neperian logarithm. All indices start from
zero.
Definition 1. An order O is a commutative unitary ring, whose additive group is
isomorphic to Zn . We denote O∗ the group of units in the order. The trace of a, tr(a), is
the trace of the endomorphism x 7→ ax.

† Remark that the schemes are proven to be at least as secure as ideal lattices, current attacks need to find
short vectors over a module of rank two.
‡ We consider therefore that a wise design based on ideal lattices should have at least 256 bits of security if
the users want to keep data secure for several decades with high probability.

ALGORITHMS ON IDEAL OVER COMPLEX MULTIPLICATION ORDER

Page 3 of 17

Notice that usually, an order is defined with respect to an algebra, this is not the case here.
For the rest of the paper, we will work with an order, always denoted by O, whose
corresponding algebra Q ⊗ O is denoted by E. We refer to elements of E ∗ ∩ O as invertible. An
order is given to an algorithm by n, followed by the n(n + 1)/2 products of two basis elements,
written as integer linear combinations of basis elements. We define the height function of x ∈ Z
to be h(x) = 2 log(2 + |x|), and extend it to the rationals h(p/q) = h(p) + h(q) where p and q
are coprime. The height of a matrix or a list is the sum of the heights of the components. It
represents the number of bits used to describe an object.
Definition 2. An integral ideal I over an order O is an O-submodule. Its norm N (I) is
defined as the cardinal of O/I. A (fractional) ideal is an integral ideal, up to a rational number.
An ideal is said to be invertible if there exists a fractional ideal J such that IJ = O.
An ideal is described by a Z-basis. It is well known that ideals can be multiplied in polynomial
time [15, Section 4.7]. It is clear that if v ∈ O is invertible, then (v) is invertible.
Definition 3. A positive-definite quadratic form f : E → Q over a Q vector space E is a
function such that (a, b) 7→ (f (a + b) − f (a − b))/4 is bilinear, and f (x) > 0 for all non-zero x.
Its determinant is the determinant of the corresponding bilinear form.
While most algorithms in the litterature are presented with lattices, they can usually be
transformed into algorithms over quadratic forms and we will be forced here to use the quadratic
form.
Notation 1.

The group of the roots of units in an order O is denoted µ(O).

Notation 2.

The p-Sylow of a finite abelian group G is denoted by Gp .

Notation 3. Given a number field F , we denote its ring of integers by ZF and its
discriminant by dF .
Theorem 2. LetQE be a commutative algebra of dimension n over the field K. Then there
is a unique E ′ = i Fi where Fi is a finite extension of K such that for all x ∈ E, there is a
unique (a, b) with a nilpotent, a + b = x and b ∈ E ′ .
Proof. This is a direct consequence of the Artin-Wedderburn theorem.
On first read, the reader may assume that O = Z[α] for some algebraic α.
An algorithm has a negligible probability of failure if the probability of failure is bounded
by 2−Ω(n) .
2.2. Advanced definitions
Definition 4. A split CM order is an order O, a norm function N : E → N where N is a
commutative semigroup, and a trace function tr : N → Q such that :
– N is a morphism as a semigroup, i.e. N (xy) = N (x)N (y) for all x, y ∈ E
– x 7→ tr(N (x)) is a positive-definite quadratic form.

Page 4 of 17

PAUL KIRCHNER

Without loss of generality, we will impose furthermore that (tr(N (x + y)) − tr(N (x − y)))/4
is an integer for all x, y ∈ O.
Norms will be used in our algorithms in a black-box manner, so we define the height of a
norm to be the number of bits used to represent it. We describe a split CM order with functions
which run in polynomial time of the height of the input and h(O) for N , multiplication and
inversion in N , as well as the trace.
We now give several examples of split CM orders. The simplest one, not interesting for
our purpose, is where the norm is the identity function and the trace is any positive-definite
quadratic form.
Definition 5. A CM order is an order O equipped with an automorphism x 7→ x which
is an involution, and such that tr(xx) is a positive-definite quadratic form. The real suborder
O+ is defined as {x = x; x ∈ O}, the imaginary lattice O− is {x = −x; x ∈ O}.
We can easily build a split CM order from a CM order by taking N (x) = xx and the
trace function as the standard trace. For α ∈ C some algebraic number, if α ∈ Z[α], then
Z[α] equipped with the conjugation is a CM order. In particular, Z[ζn ] where ζn = exp(2iπ/n)
and n a positive integer is a CM order. In these cases, the norm function is the algebraic norm
over the real subfield, which must not be confused with the corresponding geometric norm. We
define a cyclotomic field to be any Q[ζn ]. Also, Z[X]/(X n − 1) equipped with X 7→ X n−1 is a
CM order and the norm is the autocorrelation.
Finally, Z[α] with the norm α 7→ αα is a split CM order. We can generalize this construction
using Theorem 2 to give a non-trivial split CM order from any order.
Definition 6. A polarized ideal is a pair (I, r) where I is a fractional invertible ideal
and r ∈ N ∗ . The determinant of a polarized ideal (I, r) is the determinant of x 7→ tr(N (x)/r)
defined over I. The polarized ideal group is the group of all polarized ideals. The principal
polarized ideal group is the group of all ((v), N (v)) for all v ∈ E ∗ , and is a subgroup of the
polarized ideal group.
We can now state the informal problem we (partly) solve :
Problem 1. Given a split CM order and a polarized ideal (I, r), determine all invertible
solutions v ∈ O to (I, r) = ((v), N (v)).
Theorem 3. If N (v) = N (w) for v, w ∈ O invertibles, then v/w ∈ µ(O).
Proof. N ((v/w)k ) = 1 for all integer k, but since x 7→ tr(N (x)) is definite positive, (v/w)k can
take only a bounded number of values. Hence, v/w is a root of unity.
This implies that v is defined up to a group of roots of unity.
Though we will not need the following definition, it gives a nice interpretation of the GentrySzydlo algorithm.
Definition 7. Let ∆ be the determinant of (O, N (1)). The polarized ideal class group is
the maximum group of polarized ideals (I, r) of determinant ∆, modulo the principal polarized
ideal group.

ALGORITHMS ON IDEAL OVER COMPLEX MULTIPLICATION ORDER

Page 5 of 17

Lemma 1. The only nilpotent of a CM order O is 0.
Proof. Let x be a nilpotent. Then xx is also a nilpotent, so that tr(xx) = 0. Since x 7→ tr(xx)
is definite, x = 0.
The following definition is the main conceptual novelty with respect to previous descriptions
of Gentry-Szydlo’s algorithm, and allows to greatly simplify its exposition.
Definition 8. The formal products over E, Z(E) , is the additive group of function from
E to Z which are non-zero on a finite set, called support. The evaluation of f ∈ Z(E) , denoted
by [f ], is defined by
Y
xf (x) .
x∈E

We call the elements of the support the base, and f (x) is called the exponent of x. The group
law is denoted multiplicatively.
For clarity reasons, we will consider an element x ∈ E to be also the function of Z(E) equal
to zero everywhere except in x where it is equal to one.
Definition 9. We call a group of polarized ideals to be reducible if for all x, tr−1 ({x}) is
finite.
We call a group of polarized ideals to be poly-reducible if there is a constant c such that for
all (I, r) in the group with I integral, h(r) ≤ (h(O) + log(tr(r))c .
It can be checked that in all our examples of split CM orders, the full group is poly-reducible.
From a mathematical perspective, reducibility is more pertinent, as it is enough to prove that
a reducible group modulo the principal polarized ideals is finite. Yet, we need the stronger
condition for efficient computation over this finite group, see subsection 3.2. However, if we
extend the norms to N × Q, the polarized ideal class group is clearly infinite.
Lemma 2. The principal polarized ideal group is poly-reducible.
Proof. Let G be the Gram matrix of x 7→ tr(N (x)) over O. Let G = Lt L be its corresponding
Cholesky decomposition, that is L is an upper triangular matrix. Then, we can write L2i,i as
a quotient of two non-zero integer determinants of submatrices of G, so that the Hadamard
bound gives Li,i ≥ ||G||−n/2 . Therefore, for any v ∈ O which is invertible, there exists i such
that
|vi |2 ≥ v t Gv||G||−1/n = tr(N (v))||G||−n .
This implies that h(v) ≥ h(tr(N (v))) − h(||G||n ). Now, x 7→ tr(N (x)) is computed in time
polynomial in h(O) + h(x), so there exists c0 such that h(||G||n ) ≤ h(O)c0 . Also, there exists
c1 such that h(1/N (v)) ≤ h(v)c1 . We conclude that there exists c2 such that h(N (1/v)) ≤
(h(O) + h(tr(N (v))))c2 .
Lemma 3. A group is poly-reducible if and only if, there exists a constant c such that for all
polarized ideals (I, r) in the group with O ⊂ I, h(r) ≤ (h(O) + log(tr(1/r))c .
Proof. Remark that I ⊂ O, 1 ∈ I, and I −1 is integral are equivalent. Thus, because inversion
runs in polynomial time, h(1/r) = h(r)Θ(1) and the result follows.

Page 6 of 17

PAUL KIRCHNER

3. Gentry-Szydlo algorithm
We recall that an order O has a corresponding algebra Q ⊗ O denoted by E, which contains
a maximal product of number fields E ′ . This section is devoted to prove the following theorem :
Theorem 4. Given a polarized ideal (I, r) of a split CM order, if E ′ is a product of cyclotomic
field, or the Generalized Riemann Hypothesis (GRH) is true, or we have access to randomness,
we can find vω ∈ µ(E)O such that I = (v) or prove there is no such vω with (I, r) = ((v), N (v)).
(1+o(1))/ log log n
We can also do this unconditionnally in time 2n
. Furthermore, if O is a CM order,
we can find v ∈ O such that (I, r) = (v, N (v)) under the same conditions.
In the next subsections, all algorithms are authorized to fail if there is no solution to (I, r) =
((v), N (v)). Since the output of the algorithm can easily be checked, we may assume that there
is some solution v, except for the analysis of the complexity. Also, in the case of a CM order,
we can assume v is invertible by working in O/(Q ⊗ I).
We fix ∆ to be the determinant of (O, N (1)). Remark that h(∆) = h(O)O(1) .
The hero of our story will be the following group :
Definition 10. Given a poly-reducible group G where all (I, r) ∈ G are of determinant
∆ , its compactification is the group of all (I, r, s) where s ∈ Z(E) such that [s] is invertible ;
modulo the subgroup of all ((1/x), N (1/x), x) for all x ∈ E ∗ .
Indeed, it replaces Gentry-Szydlo’s cumbersome "polynomial chains", and LenstraSilverberg’s chain of tensor multiplication maps. Compactification is to be understood in its
computer science meaning, i.e. a short representation, and not in a topological sense.
In subsection 3.1, we show that using LLL, we can reduce the description of I and r to
a polynomial value, independent of I and r. In subsection 3.2, we show how to compute a
power of (I, r, 1) in polynomial time. We then use this powering algorithm in subsection 3.3
to compute the image over a field of E ′ of some high power of v, as a formal product. By
combining various high powers, we show in subsection 3.4 how to compute the image over a
field of v, up to a root of unity. Finally, we explain in subsection 3.5 how to compute the
nilpotent part of v and one root of unity.
The four different cases in the theorem are introduced in subsection 3.4.
3.1. Reduction
Theorem 5. Given a positive-definite integer matrix G of dimension n, we can compute
in polynomial time a unimodular integer matrix U such that U t GU has entries bounded by
n2n det(G).
Proof. See [16] where the Gram-Schmidt orthogonalization is replaced by Cholesky decomt
t
position. Its output
√ verifies U GU = L L where L is an upper-triangular matrix,
Q such that
Li+1,i+1 ≥ Li,i / 2 and |Li,j | ≤ Lj,j for all i, j. Let m = arg maxi Li,i . Then, i<m L2i,i is a
positive integer, since it is the determinant of the corresponding upper-left submatrix of U t GU .
Also, for any j ≥ m, Lj,j ≥ Lm,m 2(m−j)/2 . It implies that
Y
∆=
L2i,i ≥ L2(n−m)
2−(n−m)(n−m−1)/2 .
m,m
i

We deduce that Lm,m ≤ 2

(n−m−1)/2

√
∆1/(2(n−m)) ≤ 2n/2 ∆. Using |Li,j | ≤ Lj,j gives the result.

Lemma 4. Given m matrices Ai in MP
n (Q) such that a linear combination is invertible, we
can find xi ∈ Z and |xi | ≤ n such that i Ai xi is invertible in polynomial time.

ALGORITHMS ON IDEAL OVER COMPLEX MULTIPLICATION ORDER

Page 7 of 17

Proof. If m = 1, we output x0 = 1. Else, we compute r the rank of A0 and a set I of r rows and
J a set of r columns such that the restriction of A0 to these lines and columns is invertible. We
then recursively find the xi , i ≥ 1 corresponding to Bi , the restriction of Ai to the complements
of I and J. Finally, we search through all x0 from 0 to n and output the first solution.
Without loss of generality, we may analyze this algorithm by assuming A
P0 is diagonal,
with
r
ones
followed
by
zeroes
on
the
diagonal.
By
assumption
det(
i Ai Xi ) =
P
P j
P
(X
,
.
.
.
,
X
)
is
non-zero.
Then,
P
=
det(
B
X
),
and
is
also
X
j
1
m−1
r
i
i
0
i≥1
j
P
P non-zero.
By our choice of xi , that is det( i≥1 Bi xi ) ̸= 0, we have that det(A0 X + i≥1 Ai xi ) =
P j
j X0 Pj (x1 , . . . , xm−1 ) is a non-zero univariate polynomial of degree at most n, so that it
has at most n roots, which guarantees the algorithm will find a solution.
Theorem 6. Given (I, r) in a poly-reducible group of determinant D, we can find in polynomial
time x ∈ E ∗ and a basis C of I/x, such that h(C) + h(r/N (x)) = (h(O) + h(D))O(1) . Also,
O ⊂ I.
Proof. Without loss of generality, we can assume that I is an integral ideal, of basis
A = (ei )i<n . We then compute the Gram matrix corresponding to x 7→ tr(N (x)/r), that
is Gi,j = (tr(N (ei + ej )/r) − tr(N (ei − ej )/r))/4, which we can do in polynomial time. We
use Theorem 5 to compute U such that U t GU is bounded by n2n D. Now, we compute
P
B = AU = (bi )i<n , and use Lemma 4 with the multiplication matrices of bi , to find y = i xi bi
invertible. Finally, we return y and B/y.
The running time is clear. Because II −1 = O, there exists z ∈ Zn such that Az is invertible,
so that the condition of LemmaP4 is fulfilled.
We now have tr(N (y)/r) = x2i tr(N (xi )/r) ≤ n4 2n D. Since h(O) ≥ n and y ∈ I implies
I/y ⊂ O, h(r/N (y)) = (h(O) + h(D))O(1) follows from Lemma 3. Also, for all i, we have
tr(N (bi /y)N (y)/r) ≤ n2n D so that h(N (bi /y)N (y)/r) = (h(O) + h(D))O(1) . Now we can
compute N (bi /y) from N (bi /y)N (y)/r and r/N (y), and hence tr(N (bi /y)) in time (h(O) +
h(D))O(1) . It implies log tr(N (bi /y)) = (h(O) + h(D))O(1) . Then, with H = Lt L the Gram
matrix of x 7→ tr(N (x)) over O and its Cholesky decomposition, we have log(L(bi /y)j ) =
n/2
(h(O) + h(D))O(1) for all j. Since Lj,j ≥ ||H||−n/2 we have L−1
, we deduce
j,j ≤ ||H||
O(1)
h(bi /y) = (h(O) + h(D))
.
3.2. Powering
Theorem 7. Given (I, r) = ((v), N (v)) a principal polarized ideal and an integer e, we can
compute (I, r, 1)e over the compactification of the principal polarized ideal group in polynomial
time. Furthermore, the norm which is outputted have a height h(O)O(1) and the ideal contains
O.
Proof. If e = 0, we return (O, N (1), 1). If e is even, we recursively compute (I, r, 1)e/2 =
(K, u, s), use Theorem 6 with (K 2 , u2 ) which returns an ideal C and x ∈ E ∗ , and outputs
(C, u2 /N (x), s2 x) Else, we recursively compute (I, r, 1)e−1 = (K, u, s), use Theorem 6 with
(KI, ur) which returns an ideal C and x ∈ E ∗ , and outputs (C, ur/N (x), sx). If at any point,
the height is too large with respect to the bounds given by Theorem 6, we fail.
Correctness is clear. By induction, the output is reduced so its height without the formal
product is bounded by h(O)O(1) . It implies that the height of the bases in the formal product
is bounded by h(O)O(1) , while the exponents are bounded by e and the cardinal of the support
is bounded by O(log(e)). Therefore, the algorithm runs in polynomial time.
Note that we can, in fact, compute any circuit over the compactification of any poly-reducible
group in polynomial time. In particular, we may use shorter addition chains.

Page 8 of 17

PAUL KIRCHNER

3.3. Recovery of a high power of v
We fix in this subsection a maximal ideal m of E, and suppose a Q-basis is given. Remember
that E/m is a number field, which we denote F . We define O′ as a suborder of O/m.
Lemma 5. Given an invertible integral ideal a of O′ , we have for all x ∈ ak , x ̸= 0, h(x)/n ≥
k log(N (a)) − O(h(O′ )).
Proof. It is well known that the norm is multiplicative for invertible ideals, see for example [15,
Proposition 4.6.8]. Also, for x ∈ ak , x ̸= 0, we have (x) ⊂ ak so that N ((x)) ≥ N (a)k . Then,
N ((x)) is also the absolute value of the determinant of the multiplication by x. Using the
Hadamard bound, we have log(N ((x))) ≤ n(log(||x||) + h(O′ )).
Lemma 6. Given an invertible matrix A with λ1 = minx∈Zn −{0} ||Ax||, and c such that there
exists y ∈ Zn with ||Ay − c|| ≤ 2−n λ1 , we can recover y in polynomial time.
Proof. This was proven by Babai [17, Theorem 3.1], as an application of LLL.
k

Lemma 7. Given a prime ideal p of O′ with a prime number p ∈ p, we have x(N (p)−1)p ∈
1 + pk+1 for any invertible x ∈ O′ − p and k a positive integer.
Proof. We use induction on k. O′ /p is a field, so xN (p)−1 ∈ 1 + p for any invertible x ∈ O′ − p.
Now, let y ∈ pk . If we develop (1 + y)p − 1 − y p , p ∈ p divides all binomial coefficients and
the power of y is at least one, so (1 + y)p − 1 − y p ∈ (p)pk ⊂ pk+1 . Since p ≥ 2, we also have
y p ∈ pk+1 and hence (1 + y)p ∈ 1 + pk+1 .
Theorem 8. Given (I, r) = ((v), N (v)) a principal polarized ideal and p be an invertible prime
ideal of O′ with p ∈ p a prime integer and v ̸∈ p + m. Then, we can output k and s in polynomial
k
time such that v (N (p)−1)p = [s] modulo m.
Proof. Let e = (N (p) − 1)pk for some integer k. We first compute using Theorem 7 (I, r, 1)e =
(J, a, s). We know that 1/a = N ([s]/v e ), h(1/a) = h(O)O(1) and J −1 is integral, and therefore
[s]/v e is an invertible integer, whose height is in h(O)O(1) . Using Lemma 5, there exists a
constant c such that with k = h(O)c , any non zero element in pk+1 has a coordinate larger
than 2n times any coordinate of [s]/v e .
Remark that we can compute in polynomial time pk+1 . We then run Lemma 6 with the basis
of pk+1 and [s] modulo m and pk+1 ; we call the result lifted to O, c. Because of the previous
lemma, since v ̸∈ p + m, v e = 1 modulo m and pk+1 . Hence, c and [s]/v e differs by an element
of pk+1 modulo m but by definition of k, Lemma 5 and Lemma 6, it must be zero. Therefore,
we return s/c.
Though v may not be unique, the given power is.
3.4. Recovery of v over a field
Lemma 8. Given an order O′ over a number field, we can compute O′ ⊂ Op′ and integral
invertible ideals pi of Op′ such that
Y
pOp′ =
pei i
i

in time which is polynomial in the size of the input, and p. Using randomness, we can do the
same in polynomial time.
Proof. See [15, Sections 6.1 and 6.2], where the only randomness used is for factoring
polynomials modulo p.

ALGORITHMS ON IDEAL OVER COMPLEX MULTIPLICATION ORDER

Page 9 of 17

Lemma 9. Let ei be integers, si be formal products such that [si ] = v ei modulo m and I = (v).
Let g be the greatest common divisor of the ei . Then, we can find in time polynomial in the
size of the input and g, an element w such that w/v reduced modulo m is a root of unity.
Proof. We can compute in polynomial
P time by applying a Hermite normal form algorithm over
e, a vector of integers ui such that i ei ui = g. We search for some prime p such that the bases
in the support of all si are invertible modulo p. Since a ∈ O is invertible modulo p if and only
if its norm is divisible by p, there exists a p which is bounded by a polynomial of theQsize of the
input which works and we can find it in polynomial time. We then compute s = i sui i , and
evaluate [s] modulo m and some sufficiently high power of p (but polynomial in h(I)g ), so that
we recover y, congruent to v g modulo m. Finally, we factor X g − y in polynomial time over F
(see [15, Section 3.6.2]), and if there exists a linear factor X − w, we output w. Else, we fail.
Remark that v reduced modulo m is a root of X g − y, and the quotient of two roots must
be a g-th root of unity.
Lemma 10. If F is a cyclotomic field, we can choose in polynomial time two primes such that
the gcd of the corresponding exponents in Theorem 8 is polynomial.
Proof. If F = Q[ζm ], then we choose the first two primes which split in linear factors, which is
equivalent to being congruent to one modulo m. We use the latest version of Linnik’s theorem,
which says that the smallest prime congruent to a modulo k is O(k 5 ) [18, Theorem 2.1]. Then,
the smallest prime congruent to one mod m, p verifies O(m5 ). Let r be the smallest prime
which does not divide p − 1 or m, we know that r = O(log(m)). We then define a to be the
element of Z/(rm) congruent to one modulo m and to 1 + p modulo r. Thus, we can define
q to be the smallest prime congruent to a modulo rm, and q = O((m log m)5 ), q > p. Finally,
for any α, β, gcd((p − 1)pα , (q − 1)q β ) = gcd((p − 1)pα , q − 1) < q.
Remark that we can make the gcd equal to m using the technique of [4, Proposition 4.5],
but the exponent then becomes 50.
Lemma 11. Let H = F [ζm ] be a Galois extension of F and m ̸∈ p be some invertible prime
ideal of Op′ . Then, m|N (p) − 1 if and only if pZK splits completely over H.
Proof. Using the properties of the conductor ideal, it is a standard fact that without loss of
generality, we can assume Op′ = ZK . Also, p does not ramify. Remark that for any prime q
above p, we have xN (q) = x over ZH /q. Hence, p splits completely is equivalent to xN (p) fixes
ZH /p. But ζm ̸∈ p so that it is equivalent to fixing ζm , which is m|N (p) − 1.
Theorem 9. Given a polarized principal ideal (I, r) = ((v), N (v)) and m, if F is a cyclotomic
field, or GRH is true, or we have access to randomness, we can find w such that v/w modulo m
is a root of unity in polynomial time. We can also do this unconditionnally in time polynomial
(1+o(1))/ log log n
in 2n
and the size of the input.
Proof. The algorithm consists in applying Lemma 8 to generate the input of Theorem 8, and we
combine the outputs using Lemma 9. The crux of the matter is to bound the greatest common
divisor of the exponents used. The case of cyclotomic field is easily treated with Lemma 10.
Indeed, for each prime p, then either the image of v is divisible by p so the factor can then be
removed and this happens at most a polynomial number of times, or we can use some p above
p.
Under GRH, we show that using all prime ideals p of inertia degree one above all primes p
smaller than a polynomial will work. Using the previous lemma and [19, Théorème 4], we have
that there are a polynomial number of primes smaller than some polynomial who have a prime
ideal above it of inertia degree one. Hence, we can find two amongst them which does not
divide v, and m will be gcd((p − 1)pf , (q − 1)q e ) < q if q > p. Therefore, the algorithm runs in
polynomial time.

Page 10 of 17

PAUL KIRCHNER

For the other algorithms, we first start by trying for all the 2n2 + n + 1 smallest primes
any ideal above it such that the image of v is not in the ideal. Each time a prime is detected
as dividing the image of v, it can be factored out. Let m be the current greatest common
divisor of the exponent used. Remark that there are n inertia degree possible, so that by the
pigeonhole principle, there exist one degree d with 2n + 2 corresponding primes pi . Let pk | m
with k positive and p prime. By removing p from the list of pi , we have that for 2n + 1 distinct
primes pi , pk | pdi − 1. This implies that either pk = O(n2 log n), or there are 2n + 1 elements
of order dividing d in (Z/(pk ))∗ . If p is odd, the group is cyclic so that 2n + 1 ≤ d which is
absurd. Else p = 2, the group has at most 2d elements of order dividing d, and 2n + 1 ≤ 2d
which is also absurd. Hence at this point, pk = O(n2 log n) for all pk | m.
For the unconditional algorithm, we continue to do so for the first primes. Let P be the
Θ(1/ log log n)
largest prime used, which we will fix later to some function in 2n
. Using the same
argument, we have that for the new m and some d, that either m ≤ O(P n2 log n) or there
exist a m′ | m with m′ = O(P n2 log n) and odd such that all primes considered except possibly
O(n2 log n) of them are of order dividing d in (Z/(m′ ))∗ , and these primes are distinct elements
modulo m′ . Thus, there are Ω(P/n/ log P ) elements of order dividing d in (Z/(m′ ))∗ , which is a
proportion of Ω(1/n3 / log3 (n)n−Θ(1/ log log n) ) = Ω(1/n4 ). Decomposing (Z/(m′ ))∗ as a product
of cyclic groups, we first consider the groups where all elements are of order dividing d, that
is (p − 1)pk | d, for (p − 1)pk | m′ with p prime. Let (q − 1)q r be another cyclic group of equal
order. Then, without loss of generality q ≥ p and if k is positive, q | (p − 1)pk which is not
possible. Hence q is unique with respect to (p, k) and using Wiegert’s theorem, we deduce that
there are at most d(1+o(1))/ log log d cyclic groups where all elements are of order at most d.
But because of Lagrange’s theorem, there are at most O(log(n)) cyclic groups where not all
elements are of order dividing d. Hence, for
(1+o(1))/ log log d

P ≥ (n2 log n)O(log(n))+d

(1+o(1))/ log log n

this is absurd. The total running time is therefore in 2n
.
Using randomness, we sample a polynomial number of integers smaller than B 1/f with
B = exp(O(log(d) log(log d) log(log log d))) where d = dF [ζq ] for some prime power q dividing
m such that F has no q-th root of unity. If the number divides m, which happens with negligible
probability, we restart. Else, if the number is prime, we use all prime ideals above this prime.
The probability that some ideal divides v is negligible. We use all f from one to n.
[19, Théorème 3] shows that the likelihood of a complete split is then ϵ ≤ c/[F [ζq ] : F ] for a
uniform prime of norm below B and some universal constant c. Assume ϵ < 1/2. Then, there
are k ≥ 1 inertia degrees f such that the likelihood for a prime below B 1/f to have prime above
it with an inertia degree f is at least (1 − ϵ)/n. Further, the likelihood that a uniform prime of
norm below B with one of these inertia degrees not to completely split is at least (1 − ϵ)k/n.
Therefore, there exist an inertia degree f such that a uniform prime of norm below B of inertia
degree f will not completely split with probability at least (1 − ϵ)/n, and a uniform prime
below B 1/f has a probability at least (1 − ϵ)/n to have a prime of inertia degree f . We deduce
that the above procedure takes polynomial time to find a prime ideal which does not split
completely with high probability. In case we find a prime not have a complete split, because
p - m, we have gcd(m, (pf − 1)pe ) ≤ m/2 so that with high probability, after a polynomial
number of tests, we have that pk |m only if F has a pk/c root of unity. We deduce then that
m = O(n log log n)c , so that the running time is polynomial.
3.5. Recovery of v
Theorem
10. Given E, we can compute mi such that E is the sum of a nilpotent vector space
Q
and i E/mi where mi are maximal ideals of E in polynomial time. We can also compute

ALGORITHMS ON IDEAL OVER COMPLEX MULTIPLICATION ORDERPage

11 of 17

the generators
of group of roots of unity of E and O in polynomial time and ei such that
Q
O = i ei O and ei O has only trivial idempotents.
Proof. See [20, Theorem 1.2] for the first algorithm, which starts by expressing the product of
number fields as Q[x]/(f ) and then compute the factorization of f by LLL. The second part
is quite involved and is proven in [21].
The following method for recovering the root of unity is heavily inspired by [4].
Lemma 12. Let w ∈ µ(O) where O is a CM order. Then ww = 1.
Proof. With Lemma 1 and Theorem 2, E is a product of fields. Hence, E ⊗ C is isomorphic
to Cn , and the conjugation can be projected to a conjugation over C which has the same
properties. Therefore, it is the standard conjugation over C, and all roots of unity ζ over
C verifies ζζ = 1. Since the projection of a root of unity w ∈ O is a root of unity, we have
ww = 1.
Lemma 13. For any a ∈ O and O a CM order, tr(aa) ≥ r where r is the dimension of aaO.
Proof. Without loss of generality, a ̸= 0. Consider the application x 7→ xaa over aaO. Its
determinant is a non-zero integer since there is aa is not nilpotent, so that the inequality
of arithmetic and geometric means over the eigenvalues gives the result.
P
Lemma 14. If A and Q
B are CM orders, then A ⊗ B is a CM order and if
i ai ⊗ bi ∈
µ(A ⊗ B), we have A = i ai ai A ⊗ bi bi B.
Proof. The only difficult point in the first statement is to show that x 7→ tr(xx) is positivedefinite. This comes from the fact that the corresponding Gram matrix is the Kronecker product
of the two Gram matrices corresponding to A and B, which can be diagonalized thanks to the
spectral theorem.
P
PThen, if P i ai ⊗ bi ∈ µ(A ⊗ B) where the sum is finite
P and ai , bi ̸= 0, we have
(P i ai ⊗ bi )( i ai ⊗ bi ) = 1 with Lemma 12. Therefore,
bi = 1. We deduce
i ai ai ⊗ biQ
tr(a
a
)
tr(b
b
)
=
tr(1)
and
using
the
previous
lemma,
A
⊗
B
=
i i
i i
i
i ai ai A ⊗ bi bi B as
product of suborders.
Lemma 15. B = Z[X]/(X n − 1) equipped with X 7→ X n−1 is a CM order and µ(B) is
generated by X and −1. Its idempotents are zero and one.
Proof. Remark that forPany ω ∈ µ(B), we have with Lemma 12 ωω = 1. Then, with ω =
P
n−1
n−1 2
i
i
i=0 ai X , tr(ωω) = n
i=0 ai . Therefore, ω = ±X and the converse is clear.
If e is an idempotent, then ee is also an idempotent. But if e ̸= 0, tr(ee) ≥ n so that ee = 1.
Hence e is invertible, so that e = 1.
Theorem 11. Given a CM order O, an ideal I = ωO with ω ∈ µ(Q ⊗ O), we can find ζ ∈
µ(Q ⊗ O) such that ωζ ∈ O in polynomial time.
Proof. Without loss of generality, we can assume ω ∈ µ(Q ⊗ O)p and we know some e ≤ 2n
such that ω e = 1. We now compute all the primitive idempotents ei of O and by combining
the results for all I/ei O over ei O, we can assume O has only trivial idempotents.
We then build the CM order O ⊗ Z[X]/(X e − 1), by concatenating the basis of I i = (ω i ).
We now use [21, Theorem 1.2] to find the generators of the roots of unity of this order.
Because of the previous lemmata, they are of the form w ⊗ X i with w ∈ µ(O). By combining
the generators, we can deduce a root of unity of the form w ⊗ X. Hence, w ∈ ωµ(O) so we can
output 1/w.

Page 12 of 17

PAUL KIRCHNER

Theorem 12. Given (I, r), if E ′ is a product of cyclotomic field, or GRH is true, or we have
access to randomness, we can find vω ∈ µ(E)O such that I = (v) or prove there is no such vω
(1+o(1))/ log log n
with N (v) = r. We can also do this unconditionnally in time 2n
. Furthermore, if
O is a CM order, we can find v ∈ O such that (I, r) = ((v), N (v)).
Proof. We first compute all mi , apply Theorem 9 for each mi and recover some x using the
Chinese remainder theorem. Then, we compute J = I/x = (ω + a) where an = 0 and ω ∈ E
is a root of unity. From the knowledge of the group of roots of unity of E, we can deduce in
k
k
polynomial time e such that ω e = 1. We may then compute P
J e2 = (1 + b)2 with b = (ω +
n
a)e − 1, which is easily seen to be
Since 1 − x 7→ i=1 −xi /i for x nilpotent is a
Pan nilpotent.
k
morphism, whose inverse is x 7→ i=0 x /k! (see [20, Proposition 8.1]), this takes time which
is polynomial in k log(e).
We can compute O′ , the largest order which contains O and all roots of unity of E in
polynomial time, and we have b ∈ O′ . Therefore, we have (1 + b)2 = 1 + b2 in O′ /(2) so that
⌈log n⌉
k
k
(1 + b)2
∈ 1 + 2O′ . We deduce (1 + b)2 = 1 + 2k−⌊log n⌋ O′ . We apply Theorem 6 to J e2
k
k
to produce an invertible y such that y/(1 + b)2 ∈ O′ , with h(y/(1 + b)2 ) = h(O)O(1) . Hence,
k
we choose k sufficiently large so that y/(1 + b)2 is equal to the lift of y modulo 2k−⌊log n⌋ O′ .
2k
We can therefore compute (1 + b) and using the two morphisms, deduce z = x(1 + a/ω).
We finally apply the previous theorem with I/(z) to recover ω.

3.6. Comments on the algorithm
One problem with the given algorithm is that it is not explicit. In particular, we need an
upper-bound on the constants of the algorithms dealing with the norms (tr, N , multiplication
and inversion in N ). However, this seems to be an unavoidable consequence of our black-box
model, as slower algorithms mean a possibly larger set of solutions. Also, for any application
exposed at the beginning, these constants are explicit. Furthermore, if we impose that there is
a solution, one can simply increase the constant until we reach the solution.
Another difficulty is the sheer complexity of the algorithm, both in term of code length and
running time. However, a large part of this complexity can be removed. Indeed, in practice, as
soon as we combine information given by a couple of exponents (typically two, if we manage to
find small primes having a prime ideal of inertia degree one above them), the greatest common
divisor becomes tiny. It can be explained by a heuristic application of Chebotarev’s theorem :
if pk divides the current greatest common divisor but does not divide the number of roots,
the probability that k will not decrease is O(1/p). Hence, we can simply ignore all primes p
where pO is not invertible, or p divides the discriminant of the polynomial ; and beside the
exponentiation, we only need to factor the polynomial defining the number field to produce the
prime ideals. Also, applications can generally cope with finding the solution up to root of unity
of E, since they usually work with an order in a number field with a known polynomial, which
contains few roots of unity, and no nilpotents. Root extraction can be efficiently computed if
we know an inert prime ; a Newton-Hensel iteration may also work. Ideal multiplication can be
accelerated by compressing the lattice, see [22, Section 4]. While the exponent needed might
seem to be huge, it is usually fairly small. For example, when O = Z[ζm ], the precision needed
is exactly the size of a typical LLL reduction of a lattice of determinant one, which is in practice
1.022n in dimension n [23]. Finally, we explain in subsection 4.3 that under plausible heuristics,
the exponent is bounded by O(log(h(O)) log(log(h(O)))), so that the resulting complexity is
in general a couple of lattice reductions. We add that we can save an ideal powering using a
Hensel iteration :
Lemma 16. Let s be a formal product such that [s] = v e for some known e, and v ∈ O′ .
Given a bound on h(v) and a prime invertible ideal p of inertia degree f above the prime p,

ALGORITHMS ON IDEAL OVER COMPLEX MULTIPLICATION ORDERPage

13 of 17

with d = gcd(e, pf − 1), p - e and v ̸∈ p, we can compute v in time polynomial in the size of
the input, p and d.
Proof. We select some k and compute [s] mod pk and c the inverse of e/d modulo pf − 1. We
can then factor X d − [s] in the finite field O′ /p in time polynomial in p, d and the size of the
input. For each root r, we have rc a root of X e − [s] mod p, which we can extend (since p - e)
using Hensel lifting to a root of X e − [s] mod pk . Using Lemma 5 and Lemma 6, for some
polynomially large k, we can recover v from v mod pk .

4. Applications
4.1. Dimension halving
In this subsection we define O to be a CM order. The algorithm was first evoked in Gentry’s
dissertation [24, Section 6.2] before being developped in GGH [7, Section 8.8.1]. We correct
here two benign mistakes in the algorithm. The first is that we should prove the existence of a
short non-zero vector. The second is that the Gentry-Szydlo does not give a unique solution.
Lemma 17. Given an integral invertible ideal I = (v) of O and some x ∈ I − {0} which
minimizes tr(xx), then there exists y ̸= 0 in vO+ or vO− such that 0 < tr(yy) ≤ 2 tr(xx).
Furthermore, these two lattices are included in I.
Proof. Let z = x/v. Remark that tr(vzvz) = tr(vzvz) = tr(xx). Since x 7→ tr(xx) is a quadratic
form, there exists s ∈ {−1, 0, 1} such that 0 < tr(v(z + sz)v(z + sz)) ≤ 2 tr(xx) and s = 0 only
if z = z. If s = 0, then vz ∈ vO+ . If s = 1, then v(z + z) ∈ vO+ . Else s = −1 and v(z − z) ∈
vO− .
Theorem 13. Given a CM order O included in a product of k fields a principal ideal I, using
one call to Theorem 4, having access to an oracle finding a non-zero vector in a lattice at most
γ times larger than the shortest non-zero vector,√and time polynomial in the size of the input
and 2k , we can find a non-zero vector at most γ 2 larger than the shortest non-zero vector of
the ideal. Furthermore, all calls to the oracle are of dimension at most max(dim O+ , dim O− ).
Proof. Without loss of generality, I is invertible and integral. Let v ∈ O such that I = (v). We
first compute I/I and run Theorem 4, which returns some ωv/v and ω ∈ µ(O). Then, for all
ζ ∈ µ(O)/µ(O)2 , we deduce J = I(1 + ζωv/v) = (v + ζωv). For some ζ, we will have ζω = w2
and w ∈ µ(O). Thus with Lemma 12, J = (vw + vw) and I = (vw). We can then compute
J ∩ O+ = (vw + vw)O+ since vw + vw ∈ O+ . Dividing by 1 + vw2 /v, we get a basis of vO+ .
Now, the direct sum of vO+ and vO− is 2I so we can compute a basis of vO− . Using Lemma 17,
we just need to call the oracle on these two lattices.
The complexity is given by the fact that there are at most 2k different ζ.
Usually k = 1 so that the algorithm is efficient. Then, either O+ = O and nothing happens
or dim O+ = 21 dim O and the algorithm halve the dimension for a moderate cost.
It is easy to show that considering only ζ = 1 does not work. For example, with I = (1 +
i)Z[i], we have I/I = −iZ[i] = Z[i] so that we may recover 1 with Gentry-Szydlo’s algorithm.
Then I(1 + 1) = (2 + 2i)Z[i] is not generated by an element of Z[i]+ = Z.
4.2. Solving the norm equation
Problem 2.
that xx = r.

We are given a CM order O and r ∈ O+ . We want to know all x ∈ O such

Page 14 of 17

PAUL KIRCHNER

This is the norm equation problem, in the case of a CM order. The following algorithm
was introduced by Howgrave-Graham and Szydlo [25]. See [26] for a more general technique.
Remark that there may be many solutions since (xy)(xy) = (xy)(xy), and possibly more than a
polynomial. Also, this case seems to show that in a way, we are factoring a number, and hence,
discovering factors of its algebraic norm. Hence, it is plausible that the following algorithm is
close to optimal.
Theorem 14. Let O be a CM order over a number field. Given the factorisation of the algebraic
norm over Q of r ∈ O+ , with d the number of divisors and r ∈ O+ , we can compute all x ∈ O
such that xx = r, in time polynomial in the size of the input, d and calls to Theorem 4.
Proof. Without loss of generality, using [15, Section 6.1] we can assume that all primes involved
are invertible in O and O+ . We may then find the factorisation of rO+ using [15, Sections 4.8.3
and 6.2]. Then, Q ⊗ O is a Galois extension of Q ⊗ O+ so that a prime ideal p of O+ is inert or
factored into pp. If it is inert, then the p valuation of xO must be half the p valuation of rO+ .
Else, the p valuation of xO must be less than the p valuation of rO+ , and the p valuation is
uniquely determined by it. Therefore, there are at most d xO distinct, and we can find all of
them. Using Theorem 4, we may then obtain x.
4.3. Lowering the exponent and applications
In many cases, the norm, traces and exponentiation are in fact smooth functions. We can
leverage this property by trying to run Gentry-Szydlo’s algorithm with an approximate norm.
Indeed, what we need is that the last reduction in our powering algorithm (Theorem 8) gives a
meaningful result. Of course, the quality of the approximation depends on the exponent used.
We show here that heuristically, we can use tiny exponents. The idea comes from GGH [7,
Section 8.6]. Since all algorithms of this subsection use the following strong heuristic, we will
also allow them to use randomness and GRH.
Heuristic 1. Let F be a number field of Q-dimension n with exactly m roots of unity.
Then, the expected value of the number of prime ideals above p = am + 1 of inertia degree one
mφ(m)
is Ω( log(p)n
) for a random a.
Proof. Note that a prime p having a prime ideal above it of inertia degree one must be of the
form am + 1. The density of prime numbers among integers of this form is φ(m)mlog(p) . p always
factors over Q[ζm ] into φ(m) ideals of inertia degree one. The sum of k times the density of
prime ideals of Q[ζm ] having k prime ideals above it of inertia degree one is, by Chebotarev
theorem, is rφ(m)/n for some positive integer r, which is the average number of fixed point
in the Galois group. Assuming the two results occur somewhat randomly, and independently
implies the heuristic.
Theorem 15. Let O be a split CM order with no nilpotents beside zero. If the heuristic
assumption is true for each number fields, we can in polynomial time, given (I, r) = (v, N (v)),
find some solution v ∈ O if it exists. Furthermore, the exponent used in calls to Theorem 8 is
e = h(O)O(log(h(O))) . Therefore, if tr(N (x)(r̃/r)e )/ tr(N (x)) ∈ [1/2; 2] for all x ∈ O − {0}, we
can find some solution v ∈ O to (I, r) = (v, N (v)) given I and r̃.
Proof. Using Theorem 6, we can assume
that h(v) = h(O)O(1) . Let pi be the sequence of
Qk−1
prime numbers. For some k, we let e = m i=0 pi . We then proceed just like in Theorem 8 with
(I, r, 1)e . Remark that there are at least 2k divisors of e of the form km, and log(e) = O(k log k).
k
We therefore expect Ω( 2nkmφ(m)
log k ) of the 1 + d with d divisor of e to be prime with a prime ideal
pa,j of inertia degree one above it. Only O(log(h(O))) of these can divide v. The inverse of the

ALGORITHMS ON IDEAL OVER COMPLEX MULTIPLICATION ORDERPage

15 of 17

Q
Q
returned ideal is generated by a small integer in 1 + j pj . Hence, if the determinant of j paj
is exponential in h(O)O(1) , we can proceed. Then, using another prime of inertia degree one, we
k
) = h(O)O(1) ,
can finish in polynomial time with Lemma 16. Our condition is then Ω( 2 mφ(m)
n
so that some k = O(log(h(O))) works.
In case our number field is Z[ζn ], we need only the product of the primes to be above the
LLL approximation factor, which in practice is ≈ 1.022φ(n) [23]. For n = 216 , we can use k = 8
so that e = 635678883840 and the product is around 21048 which is larger than the required
21029 . This implies that only ≈ 50 lattice reductions are needed. The sum of 2/ ln(d) for all
n | d | e is ≈ 27, and there are 38 d + 1 which are primes. Taking k = 21 leads to 168076 primes
instead of the predicted 98361, and the product has more than 10 million bits while e < 2112 .
This theorem can be used to recover a unit u from its approximation ũ by calling it with
(O, ũũ) within the corresponding split CM order. If O is in a number field, R ⊗ O ≃ Rr Cs
and by applying some complex logarithm, the image of O∗ is a lattice of dimension r + s − 1.
Now, the precision required in this basis is simpler to express : the error should be at most
n−O(log(log n)) on each coordinate of the image of ũũ.
The following theorem can be seen as a way to compute a greatest common divisor.
Theorem 16. Let D be a samplable distribution over the number field E such that for all
embedding ψ : O → C, log(|ψ(a)|) has standard deviation at most σ. Given (v) and k samples
si = vai where the ai are independent and sampled from D, if the heuristic holds, we can
recover vµ(O) in polynomial time if k ≥ σ 2 nO(log log n) except with negligible probability.
Proof. We fix an embedding of E into C and then we can define the split CM order using
the norm x 7→ xx. We compute r̃ the average of si si divided by the average of ai ai computed
by sampling from D. Using Chebyshev inequality, we can prove that if we use σ 2 nO(log log n)
samples, then for all embedding ψ : E 7→ C,
ψ(r̃)/|ψ(v)| ∈ [1 − n−O(log log n) ; 1 + n−O(log log n) ]
P
with probability at least 1/2. Since tr(N (x)) = ψ |ψ(x)|2 , we can use the previous theorem.
The original Gentry-Szydlo attack on NTRU signatures [3] is essentially an application of
this theorem. It improves on it by remarking that if O is a CM order we can compute (vv),
reduce this basis, and use it to decode r̃ and recover vv. Another possibility which works for any
order is to decode r̃ over a basis of N by truncating the coefficents, which has the advantage of
being polynomial time. It gives a proven algorithm which is polynomial, and needs a number
of samples which is about the maximum coefficient of vv.
Note that taking the ideal generated by all si should get (v) for most applications so that
the hardest condition to achieve is the possibility of sampling from D.
Theorem 17. Let O be in a number field, and for some embedding in C, we define N (x) = xx.
Given (I, r) a polarized ideal of determinant ∆, if the heuristic holds, we can determine if
there exists a v ∈ I such that for all embedding ψ into C, we have |ψ(v)|2 /ψ(r) ≤ 1 + 1/e and
find it, for some e = log(h(O))O(log(h(O))) .
Qk−1
Proof. We use e = m i=0 pi and compute (I, r, 1)e = (J, p, s). Now, det(I e ) = det(I)e using [15, Proposition 4.6.8], so that the determinant of (I, r)e is also ∆. Without loss of
generality, we can assume h(I) = h(O)O(1) . We select a random subset of half the prime ideals
of inertia degree one above p with p − 1 | e, so that with high probability v e = 1 mod K where
K ∩ I has no non-zero vector shorter than 2n 3n. We deduce that v e /[s] ∈ J ∩ (1/[s] + K) and
tr(N (v e /[s])/p) = tr(N (v e )/re ) ≤ 3n. Therefore, we can apply Babai’s algorithm Lemma 6 on
J ∩ (1/[s] + K) equipped with the norm x 7→ tr(N (x)/p) and recover v e as a formal product.
We now find another small prime ideal and using Lemma 16, we recover v.

Page 16 of 17

PAUL KIRCHNER

Note that this implies that finding the shortest vector (for some norm) of invertible ideals
is easy if it is almost as small as it can be (1). If r = N (v), then det((v))/ det(I) < 2 so that
I = (v) which is the standard case.

Acknowledgement
We thank Pierre-Alain Fouque for his comments allowing to improve a draft of this paper.

References
1. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. pages 84–93, 2005.
2. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings.
pages 1–23, 2010.
3. Craig Gentry and Michael Szydlo. Cryptanalysis of the revised NTRU signature scheme. pages 299–320,
2002.
4. H. W. Lenstra and A. Silverberg. Revisiting the Gentry-Szydlo algorithm. pages 280–296, 2014.
5. Nigel P. Smart and Frederik Vercauteren. Fully homomorphic encryption with relatively small key and
ciphertext sizes. pages 420–443, 2010.
6. Craig Gentry and Shai Halevi. Implementing Gentry’s fully-homomorphic encryption scheme. pages
129–148, 2011.
7. Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal lattices. pages 1–17,
2013.
8. Peter Campbell, Michael Groves, and Dan Shepherd. Soliloquy: A cautionary tale. In ETSI 2nd QuantumSafe Crypto Workshop, 2014.
9. Dan Boneh and David Mandell Freeman. Homomorphic signatures for polynomial functions. pages 149–168,
2011.
10. Jean-François Biasse and Fang Song. Efficient quantum algorithms for computing class groups and solving
the principal ideal problem in arbitrary degree number fields. pages 893–902, 2016.
11. Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering short generators of principal ideals
in cyclotomic rings. Cryptology ePrint Archive, Report 2015/313, 2015. http://eprint.iacr.org/2015/
313.
12. Martin Albrecht, Shi Bai, and Léo Ducas. A subfield lattice attack on overstretched ntru assumptions:
Cryptanalysis of some fhe and graded encoding schemes. 2016.
13. Dwaine E. Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, and G. Edward Suh. Incremental
multiset hash functions and their application to memory integrity checking. pages 188–207, 2003.
14. Eva Bayer-Fluckiger. Ideal lattices. A panorama of number theory or the view from Baker’s garden (Zurich,
1999), pages 168–184, 2002.
15. Henri Cohen. A course in computational algebraic number theory, volume 138. Springer Science & Business
Media, 2013.
16. Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational
coefficients. Mathematische Annalen, 261(4):515–534, 1982.
17. László Babai. On lovász’lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1–13,
1986.
18. Triantafyllos Xylouris. Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in
einer arithmetischen Progression. PhD thesis, Universitäts-und Landesbibliothek Bonn, 2011.
19. Jean-Pierre Serre.
Quelques applications du théorème de densité de chebotarev.
Publications
Mathematiques de l’IHES, 54:123–201, 1981.
20. HW Lenstra Jr and A Silverberg. Algorithms for commutative algebras over the rational numbers. arXiv
preprint arXiv:1509.08843, 2015.
21. HW Lenstra Jr and A Silverberg. Roots of unity in orders. arXiv preprint arXiv:1509.02612, 2015.
22. Zhuliang Chen and Arne Storjohann. A blas based c library for exact linear algebra on integer matrices.
In Proceedings of the 2005 international symposium on Symbolic and algebraic computation, pages 92–99.
ACM, 2005.
23. Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. pages 31–51, 2008.
24. Craig Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009.
25. Nick Howgrave-Graham and Mike Szydlo. A method to solve cyclotomic norm equations f*\ bar {f}. In
Algorithmic Number Theory, pages 272–279. Springer, 2004.
26. Denis Simon. Solving norm equations in relative number fields using s-units. Mathematics of computation,
71(239):1287–1305, 2002.
27. Nicolas Gama, Phong Q. Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. pages
257–278, 2010.
28. Guillaume Hanrot, Xavier Pujol, and Damien Stehlé. Algorithms for the shortest and closest lattice vector
problems. In Coding and Cryptology, pages 159–190. Springer, 2011.

ALGORITHMS ON IDEAL OVER COMPLEX MULTIPLICATION ORDERPage

17 of 17

29. Thijs Laarhoven. Search problems in cryptography. PhD thesis, Eindhoven University of Technology, 2015.
30. Anja Becker and Thijs Laarhoven. Efficient (ideal) lattice sieving using cross-polytope LSH. Cryptology
ePrint Archive, Report 2015/823, 2015. http://eprint.iacr.org/2015/823.
31. Joppe W. Bos, Michael Naehrig, and Joop van de Pol. Sieving for shortest vectors in ideal lattices:
a practical perspective. Cryptology ePrint Archive, Report 2014/880, 2014. http://eprint.iacr.org/
2014/880.

Appendix A. Exploiting roots of unity
We assume here that E is a number field with m roots of unity in O. We show how their
presence allows to accelerate standard lattice algorithms when the geometric norm is ||x||2 =
tr(N (x)) = tr(xx). We define P as X m/2 + 1 if 4 | m, X m − 1 else ; and let m′ be the degree of
P . Remark that there is a natural bijection between the roots of unity of O and ±X i modulo
P.
Theorem 18. For all x ∈ I, with I an ideal of O, we have xω ∈ I and ||x|| = ||xω|| for any
ω ∈ µ(O).
Proof. The first property stems from I being an ideal, the second from N (ω) = ωω = 1.
This implies that I has at least |µ(O)| non-zero shortest vectors, making the extreme pruning
algorithm [27] about |µ(O)|/2 times faster than on a "random" lattice, since xµ(O) is somewhat
uniform over the sphere.
Also, sieving algorithms (see [28, 29]† for surveys) can take advantage of this by reducing the
size of the list of vectors by a factor of |µ(O)|/2 for the same reason. A recent algorithm [30]
works by introducing a hash function h which for a vector returns the index of the largest
coordinate, as well as its sign. It is then randomized to ha (x) = h(ax) for a Gaussian a to
produce a locality-sensitive hash function H by concatenating outputs of several ha .
We can improve on this by embedding I and E in Q[X]/(P (X))[Y ]/(Q(Y )) for some
irreducible polynomial Q ∈ Q[ζm ][Y ] of degree n/φ(m), so that they have the same geometry.
We can now choose ha (x) = h(ax) and observe that ha (xω) for ω a root of unity is simply
a rotation of ha . Hence, we can build H as the concatenation of ha0 , ha1 , . . . , hak where the
output of ha0 is forced to be on a positive monomial of the form Y i by considering the unique
root of unity which allows this. The algorithm then has to compute the shortest element among
x + ωy for all ω ∈ µ(E). We now show that this can be computed efficiently.
Theorem 19. Given x, y ∈ Q[X]/(P (X))[Y ]/(Q(Y )) with P and Q defined as above, we can
compute arg minω∈µ(O) ||x + ωy|| in O((n/φ(m))2 m log m) arithmetic operations.
Pn/φ(m)−1
P
Proof. We denote x = i=0
xi Y i for any x. Now ⟨x, y⟩ = i,j Gi,j ⟨xi , yj ⟩ for some Gram
matrix G with the scalar product ⟨xi , yj ⟩ corresponding to the norm over the CM order. Hence,
we only need to show how to compute ⟨a, bX i ⟩ for a, b ∈ Q[X]/(P (X)) and all i in O(m log m)
operations.
Since the norm over Q[X]/(P (X)) is x 7→ tr(xx), we have ⟨a, bω⟩ = tr(abω). We can therefore
compute ab with a Fourier transform in time O(m log m). Finally, tr(aX −i ) is exactly the i-th
coefficient of a.
This implies an overall speed-up of m1.43+o(1) , while [30] gives a speed-up of only O(m), and
the ideals were required to be over a ring of the form X m ± 1. The use of Fourier transform
for accelerating geometric computations was first introduced by [31].

† Beware that the litterature often uses different way for expressing multiplication, multiplication by a root of
unity or conjugation, such as (nega)cyclic matrices, rotation and reflex polynomial.

