PhD Stéphanie Nguyen
email: stephanie.nguyen@iae-aix.com

Professor Sylvie Llosa
email: sylvie.llosa@iae-aix.com

ON THE DIFFICULTY TO DEFINE THE SHARING ECONOMY AND COLLABORATIVE CONSUMPTION -LITERATURE REVIEW AND PROPOSING A DIFFERENT APPROACH WITH THE INTRODUCTION OF 'COLLABORATIVE SERVICES'

Keywords: sharing economy, collaborative consumption, collaborative services, online platform, triad

While the number of scientific articles related to the sharing economy (SE) and collaborative consumption (CC) has increased significantly over the past few years, many scholars still disagree on a shared definition. The scope itself of the phenomenon remains a subject for debate in the scientific community. Our objective is to compare existing definitions based on a list of different criteria. Recognizing that various interpretations exist throughout the literature, we suggest a different approach focused on the novelty and innovating features: what types of new practices have emerged, that did not exist previously? What are their characteristics and specificities? We propose to name these new types of exchanges 'collaborative services'.

The emergence of a new mass phenomenon

Over the past decade the sharing economy (SE) seems to have surged and developed across various different types of sectors: from using a velib in Paris to go to an appointment to renting someone else's house for our next vacation or ride-sharing in a complete stranger's car, many of us have already tried and experienced these new types of consumption practices. The SE has quickly grown to the point that it is now playing an important role in the overall global economy. It is not a niche market anymore and may even be on the verge of becoming a mainstream phenomenon [START_REF] Perren | Lateral Exchange Markets: How Social Platforms Operate in a Networked Economy[END_REF][START_REF] Schor | DEBATING THE SHARING ECONOMY[END_REF].

An umbrella term (re)grouping a wide range of diverse practices

The expression 'sharing economy' (SE) has certainly become popular in the mass media and the number of scientific publications on this topic has increased significantly over the past few years. But there is still an important lack of consensus among scholars: from consultants to economists, management or marketing researchers, most if not all agree on the fact that the SE is difficult to define and many gaps remain in our understanding (Belk, 2014b;[START_REF] Perren | Lateral Exchange Markets: How Social Platforms Operate in a Networked Economy[END_REF]. What's more, different terms are being used to refer to similar types of practices and the list can be quite long, to name a few : access-based consumption [START_REF] Bardhi | Access-Based Consumption: The Case of Car Sharing[END_REF], connected consumption [START_REF] Schor | Collaborating and connecting: the emergence of the sharing economy[END_REF], peer economy [START_REF] Bellotti | A muddle of models of motivation for using peer-to-peer economy systems[END_REF], peer-to-peer rental [START_REF] Hawlitschek | Understanding the Sharing Economy-Drivers and Impediments for Participation in Peer-to-Peer Rental[END_REF] or peer-to-peer markets [START_REF] Perren | Lateral Exchange Markets: How Social Platforms Operate in a Networked Economy[END_REF], collaborative economy [START_REF] Acquier | L'économie collaborative: fondements théoriques et agenda de recherche[END_REF] and last but not least collaborative consumption (CC) (Belk, 2014b;[START_REF] Botsman | The sharing economy lacks a shared definition[END_REF][START_REF] Herbert | Pratiques collaboratives et habitus consumériste: une analyse des mécanismes transformatifs de la consommation collaborative[END_REF][START_REF] Möhlmann | Collaborative consumption: determinants of satisfaction and the likelihood of using a sharing economy option again[END_REF]. SE and CC appear as the most widely quoted terms in the literature and interestingly, while a majority of authors believes SE and CC are synonyms [START_REF] Bellotti | A muddle of models of motivation for using peer-to-peer economy systems[END_REF][START_REF] Benoit | A triadic framework for collaborative consumption (CC): Motives, activities and resources & capabilities of actors[END_REF][START_REF] Schor | Collaborating and connecting: the emergence of the sharing economy[END_REF] several researchers on the other hand consider them as different concepts (Belk, 2014b;[START_REF] Frenken | Political economies and environmental futures for the sharing economy[END_REF][START_REF] Hamari | The sharing economy: Why people participate in collaborative consumption[END_REF].

The purpose of this presentation is twofold: first to present an overview of the existing literature on SE and CC based on a set of different characteristics in order to showcase the broad diversity of their current interpretations. Secondly, from this apparent lack of consensus, we suggest a new approach, based on what is different and innovative in the phenomenon. In particular our purpose is to identify what constitutes the core of the SE and CC in order to allow for a proper conceptualization, theorization and modelling. A category of practices surfaces along with its characteristics and specificities, we propose to name it 'collaborative services' (CS).

Sharing Economy (SE) and Collaborative Consumption (CC)

Surprisingly, while the SE is already present in our everyday lives and part of many of our consumers' choices, the interest on this topic from the scientific community is fairly recent and academic research on this new phenomenon is only emerging [START_REF] Benoit | A triadic framework for collaborative consumption (CC): Motives, activities and resources & capabilities of actors[END_REF]. We can find a few scientific papers addressing the SE dated before 2010 [START_REF] Benkler | Sharing nicely: On shareable goods and the emergence of sharing as a modality of economic production[END_REF]) but most articles were published after 2013. From a Marketing perspective, researchers have tried to describe and identify the phenomenon (Belk, 2014b), they have also investigated its specificities, looking for example into factors of satisfaction [START_REF] Möhlmann | Collaborative consumption: determinants of satisfaction and the likelihood of using a sharing economy option again[END_REF] or participants motivations [START_REF] Bellotti | A muddle of models of motivation for using peer-to-peer economy systems[END_REF][START_REF] Benoit | A triadic framework for collaborative consumption (CC): Motives, activities and resources & capabilities of actors[END_REF][START_REF] Hamari | The sharing economy: Why people participate in collaborative consumption[END_REF].

For Rachel [START_REF] Botsman | The sharing economy lacks a shared definition[END_REF] "the sharing economy lacks a shared definition" and Juliet [START_REF] Schor | DEBATING THE SHARING ECONOMY[END_REF] states that "a solid definition (…) that reflects common usage is nearly impossible." French researchers also make the same statement [START_REF] Herbert | Pratiques collaboratives et habitus consumériste: une analyse des mécanismes transformatifs de la consommation collaborative[END_REF][START_REF] Peugeot | Partager pour mieux consommer?[END_REF]. The origin of the term SE is not precisely associated to a specific author but as early as 2004, Yochai Benkler, in Yale's law journal, describes and analyzes what he sees as a new form of exchange, the emergence of sharing and he calls it "sharing nicely". Benkler admits that the term 'sharing' is unusual in the economic literature but more common in the anthropology literature. The apparent contradiction between 'sharing' and 'economy' is captured by [START_REF] Hawlitschek | Understanding the Sharing Economy-Drivers and Impediments for Participation in Peer-to-Peer Rental[END_REF] when they qualify the expression as an oxymoron. Others [START_REF] Herbert | Pratiques collaboratives et habitus consumériste: une analyse des mécanismes transformatifs de la consommation collaborative[END_REF] talk about a semantic confusion around the term 'sharing' and question whether the SE is really about sharing or rather 'pseudo-sharing' practices (Belk, 2014a). Illustrating this idea that the SE and CC regroup a variety of diverse practices, Benkler refers to "a cluster of social practices forming an economic phenomenon". Similarly, other authors talk about the "big tent" of the SE [START_REF] Schor | DEBATING THE SHARING ECONOMY[END_REF] or an "umbrella concept" [START_REF] Hamari | The sharing economy: Why people participate in collaborative consumption[END_REF].

In Benkler's original definition it should be noted that only exchanges between individual customers, 'peers', are included, also called C2C (or P2P) exchanges (ex: Blablacar). This seems to be a first point of disagreement among scholars as many share Benkler's vision but others believe B2C exchanges (ex: Zipcar) also belong to the SE and/or CC. This is captured in Table 1: the first column, C2C only then C2C & B2C, displays the two different perspectives. SE and CC in parenthesis identifies whether the author(s) specifically referred to the SE or CC. In fact, when reviewing the different definitions from the literature, several other aspects have been interpreted differently and we outline three other characteristics subject to debate. First, when a majority of researchers believe solely triadic exchanges mediated by an online platform (ex: Uber, Airbnb) are part of the SE/ CC, a few others consider the phenomenon also includes more traditional and dyadic forms of initiatives such as local or face-to-face practices between friends or family members (such as lending or bartering). Secondly, for most researchers the new phenomenon is exclusively based on access, also referred to as 'short term rental' (Belk, 2014b) but others believe exchanges with both access and transfer of ownership (ex: eBay) are included. Last but not least several authors consider only transactions involving a form of compensation, monetary (ex: vacation rental) or non-monetary (ex: house swapping) belong to the SE/ CC while for others free exchanges (ex: Couchsurfing) are included. The different authors' standpoints are outlined in Table 1. One first takeaway from this literature review is a possible explanation of the difficulty mentioned by many scholars to find a global definition for the SE and CC: the heterogeneity of practices encompassed within it. Table 1 reflects significant differences between authors' positions with regards to SE/ CC characteristics. What's more, it appears that several practices are not new and already existed before the rise of the SE/ CC phenomenon: sharing between friends or family members for example (Belk, 2014b), or B2C rental services (ex: Zipcar). More recently, the exchange of goods (with transfer of ownership) via an online platform (ex: eBay) started becoming popular towards the end of the 20th century. What comes to light is that one particular type of exchange is new and did not exist before the 21 st century, the exchange of services between peers on a large and global scale, made possible by web platforms. By instantaneously matching the supply and demand for services provided by individuals, web platforms facilitate these exchanges, making it possible for strangers, 'peers', to provide and consume services such as vacation rental (Airbnb, Homeaway), car rental (Ouicar, Drivy) or ride sharing (Lyft, Blablacar). Whether those exchanges are for free (Couchsurfing, Mutum) or for a fee (Blablacar, Airbnb) doesn't seem to matter as both forms of exchange are new and did not exist before.

We propose to name them collaborative services (CS) and define them as "services exchanged between peers, a service provider and a service consumer, facilitated via an online web platform acting as a trusted third party, either for free or for a fee. Both the service provider and the service consumer are customers of the web platform." Interestingly Table 1 shows that 7 authors out of 15 [START_REF] Bellotti | A muddle of models of motivation for using peer-to-peer economy systems[END_REF][START_REF] Benoit | A triadic framework for collaborative consumption (CC): Motives, activities and resources & capabilities of actors[END_REF][START_REF] Ert | Trust and reputation in the sharing economy: The role of personal photos in Airbnb[END_REF][START_REF] Hamari | The sharing economy: Why people participate in collaborative consumption[END_REF][START_REF] Huurne | Antecedents of trust in the sharing economy: A systematic review[END_REF][START_REF] Peugeot | Partager pour mieux consommer?[END_REF][START_REF] Richardson | Performing the sharing economy[END_REF] characterize either the SE or CC using similar characteristics : C2C, online, access, free and for a fee. As such, while SE and CC can be considered as umbrella terms regrouping a variety of different practices, CS could represent the core of the phenomenon.

Conclusion

Collaborative services (CS) represent a brand new category of exchanges occurring within a triadic framework [START_REF] Benoit | A triadic framework for collaborative consumption (CC): Motives, activities and resources & capabilities of actors[END_REF]. The CS triad is composed of individual service providers (1), individual service consumers (2) and a web platform (3) intermediating ( 1) and (2). In this new context, several aspects considered as 'traditional' problems already studied and addressed by Marketing researchers specialized in Services may and probably should be revisited. In particular we have identified three possible avenues for future research related to CS. First, while marketing has thoroughly studied relationships, in both triadic and dyadic frameworks, researchers have mainly studied ongoing and continuous relationships, for example between buyers and sellers in B2B exchanges. With CS, we face a new and special combination of two different types of relationships, a continuous one with the platform/brand and a discrete one between peers; are they independent or do they interfere? How constructs such as brand trust for example or customer commitment are impacted? Second, perceived risks can be significant, including a combination of information asymmetry, intangibility and interdependence but also uncertainty related to physical harm, theft or even property damage. Both service consumers and service providers are exposed and while most research has been done on service consumers' trust, only little research exists on service providers' trust and decision making processes, in particular in the context of CS. We believe it could be investigated further. Lastly, studying how to ensure consumer experience consistency when service providers are not employees hence when the platform/brand doesn't have access to the traditional means of control is another interesting research topic. Said differently, what happens to standardization in the context of CS?

Figure 1 :

 1 Figure 1: Collaborative services (CS) triad

  DE LA DIFFICULTE DE DEFINIR L'ECONOMIE DU PARTAGE ET LA CONSOMMATION COLLABORATIVE -REVUE DE LA LITTERATURE ET PROPOSITION D'UNE NOUVELLE APPROCHE A TRAVERS LES 'SERVICES COLLABORATIFS' Résumé : Alors que le nombre de publications scientifiques traitant de l'économie du partage et de la consommation collaborative a augmenté de façon très significative ces dernières années, aucun consensus clair sur une définition commune ne semble se dégager. Le périmètre même du phénomène reste sujet à de nombreux débats. Notre objectif est de comparer, à travers une revue de la littérature, les définitions existantes en fonction d'une liste de différents critères. A partir du constat qu'il existe une multitude d'acceptions et interprétations différentes, nous optons pour une approche différente basée sur le caractère innovant du phénomène: quels types de pratiques ont émergé récemment, qui n'existaient pas auparavant ? Quelles sont leurs caractéristiques et leurs spécificités ? Nous proposons de nommer ce nouveau type d'échanges 'services collaboratifs'.

	ON THE DIFFICULTY TO DEFINE THE SHARING ECONOMY AND COLLABORATIVE
	CONSUMPTION -LITERATURE REVIEW AND PROPOSING A DIFFERENT APPROACH WITH THE
	INTRODUCTION OF COLLABORATIVE SERVICES
	Mots clef : économie du partage ; consommation collaborative ; services collaboratifs ;
	plateforme web ; triade

Table 1 -

 1 Sharing Economy (SE) and Collaborative Consumption (CC) characteristics

		C2C C2C &	Online	Online	Access	Access &	For a	For a fee
		B2C		& offline		ownership	fee	& free
	Ert et al. (SE)	x	x		x			x
	Schor (SE)	x		x		x		x
	Huurne et al. (SE)	x	x		x			x
	Richardson (SE)	x	x		x			x
	Frenken 2017 (SE)	x		x	x			x
	Frenken 2017 (CC)	x		x		x		x
	Benoit et al. (CC)	x	x		x			x
	Hamari et al. (CC)	x	x		x			x
	Mohlmann (CC)	x	x			x	x

Table 2 :

 2 Services typology / classification including Collaborative Services

	MARKET &	BENEFICIARY
	SUPPLIER	Person	Object	Business
	Collaborative	Vacation rental (Airbnb), Ride	Object loans
	Services C2C	sharing (Blablacar)	(Mutum),
	Consumers B2C Hospital, Transportation, Hotel Post office, Bank
	Businesses	Industrial catering,	Machinery	Advertising,
	B2B	Transportation	maintenance	Accounting


Nicholas Coxon
email: ncoxon@maths.uq.edu.au

Keywords: Number field codes, Chinese remainder codes, List decoding Mathematics Subject Classification

. The algorithm is an implementation of the unified framework for list decoding of algebraic codes of Guruswami, Sahai and Sudan [14], specialised for number field codes. The computational complexity of the algorithm is evaluated in terms of the size of the inputs and field invariants.

Introduction

Error-correcting codes derived from algebraic number fields were first considered by Lenstra [START_REF] Lenstra | Codes from algebraic number fields[END_REF], and more recently by Guruswami [START_REF] Guruswami | Constructions of codes from number fields[END_REF]. These codes generalise the construction of Chinese remainder codes (or simply, CRT codes), the number-theoretic analogues of Reed-Solomon codes. Although the two are similar, Guruswami's construction, called number field codes (or NF-codes), is less general than the construction given by Lenstra. However, the generalisation of CRT codes to NF-codes provides a clearer analogue of the generalisation to algebraic geometry codes of Reed-Solomon codes.

Currently, all known algorithms for decoding of codes derived from algebraic number fields are limited to CRT codes. For CRT codes, decoding reduces to the following problem: given n relatively prime integers p 1 < . . . < p n , a vector (r 1 , . . . , r n ) ∈ Z n and an integer k < n, find all m ∈ Z with 0 ≤ m < is referred to as the list decoding problem for CRT codes. The first efficient algorithm for list decoding of CRT codes was provided by Goldreich, Ron and Sudan [START_REF] Goldreich | Chinese remaindering with errors[END_REF]. Their algorithm runs in polynomial time and solves the problem whenever

t ≥ 1 + 2 k • 2kn log p n log p 1 + k + 6 2 .
Subsequently, Boneh [START_REF] Boneh | Finding smooth integers in short intervals using CRT decoding[END_REF] provided a polynomial time algorithm that solves the problem whenever t ≥ kn log p n / log p 1 .

A problem common to these algorithms is the decline in their decoding performance whenever p 1 p n . In particular, Mandelbaum's algorithm may cease to run in polynomial time for such parameters (see [START_REF] Goldreich | Chinese remaindering with errors[END_REF]). Roughly speaking, the problem occurs since the amount of information provided by an integer's residue modulo p i is determined by the size of p i . This problem was overcome for unique and list decoding by Guruswami, Sahai and Sudan [START_REF] Guruswami | Soft-decision" decoding of Chinese remainder codes[END_REF]. For unique decoding, they used the algorithm of Goldreich, Ron and Sudan in a generalised minimum distance style algorithm similar to Forney [START_REF] Forney | Generalized minimum distance decoding[END_REF] to correct the natural bias in the contributions of the residues. Consequently, they obtained the first polynomial time algorithm for unique decoding. For list decoding, Guruswami et al. gave an efficient algorithm for solving the more general problem of weighted list decoding of CRT codes. Given positive weights β 1 , . . . , β n , the weighted list decoding problem for CRT codes asks to find all m ∈ Z with 0 ≤ m < k i=1 p i such that i β i ≥ t, where the sum is over all i such that m ≡ r i (mod p i ). The (uniform) list decoding problem for CRT codes then corresponds to the case where β i = 1, for 1 ≤ i ≤ n. By carefully selecting weights for their weighted list decoding algorithm, Guruswami et al. are able to solve the list decoding problem for CRT codes whenever t ≥ k(n + ε), for all ε > 0, in time polynomial in n, log p n and 1/ε. This decoding performance essentially matches that of the celebrated list decoding algorithms for Reed-Solomon and algebraic geometry codes [START_REF] Sudan | Decoding of Reed-Solomon codes beyond the error-correction bound[END_REF][START_REF] Guruswami | Improved decoding of Reed-Solomon and algebraic-geometry codes[END_REF].

It is natural to ask whether decoding algorithms exist for codes constructed from arbitrary number fields. The construction of NF-codes lies within the general framework of "ideal-based" codes [START_REF] Guruswami | Soft-decision" decoding of Chinese remainder codes[END_REF][START_REF] Sudan | Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms[END_REF]. Thus, the construction lends itself to decoding by an algorithm based on the framework for list decoding of algebraic errorcorrecting described by Guruswami et al. [START_REF] Guruswami | Soft-decision" decoding of Chinese remainder codes[END_REF]Appendix A]. This observation is used in this paper to generalise the results of Guruswami et al. on list decoding of CRT codes to number fields.

The paper is organised as follows. In Section 2, relevant background on NF-codes is provided, and notation established. In Section 3, a generic coding bound is used to establish a condition under which decoding of NF-codes is combinatorially feasible. Necessary algorithmic preliminaries are provided in Section 4. In Section 5 and Section 6, an algorithm for decoding of NF-codes is proposed. The algorithm's performance is analysed in Section 7. In Section 8, parameter selection for the decoding algorithm is considered, with attention given to the weighted and uniform list decoding problems. Finally, conclusions given in Section 9 end the paper.

While this paper was in preparation, another paper [START_REF] Cohn | Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding[END_REF] containing an algorithm for solving polynomial equations over number fields came to the author's attention.

The algorithm presented there shares much in common with ours and leads to an alternative approach to list decoding of NF-codes (see Remark 7.1). In this application, both algorithms yield similar results.

Review of number field codes

Introduced by Guruswami [START_REF] Guruswami | Constructions of codes from number fields[END_REF], NF-codes serve as a natural generalisation of CRT codes to number fields. In this section, their construction is briefly reviewed. For further background and motivation behind the construction of NF-codes, the reader is referred to Guruswami's original description. First, some notation and generalities on number fields are introduced.

Throughout, K denotes an (algebraic) number field of degree d and signature (r 1 , r 2 ). The ring of algebraic integers in K is denoted by O K and the discriminant of K by D K . The field embeddings of K in the field C are denoted by σ 1 , . . . , σ d and assumed to be ordered such that σ 1 , . . . , σ r1 are the real embeddings of K. The remaining 2r 2 = d -r 1 complex embeddings are assumed to be ordered such that σ r1+i = σ r1+r2+i , for 1 ≤ i ≤ r 2 . For all x ∈ K, the (field) norm of x, denoted N K (x), is defined as the product

N K (x) = d i=1 σ i (x). For any nonzero ideal a ⊆ O K , the quotient O K /a is finite. The norm of a nonzero integral ideal a ⊆ O K , denoted Na, is defined as Na = |O K /a|. For all x ∈ O K , the relationship |N K (x)| = N(x) holds, where (x) denotes the principal ideal generated by x in O K . Given a nonzero integral ideal a ⊆ O K , it follows that Na divides N K (x), for all x ∈ a.
The reader is referred to the texts of Marcus [START_REF] Marcus | Number fields[END_REF] and Narkiewicz [START_REF] Narkiewicz | Elementary and analytic theory of algebraic numbers[END_REF] for further background on algebraic number theory.

Given a vector s = (s 1 , . . . , s r1+r2 ) ∈ R r1 × C r2 , the s-shifted size of an element x ∈ K is defined to be

size s (x) = r1 i=1 |σ i (x) -s i | + 2 r2 i=1 |σ r1+i (x) -s r1+i |.
The 0-shifted size of an element x ∈ K is simply denoted size(x). With this notion of size, NF-codes are defined as follows: Definition 2.1 (NF-codes) For pairwise comaximal nonzero ideals a 1 , . . . , a n ⊂ O K , a positive real number M and a vector s ∈ R r1 × C r2 , the NF-code C = C K based on the number field K with parameters (n, a 1 , . . . , a n ; M, s) is defined as follows: the message set of

C is M C = {m ∈ O K | size s (m) ≤ M } and a message m ∈ M C is encoded as the vector (m + a 1 , . . . , m + a n ) ∈ O K /a 1 × . . . × O K /a n .
It is assumed throughout, without loss of generality, that the ideals a 1 , . . . , a n of an NF-code are ordered so that Na 1 ≤ Na 2 ≤ . . . ≤ Na n .

Let C = C K be an NF-code with parameters (n, a 1 , . . . , a n ; M, s). To each ideal

a i , 1 ≤ i ≤ n, an indicator function χ i : O K → {0, 1} is assigned such that χ i (x) = 1 if and only if x ∈ a i .
Then the minimum (Hamming) distance of C, denoted d(C), is defined to be the minimum of the sum n i=1 (1 -χ i (x -y)) over all pairs of distinct elements x, y ∈ M C . To obtain a lower bound on d(C), consider distinct elements x, y ∈ M C . Then, on one hand,

n i=1 Na χi(x-y) i ≤ |N K (x -y)| ≤ 1 d d size(x -y) d ,
where the final inequality follows from the observation that |N K (z)| ≤ (size(z)/d) d for all z ∈ K, which is obtained by applying the inequality of arithmetic and geometric means (AM-GM). On the other hand, it is readily verified that size(x -y) ≤ size s (x) + size s (y) ≤ 2M.

On combining the inequalities it follows that

n i=1 Na χi(x-y) i ≤ (2M/d) d . (2.1)
Consequently, as x and y were arbitrary distinct elements of M C , the lower bound [39, Section II]). Guruswami [12, Section E] notes that a standard argument from the geometry of numbers suggests that

d(C) ≥ n -k holds for any value of k ≤ n such that (2M/d) d ≤ k i=1 Na i . The rate of an NF-code C = C K with parameters (n, a 1 , . . . , a n ; M, s) is de- fined to be the quotient R(C) = log |M C |/ n i=1 log Na i (see
|M C | ≈ (2 r1 π r2 M d )/(d! |D K |).
However, this estimate cannot be used in general, since the error term may dominate. Instead, Guruswami [START_REF] Guruswami | Constructions of codes from number fields[END_REF]Proposition 19] uses an averaging argument due to Lenstra [START_REF] Lenstra | Codes from algebraic number fields[END_REF] to prove the existence of a shift

s ∈ R r1 × C r2 such that {x ∈ O K | size s (x) ≤ M } ≥ 2 r1 π r2 |D K | M d d! . (2.2)
For any such shift s, an NF-code C = C K with parameters (n, a 1 , . . . , a n ; M ; s) has rate R(C) satisfying

R(C) ≥ log(2 r1 π r2 M d ) -log d! -log |D K | n log Na n .
The existence proof is nonconstructive, and it remains an open problem as to how to find a vector s satisfying (2.2).

A combinatorial result on list decoding

For a list decoding algorithm to run in polynomial time, it is necessary that the algorithm only returns polynomially many codewords. The classical Johnson bound [START_REF] Johnson | A new upper bound for error-correcting codes[END_REF][START_REF] Johnson | Improved asymptotic bounds for error-correcting codes[END_REF] provides an upper bound on the number of codewords in a binary code at Hamming distance exactly e from an arbitrary word. This bound was later generalised by Guruswami and Sudan [START_REF] Guruswami | Extensions to the Johnson bound[END_REF] who derived a "Johnson-type" bound for the number of codewords at distance at most e from an arbitrary word in a q-ary code. In addition, Guruswami and Sudan extended their result to provide bounds on the number of codewords with sufficiently large weighted agreement. The following combinatorial result due to Guruswami [START_REF] Guruswami | List decoding of error-correcting codes[END_REF]Theorem 7.10] provides an analogous bound, which may be applied to polyalphabetic codes such as NF-codes:

Theorem 3.
β i ≥ n i=1 α i -1 - 1 d(Σ) α n i=1 β 2 i α i .
Theorem 3.1 is now used to derived a condition under which decoding of NFcodes is combinatorially feasible. In Section 8, the condition is used to evaluate the performance of the algorithm for decoding of NF-codes developed in Section 5.

Corollary 3.1 Let C be an NF-code based on a number field K with parameters (n, a 1 , . . . , a n ; M, s) such that M > d/2, and β 1 , . . . , β n be positive real numbers. Then given a vector (r 1 +a 1 , . . . , r n +a n ) ∈ O K /a 1 ו • •×O K /a n and any tolerance parameter ε > 0, there are at most polynomially many (in 1/ε and

n i=1 log Na i ) elements m ∈ M C such that n i=1 χ i (m -r i )β i ≥ d log(2M/d) n i=1 β 2 i log Na i + ε max 1≤i≤n β 2 i log 2 Na i . (3.1) Proof Define = 1 ε n i=1 log Na i d log(2M/d) -1 n i=1 log Na i .
If < 1, then an application of the Cauchy-Schwarz inequality shows that the right hand side of (3.1) is greater than n i=1 β i and thus (3.1) is never satisfied. Therefore, assume that ≥ 1. Then it is sufficient to show that there exist at most elements m ∈ M C such that (3.1) holds.

Define Σ i = O K /a i , α i = log Na i and t i = r i + a i , for 1 ≤ i ≤ n. Then applying Theorem 3.1 with Σ = C implies that there exist at most elements m ∈ M C such that

n i=1 χ i (m -r i )β i ≥ n i=1 log Na i -1 - 1 d(C) α n i=1 β 2 i log Na i , (3.2)
where d(C) α is the minimum value of the sum n i=1 (1 -χ i (x -y)) α i over all pairs of distinct elements x, y ∈ M C . As the inequality (2.1) holds for any pair of distinct elements x, y ∈ M C , it follows that

d(C) α ≥ n i=1 log Na i -d log(2M/d).
This lower bound and the assumption that ≥ 1 imply that the right had side of (3.2) is less than or equal to the right hand side of (3.1). Therefore, any element m ∈ M C that satisfies (3.1) must also satisfy (3.2). Hence, there are at most elements m ∈ M C such that (3.1) holds.

Algorithmic preliminaries

In this section, mathematical concepts and procedures which are used in the development of the weighted list decoding algorithm are summarised. These include lattices and reduced bases (Section 4.1), and methods for computing products of algebraic integers and ideals in a number field (Section 4.2). First, some notation is introduced.

For a matrix or vector (a i,j ) ∈ C n×m , define norms (a i,j ) 2 = ( i,j |a i,j | 2 ) 1/2 and (a i,j ) ∞ = max i,j |a i,j |. For f ∈ C[x], define f p , for p = 2, ∞, to be the respective vector norms of the corresponding (1 + deg f )-dimensional vector having the coefficients of the polynomial as coordinates. Denote by x := x + 1/2 the integer nearest to x ∈ R.

Generalities on lattices

A lattice is a pair (L, q), where L is a free Z-module of finite rank and q is a positive definite quadratic form on L ⊗ R. If q is clear from the context, then L is referred to as a lattice. In the following, if (L, q) is a lattice, then b denotes the symmetric bilinear form on L × L defined by b(x, y) = (q(x + y) -q(x) -q(y)) /2. A lattice is called integral if b(x, y) ∈ Z, for all x, y ∈ L.

There are two important numerical invariants associated with a lattice (L, q): its rank and determinant. The rank (or dimension) of (L, q) is simply the rank of L as a free Z-module. If (b i ) 1≤i≤n is an integral basis of L, then the determinant of (L, q) is defined to be det(L, q) = (det Q) 1/2 , where Q = (b(b i , b j )) 1≤i,j≤n is a symmetric positive definite matrix called the Gram matrix of the basis. If (b i ) 1≤i≤n is another basis of L, then there exists a unimodular matrix (u i,j ) 1≤i,j≤n ∈ Z n×n such that b i = n j=1 u i,j b j . The Gram matrix of (b i ) 1≤i≤n is then U QU t . It follows that det(L, q) is independent of the choice of basis. If (b * i ) 1≤i≤n is the result of applying Gram-Schmidt orthogonalisation to

(b i ) 1≤i≤n , then det(L, q) = n i=1 q(b * i ) 1/2 . A sublattice of (L, q) is a lattice (M, q) such that M is a subgroup of L. If M is a finite index subgroup of L, then the determinant of (M, q) is det(M, q) = [L : M ] • det(L, q).
A nonzero element y ∈ L with q(y) approximating the minimum of q(x) over all nonzero x ∈ L, denoted λ(L, q), may be found by computing an LLL-reduced basis: Theorem 4.1 Let (b i ) 1≤i≤n be an LLL-reduced basis of a rank n lattice (L, q) and (b * i ) 1≤i≤n be the associated orthogonalised Gram-Schmidt basis. Then 1. q(b 1 ) ≤ 2 n-1 λ(L, q); 2. q(b 1 ) ≤ 2 (n-1)/2 det(L, q) 2/n ;

3. q(b i ) ≤ 2 i-1 q(b * i ), for 1 ≤ i ≤ n; and 4. µ i,j := b(b i , b * j )/b(b * j , b * j ) satisfies |µ i,j | ≤ 1/2, for 1 ≤ j < i ≤ n.
Proofs of properties 1-3 of Theorem

= (a i,j ) ∈ Z n×n is in HNF if A is upper triangular; a i,i > 0, for 1 ≤ i ≤ n; and 0 ≤ a i,j < a i,i , for 1 ≤ i < j ≤ n.
In the following, it is assumed that the HNF computation of a matrix A ∈ Z m×n is performed with the algorithm of Storjohann [START_REF] Storjohann | Algorithms for matrix canonical forms[END_REF]Chapter 6] in

Õ mnr 2 log A ∞ + mnM (r log A ∞ )
bit operations, where r is the rank of A and Õ is the "soft-O" notation, which ignores polylogarithmic factors.

Let ω 1 , . . . , ω d be an integral basis of O K . Then computing the coefficients of the product xy, for x, y ∈ O K , with respect to ω 1 , . . . , ω d reduces by linearity to computing the coefficients of each of the products ω i ω j . For

1 ≤ i, j, k ≤ d, define m i,j,k ∈ Z such that ω i ω j = d k=1 m i,j,k ω k . Then (m i,j,k ) 1≤i,j,k≤d is called the multiplication table of
O d 3 M B + log d + log (m i,j,k ) ∞ bit operations, where (m i,j,k ) ∞ := max 1≤i,j,k≤d |m i,j,k |.
In situations where it is necessary to compute several products involving an element x ∈ O K , it may be more efficient to compute the matrix M x representing multiplication by x:

if x = d k=1 x k ω k for integers x 1 , . . . , x d , then M x = (M k,j ) 1≤k,j≤d , where M k,j = d i=1 x i m i,j,k , for 1 ≤ k, j ≤ d. If y = d k=1 y k ω k and xy = d k=1 z k ω k for integers y 1 , . . . , y d and z 1 , . . . , z d , then the column vectors y = (y 1 , . . . , y d ) and z = (z 1 , . . . , z d ) satisfy z = M x y. Therefore, if the coeffi- cients x k and y k are B-bit integers for 1 ≤ k ≤ d, then the matrix M x is computed in O d 3 M B + log d + log (m i,j,k ) ∞ bit
operations and the product xy (i.e., the vector

M x y) in O d 2 M B + log d + log (m i,j,k ) ∞ bit operations.
There are two commonly used representations of an integral ideal a ⊆ O K . The first, is by a matrix A = (a i,j ) ∈ Z d×d such that the elements d i=1 a i,j ω i ∈ O K , for 1 ≤ j ≤ n, form an integral basis for a. If A is in HNF, then A is unique and called the HNF of a with respect to the basis ω 1 , . . . , ω d . The second representation, is by generators α, β ∈ O K such that a = (α, β), which always exists [START_REF] Cohen | A course in computational algebraic number theory[END_REF]Proposition 4.7.7] and is called a two-element representation. Given a two element representation a = (α, β), the HNF of a is computed as the HNF of the matrix (M α | M β ) ∈ Z d×2d . Using a matrix representation to compute a two-element representation is more difficult, and is not considered here (instead, see [START_REF] Belabas | Topics in computational algebraic number theory[END_REF]Section 6.3]).

If nonzero integral ideals a, a ⊆ O K are given by HNF matrices A, A ∈ Z d×d respectively, then their product aa is computed as follows: let α 1 , . . . , α d ∈ O K (resp. α 1 , . . . , α d ∈ O K ) be the integral basis described by A (resp. A ), then compute the HNF of the d × d 2 matrix whose column vectors are the coordinate vectors of the products

α i α j , for 1 ≤ i, j, ≤ d. If A ∞ and A ∞ are B-bit integers, then the d 2 products α i α j are computed in O d 5 M B + log d + log (m i,j,k ) ∞ bit
operations and the HNF computation performs

Õ d 5 2B + log (m i,j,k ) ∞ + d 3 M d 2B + log (m i,j,k ) ∞
bit operations. As the matrix A is in HNF, the product of its diagonal elements (i.e., the determinant of A) is equal to [O K : a] = Na (see [START_REF] Cohen | A course in computational algebraic number theory[END_REF]Proposition 4.7.4]). It follows that A ∞ ≤ Na and, similarly, that A ∞ ≤ Na . Hence, the HNF of the product aa is computed in O(poly(d, log Na, log Na , log (m i,j,k ) ∞ )) bit operations.

Weighted list decoding of NF-codes

In this section, a weighted list decoding algorithm for NF-codes is developed. For an NF-code C = C K with parameters (n, a 1 , . . . , a n ; M, s), weighted list decoding reduces to the following problem: given a vector (r 1 + a 1 , . . . , r n + a n ) ∈ O K /a 1 × . . . × O K /a n , called a received word, positive real weights β 1 , . . . , β n and a real number t ≥ 0, find all m ∈ M C such that n i=1 χ i (m -r i )β i ≥ t. List decoding is captured by the special case in which the weights are equal. Currently, no method is known for determining shift parameters s ∈ R r1 × C r2 such that (2.2) holds. Consequently, attention is limited in this section to decoding with the shift s = 0.

The decoding algorithm's development is based on implementing the unified framework for list decoding of algebraic error-correcting codes of Guruswami, Sahai and Sudan [14, Appendix A], specialised for NF-codes. A full description and analysis of the framework for list decoding of algebraic error-correcting codes is provided by Guruswami [START_REF] Guruswami | List decoding of error-correcting codes[END_REF]Section 7]. At a high level, the framework suggests the following approach to decoding when given an NF-code C = C K with parameters (n, a 1 , . . . , a n ; M, 0), weights β 1 , . . . , β n and a received word (r 1 +a 1 , . . . , r n +a n ):

1. Define ideals A 1 , . . . , A n ⊆ O K [x]
as follows:

A i = (x -r i )O K [x] + a i O K [x], for 1 ≤ i ≤ n.
To each ideal A i , assign a positive integer parameter z i , for 1 ≤ i ≤ n.

Find a nonzero polynomial h ∈

n i=1 A zi
i of degree at most and with small coefficients.

3. Find the roots of h over K, and return all roots m ∈ M C such that the sum n i=1 χ i (m -r i )β i is sufficiently large. The definition of the ideals A 1 , . . . , A n and the Chinese remainder theorem imply that any polynomial h ∈

n i=1 A zi i satisfies h(m) ∈ n i=1 a χi(m-ri)zi i
, for all m ∈ O K . The requirement that h has "small coefficients" is used to guarantee that all m ∈ M C for which n i=1 Na χi(m-ri)zi i is sufficiently large are not only modular roots of h but are also roots of h over K. Thus, all such m ∈ M C are found in the root finding step. For K = Q, repeating arguments of Howgrave-Graham [19, Section 2] provides the following sufficient condition for the modular root to additionally be an integer root:

if m ∈ M C and a polynomial h ∈ n i=1 A zi i of degree at most satisfy n i=1 Na χi(m-ri)zi i > √ + 1 • h(xM ) 2 , (5.1)
then h(m) = 0. Thus, in the special case where K = Q, the result of Howgrave-Graham provides motivation for the following notion of a polynomial h ∈ n i=1 A zi i with small coefficients: h has small coefficients whenever h(xM ) 2 is small. This notion of size is used by Guruswami et al. in their weighted list decoding algorithm for CRT codes, where a lattice-based approach is used to find a small polynomial. To obtain a decoding algorithm for NF-codes based on fields other than Q, the result of Howgrave-Graham and the lattice-based approach to finding a small polynomial are generalised to arbitrary number fields. The ring of integer O K carries a natural lattice structure defined by the positive definite quadratic form

T 2 (x) := Tr K R /R (xx) on the R-algebra K R := K ⊗ Q R,
where Tr K R /R denotes the trace of K R and ¯: K R → K R is the involution induced by complex conjugation. For x ∈ K, the quadratic form is given explicitly by the sum

T 2 (x) = d i=1 |σ i (x)| 2 . Consequently, the determinant det(O K , T 2 ) = |D K |.
Define the norm associated with T 2 by x = T 2 (x), for all x ∈ K R . For polynomials in O K [x], the following lemma provides a sufficient condition for a modular root to also be a root over K, which, in addition, provides a notion of a polynomial with "small coefficients" which is compatible with a lattice-based approach:

Lemma 5.1 Let K be a degree d number field, h = i=0 h i x i ∈ O K [x]
be a polynomial of degree at most , a be a nonzero ideal of O K and M be a positive real number. Suppose that 1. h(m) ∈ a, for some m ∈ O K with size(m) ≤ M ; and

2. i=0 T 2 (h i )M 2i 1/2 < d (Na) 1/d / √ + 1.
Then h(m) = 0 over K.

Proof Applying the AM-GM inequality yields

|N K (h(m))| 1/d ≤ 1 d size (h(m)) ≤ 1 d i=0 size h i m i .
Furthermore, applying the Cauchy-Schwarz inequality shows that

size(h i m i ) ≤ T 2 (h i ) • T 2 (m i ) ≤ T 2 (h i ) • T 2 (m) i ≤ T 2 (h i ) • size(m) i , for 0 ≤ i ≤ . Thus, |N K (h(m))| ≤ 1 d d ( + 1) • i=0 T 2 (h i )M 2i d 2 < Na. However, Na divides N K (h(m)), since h(m) ∈ a. Therefore, if h(m) = 0, then Na ≤ |N K (h(m))| < Na, which is absurd. Hence, h(m) = 0 over K.
Lemma 5.1 provides a natural generalisation of condition (5.1): the lemma implies that a polynomial h ∈ n i=1 A zi i of degree at most will have amongst its roots all m ∈ M C such that

n i=1 Na χi(m-ri)zi i > 1 d • √ + 1 • h 2,M d , (5.2)
where i a i x i 2,M := i T 2 (a i )M 2i 1/2 , for all i a i x i ∈ K[x]
and any positive real number M . Based on this observation, a polynomial h ∈ O K is said to have small coefficients whenever h 2,M is small. With this notion of size, there are three main tasks that arise from the approach to decoding of NF-codes suggested by the general framework: the first, is the selection of the parameters z 1 , . . . , z n and ; the second, is to find a nonzero polynomial h ∈ n i=1 A zi i of degree at most such that h 2,M is small; and the third, is to determine the roots of h in M C . Selection of the parameters z 1 , . . . , z n and is considered in Section 8, with the parameters considered as free in the meantime. For the third task, one of several efficient algorithms for factoring polynomials over number fields may be applied (see [START_REF] Lenstra | Factoring polynomials over algebraic number fields[END_REF][START_REF] Landau | Factoring polynomials over algebraic number fields[END_REF] and references therein). However, a specialised algorithm is developed in Section 6, which is used to establish the complexity of the decoding algorithm. For the second task, as suggested above, a lattice-based approach is employed.

For nonnegative

∈ Z, let O K [x] O +1 K (resp. A ) denote the free Z-module of polynomials of degree at most in O K [x] (resp. n i=1 A zi i ). Then O K [x]
together with the quadratic form . 2 2,M forms a lattice. Thus, a polynomial h ∈ A with small coefficients is found by computing an LLL-reduced basis of the sublattice (A , .

2 2,M ). However, the Gram matrix of the sublattice does not contain integral entries in general. As more is known about the complexity of the LLL-algorithm for integral lattices, an approach of Belabas [2, Section 4.2], which uses integral reduction to produce a (not necessarily LLL-reduced) basis containing a short vector, is used in the decoding algorithm.

Let ω 1 , . . . , ω d be an integral basis of O K and R t R be the Cholesky decomposition of the corresponding Gram matrix of the lattice

(O K , T 2 ). Then R = diag( ω * 1 , . . . , ω * d ) • (µ j,i ) 1≤i,j≤d ,
where µ i,j is defined as in Theorem 4.1, for 1 ≤ j < i ≤ d; µ i,i := 1, for 1 ≤ i ≤ d; and µ i,j := 0, for

1 ≤ i < j ≤ d. If x = d i=1 x i ω i ∈ K[x] is represented by the column vector δ(x) := (x 1 , . . . , x d ) ∈ Q d , then T 2 (x) = Rδ(x) 2 2 . Belabas [2, Section 4.2] observes that for e ∈ Z such that 2 e • min 1≤i≤d ω * i > 1/2, (5.3)
the matrix R e := 2 e R has maximal rank and R e δ(x)

2 2 provides a "convenient" integral approximation to 2 2e T 2 (x), which may be substituted for T 2 whenever reduction is performed on a sublattice of (O K , T 2 ). If the integral basis is LLL-reduced, then property 3 of Theorem 4.1 and the observation that λ(O K , T 2 ) = d imply that

ρ := min 1≤i≤d ω * i ≥ min 1≤i≤d 2 (1-i)/2 ω i ≥ 2 (1-d)/2 √ d, (5.4)
so that e need only satisfy e > (d -3 -log d)/2. This idea extended for use in the decoding algorithm by defining the block diagonal matrix R e, ,M := diag 2 e R , 2 e M R , . . . ,

2 e M R ∈ Z d( +1)×d( +1) ,
for nonnegative ∈ Z, nonnegative e ∈ Z such that (5.3) holds, and real M ≥ 1.

To each polynomial a = i=0 a i x i ∈ O K [x] , assign the column vector δ (a) ∈ Z d( +1) , which is viewed as having + 1 blocks, with the ith block equal to δ(a i-1 ).

Then R e, ,M δ (a) In order to perform lattice reduction, an initial basis of A is required. To address this problem for CRT codes (i.e., for K = Q), Guruswami et al. begin by computing a basis (provided by [14, Lemma 2]) for the free Z-module of polynomials of degree at most in A zi i , for 1 ≤ i ≤ n. Then a general method for computing the intersection of two real full-rank lattices [14, Appendix B] is used to compute a basis of the lattice δ (A ). Applying this approach to general number fields requires performing operations on potentially large matrices: computing the intersection requires 2(n -1) inversions of d( + 1) × d( + 1) upper triangular matrices and n -1 Hermite normal form computations of d( + 1) × 2d( + 1) matrices. The following lemma provides an explicit basis of A and a means to circumvent operations on large matrices: Lemma 5.2 With notation as above, let α j,1 , . . . , α j,d ∈ O K be an integral basis of the ideal

n i=1 a max{zi-j,0} i , for 0 ≤ j ≤ . Suppose that r ∈ O K satisfies r -r i ∈ a i , for 1 ≤ i ≤ n.
(Such an element exists by the Chinese remainder theorem.) Then the polynomials

u dj+k (x) = x max{0,j-zmax} α j,k (x -r) min{j,zmax} , for 0 ≤ j ≤ , 1 ≤ k ≤ d,
where z max = max 1≤i≤n z i , form an integral basis of A .

Proof Each polynomial h ∈ O K [x] may be expressed in the form

h(x) = h zmax (x) • (x -r) zmax + zmax-1 j=0 h j (x -r) j , (5.5
)

such that h 0 , . . . , h zmax-1 ∈ O K and h zmax ∈ O K [x]
. The coefficients h 0 , . . . , h zmax are then uniquely determined. From the definition of r, it follows that

A i = ((x -r) + (r -r i )) O K [x] + a i O K [x] = (x -r)O K [x] + a i O K [x],
for

1 ≤ i ≤ n. Therefore, if h ∈ O K [x]
, when expressed in the form (5.5), has coefficients satisfying

h j ∈ n i=1 a max{zi-j,0} i
, for 0 ≤ j < z max , then h ∈ A since the ideals a 1 , . . . , a n are pairwise comaximal. In particular, the polynomials u 1 , . . . , u d( +1) ∈ A . It is shown that the converse also holds. Then it is clear that any polynomial h ∈ A may be expressed as a Z-linear combination of the polynomials u 1 , . . . , u d( +1) . Linear independence of the polynomials follows from that of the bases (α j,k ) 1≤k≤d , for 0 ≤ j ≤ . Therefore, if the converse holds, then the polynomials u 1 , . . . , u d( +1) form an integral basis of A .

To prove the converse, assume now that h ∈ A . Then h may be expressed in the form (5.5) and, since h ∈ A z1

1 , may also be expressed in the form

h(x) = λ zmax (x) • (x -r) zmax + zmax-1 j=0 λ j (x) • a j (x -r) j ,
where a j ∈ a max{z1-j,0} 1

, for 0 ≤ j < z max , and λ 0 , . . . ,

λ zmax ∈ O K [x]. Moreover, since (x -r) • a j (x -r) j = a j • (x -r) j+1 and a max{z1-j,0} 1 ⊆ a max{z1-j-1,0} 1
, for 0 ≤ j < z max , it is assumed that λ 0 , . . . , λ zmax-1 ∈ O K . However, uniqueness of the coefficients h 0 , . . . , h zmax then implies that h j = λ j a j ∈ a max{z1-j,0} 1

, for 0 ≤ j < z max . Repeating this argument for i = 2, . . . , n, shows that

h j ∈ n i=1 a max{zi-j,0} i = n i=1 a max{zi-j,0} i , for 0 ≤ j < z max .
Hence, the converse holds. Lemma 5.2 permits an integral basis for A to be computed with operations performed on matrices which have dimensions dependent on d and not on . The resulting CRT problem may be solved by means of the polynomial time extended Euclidean algorithm for number fields of Cohen [5, Algorithm 1.3.2, Proposition 1.3.7], or the improved variant of Belabas [2, Algorithm 5.4]. In particular, the CRT problem may be solved by the method described by Belabas [2, Algorithm 6.10], which is used with minor modifications in the decoding algorithm.

Based on the above discussion, the following algorithm is proposed for weighted list decoding of NF-codes: Algorithm 5.1 (Weighted List Decoding of NF-codes) INPUT: A code C based on a number field K with parameters (n, a 1 , . . . , a n ; M, 0) such that M ≥ 1 and the ideal a i is provided by its HNF A i ∈ Z d×d , for 1 ≤ i ≤ n; a vector (r 1 , . . . , r n ) ∈ O n K such that δ(r i ) ∞ ≤ Na i , for 1 ≤ i ≤ n; an LLLreduced basis ω 1 , . . . , ω d of the lattice (O K , T 2 ) such that ω 1 = 1, the corresponding multiplication table (m i,j,k ) 1≤i,j,k≤d and Cholesky factor R; a nonnegative integer e that satisfies (5.3); and positive integers t, z 1 , . . . , z n and . OUTPUT: A set containing elements m ∈ O K such that size(m) ≤ M + 2 -t .

1. [Solve the CRT problem] Set r = 0. For j = 1, . . . , n, construct an element r ∈ O K such that r -r i ∈ a i , for 1 ≤ i ≤ j, by performing the following steps: (a) Use the methods discussed in Section 4.2 to compute the HNF B j ∈ Z d×d of the ideal b j := i =j a i . (b) Use the extended gcd algorithm for number fields [2, Algorithm 5.4] to find an element β j ∈ b j such that 1 -β j ∈ a j . (c) Set r ← r + r j β j (mod a) such that δ(r) ∞ < a, where a is the positive generator of ( n i=1 a i ) ∩ Z. (Note that a is computed as the lcm of the upper left most entries of A 1 and B 1 , since ω 1 = 1.) 2. Define z max = max 1≤i≤n z i . For j = min{z max , }, . . . , 0, use the methods discussed in Section 4.2 to compute the HNF

V j ∈ Z d×d of n i=1 a max{zi-j,0} i . (Note that V zmax = I d .) 3.
[Compute an integral basis of A ] Let M r ∈ Z d×d be the matrix representing multiplication by r and a z be the upper left most entry of V 0 . Compute the d( + 1) × d( + 1) block matrix U := (U s,t ) 1≤s,t≤ +1 , with blocks U s,t ∈ Z d×d such that U s,t ∞ ≤ n i=1 Na zi i , defined as follows:

U m+1,j+1 =      (-1) j-m j m M j-m r V j (mod a z ) if m < j, V j if m = j, 0 if m > j,
for 0 ≤ m ≤ , 0 ≤ j ≤ min{z max , }; and, if > z max , [START_REF] Nguyen | An LLL algorithm with quadratic complexity[END_REF] to find an LLL-reduced basis b 1 , . . . , b d( +1) of the lattice (Λ, .

U m+1,j+1 = 0 if m < j -z max or m > j, U m-j+zmax+1,zmax+1 if j -z max ≤ m ≤ j, for 0 ≤ m ≤ , z max < j ≤ . 4. [Perform lattice reduction] Compute Q := R e, ,M U . Use the L 2 algorithm
2 ) with basis given by the column vectors of Q.

[Compute roots of h] Compute

h := δ -1 ((R e, ,M ) -1 b 1 ). If h is constant,
= m + y if m ∈ M C .
6 The root finding sub-algorithm

In this section, the sub-algorithm used in Step 5 of Algorithm 5.1 to determine the roots of the polynomial h is described. As noted in Section 5, the computation of the roots of h can be performed by applying existing algorithms for factoring over number fields. However, the full factorisation of h is not required in the context of Algorithm 5.1 and only those roots of h in M C are of interest. By specialising existing algorithms, namely those based on the norm-based approach proposed by Kronecker [START_REF] Kronecker | Grundzüge einer arithmetischen Theorie der algebraischen Grössen[END_REF] (see also [START_REF] Landau | Factoring polynomials over algebraic number fields[END_REF][START_REF] Edwards | Galois theory[END_REF] and references therein), this problem is addressed more efficiently. Moreover, the specialised algorithm is designed to exploit the fact that h belongs to the special subring

O K [x] of K[x] and that an integral basis of O K is known. For a polynomial f ∈ K[x], define M f = (m i,j ) 1≤i,j≤d by f ω j = d i=1 m i,j ω i , for 1 ≤ j ≤ d. The norm of f ∈ K[x]
is then defined to be the determinant N K (f ) := det M f . When f ∈ O K , this definition is consistent with the previous definition from Section 4.2. For all f, g ∈ K[x], the definition of matrix multiplication implies that M f g = M f M g . Consequently, the norm map is multiplicative.

It follows immediately that if a ∈ K is a root of f ∈ K[x], then N K (x -a) divides N K (f ) in Q[x]. If φ a (x) ∈ Q[x] denotes the minimal polynomial of a ∈ K, then N K (x -a) = det(xI d -M a ) = φ a (x) [K:Q(a)] .
Therefore, the minimal polynomial of any root of f

∈ K[x] is an irreducible factor of N K (f ) in Q[x].
To determine the roots of the polynomial h in Step 5 of Algorithm 5.1, the norm

N K (h) ∈ Z[x] is factored into irreducible factors in Z[x]
, then the roots (in C) of each monic irreducible factor of degree at most d are computed. Amongst the roots are all roots of h in M C . The norm N K (h) can be computed using the modular evaluation-interpolation approach of McClellan [START_REF] Mcclellan | The exact solution of systems of linear equations with polynomial coefficients[END_REF] (see also [START_REF] Horowitz | On computing the exact determinant of matrices with polynomial entries[END_REF]). The following lemma provides an alternative method for computing the norm, which is used to establish the polynomial bit complexity of the root finding sub-algorithm: h λ M h ), and thus N K (h), are precisely the eigenvalues of the matrix N K (h λ ) -1 C, where C is the dλ × dλ block matrix

Lemma 6.1 Suppose that the polynomial h ∈ O K [x] from Step 5 of Algorithm 5.1 is non-constant. Then N K (h) is computed in O(poly(d, log |D K |, , log h 2,M )) bit operations. Furthermore, log N K (h) ∞ is O(poly(d, log |D K |, , log h 2,M )). Proof Suppose that h = λ k=0 h k x k is non-constant, with h 0 , . . . , h λ ∈ O K and h λ = 0. Then the matrix M h = λ k=0 M h k x k , where det M h λ = N K (h λ ) is nonzero. Thus, N K (h)
C = N K (h λ ) •        0 I d 0 . . . 0 0 0 I d . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . I d -M -1 h λ M h0 -M -1 h λ M h1 -M -1 h λ M h2 . . . -M -1 h λ M h λ-1        . Let χ C (x) denote the characteristic polynomial of C. Then the characteristic polyno- mial of the matrix N K (h λ ) -1 C is χ C (N K (h λ )x)•N K (h λ ) -dλ . Therefore, the roots of N K (h) coincide with the roots of the polynomial χ C (N K (h λ )x) • N K (h λ ) 1-dλ .
However, the leading coefficient of the latter polynomial is equal to N K (h λ ) and

N K (h)(x) = N K (h λ )
x dλ + terms of degree less than dλ.

Hence, the two polynomials are in fact equal.

The matrix C has integer entries, thus its characteristic polynomial χ C is computed in O(poly(d, λ, log C ∞ )) bit operations (see [START_REF] Dumas | Efficient computation of the characteristic polynomial[END_REF] and references therein). Applying the AM-GM inequality provides the bound

|N K (h λ )| ≤ d -d/2 T 2 (h λ ) d/2 ≤ d -d/2 h d 2,M . (6.1)
The Cauchy-Schwarz inequality and the bound on the norm of the adjoint matrix obtained by Richter [START_REF] Richter | Bemerkung zur Norm der Inversen einer Matrix[END_REF] imply that Proposition 5.1] provides the following "pessimistic" bound on the entires of the multiplication table (m i,j,k ) 1≤i,j,k≤d :

M adj h λ M h k ∞ ≤ M adj h λ 2 M h k 2 ≤ d -(d-2)/2 M h λ d-1 2 M h k 2 , (6.2) for 0 ≤ k < λ, where M adj h λ = N K (h λ )M -1 h λ is the adjoint matrix of M h λ . Finally, since ω 1 , . . . , ω d is an LLL-reduced basis for (O K , T 2 ), Belabas [2,
|m i,j,k | ≤ 2 3d(d-1)/4 d (1-2d)/2 |D K | , for 1 ≤ i, j, k ≤ d. (6.3)
Therefore, combining (6.1), (6.2) and ( 6.3) implies that the matrix C, its characteristic polynomial χ C and N K (h) are each computed in

O poly d, log |D K |, , log h 2,M , log max 0≤k≤λ δ(h k ) ∞ bit operations. The coefficients of N K (h) satisfy N K (h) ∞ ≤ |N K (h λ )| • χ C ∞ ≤ |N K (h λ )| • max 0≤k≤dλ dλ k k k/2 C k ∞ ,
where the final inequality is obtained by applying a bound of Cohen [4, Proposition 2.2.10]. It follows that log

N K (h) ∞ is O poly d, log |D K |, , log h 2,M , log max 0≤k≤λ δ(h k ) ∞
Arguments due to Belabas [2, p. 28] are now used to establish the following claim:

δ(a) 2 ≤ 2 (1-d)/2 d d+1/2 a , for all a ∈ O K . (6.4)
Given the claim, it follows that

δ(h k ) ∞ ≤ δ(h k ) 2 ≤ 2 (1-d)/2 d d+1/2 h k ≤ 2 (1-d)/2 d d+1/2 h 2,M , (6.5)
for 0 ≤ k ≤ λ, thus completing the proof of the lemma. An application of the Cauchy-Schwarz inequality shows that

δ(a) 2 ≤ R -1 2 Rδ(a) 2 = R -1 2 a , for all a ∈ O K . (6.6) Write R = D + N , where D = diag( ω * 1 , . . . , ω * d ) and N is upper triangular nilpotent. Setting Z = D -1 N , it follows that R -1 = (I d + Z) -1 D -1 = d-1 i=0 (-1) i-1 Z i D -1 .
A nonzero entry of Z is a Gram-Schmidt coefficient µ i,j , such that j < i, of the reduced basis ω 1 , . . . , ω d . Therefore, property 4 of Theorem 4.1 implies that Z ∞ ≤ 1/2. Consequently,

R -1 2 ≤ d R -1 ∞ ≤ d ρ d-1 i=0 Z i ∞ ≤ d ρ d-1 i=0 d i Z i ∞ ≤ d d+1 2 d-1 ρ , (6.7)
where ρ = min 1≤i≤d ω * i . Combining (6.6) and (6.7) with the lower bound (5.4) then completes the proof of (6.4).

The norm N

K (h) ∈ Z[x] is factored into irreducible factors in Z[x]
by the algorithm of Lenstra, Lenstra and Lovász [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] in O(poly(deg N K (h), log N K (h) ∞ )) bit operations. The roots of the irreducible factors are computed, with guaranteed error terms, by the polynomial time algorithm of Pan [START_REF] Pan | Sequential and parallel complexity of approximate evaluation of polynomial zeros[END_REF]: Theorem 6.1 Let φ ∈ Z[x] be a degree d polynomial with roots α 1 , . . . , α d ∈ C and t be a positive integer. Then O(poly(d, t, log φ ∞ )) bit operations are sufficient to find numbers ᾱ1 , . . . , ᾱd

∈ Q + iQ such that max 1≤i≤d |α i -ᾱi | ≤ 2 -t . If φ ∈ Z[x] is a monic irreducible factor of N K (h) such that deg φ ≤ d,
and a ∈ C is a root of φ, then there is no guarantee that a belongs to M C , much less that a is a root of h over K. If a ∈ M C and φ a ∈ Z[x] is its minimal polynomial, then

φ a ∞ ≤ max 0≤j≤deg φa deg φ a j M deg φa-j . Moreover, if φ a = deg φa j=1 (x -σ ij (a)), then size(a) = d deg φ a deg φa j=1 |σ ij (a)| ≤ M.
To determine if a ∈ C \ Z belongs to O K , the algorithm of Just [START_REF] Just | Integer relations among algebraic numbers[END_REF][START_REF] Just | Integer relations among algebraic numbers[END_REF] is used to find a nonzero vector (y 1 , . . . , y d , q) ∈ Z d+1 such that y 1 ω 1 + . . . + y d ω d = qa, or show that no such vector exists. If such a vector is found, then the linear independence of the integral basis implies that a ∈ O K if and only if (y 1 /q, . . . , y d /q) ∈ Z d . Moreover, if a ∈ O K , then δ(a) = (y 1 /q, . . . , y d /q). The algorithm of Just for determining an integer relation, or proving that one does not exist, has complexity summarised by the following theorem: Theorem 6.2 Let algebraic numbers α 1 , . . . , α n ∈ C be given by approximations ᾱ1 , . . . , ᾱn

∈ Q + iQ such that max 1≤i≤n |α i -ᾱi | ≤ 2 -t , for t = log 4n √ 2 • Y 1/n • max 1≤i≤n M (α i ) 1/[Q(αi):Q] n[Q(α1,...,αn):Q] ,
where Y > 1 and M (α i ) is the Mahler measure of α i , for

1 ≤ i ≤ n. Then O poly n, log Y, max 1≤i≤n log M (α i ), [Q(α 1 , . . . , α n ) : Q]
bit operations are sufficient to either find a nonzero integer vector y = (y 1 , . . . , y n ) such that y 2 ≤ 2 n/2 Y and n i=1 a i α i = 0, or prove that there is no nonzero integer vector x = (x 1 , . . . , x n ) such that x 2 ≤ Y and n i=1 x i α i = 0. The Mahler measure of an algebraic number α ∈ C, with minimal polynomial

φ α (x) = ϕ • (x -α 1 ) • • • (x -α n ) over Z, is defined to be the product M (α) = |ϕ| • n i=1 max {1, |α i |}. Mignotte [33, Theorem 1] showed that the Mahler measure of α satisfies M (α) ≤ φ α 2 . For a ∈ K, M (a) 1/[Q(a):Q] = d i=1 max{1, |σ i (a)|} 1/d ≤ 1 d n i=1 max {1, |α i |} ≤ a √ d + 1,
where the first inequality is obtained by applying the AM-GM inequality. Based on the above discussion, the following sub-algorithm is proposed for determining the roots of h in Step 5 of Algorithm 5.1: Sub-Algorithm 6.1 (Root finding step) 1. Use the method described in the proof of Lemma 6.1 to compute N K (h). 2. Use the algorithm of Lenstra, Lenstra and Lovász [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] to compute the set Φ of monic non-constant irreducible factors of

N K (h) in Z[x]. 3. Set R ← {δ(a) | (x -a) ∈ Φ, size(a) ≤ M and h(a) = 0 over K}. 4. For each polynomial φ ∈ Φ that satisfies 2 ≤ deg φ ≤ d and φ ∞ ≤ max 0≤j≤deg φ deg φ j M deg φ-j , (6.8)
perform the following steps: (a) Set

τ ← log 4(d + 1) √ 2 • Y 1/(d+1) • max X, φ 1/ deg φ 2 d 2 (d+1)
, where

Y = 2 1-d d 2d+1 M + 2 -t 2 + 1 1/2 and X = 1 + 1 √ d max 1≤i≤d ω i .
(b) Let a 1 , . . . , a deg φ ∈ C denote the roots of φ. Use the algorithm of Pan [START_REF] Pan | Sequential and parallel complexity of approximate evaluation of polynomial zeros[END_REF] to compute approximations ā1 , . . . ,

ādeg φ ∈ Q + iQ such that max 1≤j≤deg φ |a j -āj | ≤ min 2 -τ , (2 -(t+1) • deg φ)/d 2 .
(c) If the inequality

(d/ deg φ) • deg φ j=1 |ā j | ≤ M + 2 -(t+1) (6.9)
is satisfied, then perform the following steps for k = 1, . . . , deg φ: i. Use the algorithm of Just [START_REF] Just | Integer relations among algebraic numbers[END_REF] to search for a nonzero integer vector y = (y 1 , . . . , y d , q) such that y 2 ≤ 2 (d+1)/2 Y and d i=1 y i ω i = qa k . ii. If such a vector (y 1 , . . . , y d , q) ∈ Z d+1 is found and (y 1 /q, . . . , y d /q) has integral entries, then compute h(a k ) ∈ O K . If h(a k ) = 0 over K, then set R ← R ∪ {(y 1 /q, . . . , y d /q)}. 5. Return R. Lemma 6.2 The set R returned by Sub-Algorithm 6.1 contains the vector δ(m) for all roots m ∈ M C of h over K, plus finitely many vectors δ(a) such that a ∈ O K is a root of h (over K) and M < size(a) ≤ M + 2 -t . Moreover, the algorithm performs

O(poly(d, log |D K |, , log M, t, log h 2,M )) bit operations. Proof The minimal polynomial of any root of h in O K is a monic irreducible factor of N K (h) in Z[x]. Therefore, if a ∈ Z is a root of h over K, then it is clear from the construction of R that δ(a) ∈ R if and only if size(a) ≤ M . Moreover, if a ∈ O K \Z
is a root of h over K, then the minimal polynomial of a belongs to the set Φ.

Let φ ∈ Φ and a 1 , . . . , a deg φ be the roots of φ in C. Fix an index k such that 1 ≤ k ≤ deg φ. If a k ∈ M C , then the approximate roots ā1 , . . . , ādeg φ satisfy (6.9):

d deg φ deg φ j=1 |ā j | ≤ size(a k ) + d deg φ deg φ j=1 |a j -āj | ≤ M + 2 -(t+1) .
The converse may not hold. However, if a k ∈ O K and (6.9) is satisfied, then

size(a k ) ≤ M + 2 -(t+1) + d deg φ deg φ j=1 |a j -āj | ≤ M + 2 -t .
Consequently, (6.4) implies that

δ(a k ) 2 ≤ 2 (1-d)/2 d d+1/2 a k ≤ 2 (1-d)/2 d d+1/2 M + 2 -t .
Therefore, if the approximate roots ā1 , . . . , ādeg φ satisfy (6.9), then a k ∈ O K if and only if there exists a nonzero vector x = (x 1 , . . . , x d , -1) ∈ Z d+1 such that x 2 ≤ Y and

d i=1 x i ω i = a k . As [Q(ω 1 , . . . , ω d , a k ) : Q] ≤ d 2 , max 1≤i≤d M (ω i ) 1/[Q(ωi):Q] ≤ X and M (a k ) 1/[Q(a k ):Q] ≤ φ 1/ deg φ 2 ,
it follows from Theorem 6.2 that the algorithm of Just either proves such a vector x does not exist, or finds a nonzero vector (y 1 , . . . , y d , q) ∈ Z d+1 such that d i=1 y i ω i = qa k . In the latter case, a k ∈ O K if and only if (y 1 /q, . . . , y d /q) has integral entries. Moreover, if a k ∈ O K , then δ(a k ) = (y 1 /q, . . . , y d /q). Therefore, if the approximate roots ā1 , . . . , ādeg φ satisfy (6.9) and a k ∈ O K , then δ(a k ) is added to R if h(a k ) = 0 over K. Hence, if a k ∈ M C and h(a k ) = 0 over K, then δ(a k ) ∈ R. Furthermore, if a k ∈ O K and δ(a k ) ∈ R, then a k is a root of h over K, and size(a k ) ≤ M + 2 -t . The proof of the first assertion of the lemma is completed by noting that the cardinality of R is bounded by deg N K (h) ≤ d .

The factorisation of N K (h) is performed in O(poly(d, , log N K (h) ∞ )) bit operations. Consequently, it follows from Lemma 6.1 that Step 1 and Step 2 perform O(poly(d, log |D K |, , log h 2,M )) bit operations. The inequalities (6.3), (6.4) and (6.5) imply that the evaluation of h(a), for an element a ∈ O K such that size(a) ≤ M + 2 -t , performs O(poly(d, log |D K |, , log M, log h 2,M )) bit operations, using the methods described in Section 4.

Analysis of the decoding algorithm

In this section, the decoding performance and complexity of Algorithm 5.1 is evaluated. The following two lemmas are used to establish a bound on h 2,M , which, when combined with Lemma 5.1, determines the decoding performance of the algorithm:

Lemma 7.1 Let h ∈ O K [x] be the polynomial found in Step 5 of Algorithm 5.1. Then h 2,M ≤ 2 -e • 1 + d 2 d(d + 1) 2 2 e ρ - 1 2 -1
• R e,l,M δ (h) 2 ,

where ρ = min 1≤i≤d ω * i .

Proof Write h = j=0 h j x j , where h 0 , . . . , h ∈ O K . Define matrices E j = 2 e M j R -2 e M j R, for 0 ≤ j ≤ . Then

2 2e h 2 2,M = j=0 2 2e M 2j Rδ(h j ) 2 2 = j=0 2 e M j R -E j δ(h j ) 2 2 ≤ j=0 1 + E j 2 e M j R -1 2 2 2 e M j R δ(h j ) 2 2 , (7.1)
where the inequality is obtained by applying the Cauchy-Schwarz inequality to each term of the sum and 2 e M j R -1 exists, for 0 ≤ j ≤ , as a result of the inequalities M ≥ 1 and (5.3). The matrix E j 2 e M j R -1 is upper triangular and

E j ∞ ≤ 1/2,
for 0 ≤ j ≤ . Thus,

E j 2 e M j R -1 2 ≤ d 2 d(d + 1) 2 2 e M j R -1 ∞ , for 0 ≤ j ≤ . (7.2)
For each value of j, 0 ≤ j ≤ , if E j = ε (j) s,t 1≤s,t≤d , then

2 e M j R = 2 e M j R + E j = 2 e+1 M j • diag ( ω * 1 , . . . , ω * d ) • (I d + F j ) ,
where

F j := µ t,s 2 + ε (j) s,t 2 e+1 M j ω * s 1≤s,t≤d -I d .
For 0 ≤ j ≤ , the inequalities M ≥ 1 and (5.3) imply that

1 -F j ∞ ≥ 1 - 1 2 + 1 2 e+2 M j ρ ≥ 1 2 1 - 1 2 e+1 ρ > 0.
Therefore, [START_REF] Stoer | Introduction to numerical analysis[END_REF]Lemma 4.4.14]) and

(I d + F j ) -1 ∞ ≤ (1 -F j ∞ ) -1 (see
2 e M j R -1 ∞ ≤ 1 2 e+1 ρ 1 -F j ∞ ≤ 1 2 e ρ -1/2
, for 0 ≤ j ≤ . (7.3)

Hence, combining inequalities (7.1), (7.2) and ( 7.3) shows that

2 e h 2,M ≤ 1 + d 2 d(d + 1) 2 2 e ρ - 1 2 -1   j=0 2 e M j R δ(h j ) 2 2   1 2
, where the second factor on the right-hand side is equal to R e, ,M δ (h) 2 .

Lemma 7.2 The lattice (Λ, .

≤ n i=1 Na ( z i +1 2 ) i 2 e M 2 |D K | 1 2d 1 + 1 2 e+1 ρ d( +1) . (7.4) 2 2 )
Proof The rank of (Λ, . The matrix U = (U s,t ) 1≤s,t≤ +1 is block upper triangular, with U j+1,j+1 = V j for 0 ≤ j ≤ min{z max , }, and all remaining blocks along the leading diagonal (if any) equal to the d × d identity matrix. By construction, the matrix V j is the HNF of the ideal

n i=1 a max{zi-j,0} i , for 0 ≤ j ≤ min{z max , }. It follows that |det V j | = O K : n i=1 a max{zi-j,0} i = n i=1 Na max{zi-j,0} i = 0,
Combining this inequality with Lemma 7.1 and Lemma 7.2 implies that

h 2,M ≤ 2 d 4 d ∆ (ρ,e) K M 2 n i=1 Na ( z i +1 2 ) i 1 d( +1)
. Therefore, given m ∈ M C such that (7.8) holds, (5.2) is satisfied and applying Lemma 5.1 with a = n i=1 a χi(m-ri)zi i shows that h(m) = 0 over K. Hence, it follows from Lemma 6.2 that for all such m ∈ M C , the vector δ(m) is found by Sub-Algorithm 6.1 and, thus, m is returned by Algorithm 5. Computing the matrix U in Step 3 reduces to computing the blocks U m+1,j+1 , for 0 ≤ m < j ≤ min{z max , }: all remaining blocks are either equal to one of these blocks, equal to the d × d zero matrix, or equal to one of the matrices V j . The bound (6.3) on the entries of the multiplication table implies that M r is computed modulo a z ≤

K |, z max , n i=1 log Na i )) bit operations. The matrix R satisfies R ∞ ≤ 1 2 • max 1≤i≤d ω * i ≤ d i=1 ω * i 2 (min 1≤i≤d ω * i ) d-1 ≤ 2 (d-1) 2 /2 2d (d-1)/2 |D K |,
where the final inequality follows from (5. For a ∈ O K such that δ(a) ∈ R, the value of χ i (a -r i ), 1 ≤ i ≤ n, is determined by using backward substitution to successively compute the entries of the vector A -1 i δ(a -r i ) and check that they are integers. Lemma 6.2 and (6.4) imply that δ(a) ∞ ≤ 2 (1-d)/2 d d+1/2 (M + 2 -t ), for all δ(a) ∈ R. Moreover, the set R contains at most d vectors. Therefore, computing the left hand side of (5.2), for all

O d 5 ( + 1) 5 (d( + 1) + log Q ∞ ) log Q ∞ bit operations. As the matrix R e, ,M is block diagonal, it follows that Q ∞ ≤ d R e, ,M ∞ U ∞ , where U ∞ ≤ n i=1 Na zi i and R e, ,M ∞ ≤ 2 e M R ∞ + 1 2 ≤ 2 (d-1) 2 /2 2d (d-1)/2 2 e M |D K | + 1 2 . ( 7
a ∈ O K such that δ(a) ∈ R, is performed in O poly d, n, z max , , log M,
= + 1 -k deg f , returns all m ∈ O K such that size(m) ≤ M and N gcd ((f (m)), a) k > 2 d( +1)-1 4 + 1 d |D K | 1 2d M 2 d Na ( k+1 2 ) deg f +1 .
Given an NF-code C = C K with parameters (n, a 1 , . . . , a n ; M, 0), positive integer weights z 1 , . . . , z n and a received word (r 1 + a 1 , . . . , r n + a n ), weighted list decoding is performed with their algorithm by additionally setting a = n i=1 a i , k = max 1≤i≤n z i and f = x -r, where r ∈ O K satisfies r -r i ∈ a i , for 1 ≤ i ≤ n. For list decoding, where the weights z 1 , . . . , z n are equal, this approach performs almost identically to Algorithm 5.1, with both methods providing a generalisation of the list decoding algorithm for CRT codes of Boneh [START_REF] Boneh | Finding smooth integers in short intervals using CRT decoding[END_REF].

Parameter selection

Theorem 7.8 shows that Algorithm 5.1 returns all elements of the message space that satisfy a certain "weighted" condition. In this section, parameter selection for Algorithm 5.1 is used to evaluate the algorithm's performance for arbitrarily chosen weights and for the uniform weighting associated with traditional list decoding. The results of this section are straightforward generalisations of those obtained by Guruswami, Sahai and Sudan [START_REF] Guruswami | Soft-decision" decoding of Chinese remainder codes[END_REF]Section 3.4] for decoding of CRT codes (see also [START_REF] Guruswami | List decoding of error-correcting codes[END_REF]Section 7.6.3]). Consequently, their proofs are abridged, with details left to the reader.

Theorem 8.1 Let K be a degree d number field and C = C K be an NF-code with parameters (n, a 1 , . . . , a n ; M, 0) such that M ≥ 1. For positive reals β 1 , . . . , β n and any tolerance parameter ε > 0, there exists a choice of parameters z 1 , . . . , z n , , e such that Algorithm 5.1, when given any input vector (r To complete the proof, the remaining parameters , A and e are chosen such that this inequality holds for all m ∈ M C that satisfy condition (8.1). Define Z i = For this choice of and e, the right hand side of (8.

β 2 i log Nai + 3 A β i + 2 A 2 log Na i , for 1 ≤ i ≤ n. Set = A n i=1 Z i d log(2

Conclusion

A polynomial time algorithm (Algorithm 5.1) for solving the weighted list decoding problem for number field codes was presented. The algorithm extends known results for Chinese remainder codes to number fields and reduces the gap to analogous results for Reed-Solomon and algebraic geometry codes [START_REF] Sudan | Decoding of Reed-Solomon codes beyond the error-correction bound[END_REF][START_REF] Guruswami | Improved decoding of Reed-Solomon and algebraic-geometry codes[END_REF]. Comparing Theorem 8.1 with the combinatorial result Corollary 3.1 suggests that Algorithm 5.1 performs suboptimally for number fields other than Q. The difference between conditions (8.1) and (3.1), which depends on the degree of the number field only, is a consequence of the loss of structure that results from treating the O K -module A as a Z-module. Progress toward an algorithm that attains the combinatorial bound may result from considering the additional structure.

  O K with respect to the basis ω 1 , . . . , ω d . Given elements x = d k=1 x k ω k and y = d k=1 y k ω k such that the coefficients x k and y k are B-bit integers, the product xy is computed using the multiplication table in

2 2 provides an integral approximation of 2 2e a 2 2

 22 ,M , for all a ∈ O K [x] , which is substituted for .

2 2 ,

 2 M in the decoding algorithm.

  and the determinant of the matrix M -1 h λ M h have precisely the same roots. It follows from a result of Gohberg, Lancaster and Rodman [10, Theorem 1.1] that the roots of det(M -1

  d i=1 (x -σ i (a)) = φ a (x) d/ deg φa , where the conjugates σ 1 (a), . . . , σ d (a) satisfy |σ i (a)| ≤ size(a), for 1 ≤ i ≤ d. By expressing the coefficients of φ a as symmetric polynomials in its roots, it follows that

2 .

 2 As the number of linear factors of N K (h) is bounded by deg N K (h) ≤ d , it follows that Step 3 performs O(poly(d, log |D K |, , log M, log h 2,M )) bit operations. Similarly, the number of iterations of the outer loop in Step 4 is bounded by d /2. For each iteration, the condition (6.8) and Theorem 6.1 imply that O(poly(d, log |D K |, , log M, t, log h 2,M )) bit operations are performed in Step 4b. For each iteration of the outer loop, there are at most d iterations of the inner loop in Step 4c. As ω 1 , . . . , ω d is a reduced basis for (O K , T 2 ), property 3 of Theorem 4.1 implies thatmax 1≤i≤d ω i ≤ d i=1 2 (i-1)/2 ω * i (min x∈O k \{0} x ) d-1 = 2 d(d-1)/4 |D K | d (d-1)/2 . since det(O K , T 2 ) = d i=1 ω * i (see [4, Proposition 2.5.4]). Using this inequality to bound the constant X and applying Theorem 6.2, shows that Step 4(c)i performs O(poly(d, log |D K |, , log M, log h 2,M )) bit operations for each iteration of the inner loop. In Step 4(c)ii, O(d(d + log Y ) 2 ) bit operations are performed to determine if the vector (y 1 /q, . . . , y d /q) has integral entries. Thus, for each iteration of the inner loop, Step 4(c)ii performs O(poly(d, log |D K |, , log M, log h 2,M )) bit operations. Hence, Step 4 performs O(poly(d, log |D K |, , log M, t, log h 2,M )) bit operations.

2 2 )

 2 from Step 4 of Algorithm 5.1 has rank d( + 1) and det(Λ, .

2 2 )

 2 is equal to the rank of the matrix Q and its determinant det(Λ, .

2 2 )

 2 = det(Q t Q)1/2 . The inequalities M ≥ 1 and (5.3) imply that the matrix 2 e M j R has maximal rank, for 0 ≤ j ≤ . Thus, R e, ,M has maximal rank and det R e, ,M =

ni=1

  Na zi i in O(poly(d, log |D K |, z max , n i=1 log Na i )) bit operations. The matrix V j is the HNF of the ideal n i=1 a max{zi-j,0} i , thus V j ∞ ≤ n i=1 Na zi i , for 0 ≤ j ≤ min{z max , }. Therefore, by performing arithmetic modulo a z when computing the blocks U m+1,j+1 , for 0 ≤ m < j ≤ min{z max , }, Step 3 performs O(poly(d, log |D

  4). Consequently, the matrix R e, ,M is computed in O(poly(d, log |D K |, , log M, e)) bit operations. The matrix R e, ,M is block diagonal and U is block upper triangular, with each matrix having d × d blocks. Therefore, O(d 3 2 M(log R e, ,M ∞ + log U ∞ )) bit operations are performed when computing their product Q = R e, ,M U . The L 2 algorithm performs

Remark 7 . 1

 71 Given a monic polynomial f ∈ O K [x], a nonzero ideal a ⊂ O K , a positive real number M and positive integers k and such that ≥ k deg f , the polynomial time algorithm described by Cohn and Heninger[START_REF] Cohn | Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding[END_REF] in the proof of their Theorem 1.3, when applied with parameters f , I = a, λ 1 = . . . = λ d = M , k and t

- 3 -

 3 log d) + 1.

< 2 2 ii=1

 22 (d+3)/4 |D K | 1/2d (d + 1/d). Consequently, there exists a positive constant A 0 = poly(d, log |D K |, n i=1 log Na i , 1/ε) such that, for all A ≥ A 0 , is positive and the right hand side of (8.2) is less than or equal tolog Na i + ε .Therefore, set A = A 0 . For this choice of A, the parameters z 1 , . . . , z n and chosen above are all O(poly(d, log |D K |, n i=1 log Na i , 1/ε)). Thus, the bit complexity follows directly from Theorem 7.1.A bound on the performance of Algorithm 5.1 as a traditional (uniform) list decoding algorithm is obtained directly from Theorem 8.1 by setting β i = 1, for 1 ≤ i ≤ n. A second and generally incomparable bound, is provided by the following corollary to Theorem 8.1: Corollary 8.1 Let K be a degree d number field and C = C K be an NF-code with parameters (n, a 1 , . . . , a n ; M, 0) such that M ≥ 1. Suppose there exists an integer k ≤ n such that k i=1 Na i ≥ 2 d 2 /2 M d . Then, for any tolerance parameter ε > 0, there exist parameters for Algorithm 5.1 such that, given any input vector (r 1 , . . . , r n ) ∈ O n K , the algorithm returns all m ∈ M C such thatn i=1 χ i (m -r i ) ≥ k(n + 1 + ε). If k Na i = 2 d 2 /2 M d , the bound becomes n i=1 χ i (m -r i ) ≥ k(n + ε).Proof By applying Theorem 8.1 withβ i = log Na i / log Na k , for 1 ≤ i < k, β i = 1,for k ≤ i ≤ n, and tolerance parameter ε = ε log Na k , it follows that there exists a choice of parameters for Algorithm 5.1 with the property that, given any input vector (r 1 , . . . , r n ) ∈ O n K , the algorithm returns all m ∈ M C such thatn i=1 χ i (m -r i ) is at least k -d log 2 d/2 M log Na k + d log 2 d/2 M log Na k d log 2 d/2 M log Na k + n i=k log Na k log Na i + ε . If k i=1 Na i = 2 d 2 /2 M d ,then the lower bound of summation in this expression may be increased from k to k + 1. In either case, the remainder of the proof follows arguments of Guruswami et al.[START_REF] Guruswami | Soft-decision" decoding of Chinese remainder codes[END_REF] Theorem 5].

  1 Let Σ 1 , . . . , Σ n be finite nonempty sets and Σ ⊆ Σ 1 × . . . × Σ n be nonempty. Let vectors (α 1 , . . . , α n ) and (β 1 , . . . , β n ) contain positive real entries. Define d(Σ) α to be the minimum of i:xi =yi α i over all pairs of distinct vectors (x 1 , . . . , x n ), (y 1 , . . . , y n ) ∈ Σ. Then, for any vector (t 1 , . . . , t n ) ∈ Σ 1 × . . . × Σ n and > 0, there exist at most vectors (x 1 , . . . , x n ) ∈ Σ such that

i:xi=ti

  then return the empty set and stop. Otherwise, perform Sub-Algorithm 6.1. 6. [Remove spurious roots] Return the set of all m ∈ O K such that δ(m) belongs to the set R returned by Sub-Algorithm 6.1 and (5.2) holds. There is little loss of generality resulting from the input requirement on M : if 0 ≤ M < d, then M C = {0} and decoding is a greatly simplified problem. 2. A suitable input basis ω 1 , . . . , ω d (i.e., LLL-reduced, with ω 1 = 1) is found with the method described by Belabas [2, Section 4.3]. As noted by Belabas [1, Section 4.2], the entries of R are obtained as by-products of the reduction used to obtain the input basis. It is assumed above (and in the analysis of the decoding algorithm) that the integral basis and R are provided with the precision required by Algorithm 5.1 and Sub-Algorithm 6.1. 3. The computation of the ideal products in Step 1 and Step 2 may be greatly aided by the knowledge of two-element representations for some or all of the ideals a 1 , . . . , a n (see [4, Section 4.7.1] or [1, Section 5.3.2]). 4. For an NF-code C with parameters (n, a 1 , . . . , a n ; M, s) such that s = 0, decoding may be performed as follows: use an algorithm for finding an approximate closest vector in a lattice[START_REF] Hanrot | Algorithms for the shortest and closest lattice vector problems[END_REF], applied to (O K , T 2 ), to find an element y ∈ O K such that size s (y) is small; apply Algorithm 5.1 to the code C with parameters (n, a 1 , . . . , a n ; M + size s (y), 0) and received word ((r 1 -y) + a 1 , . . . , (r ny) + a n ); for each output m of Algorithm 5.1, return m

	Remarks 5.1
	1.

  1. If computations from previous iterations are reused on each pass of the loop in Step 1, then the matrices B 1 , . . . , B n are computed by performing O(n) multiplications of ideals, given by their HNF, with norms bounded by n i=1 Na i . For each iteration, the extended gcd computation in Step 1b performs O(poly(d,n i=1 log Na i )) bit operations, with each β i satisfying δ(β i ) ∞ ≤ Na i . Furthermore, δ(r i ) ∞ ≤ Na i , for 1 ≤ i ≤ n.As a result, for each iteration of the loop, the sum in Step 1c is computed by performing O(poly(d, n i=1 log Na i , log (m i,j,k ) ∞ )) bit operations, using the methods described in Section 4.2. Therefore, using (6.3) to bound the entries of the multiplication table shows that O(poly(d, log|D K |, n, n i=1 log Na i )) bit operations are performed in Step 1.If computations from previous iterations are reused on each pass of the loop in Step 2, then the matrices V 0 , . . . , V min{zmax, } are computed by performing O(z max + n) multiplications of ideals, given by their HNF, with norms bounded by n i=1 Na zi i . Therefore, the bound (6.3) on the entries of the multiplication table implies that Step 2 performs O(poly(d, log |D K |, n, z max , n i=1 log Na i )) bit operations, using the methods described in Section 4.2.

	generator a satisfies a ≤	n i=1	n i=1 Na i . By definition, the

  .9) Therefore, Step 4 performs O(poly(d, log |D K |, z max , , log M, The matrix R e, ,M is block diagonal, with upper triangular blocks on the diagonal. Therefore, using backward substitution to compute each coefficient of h, the polynomial is computed in O(d 2 M(log R e, ,M ∞ + log b 1 ∞ )) bit operations. Sub-Algorithm 6.1 performs O(poly(d, log |D K |, , log M, t, log h 2,M )) bit operations (see Lemma 6.2). Therefore, Step 5 performs O poly d, log |D K |, z max , , log M,

	n i=1 log Na i , e))
	bit operations.
	n
	log Na i , e, t
	i=1
	bit operations.

  1 , . . . , r n ) ∈ O n K , performs O poly d, log |D K |, n, log M,Proof The condition (8.1) is invariant under scaling of the parameters β 1 , . . . , β n . Therefore, assume without loss of generality that max 1≤i≤n (β i / log Na i ) = 1. Let A be an integer parameter to be determined later and setz i = Aβ i / log Na i , for 1 ≤ i ≤ n. Then Aβ i / log Na i ≤ z i < (Aβ i / log Na i ) + 1, for 1 ≤ i ≤ n.Therefore, Theorem 7.1 implies that Algorithm 5.1, for parameters z 1 , . . . , z n , finds all m ∈ M C such that

				d 2 M		n i=1	β 2 i log Na i	+ ε max 1≤i≤n	β 2 i log 2 Na i	. (8.1)
	n i=1	χ i (m -r i )β i ≥	1 2A	d log(2	d 2 M ) + d log( + 1) +	d A	log ∆	(ρ,e) K
			+	A 2( + 1)	n i=1	β 2 i log Na i	+	3 A	β i +	2 A 2 log Na

n i=1 log Na i , t, 1/ε bit operations and returns all m ∈ M C such that n i=1 χ i (m -r i )β i ≥ d log 2 i . (8.2)

Acknowledgements The author would like to thank Dr Victor Scharaschkin for many helpful discussions and suggestions throughout the preparation of this paper.

for 0 ≤ j ≤ min{z max , } (see [START_REF] Cohen | A course in computational algebraic number theory[END_REF]Section 4.7.1]). Hence, U has maximal rank and

Consequently, Q = R e, ,M U has maximal rank and det(Λ, .

Combining (7.5), (7.6) and (7.7) then yields (7.4).

The following theorem, the main algorithmic result of the paper, describes the decoding performance and computational complexity of Algorithm 5.1:

where

Moreover, the algorithm performs

be the element such that δ(α j,k ) is the kth column vector of V j , for 0 ≤ j ≤ min{z max , }, 1 ≤ k ≤ d. Let u j ∈ O K [x] be the polynomial such that δ (u j ) is the jth column vector of U , for 1 ≤ j ≤ d( + 1). Then there exist polynomials u * 1 , . . . , u * d( +1) ∈ O K [x] such that deg u * dj+k < j and

and a z is the positive generator of ( n i=1 a zi i ) ∩ Z. It follows that u 1 , . . . , u d( +1) ∈ A (in fact, the polynomials form an integral basis of A as a consequence of Lemma 5.2). Therefore, the polynomial h, which by construction is a Z-linear combination of the polynomials u 1 , . . . , u d( +1) , also belongs to A . From Lemma 7.2, it is known that (Λ, . det(Λ, .