Tommaso Caselli
email: t.caselli@vu.nl

Isabella Chiari
email: isabella.chiari@uniroma1.it

Aldo Gangemi
email: gangemi@loa-cnr.it

Elisabetta Jezek
email: jezek@unipv.it

Alessandro Oltramari
email: aoltrama@andrew.cmu.edu

Guido Vetere
email: gvetere@it.ibm.com

Laure Vieu
email: vieu@irit.fr

Fabio Massimo Zanzotto

English. Senso Comune is a linguistic knowledge base for the Italian Language, which accommodates the content of a legacy dictionary in a rich formal model. The model is implemented in a platform which allows a community of contributors to enrich the resource. We provide here an overview of the main project features, including the lexical-ontology model, the process of sense classification, and the annotation of meaning definitions (glosses) and lexicographic examples. Also, we will illustrate the latest work of alignment with MultiWordNet, to illustrate the methodologies that have been experimented with, to share some preliminary result, and to highlight some remarkable findings about the semantic coverage of the two resources.

Introduction

Senso Comune 1 is an open, machine-readable knowledge base of the Italian language. The lexical content has been extracted from a monolingual Italian dictionary 2 , and is continuously enriched through a collaborative online platform. The knowledge base is freely distributed. Senso Comune linguistic knowledge consists in a structured lexicographic model, where senses can be qualified with respect to a small set of ontological categories. Senso Comune's senses can be further enriched in many ways and mapped to other dictionaries, such as the Italian version of Mul-tiWordnet, thus qualifying as a linguistic Linked Open Data resource.

General principles

The Senso Comune initiative embraces a number of basic principles. First of all, in the era of user generated content, lexicography should be able to build on the direct witness of native speakers. Thus, the project views at linguistic knowledge acquisition in a way that goes beyond the exploitation of textual sources. Another important assumption is about the relationship between language and ontology (sec. 2.1). The correspondence between linguistic meanings, as they are listed in dictionaries, and ontological categories, is not direct (if any), but rather tangential. Linguistic senses commit to the existence of various 1 www.sensocomune.it 2 T. De Mauro, Grande dizionario italiano dell'uso (GRA-DIT), UTET 2000 Q u e o e -b o in many ways and mapped to other in many ways mapped to other as the Italian version of Mul-as the Italian version of Mulas a Linked as a linguistic Linked kinds of entities, but should not be in general confused with (and collapsed to) logical predicates directly interpretable on these entities. Finally, we believe that, like the language itself, linguistic knowledge should be owned by the entire community of speakers, thus they are committed to keep the resource open and fully available.

2 Senso Comune Essentials

Lexicon and ontology

In compliance with recent trends of research in integrating ontologies and lexical resources (see e.g. [START_REF] Oltramari | New Trends of Research in Ontologies and Lexical Resources[END_REF] and [START_REF] Prévot | Ontology and the Lexicon[END_REF]) Senso Comune model includes a lexicon and an ontology as independent semantic layers. Instead of providing synsets with formal specifications aimed at qualifying them as ontological classes [START_REF] Gangemi | The ontowordnet project: extension and axiomatization of conceptual relations in wordnet[END_REF], Senso Comune adopts a notion of ontological commitment, which can be summarized as follows:

If the sense S commits to ( →) the concept C, then there are entities of type C to which occurrences of S may refer to.

(S → C) ⇔ ∃s, c|S(s) ∧ C(c) ∧ ref ers to(s, c)
This way, linguistic senses are not modelled as logical predicates to be directly interpreted with respect to individuals in some domain of quantification, but rather as semiotic objects that occur in texts or communication acts, whose relationship with other real world entities is mediated by cognitive structures, emotional polarity and social interactions.

As a consequence of this model, lexical relations such as synonymy, which hold among senses, do not bear any direct ontological import; conversely, ontological axioms, such as disjointness, do not have immediate linguistic sideeffects. This approach allows senses of different types to be freely put into lexical relations, without the need of assigning the same (complex) type to every member of the synonymy relation; on the other hand, it prevents the system from directly inferring ontological relations out of linguistic evidences, which might be a limitation in many cases. Anyway, if the equivalence of linguistic senses to logic predicates is desired (e.g. for technical, monosemic portions of the dictionary), this condition can be specifically formalized and managed.

Sense classification

Meanings from De Mauro's core Italian lexicon have been clustered and classified according to ontological categories belonging to Senso Comune model, through a supervised process we called TMEO, a tutoring methodology to support sense classification by means of interactive enrichment of ontologies [START_REF] Oltramari | An introduction to hybrid semantics: The role of cognition in semantic resources[END_REF]. TMEO is based on broad foundational distinctions derived from a simplified version of DOLCE3 [START_REF] Masolo | WonderWeb Deliverable D17: The WonderWeb Library of Foundational Ontologies[END_REF] [START_REF] Chiari | An open knowledge base for italian language in a collaborative perspective[END_REF]. The overarching goal is to support users that, by design, have only access to the lexical level of the resource, in the task of selecting the most adequate category of the Senso Comune ontology as the super-class of a given lexicalized concept: different answer paths lead to different mappings between the lexical and the ontological layer of Senso Comune knowledge base.

Ongoing work on TMEO focuses on extending the coverage of the methodology and refining both the category distinctions in the ontology and the questions in the decision tree. In a previous experiment reported in [START_REF] Chiari | Di che cosa parliamo quando parliamo fondamentale[END_REF], we observed that users have a high degree of confidence and precision in classifying the concepts referring to the physical realm, while they face several problems in identifying abstract notions like 'company', 'text', 'beauty', 'duration', 'idea', etc. Accordingly, the new scheme, already tested in our last experiment [START_REF] Jezek | Enriching senso comune with semantic role sets[END_REF] summarized below, mainly improves the Senso Comune ontology in the abstract realm. It substitutes the too vague category Idea with the more generic SocialOrMentalObject, within which InformationObject and Organization are distinguished subcategories. In addition, the remaining abstract categories TemporalQuality, Quality and Function are complemented and grouped under a more general category PropertyOrRelation. Finally, we added the possibility to distinguish, for each category, a singular and a collective sense, thus allowing to annotate the main senses of the lemmas 'popolo' (people) and 'gregge' (herd) with the categories Person and Animal (adding a 'collective' tag). The results are a richer taxonomy and better organized decision tree. to the realm, while to the physical realm, while y face several problems in identifying abstract y face several problems in identifying e 'company', 'text', 'beauty', 'dura-e 'company', 'text', 'beauty', . Accordingly, the new scheme, . Accordingly, the new scheme, in our last experiment (Jezek et al., in The annotation task, which is performed through a Web-based tool, is organized in two main subtasks. The first (task 1) consists in identifying the constituents that hold a relation with the target verb in the example and to annotate them with information about the type of phrase and grammatical relation. In semantic annotation (task 2), users are asked to attach a semantic role, an ontological category and the sense definition associated with the argument filler of each frame participant in the instances. For this aim, we provide them with a hierarchical taxonomy of 24 coarse-grained semantic roles based on [START_REF] Bonial | A hierarchical unification of lirics and verbnet semantic roles[END_REF], together with definitions and examples for each role, as well as decision trees for the roles with rather subtler differences. The TMEO methodology is used to help them selecting the ontological category in a new simplified ontology based on Senso Comune's top-level. For noun tagging, the annotator exploits the senses already available in the resource. Drawing on the results of the previous experiment on nouns senses, we allow multiple classification in all the three semantic subtasks, that is, we allow the users to annotate more than one semantic role, ontological category and sense definition each frame participant. Up to now we performed two pilot experiments to release the beta version of the annotation scheme. The results of IA agreement are very good for the syntactic dependency annotation task and fair for the semantic task, the latter especially so since these tasks are notoriously difficult (see [START_REF] Jezek | Enriching senso comune with semantic role sets[END_REF] for details). Once completed, the annotated data will be used to conduct an extensive study of the interplay between thematic role information and ontological constraints associated with the participants in a frame; to refine the ontologisation of nouns senses in Senso Comune by assigning ontological classes to nouns in predicative context instead of nouns in isolation; to investigate systematic polysemy effects in nominal semantics on a quantitative basis. Our long-term goal is to enrich the resource with a rich ontology for verb types, informed by the empirical data provided by the an-notated corpus.

Word Sense Alignment: Towards Semantic Interoperability

As a strategy to enrich the Senso Comune Lexicon (SCL) and make it interoperable with other Lexico-semantic resources (LSRs), two experiments of Word Sense Alignment (WSA) have been conducted: a manual alignment and an automatic one. WSA aims at creating a list of pairs of senses from two (or more) lexical-semantic resources where each pair of aligned senses denotes the same meaning [START_REF] Matuschek | [END_REF].

The target resource for the alignment is Multi-WordNet (MWN) [START_REF] Pianta | MultiWordNet: developing an aligned multilingual database[END_REF]. SCL and MWN are based on different models4 .

The alignment aims at finding a semantic portion common to the set of senses represented in SCL by the conjunction of glosses and usage examples and in MWN by the synset words and their semantic relationships (hypernyms, hyponyms, etc.). Since semantic representation in the form of lexicographic glosses and in the form of synsets cannot be considered in any respect homomorphic the procedure of alignment is not biunique in any of the two directions. Thus, there are single SCL glosses aligned to more than one MWN synsets and single MWN synsets aligned with more than one SCL gloss. Another goal of the alignment experiments is the integration of high quality Italian glosses in MWN, so as to make available an enhanced version of MWN to NLP community, which could help improving Word Sense Disambiguation (WSD) and other tasks.

Manual aligment

On going work on the manual alignment of SCL and MWN synsets aims at providing associations between SCL glosses and synsets for all 1,233 nouns labelled as belonging to the basic vocabulary. The alignment is performed through the online platform that allows for each SCL word sense the association with one or more MWN synset.

At the time of this writing, 584 lemmas of SCL have been processed for manual alignment, for a total of 6,730 word senses (glosses), about 3.64 average word senses for each lemma. [START_REF] Pianta | MultiWordNet: developing an aligned multilingual database[END_REF]. WordNet (MWN) [START_REF] Pianta | MultiWordNet: developing an aligned multilingual database[END_REF].

are based on different models are based on models alignment aims at finding a semantic portion alignment aims finding a semantic portion the set of senses represented in SCL by common to of senses represented in SCL by the conjunction the conjunction word senses not labelled as fundamental (about 29% of all word senses). Preliminary results show that only 2,131 glosses could be aligned with at least one MWN synset (31.7%) and 2,187 synsets could be aligned to at least one gloss. Exclusively biunique relationships among SCL glosses and MWN synsets involve 1,093 glosses. Each SCL gloss is associated to one synset in 1,622 cases (76.1%), to two synsets in 367 cases (17.2%), to three synsets 108 cases (5%), to four 25 (1,1%), to five in four cases, to six in three cases and to seven synsets in one case. While on the other side each MWN synset is associated to one SCL gloss in 1,681 cases (76.8%), to two glosses in 400 cases (18.2%), to three glosses in 85 cases (3.8%), to four in 17 cases, to five in three cases, and to six glosses in one case. The picture portrayed by the asymmetry of relationship between the granularity of SCL and MWN appears very similar, meaning that there is no systematic difference in the level of detail in the two resources aligned, as far as this preliminary analysis reveals. Attention should be drawn to the fact that biunique associations do not directly entail that the semantic representation deriving from the SCL gloss and the MWN synset are semantically equivalent or that they regard the same set of senses. These association only indicate that there is no other gloss or synset that can properly fit another association procedure. Levels of abstraction can be significantly different. Furthermore, as data show, there is a large number of SCL glosses not aligned to any MWN synset, and vice versa. This mismatch probably derives from the fact that MWN synsets are modelled on the English WN. Many WN synsets could be aligned to Italian senses outside the basic vocabulary; however, in general, we think that this mismatch simply reflects the semantic peculiarity of the two languages.

Automatic alignment

We conducted two automatic alignment experiments by applying state-of-the-art WSA techniques. The first technique, Lexical Match, aims at aligning the senses by counting the number of overlapping tokens between two sense descriptions, normalized by the length of the strings. We used Text::Similarity v.0.09 The second technique, Sense Similarity, is based on computing the cosine score between the vector representations of the sense descriptions. Vector represen-tations have been obtained by means of the Personalized Page Rank (PPR) algorithm [START_REF] Agirre | Random walks for knowledge-based word sense disambiguation[END_REF] with WN30 extended with the "Princeton Annotated Gloss Corpus" as knowledge base 5 . The evaluation of the automatic alignments is performed with respect to two manually created Gold Standards, one for verbs and one for nouns, by means of standard Precision (P), Recall (R) and F1 score. The verb Gold Standard contains 350 sense pairs over 44 lemmas, while the noun Gold Standard has 166 sense pairs for 46 lemmas. The two gold standards have been independently created with respect to the manual alignment described in Section 3.1 and took into account only fundamental senses. Concerning the coverage of in terms of aligned entries, as for verbs MWN covers 49.76% of the SCDM senses while for nouns MWN covers 62.03% of the SCDM senses. The best results in terms of F1 score have been obtained by merging the outputs of the two approaches together, namely we obtained an F1 equals to 0.47 for verbs (P=0.61, R=0.38) and of 0.64 for nouns (P=0.67, R=0.61).

Conclusion

In this paper, we have introduced Senso Comune as an open cooperative knowledge base of Italian language, and discussed the issue of its alignment with other linguistic resources, such as WordNet. Experiments of automatic and manual alignment with the Italian MultiWordNet have shown that the gap between a native Italian dictionary and a WordNet-based linguistic resource may be relevant, both in terms of coverage and granularity. While this finding is in line with classic semiology (e.g. De Saussure's principle of arbitrariness), it suggests that more attention should be paid to the semantic peculiarity of each language, i.e. the specific way each language constructs a conceptual view of the World. One of the major features of Senso Comune is the way linguistic senses and ontological concepts are put into relation. Instead of equalising senses to concepts, a formal relation of ontological commitment is adopted, which weakens the ontological import of the lexicon. Part of our future research will be dedicated to leverage on this as an enabling feature for the integration of different lexical resources, both across and within national languages. 5 Readers are referred to [START_REF] Caselli | Aligning an italianwordnet with a lexicographic dictionary: Coping with limited data[END_REF] for details on the two methods used and result filtering. there is no systematic difference in the level there is no systematic difference in the level of detail in the two resources aligned, as far as this of detail in two resources aligned, as far as analysis Attention should be analysis reveals. Attention should be wn to the that biunique associations do not wn to the fact that biunique do the semantic the semantic riving from the SCL gloss and the MWN synset riving from the SCL gloss and the synset valent or they regard the valent or they regard the of senses. These association only indi-of senses. association only indiis no gloss or synset that can is no other gloss or synset that can fit another association procedure. Levels fit another association procedure. Levels

  precision in classifying the of confidence and precision in classifying the

  SCL MWN appears very similar, meaning of SCL and MWN appears very similar, meaning

  Ongoing work in Senso Comune focuses on manual annotation of the usage examples associated with the sense definitions of the most common verbs in the resource, with the goal of providing Senso Comune with corpus-derived verbal frames.

	2.3 Annotation of lexicographic examples
	and definitions
	our last (Jezek al.,
	w, mainly improves the w, mainly the
	in the realm. in the abstract realm.
	It the too vague category It substitutes the too vague category Ide Ide
	rMental rMental
	InformationObject InformationObject
	tinguished tinguished
	egories. addition, the remaining abstract egories. In addition, the remaining abstract
	alQuality alQualit
	complemente complemente
	a general category a more general category
	lation. Finally, we added . Finally, added
	to distinguish, for each category, a to distinguish, for each category, a
	a collective sense, thus allowing to a collective sense, allowing to
	senses of the lemmas 'popolo' senses of the lemmas 'popolo'
	gge' (herd) gge' (herd)
	Animal Animal
	are a richer and better are a richer taxonomy and better

http://www.loa.istc.cnr.it/old/DOLCE. html

Readers are referred to[START_REF] Vetere | Senso Comune, an open knowledge base for italian[END_REF] and[START_REF] Caselli | Aligning an italianwordnet with a lexicographic dictionary: Coping with limited data[END_REF] for details on the two resources and their differences.


Olivier Thomas

Mélodie Monteil

Cyril Touzé

Complicated dynamics exhibited by thin shells displaying numerous internal resonances: application to the steelpan

Summary. Nonlinear vibrations of a steelpan, a musical instrument from the Caribbean islands, are experimentally and theoretically studied. Modal analysis reveals the existence of numerous modes displaying internal resonances, enabling the structure to transfer energy from low or high frequency modes. The complicated dynamics in forced vibrations is precisely measured by following the different harmonics of the responses. Energy transfers are explained in light of high order couplings, and simple models displaying 1:2:2 and 1:2:4 internal resonance are fitted to the experiments. The measurements reveals that mode couplings are activated for very low amplitudes of order 1/25 times the thickness, and that numerous modes are rapidly excited, giving rise to frequency responses with complex shape. This ease in transferring energy is a key feature for explaining the peculiar tone of the steelpan. The identified 1:2:4 model is finally used to recover the time oscillations of an impacted note in normal playing condition, resulting in a perfect agreement for the first four harmonics.

Core of the study Steelpans are musical percussion instruments coming from the island of Trinidad and Tobago in the Caribbean. They are traditionnally played in orchestras called steelbands. These orchestras are composed of several steelpans covering a range of several octaves. Each steelpan is made of an oil barrel that is subjected to several stages of metal forming that stretch and bend the structure. The top of the barrel is pressed, hammered, punched and burnt in order to obtain a sort of main bowl within which convex domes are formed, each one corresponding to a particular musical note (Fig. 1).

A modal analysis reveals that the mode shapes of the instruments are localized on the convex domes, each one being associated to a set of modes which natural frequencies are precisely tuned according to harmonic relationships to obtain musical notes [START_REF] Rossing | Vibrational mode shapes in Caribbean steelpans. I. Tenor and double second[END_REF]. The first (fundamental) mode of the domes is tuned to the frequency of the corresponding musical note. Then, the second mode is tuned to twice the frequency of the fundamental one, giving rise to 1:2 relationship. Due to localization and to the octave tuning of successive notes, it is generally observed that the second mode is degenerate so that a 1:2:2 internal resonance is present. The third mode is tuned either at the third or at the fourth of the fundamental frequency, so that 1:2:2:3 or 1:2:2:4 internal resonances are possible. Finally, higher modes are also found to be tuned, hence the presence of modes at six times and/or eight times the fundamental frequency are also generally found. In normal playing where a note is stroke with a stick, vibrations amplitudes are such that geometric nonlinearities cannot be neglected. This property is recognized as a key feature for explaining the peculiar tone of the steelpan [START_REF] Achong | Mode locking on the nonlinear notes of the steelpan[END_REF]. This nonlinearities, combined with the numerous possible internal resonances, activates energy transfer to higher modes. In playing conditions, energy transfers up to a dozen of mode are usually observed.

The aim of the present work is to study energy exchanges and activation of internal resonances in the nonlinear dynamics exhibited by the steelpan, and more generally on systems that show 1:2:2:4 internal resonances. Forced vibrations and frequency response curves are used to identify and localize instabilities and mode coupling. For that purpose, the different harmonics of the responses are measured with a lock-in amplifier, during controlled step-by-step, forward and backward sweeps around the resonances of several eigenfrequencies. Frequency responses show complicated dynamics and activation of mode coupling from low to high-frequency as well as from high to low frequencies. The two following three degrees of freedom models are theoretically studied:

   q1 + 2ξ1ω1 q1 + ω 2 1 q1 + α1q1q2 + α2q1q3 = δ1F1 cos(Ωt), q2 + 2ξ2ω2 q2 + ω 2 2 q2 + α3q 2 1 = δ2F2 cos(Ωt), q3 + 2ξ3ω3 q3 + ω 2 3 q3 + α4q 2 1 = δ2F3 cos(Ωt)    q1 + 2ξ1ω1 q1 + ω 2 1 q1 + α1q1q2 = δ1F1 cos(Ωt), q2 + 2ξ2ω2 q2 + ω 2 2 q2 + α2q 2 1 + α3q2q3 = δ2F2 cos(Ωt), q3 + 2ξ3ω3 q3 + ω 2 3 q3 + α4q 2 2 = δ3F3 cos(Ωt),
where δ i ∈ {0, 1} are Kronecker symbols used to distinguish the oscillators which are forced (if oscillator i is forced, δ j = 0 ∀j = i) [START_REF] Monteil | Nonlinear forced vibrations of thin structures with tuned eigenfrequencies: the cases of 1:2:4 and 1:2:2 internal resonances[END_REF]. Those models are obtained by normal form reductions, by keeping in the oscillators all nonlinear resonant terms responsible of a 1:2:2 internal resonance (model on the left) and a 1:2:4 internal resonance (model on the right). Original analytical results are obtained by the multiple scale method. It is shown that the nonlinear dynamics of the oscillators in 1:2:4 internal resonance may be interpreted as a cascade of two 1:2 internal resonances, whereas the one of the 1:2:2 case is equivalent to two nested 1:2 internal resonances. Instability regions in the amplitude/frequency domains are exhibited, leading to the appearance of coupled periodic solutions as well as quasiperiodic solutions obtained after Neimark-Sacker bifurcations. Figure 2 gives a snapshot of the results in the case of the G3 note of the steelpan for which the natural frequencies are tuned so that ω 3 ≃ ω 2 ≃ 2ω 1 , ω 4 ≃ ω 5 ≃ 4ω 1 , ω 6 ≃ 6ω 1 and ω 7 ≃ 8ω 1 (where the ω i are the natural frequencies of the note), thus displaying a 1:2:2:4:4:6:8 internal resonance. If the fundamental mode is directly driven by a resonant driving so that the driving frequency is Ω ≃ ω 1 , an energy transfer to modes 2, 3 (oscillating at 2Ω) and 4 (oscillating at 4Ω) is observed on the left column of Fig 2 . If the second and third modes are driven with Ω ≃ ω 2 ≃ ω 3 , energy transfers to the other modes are also observed, with, among others, a subharmonic resonant excitation of the fundamental mode, that oscillates at half the driving frequency (Ω/2). The fittings of the theoretical models are also displayed, showing a correct agreement, even if those models should be composed of at least four degrees of freedom instead of three to be closer to the experiments.

Conclusion

A complicated dynamics was exhibited on a particular vibrating shell structure with tuned eigenfrequencies. Numerous experiments in forced vibrations have been performed, showing energy transfers explained by up to 1:2:2:4:6:8 internal resonance. To explained those results, two three degrees of freedom models have been analytically explored, showing that the dynamics can be qualitatively explained by cascades and mixes of 1:2 internal resonances. A fitting of the models to the experiments in forced vibrations was also useful to synthesize a free vibration response of the structure very close to the experiments (not shown here).

Figure 1 :

 1 Figure 1: Photograph of a steel band, of a particular steelpan in normal playing conditions and sketch of the musical notes pattern on the upper surface of the instrument

Figure 2 :

 2 Figure2:(left) Resonance curve of the G3 note of the steelpan excited in the vicinity of its fundamental frequency. The results from the 1:2:2 (blue curve) and 1:2:4 (red curve) three dof. models fitted to experimental results ('⊲' and ⊳') are also shown. First (w1), second (w2) and fourth (w3) harmonics of the signal. (right) Experimental resonance curve of the G3 note of the steelpan excited in the vicinity of its second natural frequency. Subharmonic (H1), fundamental (H2) and second harmonics (H4) of the signal.

  Complicated dynamics exhibited by thin shells displaying numerous internal resonances: application to the steelpan Olivier THOMAS ♯ , Mélodie MONTEIL ♮♭ and Cyril TOUZÉ ♭ ♯ LSIS UMR 7296, Arts et Métiers ParisTech, Lille, France ♮ Université Pierre et Marie Curie, Paris, France ♭ Unité de Mécanique, ENSTA, Palaiseau, France


Benjamin Smith

The Q-curve Construction for Endomorphism-Accelerated Elliptic Curves

Keywords: Elliptic curve cryptography, endomorphism, exponentiation, GLS, GLV, Q-curves, scalar decomposition, scalar multiplication

We give a detailed account of the use of Q-curve reductions to construct elliptic curves over F p 2 with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant-Lambert-Vanstone (GLV) and Galbraith-Lin-Scott (GLS) endomorphisms. Like GLS (which is a degenerate case of our construction), we offer the advantage over GLV of selecting from a much wider range of curves, and thus finding secure group orders when p is fixed for efficient implementation. Unlike GLS, we also offer the possibility of constructing twist-secure curves. We construct several one-parameter families of elliptic curves over F p 2 equipped with efficient endomorphisms for every p > 3, and exhibit examples of twist-secure curves over F p 2 for the efficient Mersenne prime p = 2 127 -1.

Introduction

Let E be an elliptic curve over a finite field F q , and let G ⊆ E(F q ) be a cyclic subgroup of prime order N . When implementing cryptographic protocols in G, the fundamental operation is scalar multiplication (or exponentiation):

Given P in G and m in Z, compute [m]P := P ⊕ • • • ⊕ P m times .
The literature on general scalar multiplication algorithms is vast, and we will not explore it in detail here (see [15, §2.8, §11.2] and [START_REF]Handbook of elliptic and hyperelliptic curve cryptography[END_REF]Chapter 9] for introductions to exponentiation and multiexponentiation algorithms). For our purposes, it suffices to note that the dominant factor in scalar multiplication time using conventional algorithms is the bitlength ⌈log 2 |m|⌉ of m. As a basic example, we may compute [m]P using a variant of the classic binary method, which requires at most ⌈log 2 |m|⌉ doublings and (in the worst case) about as many addings in G (in general, log 2 |m| ∼ log 2 N ∼ log 2 q). Suppose E is equipped with an efficient F q -endomorphism ψ. By efficient, we mean that we can compute the image ψ(P ) of any point P in E(F q ) for the cost of O(1) operations in F q . In practice, we want this to cost no more than a few doublings in E(F q ). Assume ψ(G) ⊆ G, or equivalently, that ψ restricts to an endomorphism of G. 1 Now G is a finite cyclic group, isomorphic to Z/N Z, and every endomorphism of Z/N Z is just an integer multiplication modulo N . Hence, ψ acts on G as multiplication by some integer eigenvalue λ ψ : that is,

ψ| G = [λ ψ ] G for some -N /2 < λ ψ ≤ N/2 .
The eigenvalue λ ψ is a root of the characteristic polynomial of ψ in Z/N Z.

Returning to the problem of scalar multiplication: we want to compute [m]P . Rewriting m as m = a + bλ ψ (mod N )

for some a and b, we can compute [m]P using the relation and a 2-dimensional multiexponentation such as Straus's algorithm [START_REF] Straus | Addition chains of vectors[END_REF], which has a loop length of log 2 (a, b) ∞ : that is, log 2 (a, b) ∞ doubles and at most as many adds 2 (recall (a, b) ∞ = max(|a|, |b|)). If |λ ψ | is not too small, then we can easily find (a, b) such that log 2 (a, b) ∞ is roughly 1 2 log 2 N (we remove the "If" and the "roughly" for our ψ in §4.)

The endomorphism therefore lets us replace conventional log 2 N -bit scalar multiplications with ( 1 2 log 2 N )-bit multiexponentiations. In basic binary methods this means halving the loop length, cutting the number of doublings in half.

Of course, in practice we are not halving the execution time. The precise speedup depends on a variety of factors, including the choice of exponentiation and multiexponentiation algorithms, the cost of computing ψ, and the cost of doublings and addings in terms of bit operations-to say nothing of the cryptographic protocol, which may prohibit some other conventional speedups. For example: in [START_REF] Galbraith | Endomorphisms for faster elliptic curve cryptography on a large class of curves[END_REF], Galbraith, Lin, and Scott report experiments where cryptographic operations on GLS curves required between 70% and 83% of the time 1 The assumption is satisfied, almost by default, in the context of classical discrete log-based cryptosystems. If ψ(G) ⊆ G, then E [N ](Fq) = G +ψ(G) ∼ = (Z/N Z) 2 , so N 2 | #E (Fq) and N | q -1; such E are cryptographically inefficient, and discrete logs in G are vulnerable to the Menezes-Okamoto-Vanstone and Frey-Rück reductions [START_REF] Menezes | Reducing elliptic curve logarithms to logarithms in a finite field[END_REF][START_REF] Frey | The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems[END_REF]. However, the assumption should be verified carefully in the context of pairingbased cryptography, where G and ψ with ψ(G) ⊆ G arise naturally. 2 Straus's algorithm serves as a simple and convenient reference example here: like all multiexponentiation algorithms, its running time depends essentially on log 2 (a, b) ∞. It is not the fastest multiexponentiation, nor is it uniform or constanttime; as such, it is not recommended for real-world implementations.

required for the previous best practice curves-with the variation depending on the architecture, the underlying curve arithmetic, and the protocol in question.

To put this technique into practice, we need a source of cryptographic elliptic curves equipped with efficient endomorphisms. In the large characteristic case 3 , there are two archetypal constructions:

1. The classic Gallant-Lambert-Vanstone (GLV) construction [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphisms[END_REF] uses elliptic curves with explicit complex multiplication (CM) by quadratic orders with tiny discriminants. These curves can be found by reducing CM curves over number fields modulo suitable primes. 2. The more recent Galbraith-Lin-Scott (GLS) construction [START_REF] Galbraith | Endomorphisms for faster elliptic curve cryptography on a large class of curves[END_REF]. Here, curves over F p are viewed over F p 2 ; the p-power sub-Frobenius induces an extremely efficient endomorphism on the quadratic twist (which can have prime order).

GLV and GLS have been combined to give higher-dimensional variants for elliptic curves ( [START_REF] Longa | Four-dimensional Gallant-Lambert-Vanstone scalar multiplication[END_REF], [START_REF] Zhou | Efficient 3-dimensional GLV method for faster point multiplication on some GLS elliptic curves[END_REF]), and extended to hyperelliptic curves ( [START_REF] Bos | Fast cryptography in genus 2[END_REF], [START_REF] Kohel | Efficiently computable endomorphisms for hyperelliptic curves[END_REF], [START_REF] Sica | Analysis of the Gallant-Lambert-Vanstone method based on efficient endomorphisms: Elliptic and hyperelliptic curves[END_REF], [START_REF] Takashima | A new type of fast endomorphisms on Jacobians of hyperelliptic curves and their cryptographic application[END_REF]).

New endomorphisms from Q-curves. This work develops a new source of elliptic curves over F p 2 with efficient endomorphisms: reductions of quadratic Q-curves.

Definition 1. A quadratic Q-curve of degree d is an elliptic curve E without CM, defined over a quadratic number field K, such that there exists an isogeny of degree d from E to its Galois conjugate σ E (formed by applying σ to the coefficients of the defining equation of E), where σ = Gal(K/Q).

Q-curves are well-established objects of interest in number theory, where they have formed a natural setting for generalizations of the Modularity Theorem. We recommend Ellenberg [START_REF] Ellenberg | Q-curves and Galois representations[END_REF] for an excellent introduction to the theory.

Our application of quadratic Q-curves is somewhat more prosaic: given a d-isogeny E → σ E over a quadratic field, we reduce modulo an inert prime p to obtain an isogeny E → σ E over F p 2 . We then exploit the fact that the ppower Frobenius isogeny maps σ E back onto E; composing with the reduced d-isogeny, we obtain an endomorphism of E of degree dp. For efficiency, d must be small; happily, for small values of d, Hasegawa has written down universal one-parameter families of Q-curves [START_REF] Hasegawa | Q-curves over quadratic fields[END_REF]. We thus obtain one-parameter families of elliptic curves over F p 2 equipped with efficient non-integer endomorphisms. 4For concrete examples, we consider d = 2, 3, 5, and 7 in §5, §6, §7, and §8, respectively. We define our curves in short Weierstrass form for maximum generality and flexibility, but we also give isomorphisms to Montgomery, twisted Edwards, and Doche-Icart-Kohel models where appropriate.

Comparison with GLV. Like GLV, our method involves reducing curves defined over number fields to obtain curves over finite fields with explicit CM. However, we emphasise a profound difference: in our method, the curves over number fields generally do not have CM themselves.

GLV curves are necessarily isolated examples-and the really useful examples are extremely limited in number (cf. [29, App. A]). The scarcity of GLV curves is their Achilles' heel: as noted in [START_REF] Galbraith | Endomorphisms for faster elliptic curve cryptography on a large class of curves[END_REF], if p is fixed then there is no guarantee that there will exist a GLV curve with prime (or almost-prime) order over F p . While we discuss this phenomenon further in §9, it is instructive to consider the example discussed in [16, §1]: the most efficient GLV curves have CM discriminants -3 and -4. If we are working at the 128-bit security level, then taking p = 2 255 -19 allows particularly fast arithmetic in F p . But the largest prime factor of the order of a curve over F p with CM discriminant -4 (resp. -3) has 239 (resp. 230) bits: using these curves wastes 9 (resp. 13) potential bits of security. In fact, we are lucky with -3 and -4: for all of the other discriminants offering endomorphisms of degree at most 3, we can do no better than a 95-bit prime factor, which represents a catastrophic 80-bit loss of relative security.

In contrast, our construction yields true families of curves, covering ∼ p isomorphism classes over F p 2 for any choice of p. This gives us a vastly higher probability of finding secure curves over practically important fields.

Comparison with GLS. Like GLS, we construct curves over F p 2 equipped with an inseparable endomorphism. And like GLS, each of our families offer around p distinct isomorphism classes of curves, making it easy to find secure group orders when p is fixed.

But unlike GLS, our curves have j-invariants in F p 2 and not F p : they are not isomorphic to, or twists of, subfield curves. This allows us to find twist-secure curves: that is, curves with secure orders whose twists also have secure orders.

Twist-security is crucial in many elliptic curve-based protocols (including [START_REF] Kaliski | A pseudo-random bit generator based on elliptic logarithms[END_REF], [START_REF] Kaliski | One-way permutations on elliptic curves[END_REF], [START_REF] Boyd | Elliptic curve based password authenticated key exchange protocols[END_REF], [START_REF] Möller | A public-key encryption scheme with pseudo-random ciphertexts[END_REF], and [START_REF] Chevassut | The twist-augmented technique for key exchange[END_REF]); it is particularly important in modern x-coordinateonly ECDH implementations, such as Bernstein's Curve25519 software [START_REF] Bernstein | Curve25519: new Diffie-Hellman speed records[END_REF] (which anticipates the kind of fault attack detailed in [START_REF] Fouque | Fault attack on elliptic curve with Montgomery ladder[END_REF]). GLS curves cannot be used in any of these constructions.

As we will see in §3, our construction degenerates to GLS when d = 1. Our construction is therefore a sort of generalized GLS-though it is not the higherdegree generalization anticipated by Galbraith, Lin, and Scott themselves, which composes a p-power sub-Frobenius endomorphism with a non-rational separable isogeny and its dual isogeny (cf. [START_REF] Galbraith | Endomorphisms for faster elliptic curve cryptography on a large class of curves[END_REF]Theorem 1]).

Acknowledgements. The author thanks Craig Costello, Hüseyin Hışıl, François Morain, and Charlotte Scribot for their help and advice throughout this project.

Notation and Elementary Constructions

Throughout, we work over fields of characteristic not 2 or 3. Let E : y 2 = x 3 + Ax + B be an elliptic curve over such a field K. (Recall that for an equation in this form to define an elliptic curve, the discriminant -16(4A 3 + 27B 2 ) must be nonzero.) Galois conjugates. For every automorphism σ of K, we have a conjugate curve σ E :

y 2 = x 3 + ( σ A)x + ( σ B) .
If φ : E 1 → E 2 is an isogeny, then we obtain a conjugate isogeny σ φ : σ E 1 → σ E 2 by applying σ to the defining equations of φ, E 1 , and E 2 . We write (p) for the p-th powering automorphism of F p . We note that (p) is trivial to compute on

F p 2 = F p ( √ ∆), since (p) (a + b √ ∆) = a -b √ ∆ for all a and b in F p .
Quadratic twists and twisted endomorphisms. For every nonzero λ in K, the quadratic twist of E by λ is the curve over K(λ 2 ) defined by

E λ : y 2 = x 3 + λ 4 Ax + λ 6 B .
The twisting isomorphism δ(λ) : E → E λ is defined over K(λ) by δ(λ) : (x, y) -→ (λ 2 x, λ 3 y) .

Observe that δ(λ 1 )δ(λ 2 ) = δ(λ 1 λ 2 ) for any λ 1 , λ 2 ; and δ(-λ) = -δ(λ). For every K-endomorphism ψ of E, there is a twisted K(λ 2 )-endomorphism

ψ λ := δ(λ)ψδ(λ -1 ) in End(E λ ) .
It is important to distinguish conjugates (marked by left-superscripts) from twists (marked by right-superscripts); note that σ (E λ ) = ( σ E) σ λ for all λ and σ.

Quadratic twists over finite fields. If µ is a nonsquare in K = F q , then E √ µ is a quadratic twist of E. But E √ µ1 and E √ µ2 are F q -isomorphic for all nonsquares µ 1 and µ 2 in F q (the isomorphism δ( µ 1 /µ 2 ) is defined over F q because µ 1 /µ 2 must be a square); so, up to F q -isomorphism, it makes sense to speak of the quadratic twist. We let E ′ denote the quadratic twist when the choice of nonsquare is not important. Similarly, if ψ is an F q -endomorphism of E, then ψ ′ denotes the corresponding twisted F q -endomorphism of E ′ .

Traces and cardinalities. If K = F q , then π E denotes the q-power Frobenius endomorphism of E. The characteristic polynomial of π E has the form

χ E (T ) = T 2 -t E T + q; the trace t E satisfies the Hasse bound |t E | ≤ 2 √ q. Recall #E(F q ) = q + 1 -t E and t E ′ = -t E , so #E(F q ) + #E ′ (F q ) = 2(q + 1) . (1)
Explicit isogenies. Let S ⊂ E be a finite subgroup defined over K; Vélu's formulae ([26, §2.4], [START_REF] Vélu | Isogénies entre courbes elliptiques[END_REF]) compute the explicit (normalized) quotient isogeny

φ : E -→ E/S : y 2 = x 3 + A S x + B S ,
mapping (x, y) to (φ x (x), yφ ′ x (x)) for some φ x in K(x). We will need explicit formulae for the cases #S = 2, 3, 5, and 7. If S = {0, (α, 0)} has order 2, then

A S = -4A -15α 2 , B S = B -7α(3α 2 + A) , and φ x (x) = x + 3α 2 +A x-α . (2)
If S has odd order d = 2e + 1, then it is defined by a kernel polynomial F (x) = e i=0 f i x e-i (so F (x(P )) = 0 if and only if P is in S \ {0}); and then

A S = (1 -10e)A -30(f 1 /f 0 ) 2 + 60f 2 /f 0 , (3)
B S = (1 -28e)B + 28f 1 /f 0 + 70(f 1 /f 0 ) 3 -210f 1 f 2 /f 2 0 + 210f 3 /f 0 , (4)
and

φ x (x) = (2e + 1)x + 2 f1 f0 -4(x 3 + Ax + B) F ′ (x) F (x) ′ -2(3x 2 + A) F ′ (x) F (x) . ( 5
)
Legendre symbols. The Legendre symbol n p is defined to be 1 if n is a square mod p, -1 if n is not a square mod p, and 0 if p divides n.

Reduced lattice bases. We work exclusively with the infinity norm

• ∞ in this article (recall (a, b) ∞ := max(|a|, |b|)). An ordered basis [e 1 , e 2 ] of a lattice in Z 2 is reduced if e 1 ∞ ≤ e 2 ∞ ≤ e 1 -e 2 ∞ ≤ e 1 + e 2 ∞ ; (6)
a reduced basis has minimal length with respect to • ∞ (see [START_REF] Kaib | The Gauss lattice basis reduction algorithm succeeds with any norm[END_REF]).

3 Quadratic Q-curves and their Reductions Suppose E/Q( Looking at the Galois groups of our fields, we have a series of injections

(p) = Gal(F p ( √ ∆)/F p ) ֒→ Gal(Q( √ ∆)/Q) ֒→ Gal(Q( √ ∆, √ -d)/Q) . The image of (p) in Gal(Q( √ ∆)/Q) is σ, because p is inert in Q( √ ∆). We extend σ to the automorphism of Q( √ ∆, √ -d
) that is the image of (p): that is,

σ α + β √ ∆ + γ √ -d + δ √ -d∆ = α -β √ ∆ + -d p γ √ -d -δ √ -d∆ (7)
for all α, β, γ, and δ ∈ Q. Now let E/F p 2 be the reduction modulo p of E. The curve σ E reduces to (p) E, while the d-isogeny φ :

E → σ E reduces to a d-isogeny φ : E → (p) E over F p 2 .
Applying σ to φ, we obtain a second d-isogeny σ φ : σ E → E travelling in the opposite direction, which reduces mod p to a conjugate isogeny (p) φ : (p) E → E defined over F p 2 . Composing σ φ with φ yields endomorphisms σ φ • φ of E and φ • σ φ of σ E, each of degree d 2 . But (by definition) E and σ E do not have CM, so all of their endomorphisms are integer multiplications; and since the only integer multiplications of degree d 2 are [d] and [-d], we conclude that

σ φ • φ = [ǫ p d] E and φ • σ φ = [ǫ p d] σ E , where ǫ p ∈ {±1} .
Technically, σ φ and (p) φ are-up to sign-the dual isogenies of φ and φ, respectively. The sign ǫ p depends on p:

if τ is the extension of σ to Q( √ ∆, √ -d) that is not the image of (p), then τ φ • φ = [-ǫ p d] E . Reducing modulo p, we see that (p) φ • φ = [ǫ p d] E and φ • (p) φ = [ǫ p d](p) E .
The map (x, y) → (x p , y p ) defines p-isogenies

π p : (p) E -→ E and (p) π p : E -→ (p) E .
Observe that (p) π p • π p = π E and π p • (p) π p = π(p) E . Composing π p with φ yields a degree-pd endomorphism

ψ := π p • φ ∈ End(E) .
We also obtain an F p 2 -endomorphism ψ ′ on the quadratic twist E ′ .

If d is very small, then ψ and ψ ′ are efficient because φ is defined by polynomials of degree about d, and π p acts as a simple conjugation on coordinates in F p 2 (as in Eq. ( 7)). In this article we concentrate on prime d ≤ 7.

Theorem 1. The endomorphisms ψ and ψ ′ satisfy

ψ 2 = [ǫ p d]π E and (ψ ′ ) 2 = [-ǫ p d]π E ′ ,
respectively. There exists an integer r satisfying 5

dr 2 = 2p + ǫ p t E (8) such that [r]ψ = [p] + ǫ p π E and [r]ψ ′ = [p] -ǫ p π E ′ ; (9)
the characteristic polynomial of both ψ and ψ ′ is

P ψ (T ) = P ψ ′ (T ) = T 2 -rdT + dp . Proof. Clearly π p • φ = (p) φ • (p) π p , so ψ 2 = π p φπ p φ = π p φ (p) φ (p) π p = π p [ǫ p d] (p) π p = [ǫ p d]π p (p) π p = [ǫ p d]π E .
Similarly, choosing a nonsquare µ in F p 2 , so

E ′ = E √ µ and ψ ′ = ψ √ µ , we find (ψ ′ ) 2 = δ(µ 1 2 )ψ 2 δ(µ -1 2 ) = δ(µ 1 2 (1-p 2 ) )[ǫ p d]π E ′ = δ(-1)[ǫ p d]π E ′ = [-ǫ p d]π E ′ .
The degree of ψ (and ψ ′ ) is dp, so both have a characteristic polynomial in the form P ψ (T ) = T 2 -aT + dp for some integer a. Hence,

[a]ψ = ψ 2 + [dp] = [ǫ p d]π + [dp] . (10)
Squaring both sides, replacing ψ 2 with [ǫ p d]π, and then factoring out [ǫ p d]π, we find a 2 = 2dp + dǫ p t E . It follows that d | a 2 ; but d is squarefree, so a = dr for some integer r, whence Eq. ( 8) and the characteristic polynomial. Putting a = dr in Eq. ( 10) yields [r]ψ = [p] + ǫ p π; a similar argument for ψ ′ , using

ψ ′2 = [-ǫ p d]π E ′ , yields [r]ψ ′ = [p] -ǫ p π, completing Eq. (9). ⊓ ⊔ Corollary 1.
The curves E and E ′ are ordinary if and only if r = 0; and then

|r| = [Z[ψ] : Z[π E ]] = [Z[ψ ′ ] : Z[π E ′ ]] .
Proof.

-4p 2 = r 2 (d 2 r 2 -4dp), respectively, so |r| is the conductor of Z[π ′ E ] in Z[ψ].
The same holds for ψ ′ and π E ′ on E ′ . ⊓ ⊔ Equation ( 8) relates r to the orders of E and E ′ : we find

#E(F p 2 ) = (p + ǫ p ) 2 -ǫ p dr 2 and #E ′ (F p 2 ) = (p -ǫ p ) 2 + ǫ p dr 2 . ( 11
)
If E is supersingular, so r = 0, then [51, Theorem 1.1] yields a stronger statement:

E(F p 2 ) ∼ = (Z/(p + ǫ p )Z) 2 and E ′ (F p 2 ) ∼ = (Z/(p -ǫ p )Z) 2 . Corollary 2. Suppose E is ordinary. If G ⊆ E(F p 2 ) (resp. G ′ ⊆ E ′ (F p 2 )) is a cyclic subgroup such that ψ(G) ⊆ G (resp. ψ ′ (G ′ ) ⊆ G ′ ), then the eigenvalue of ψ on G (resp. ψ ′ on G ′ ) is λ ψ ≡ p + ǫ p r (mod #G) and λ ψ ′ ≡ p -ǫ p r (mod #G ′ ) . Proof. Theorem 1 states that [r]ψ = [p]+ǫ p π in End(E), so ker([p]+ǫ p π) contains E[r],
and hence [p] + ǫ p π is divisible by r in End(E): indeed, the quotient is ψ.

The result follows on restricting to G; the argument for ψ ′ and G ′ is the same. ⊓ ⊔ Q-curves: Where from, and why? Now we just need a source of quadratic Qcurves of small degree. Elkies [START_REF] Elkies | On elliptic k-curves[END_REF] shows that all Q-curves correspond to rational points on certain modular curves:6 Let X * (d) be the quotient of the modular curve X 0 (d) by all of its Atkin-Lehner involutions. If e is a point in

X * (d)(Q) and E is a preimage of e in X 0 (d)(Q( √ ∆)) \ X 0 (d)(Q) for some ∆, then E parametrizes (up to Q-isomorphism) a d-isogeny φ : E → σ E over Q( √ ∆)
, where σ is the involution of Q( √ ∆)/Q. Luckily enough, for very small d, both X 0 (d) and X * (d) have genus zeroso not only can we get plenty of rational points on X * (d), we can get a whole one-parameter family of Q-curves of degree d. Hasegawa gives explicit universal curves for d = 2, 3, and 7 in [20, Theorem 2.2]: for each squarefree integer

∆ = 1, every Q-curve of degree d = 2, 3, 7 over Q( √ ∆) is Q-isomorphic to a rational specialization of one of these families.
Crucially, Hasegawa's families for d = 2, 3, and 7 are defined for any squarefree ∆; so we are free to start by fixing p, before choosing a ∆ to suit. Indeed, the particular choice of ∆ is theoretically irrelevant-since all quadratic extensions of F p are isomorphic-so we may choose any practically convenient value for ∆, such as one permitting faster arithmetic in F p 2 = F p ( √ ∆). Of course, one might ask why it is necessary to use this characteristic-zero theory when we could simply search for curves over F p 2 with a d-isogeny to their Galois conjugate. But for low degrees d where X 0 (d) has genus zero, every such curve arises as the reduction mod p of a Q-curve over Q( √ ∆) where ∆ is a nonsquare mod p. Indeed, the curves over F p 2 with d-isogenies to their Galois conjugates correspond (up to isomorphism) to points in

X * (d)(F p ) with preimages in X 0 (d)(F p 2 ) \ X 0 (d)(F p ). But X 0 (d)
is isomorphic to P 1 over the ground field in the cases we consider, so every such point lifts trivially to a point in

X * (d)(Q) with preimages in X 0 (d)(Q( √ ∆)) \ X 0 (d)(Q):
that is, to a Q-curve. We therefore lose no candidate curves over F p 2 by reducing Q-curves mod p instead of working directly over F p 2 . What we gain by working with Q-curves is some simplicity 7 and universality in our proofs, to say nothing of the wealth of mathematical literature to be raided for examples and theorems. For example: instead of deriving and proving defining equations for these families over F p 2 , we can just conveniently borrow Hasegawa's universal Q-curve equations.

GLS as the degenerate case

d = 1. Suppose φ : E → σ E is an isogeny of degree d = 1: that is, an isomorphism. Then j( E) = j( σ E) = σ j( E), so j( E) is in Q, and E is Q( √ ∆)-isomorphic to a curve defined over Q. Suppose, then, that
E is defined over Q and base-extended to Q( √ ∆): then E = σ E, and we can apply our construction taking φ : E → σ E to be the identity map. Reducing modulo an inert p, we have ψ = π p and ψ 2 = π 2 p = π E , so ψ has eigenvalue ±1 on cryptographic subgroups of E(F p 2 ): clearly, ψ is of no use to us for scalar decompositions. However, the twisted endomorphism ψ ′ on E ′ satisfies (ψ ′ ) 2 = -π E ′ , so the eigenvalue of ψ ′ on cryptographic subgroups is a square root of -1, which is large enough to yield good scalar decompositions. We have recovered the GLS endomorphism (cf. [START_REF] Galbraith | Endomorphisms for faster elliptic curve cryptography on a large class of curves[END_REF]Theorem 2]).

While E ′ (F p 2 ) may have prime order, E(F p 2 ) cannot: the fixed points of π p form a subgroup of order p + 1 -t 0 , where t 2 0 -2p = t E (and the complementary subgroup has order p + 1 + t 0 ). Hence, the largest prime divisor of #E(F p 2 ) can be no larger than O(p); the curve E ′ can therefore never be twist-secure.

Short Scalar Decompositions

Before moving on to concrete families and examples, we will show that the endomorphisms developed in §3 yield short scalar decompositions.

Suppose

G ∼ = Z/N Z is a cyclic subgroup of E(F p 2 ) such that ψ(G) ⊆ G.
L := (N, 0), (-λ ψ , 1) ⊂ Z 2
is the lattice of decompositions of 0: that is, of integer pairs (a, b) such that a + bλ ψ ≡ 0 (mod N ).

We want to find a decomposition of m where a and b have minimal bitlength: that is, where ⌈log 2 (a, b) ∞ ⌉ is as small as possible. The following algorithm 8 computes an optimal decomposition of m given a reduced basis of L. Step 2 Let c be the shortest of the four vectors ⌊α⌋b 1 + ⌊β⌋b 2 , ⌊α⌋b 1 + ⌈β⌉b 2 , ⌈α⌉b 1 + ⌊β⌋b 2 , and ⌈α⌉b 1 + ⌈β⌉b 2 .

8 Algorithm 1 differs from the standard technique (cf. [17, §4]), based on Babai rounding [START_REF] Babai | On Lovasz' lattice reduction and the nearest lattice point problem[END_REF], in Step 2. Instead of choosing c to be the shortest of the four vectors, Babai rounding approximates it by selecting c ′ = ⌊α⌉e1 + ⌊β⌉e2 (this is the correct choice for most m). In terms of bitlength, this means an excess of one bit in the worst case.

Step 3 Return (a, b) := (m, 0)c.

Proof. It is easily checked that (α, β) is the unique solution in Q 2 to the linear system αb 1 + βb 2 = (m, 0) (here we use the fact that N = det L). Then c is the closest vector to (m, 0) in L by Theorem 19 of [START_REF] Kaib | The Gauss lattice basis reduction algorithm succeeds with any norm[END_REF], so (a, b) ∞ is minimal over all decompositions of m. For the bound on (a, b) ∞ , set c ′ := ⌊α⌉b 1 + ⌊β⌉b 2 ; then (m, 0)c ∞ ≤ (m, 0)c ′ ∞ . The triangle inequality and |x-⌊x⌉| ≤ 1/2 for all

x in Q imply (m, 0) -c ′ ∞ ≤ max( b 1 ∞ , b 2 ∞ ) = b 2 ∞ . ⊓ ⊔
It remains to precompute a reduced basis for L. If |λ ψ | is not unusually small, then there exists a reduced basis of size O( √ N ). 9 Traditionally, we would compute it using the Gauss reduction or Euclidean algorithms (cf. [START_REF] Kaib | The Gauss lattice basis reduction algorithm succeeds with any norm[END_REF], [17, §4] and [15, §17.1.1]), but in our case lattice reduction algorithms are unnecessary: following the approach outlined in [START_REF] Smith | Easy scalar decompositions for efficient scalar multiplication on elliptic curves and genus 2 Jacobians[END_REF], we can immediately write down a reduced basis for a large sublattice of L, which coincides with L when G = E(F p 2 ). If G has a small cofactor in E(F p 2 ), then we can easily modify the sublattice basis to give a proper reduced basis for L (as we will do in Lemmas 2, 3, and 4 below).

Lemma 1. The vectors e 1 = (p + ǫ p , -r) and e 2 = (-ǫ p dr, p

+ ǫ p ) generate a sublattice L 0 ⊆ L of index [L : L 0 ] = #E(F p 2 )/N . In particular, if #E(F p 2 ) = N , then L = L 0 . For large p, -if ǫ p = -1, then [e 1 , e 2 ] is reduced; -if ǫ p = 1, then [e 1 + e 2 , e 1 ] (if r > 0) or [e 1 -e 2 , e 1 ] (if r < 0) is reduced.
In either case, the bitlength of the reduced basis is ⌈log 2 (p + ǫ p )⌉.

Proof. Corollary (2) implies rλ ψ ≡ p + ǫ p and rǫ p d ≡ (p + ǫ p )λ ψ (mod N ), so e 1 and e 2 are in L; they are linearly independent, so they generate a sublattice. The determinant is (p + ǫ p ) 2 -ǫ p dr 2 , which is #E(F p 2 ) by Eq. [START_REF] Elkies | On elliptic k-curves[END_REF]. Recall that r is in O( √ p) and d is very small, so e 1 ∞ = e 2 ∞ = p + ǫ p . The bases satisfy Inequality [START_REF]Handbook of Magma functions[END_REF], and hence are reduced. ⊓ ⊔

5 Endomorphisms from Quadratic Q-curves of Degree 2

Let ∆ be a squarefree integer. Hasegawa defines a one-parameter family

E 2,∆,s : y 2 = x 3 + 2(C 2,∆ (s) -24)x -8(C 2,∆ (s) -16) of Q-curves of degree 2 over Q( √ ∆) in [20, Theorem 2.2],
where

C 2,∆ (s) := 9(1 + s √ ∆)
and s is a free parameter taking values in Q. Observe that σ E 2,∆,s = E 2,∆,-s .

To realise the Q-curve structure, observe that E 2,∆,s has a rational 2-torsion point (4, 0). We compute the normalized quotient isogeny E 2,∆,s → E 2,∆,s / (4, 0) using Eq. ( 2); but then we observe that E 2,∆,s / (4, 0) = ( σ E 2,∆,s ) √ -2 , so composing the quotient with the twisting isomorphism δ(1/ √ -2) yields a 2-isogeny

φ 2,∆,s : E 2,∆,s -→ σ E 2,∆,s
defined by the rational map

φ 2,∆,t : (x, y) -→ -x 2 - C 2,∆ (s) x -4 , y √ -2 -1 2 + C 2,∆ (s) (x -4) 2 .
(The arbitrary choice of one of the two square roots of -2 results in an arbitrary sign on φ 2,∆,s .) Conjugating and composing again, we find that

σ φ 2,∆,s • φ 2,∆,s = [ǫ2] E2,∆,s where ǫ = -1 if σ √ -2 = √ -2 +1 if σ √ -2 = - √ -2 (12)
-and similarly, φ 2,∆,s

• σ φ 2,∆,s = [ǫ2] σ E2,∆,s .
The discriminant of the family

E 2,∆,s is 2 9 • C 2,∆ (s) 2 • σ C 2,∆ (
s), and

j( E 2,∆,s ) = -12 3 (C 2,∆ (s) -24) 3 C 2,∆ (s) 2 • σ C 2,∆ (s)
(letting s → ∞, 10 we find j( E 2,∆,∞ ) = 1728). We see that E 2,∆,s reduces modulo any inert p > 3 to give a family of elliptic curves over F p 2 , and then every value of s in F p yields an elliptic curve over F p 2 . (Proposition 1 below shows that at most two of these curves are isomorphic.)

Theorem 2. Let p > 3 be prime, fix a nonsquare ∆ modulo p, so F p 2 = F p ( √ ∆), and let E 2,∆,s and φ 2,∆,s be the reductions modulo p of E 2,∆,s and φ 2,∆,s .

For each s in F p , the curve E 2,∆,s /F p 2 has an efficient F p 2 -endomorphism

ψ 2,∆,s := π p • φ 2,∆,s of degree 2p such that ψ 2 2,∆,s = [ǫ p 2]π E2,∆,s and (ψ ′ 2,∆,s ) 2 = [-ǫ p 2]π E ′ 2,∆,s
, where

ǫ p := --2 p = -1 if p ≡ 1, 3 (mod 8) , +1 if p ≡ 5, 7 (mod 8) .
10 "Letting s → ∞" has a proper technical meaning here (and also in §6, §8, and §9)even over finite fields. The parameter s is defined by Hasegawa's choice (following Fricke) of a rational parametrization of the modular curve X0(2): that is, a birational map between P 1 and X0(2). Under this parametrization, the point at infinity on P 1 corresponds to the isomorphism class of the 2-isogeny (in fact, the endomorphism) 1 + ι, where ι is an automorphism of order 4 of the curve with j-invariant 1728; this reflects what we find when we put s = ∞ in the formula for j( E2,∆,s).

There exists an integer r satisfying 2r 2 = 2p + ǫ p t E2,∆,s such that

[r]ψ 2,∆,s = [p] + ǫ p π E2,∆,s and [r]ψ ′ 2,∆,s = [p] -ǫ p π E ′ 2,∆,s ;
the characteristic polynomial of ψ 2,∆,s and ψ ′ 2,∆,s is P 2,∆,s (T ) = T 2 -2rT + 2p. In particular, if E 2,∆,s is ordinary and G ⊆ E 2,∆,s (F p 2 ) is a cyclic subgroup of order N such that ψ 2,∆,s (G) ⊆ G, then the eigenvalue of ψ 2,∆,s on G is λ 2,∆,s ≡ (p + ǫ p ) /r ≡ ± ǫ p 2 (mod N ) .

Proof. Apply Theorem 1 and Corollary 2 to φ 2,∆,s using Eq. ( 12).

⊓ ⊔ Proposition 1. If p > 7, then # j(E 2,∆,s ) : s ∈ F p = p if -7 is a square in F p , and p -1 otherwise.

Proof. Suppose j(E 2,∆,s1 ) = j(E 2,∆,s2 ), with s 1 = s 2 . Equating the j-invariants symbolically, we must have

F 0 (s 1 , s 2 ) = 2 √ ∆F 1 (s 1 , s 2 )
, where the polynomials

F 0 (T 1 , T 2 ) = (∆T 1 T 2 + 1)(81∆T 1 T 2 -175) + 49∆(T 1 + T 2 ) 2 and F 1 (T 1 , T 2 ) = (T 1 + T 2 )(63∆T 1 T 2 -65) have coefficients in F p . If s 1 and s 2 are in F p , then F 0 (s 1 , s 2 ) = F 1 (s 1 , s 2 ) = 0;
′ 2,∆,s . If #E 2,∆,s (F p 2 ) = 2 k N and #E ′ 2,∆,s (F p 2 ) = 2 k ′ N ′
with N and N ′ odd, then Eq. ( 1) modulo 8 implies that either k = k ′ = 1, or k = 2 and k ′ ≥ 3, or k ≥ 3 and k ′ = 2. Equation ( 11) modulo 3 implies that if p ≡ 2 (mod 3) then either E 2,∆,s (F p 2 ) or E ′ 2,∆,s (F p 2 ) contains a point of order 3.

Optimal decompositions. In view of the Pohlig-Hellman-Silver reduction [START_REF] Pohlig | An improved algorithm for computing logarithms over GF (p) and its cryptographic significance[END_REF] and the rational 2-torsion point on E 2,∆,s , the "optimal" situation for discretelog based cryptosystems is when E 2,∆,s (F p 2 ) ∼ = Z/2Z× G with #G prime (though for faster arithmetic, we may want a cofactor of 4 instead of 2; we consider this later). Lemma 2 constructs an optimal basis for the GLV lattice L in this case. We can use this basis in Algorithm 1 to decompose scalar multiplications in G as [m]P = [a]P ⊕ [b]ψ 2,∆,s (P ) where a and b have at most ⌈log 2 p⌉ bits.

Lemma 2. Suppose E 2,∆,s (F p 2 ) ∼ = Z/2Z × Z/N Z with N odd, and let L = (N, 0), (-λ 2,∆,s , 1) . Let e 1 and e 2 be defined as in Lemma 1. For large p,

-if ǫ p r ≥ 0, then [-e 2 /2, e 1 + e 2 /2] is a reduced basis for L; -if ǫ p r < 0, then [-e 2 /2, e 1 -e 2 /2
] is a reduced basis for L.

In either case, the bitlength of the reduced basis is ⌈log 2 (p + ǫ p -|r|)⌉.

Proof. Let L 0 := e 1 , e 2 with e 1 := (p + ǫ p , -r) and e 2 := (-ǫ p 2r, p + ǫ p ) as in Lemma 1; then [L : L 0 ] = 2, so exactly one of e 1 /2, e 2 /2, or (e 1 + e 2 )/2 is in L. Equation [START_REF] Elkies | On elliptic k-curves[END_REF] shows that 2N = (p + ǫ p ) 2 -2ǫ p r 2 with |r| < √ 2p; since N is odd, r must also be odd, so e 2 /2 is in Z 2 but e 1 /2 and (e 1 + e 2 )/2 are not-and hence they cannot be in L, either. We conclude that L = e 1 , e 2 /2 . Inequality ( 6

#E 2,-1,28106 (F p 2 ) = p 2 + 1 -t E2,-1,28106 = 2 • N and #E ′ 2,-1,28106 (F p 2 ) = p 2 + 1 + t E2,-1,28106 = 2 • N ′
where N and N ′ are 253-bit primes.11 Algorithm 1 and Lemma 2 transform 253bit scalar multiplications in E 2,-1,28106 (F p 2 )[N ] into 128-bit multiexponentations. This value of s is the "smallest" (counting upwards from 1) yielding a curve-twist pair such that both curve orders are twice a prime. The curve coefficients, being linear in s, are relatively small; but while small coefficients are important in optimized implementations, here this is no more than a happy coincidence-we did not explicitly search for an example with convenient coefficients.

B M 2,∆ (s) := (2C 2,∆ (s)) 1/2 and A M 2,∆ (s) := 12/B M 2,∆ (s) , the birational map (x, y) → (X/Z, Y /Z) = (x -4)/B M 2,∆ (s), y/B M 2,∆ (s) 2 takes
us from E 2,∆,s to the projective Montgomery model

E M 2,∆,s : B M 2,∆ (s)Y 2 Z = X X 2 + A M 2,∆ (
s)XZ + Z 2 (we may replace the term B M 2,∆ (s)Y 2 Z in the defining equation with a conveniently small multiple of Y 2 Z, if desired, by scaling the Y coordinate).

Montgomery models offer a particularly efficient arithmetic using only the X and Z coordinates [START_REF] Montgomery | Speeding the Pollard and Elliptic Curve Methods of factorization[END_REF]. The induced endomorphism on the (X : Z)-line is

ψ M 2,∆,s : (X : Z) -→ X 2p + A M 2,∆ (s) p X p Z p + Z 2p : -2A M 2,∆ (s) p-1 X p Z p ;
an implementation of fast scalar multiplication using ψ M 2,∆,s is detailed in [START_REF] Costello | Faster compact Diffie-Hellman: endomorphisms on the x-line[END_REF]. Twisted Edwards models. Every Montgomery model corresponds to a twisted Edwards model, and vice versa (cf. [START_REF] Bernstein | Twisted Edwards curves[END_REF] and [START_REF] Hisil | Twisted Edwards curves revisited[END_REF]). Indeed, E 2,∆,s is isomorphic to the twisted Edwards model ) if and only if E 2,∆,s has full rational 2-torsion. The optimal situation for discrete log-based cryptography on these curves is therefore when E 2,∆,s (F p 2 ) ∼ = (Z/2Z) 2 × G with #G prime. Lemma 3 gives a reduced basis for the GLV lattice in this case, which we can use in Algorithm 1 to decompose scalar multiplications in G as [m]P = [a]P ⊕ [b]ψ 2,∆,s (P ) where a and b have at most ⌈log 2 p⌉ -1 bits. Lemma 3. Suppose E 2,∆,s (F p 2 ) ∼ = (Z/2Z) 2 × Z/N Z with N odd, and let L = (N, 0), (-λ 2,∆,s , 1) . Let e 1 and e 2 be defined as in Lemma 1. For large p, -if ǫ p = 1 and r ≥ 0, then [(e 1 + e 2 )/2, e 2 /2] is a reduced basis for L; -if ǫ p = 1 and r < 0, then [(e 1e 2 )/2, -e 2 /2] is a reduced basis for L; -if ǫ p = -1 and r ≥ 0, then [e 1 /2, e 2 /2] is a reduced basis for L; -otherwise, if ǫ p = -1 and r < 0, then [e 1 /2, -e 2 /2] is a reduced basis for L.

E TE 2,∆,s : 12 + 2B M 2,∆ (s) x 2 1 + x 2 2 = 1 + 12 -2B M 2,∆ (s) x 2 1 x 2 2 via (x, y) → (x 1 , x 2 ) = (x -4)/y, (x -4 -B M 2,∆ (s))/(x -4 + B M 2,∆ (s)
In each case, the bitlength of the reduced basis is ⌈log 2 (p + ǫ p )⌉ -1.

Proof. The sublattice L 0 = e 1 , e 2 has index 4 in L. Equation ( 11) implies (p + ǫ p ) 2 ≡ 2ǫ p r 2 (mod 4), and since p + ǫ p is even, r must be even as well; so we can replace the relation ǫ p rλ 2,∆,s ≡ p + ǫ p with ǫ p (r/2)λ 2,∆,s ≡ (p + ǫ p )/2 (mod N ). Hence, both e 1 /2 and e 2 /2 are in L; so they must form a basis for L. The listed bases are combinations of e 1 /2 and e 2 /2 satisfying Ineq. ( 6), and are therefore reduced. The longest vector in each basis has length (p + ǫ p )/2.

⊓ ⊔ Doche-Icart-Kohel models. Doubling-oriented Doche-Icart-Kohel models are defined by equations of the form y 2 = x(x 2 + Dx + 16D). These curves have a rational 2-isogeny φ with kernel (0, 0) , and both φ and its dual φ † are in a special form that allows marginally faster doubling using the factorization [START_REF] Bernstein | Curve25519: new Diffie-Hellman speed records[END_REF] = φ † φ (see [10, §3.1] for details). Our curves E 2,∆,s come equipped with a rational 2-isogeny, so it is natural to try putting them in Doche-Icart-Kohel form. The same 2-isogeny plays two rôles in this situation: as a factor of our endomorphism for scalar decomposition, and as a factor of the doubling map for Doche-Icart-Kohel arithmetic. We emphasize that these two applications are distinct and complementary, and their benefits are cumulative. We have an isomorphism from E 2,∆,s to the Doche-Icart-Kohel model

E DIK 2,∆,s : v 2 = u u 2 + 1152 C2,∆(s) u + 16 • 1152 C2,∆(s) , defined by (x, y) → (u, v) = (α(x -4), α 3/2 y) where α = 96/C 2,∆ (s); if C 2,∆ (s) is not a square in F p 2 , then E DIK 2,∆,s is F p 2 -isomorphic to E ′ 2,∆,s .
6 Endomorphisms from Quadratic Q-curves of Degree 3

Let ∆ be a squarefree integer. Hasegawa defines a one-parameter family

E 3,∆,s : y 2 = x 3 -3(2C 3,∆ (s) + 1)x + C 3,∆ (s) 2 + 10C 3,∆ (s) -2 of Q-curves of degree 3 over Q( √ ∆) in [20, Theorem 2.2],
where

C 3,∆ (s) := 2(1 + s √ ∆)
and s is a free parameter taking values in Q. Observe that σ E 3,∆,s = E 3,∆,-s .

To realize the degree-3 Q-curve structure, note that x -3 defines an order-3 subgroup S = {0, (3,

± σ C 3,∆ (s))} of E 3,∆,s (Q( √ ∆)).
Computing the normalized quotient isogeny E 3,∆,s → E 3,∆,s /S using Eqs. ( 3), (4), and ( 5), we observe that E 3,∆,s /S = ( σ E 3,∆,s ) √ -3 ; so composing the quotient with δ(1/ √ -3) yields an explicit 3-isogeny φ 3,∆,s : E 3,∆,s → σ E 3,∆,s defined by the rational map

φ 3,∆,s : (x, y) -→ ( φ 3,∆,s ) x (x), y √ - 3
d( φ 3,∆,s ) x dx (x)
where

( φ 3,∆,s ) x (x) = - 1 3 x + 12 • σ C 3,∆ (s) x -3 + 4 • σ C 3,∆ (s) 2 (x -3) 2 .
Conjugating and composing again, we see that

σ φ 3,∆,s • φ 3,∆,s = ǫ[3] E3,∆,s where ǫ = -1 if σ √ -3 = √ -3 +1 if σ √ -3 = - √ -3 (13)
(and similarly, φ 3,∆,s

• σ φ 3,∆,s = ǫ[3] σ E3,∆,s ).
This family has discriminant 2

4 • 3 3 • C 3,∆ (s) • σ C 3,∆ (s) 3 and j-invariant j( E 3,∆,s ) = 2 8 • 3 3 • (2C 3,∆ (s) + 1) 3 C 3,∆ (s) • σ C 3,∆ (s) 3
(letting s → ∞, we see that j( E 3,∆,∞ ) = 0). Hence, E 3,∆,s reduces modulo any inert p > 3 to give a family of elliptic curves over F p 2 , and then every value of s in F p yields an elliptic curve over F p 2 . A calculation similar to Proposition 1 shows that we get at least p -8 non-isomorphic curves in this way.

Theorem 3. Let p > 3 be prime, fix a nonsquare ∆ modulo p, so F p 2 = F p ( √ ∆), and let E 3,∆,s and φ 3,∆,s be the reductions modulo p of E 3,∆,s and φ 3,∆,s .

For each s in F p , the curve E 3,∆,s /F p 2 has an efficient F p 2 -endomorphism

ψ 3,∆,s := π p • φ 3,∆,s of degree 3p, such that ψ 2 3,∆,s = [ǫ p 3]π E3,∆,s and (ψ ′ 3,∆,s ) 2 = [-ǫ p 3]π E ′ 3,∆,s
, where

ǫ p := --3 p = +1 if p ≡ 2 (mod 3) , -1 if p ≡ 1 (mod 3) .
There exists an integer r satisfying 3r 2 = 2p + ǫ p t E3,∆,s such that

[r]ψ 3,∆,s = [p] + ǫ p π E3,∆,s and [r]ψ ′ 3,∆,s = [p] -ǫ p π E3,∆,s ;
the characteristic polynomial of ψ 3,∆,s and ψ ′ 3,∆,s is P 3,∆,s (T ) = T 2 -3rT + 3p. In particular, if E 3,∆,s is ordinary and G ⊆ E 3,∆,s (F p 2 ) is a cyclic subgroup of order N such that ψ 3,∆,s (G) ⊆ G, then the eigenvalue of ψ 3,∆,s on G is λ 3,∆,s ≡ (p + ǫ p )/r ≡ ± ǫ p 3 (mod N ) .

Proof. Follows from Theorem 1 and Corollary 2 using Eq. ( 13).

⊓ ⊔

Optimal decompositions. The kernel of ψ 3,∆,s is generated by the rational points (3, ± σ C 3,∆ (s)), so #E 3,∆,s (F p 2 ) is always divisible by 3. However, the nontrivial points in the kernel of the twisted endomorphism ψ ′ 3,∆,s are not defined over F p 2 (they are conjugates), so it is possible for E ′ 3,∆,s (F p 2 ) to have prime order. From the point of view of the Pohlig-Hellman-Silver reduction, the "most secure" curves in E 3,∆,s /F p 2 have E 3,∆,s (F p 2 ) ∼ = Z/3Z × G, with G of prime order. Lemma 4 gives an optimal basis for the GLV lattice L in this case (for a prime-order twist, the basis of Lemma 1 is already optimal). Lemma 4. Suppose E 3,∆,s (F p 2 ) ∼ = Z/3Z × Z/N Z with N prime to 3, and let L = (N, 0), (-λ 3,∆,s , 1) . Let e 1 and e 2 be defined as in Lemma 1. For large p,

-if ǫ p r ≥ 0, then [e 2 /3, e 1 + 2e 2 /3] is a reduced basis of L; -if ǫ p r < 0, then [e 2 /3, e 1 -2e 2 /3] is a reduced basis of L.
In either case, the bitlength of the reduced basis is ⌈log 2 (p + ǫ p -2|r|)⌉.

Proof. The proof is essentially the same as for Lemma 2, with 3 in place of 2.

The sublattice e 1 , e 2 has index 3 in L, so exactly one of 1 3 e 1 , 1 3 e 2 , 1 3 (e 1 + e 2 ), and 1 3 (e 1e 2 ) is in L. Equation ( 11) gives 3N = (p + ǫ p ) 2 -3ǫ p r 2 ; but p ≡ -ǫ p (mod 3), so 1 3 e 2 is in Z 2 . On the other hand, 3 ∤ r (since otherwise 3 | N ), so neither 1 3 e 1 nor 1 3 (e 1 ± e 2 ) is in Z 2 . Hence e 1 , 1 3 e 2 is the only lattice in Z 2 containing e 1 , e 2 with index 3, so L = e 1 , 1 3 e 2 . The vectors 1 3 e 2 and e 1 ± 2e 2 /3 satisfy Ineq. [START_REF]Handbook of Magma functions[END_REF], so they form a reduced basis for L; the longest of their components is p + ǫ p -2|r|.

⊓ ⊔ Example 2. Let p = 2 127 -1; then ∆ = -1 is a nonsquare in F p . The parameter value s = 10400 yields a twist-secure curve at the 128-bit security level: #E 3,-1,10400 (F p 2 ) = 3 • N and #E ′ 3,-1,10400 (F p 2 ) = N ′ , where N and N ′ are 253and 254-bit primes, respectively. As in Example 1, this is the smallest value of s yielding a curve-twist pair with orders in this form. Any scalar multiplication in

E 3,-1,10400 (F p 2 )[N ] or E ′ 3,-1,10400 (F p 2 )[N ′
] can be computed via a 127-bit multiexponentiation using Algorithm 1 with the basis of Lemma 4. (We warn the reader that here, one of the curve coefficients is quadratic in s; so small values of s may not yield particularly convenient coefficients for serious implementations.) Doche-Icart-Kohel models. We can exploit the 3-isogeny on E 3,∆,s for faster tripling (cf. [10, §3.2]): E 3,∆,s is isomorphic to the tripling-oriented Doche-Icart-Kohel model

E DIK 3,∆,s : v 2 = u 3 + 3 • 9 C 3,∆ (s) p (u + 1) 2 via (x, y) → (u, v) = α(x -3), α 3/2 y where α := 3C 3,∆ (s) -p . This is an F p 2 - isomorphism if C 3,∆ (s) is a square in F p 2 ; otherwise, E DIK 3,∆,s ∼ =F p 2 E ′ 3,∆,s .
For d = 5, Hasegawa notes that it is impossible to give a universal Q-curve for arbitrary squarefree ∆: there exists a quadratic Q-curve of degree 5 over Q( √ ∆) if and only if 5 p i = 1 for every prime p i = 5 dividing ∆ (see [START_REF] Hasegawa | Q-curves over quadratic fields[END_REF]Proposition 2.3]). This restricts our choice of ∆ for a given p.

The special case ∆ = -1 is particularly interesting: by the above, there exists a family of Q-curves of degree 5 over Q( √ -1), and every prime p ≡ 3 (mod 4) is inert in Q( √ -1). We work this case out in detail below. The remaining case p ≡ 1 (mod 4) is a straightforward exercise: given a fixed prime p > 5, we choose a squarefree ∆ meeting the condition above, then apply [START_REF] Hasegawa | Q-curves over quadratic fields[END_REF]Theorem 2.4] to derive a family of degree-5 Q-curves over Q( √ ∆) amenable to the construction of §3.12 Of course, compared with d = 2 and 3, endomorphisms with separable degree d = 5 are intrinsically slower. The chief interest of this family is that unlike with d = 2 and 3, here neither the generic curve nor its twist have rational torsion points, so it is possible for reductions and their twists to both have prime order.

Let E 5,-1,s be the family of elliptic curves over Q( √ -1) defined by

E 5,-1,s : y 2 = x 3 + A 5,-1 (s)x + B 5,-1 (s)
where

A 5,-1 (s) := -27s(11s -2) 3(6s 2 + 6s -1) -20s(s -1) √ -1 , B 5,-1 (s) := 54s 2 (11s -2) 2 (13s 2 + 59s -9) -2(s -1)(20s + 9) √ -1 ,
and s is a free parameter taking values in Q.

The family E 5,-1,s is a family of Q-curves of degree 5: the polynomial

(1 + 2 √ -1)(x -3s(11s -2)(2 - √ -1)) 2 + 81s(11s -2)(1 + s √ -1) 2
defines the kernel S of a 5-isogeny φ 5,-1,s : E 5,-1,s → σ E 5,-1,s over Q( √ -1), which is the composition of the normalized quotient E 5,-1,s → E 5,-1,s /S (as in Eqs. (3), (4), and ( 5)) with the twisting isomorphism δ(5/(1 + 2 √ -1)). Conjugating and composing again, we find

The family has discriminant -2 6 3 12 s 3 (11s -2) 3 (1 + s 2 )(1 + s √ -1) 4 , and

j( E 5,-1,s ) = -64 3(6s 2 + 6s -1) -20(s 2 -s) √ -1 3 (1 + s 2 )(1 + s √ -1) 4 .
Hence, E 5,-1,s is an elliptic curve for all s in Q \ {0, 2/11}, and these E 5,-1,s have good reduction at any p > 5 inert in Q( √ -1). The analogue of Proposition 1 shows that we get at least p -25 non-isomorphic curves in this way. Theorem 4. Let p be a prime congruent to 3 modulo 4, so F p 2 = F p ( √ -1), and let E 5,-1,s and φ 5,-1,s be the reductions mod p of E 5,-1,s and φ 5,-1,s .

For each s = 0 or 2/11 in F p , the curve E 5,-1,s /F p 2 has an efficient F p 2endomorphism ψ 5,-1,s := π p • φ 5,-1,s

of degree 5p such that ψ 2 5,-1,s = [5]π E5,-1,s and (ψ ′ 5,-1,s ) 2 = [-5]π E ′ 5,-1,s . There exists an integer r satisfying 5r 2 = 2p + t E5,-1,s such that Proof. Follows from Theorem 1 and Corollary 2 using Eq. ( 14).

⊓ ⊔

Reductions of curves in E 5,-1,s may have prime order, and so can their twists. In this situation, Algorithm 1 with the basis of Lemma 1 computes optimal scalar decompositions for ψ 5,-1,s (of bitlength at most ⌈log 2 (p + 1)⌉).

Example 3. Let p = 2 127 -1 and ∆ = -1. Taking s = 7930 in the degree-5 family yields a twist-secure curve at the 128-bit security level: the trace of E 5,-1,7930 is t E2,-1,28106 = 160084314926568661653252069280514036151 , so #E 5,-1,7930 (F p 2 ) and #E ′ 5,-1,7930 (F p 2 ) are both 254-bit primes. We transform 254-bit scalar multiplications in E 5,-1,7930 (F p 2 ) into a 127-bit multiexponentiations using Algorithm 1 with the basis of Lemma 1. As in Examples 1 and 2, this is the smallest value of s yielding a curve-twist pair with both curves of prime order. (Here the curve coefficients are quartic and sextic in s, so the smallness of s has little effect on the convenience of the coefficients for implementationshowever, as we remarked above, this family is essentially of theoretical interest.)

8 Endomorphisms from Quadratic Q-curves of Degree 7

For completeness, we include a family of Q-curves of degree 7. These curves are less interesting for practical applications, since the higher degree renders the endomorphism intrinsically slower than the curves with d = 2, 3, and 5.

Let ∆ be a squarefree integer. Hasegawa defines a one-parameter family

E 7,∆,s : y 2 = x 3 + A 7,∆ (s)x + B 7,∆ (s) of Q-curves of degree 7 over Q( √ ∆) in [20, Theorem 2.2],
where The family E 7,∆,s is a family of quadratic Q-curves of degree 7. More explicitly: E 7,∆,s has a subgroup S of order 7 defined by the kernel polynomial

A 7,∆ (s) = -3C
(x -C 7,∆ (s)) 3 -4 2 (1 -s √ ∆) 2 C 7,∆ (s) 3(x -C 7,∆ (s)) + 4(1 -s √ ∆)(27 + s √ ∆) .
While S is defined over Q( √ ∆), none of its nontrivial points are. Computing the normalized quotient E 7,∆,s → E 7,∆,s /S (using Eqs. ( 3), (4), and ( 5)) and composing with the twisting isomorphism δ(1/ √ -7) yields an explicit 7-isogeny φ 7,∆,s : E 7,∆,s → E 7,∆,s . Conjugating and composing again, we see that

σ φ 7,∆,s • φ 7,∆,s = [ǫ7] E7,∆,s where ǫ = -1 if σ √ -7 = √ -7 +1 if σ √ -7 = - √ -7 (15)
(and similarly, φ 7,∆,s 6 , and

• σ φ 7,∆,s = [ǫ7]σ E7,∆,s ). The discriminant of E 7,∆,s is 2 12 • 3 6 • 7 • C 7,∆ (s) 2 (1 -s 2 ∆)(1 -s √ ∆)
j E 7,∆,s = (27 + s 2 ∆) 85 + 96s √ ∆ + 15s 2 ∆ 3 (1 -s 2 ∆)(1 -s √ ∆) 6
(letting s → ∞, we find j( E 7,∆,∞ ) = -3375); so E 7,∆,s reduces modulo any inert p > 7 to give a family of elliptic curves E 7,∆,s /F p 2 , and then any value of s in F p such that s 2 = -27/∆ yields an elliptic curve over F p 2 . A calculation similar to Proposition 1 shows that we get at least p -48 non-isomorphic curves in this way, when p is sufficiently large.

Theorem 5. Let p > 7 be prime, fix a nonsquare ∆ modulo p, so F p 2 = F p ( √ ∆), and let E 7,∆,s and φ 7,∆,s be the reductions modulo p of E 7,∆,s and φ 7,∆,s .

For each s in F p such that s 2 = -27/∆, the curve E 7,∆,s /F p 2 has an efficient F p 2 -endomorphism ψ 7,∆,s := π p • φ 7,∆,s of degree 7p satisfying There exists an integer r satisfying 7r 2 = 2p + ǫ p t E7,∆,s such that

[r]ψ 7,∆,s = [p] + ǫ p π E7,∆,s and [r]ψ ′ 7,∆,s = [p] -ǫ p π E7,∆,s ; the characteristic polynomial of ψ 7,∆,s and ψ ′ 7,∆,s is P 7,∆,s (T ) = T 2 -7rT + 7p. In particular, if E 7,∆,s is ordinary and G ⊆ E 7,∆,s (F p 2 ) is a cyclic subgroup of order N such that ψ 7,∆,s (G) ⊆ G, then the eigenvalue of ψ 7,∆,s on G is λ 7,∆,s ≡ (p + ǫ p ) /r ≡ ± ǫ p 7 (mod N ) .
Proof. Follows from Theorem 1 and Corollary 2 using Eq. [START_REF] Galbraith | Mathematics of public key cryptography[END_REF].

⊓ ⊔

By definition, Q-curves do not have CM. However, if E s is a family of Q-curves then some isolated curves in E s may have CM. These exceptional curves are of interest for 4-dimensional scalar decompositions: they form a natural generalization of the GLV+GLS curves described by Longa and Sica [START_REF] Longa | Four-dimensional Gallant-Lambert-Vanstone scalar multiplication[END_REF]. Briefly: if E/Q( √ ∆) has CM by an order of small discriminant, then we can compute an explicit endomorphism ρ of E of small degree (using Stark's algorithm [START_REF] Stark | Class numbers of complex quadratic fields[END_REF], say), which then yields an efficient endomorphism ρ on the reduction E of E modulo p, exactly as in the GLV construction. If E is d-isogenous to σ E and p is inert in Q( √ ∆), then E also has the degree-dp endomorphism ψ constructed in §3. The endomorphisms [START_REF] Babai | On Lovasz' lattice reduction and the nearest lattice point problem[END_REF], ρ, ψ, and ρψ may then be used as a basis for the 4-dimensional decomposition techniques elaborated in [START_REF] Longa | Four-dimensional Gallant-Lambert-Vanstone scalar multiplication[END_REF].

Practical limitations of 4-dimensional decompositions. "Q-curves with CM" inherit the chief drawback of the GLV construction: as noted in §1, we cannot hope to find secure (and twist-secure) curves when p is fixed. This scarcity of secure curves is easily explained: reductions of CM endomorphisms (including GLV endomorphisms) are separable, and efficient separable endomorphisms have extremely small degree, so that their (dense) defining polynomials can be evaluated quickly. 13 But the degree of an endomorphism is the norm of the corresponding CM-order element; and to have non-integers of very small norm, the CM-order must have a tiny discriminant. Up to twists, the number of elliptic curves with CM discriminant -D is the class number h(-D) (which is asymptotically in O( √ D)). The six orders containing endomorphisms of degree ≤ 3 have class number 1, and hence only one corresponding j-invariant. For -D = -4, corresponding to j = 1728, there are two or four F p 2 -isomorphism classes; for -D = -3, corresponding to j = 0, we have two or six; and otherwise we have only two. In particular, there are at most 18 pairwise non-isomorphic curves over F p 2 with a nontrivial endomorphism of degree at most 3.

Over a fixed finite field, the probability that any of these curves will have a secure group order, let alone be twist-secure, is very low: roughly speaking, we expect to try O(log 2 p) random curves over F p 2 before finding a twist-secure one (see [START_REF] Shparlinski | Distribution of elliptic twin primes in isogeny and isomorphism classes[END_REF], for example, for more accurate heuristics). In practice, then, we cannot use these curves when p is fixed for efficiency. Higher-dimensional scalar decomposition speedups therefore come at the cost of suboptimal field arithmetic: we pay for shorter loop lengths with comparatively slower field (and hence group) operations, to say nothing of a more complicated multiexponentiation algorithm.

We must therefore choose between 4-dimensional decompositions and faster underlying field arithmetic. Here we have chosen the latter, so we do not treat CM curves in depth. However, we enumerate the exceptional CM curves in our families in Theorem 6, to provide a convenient source of curves for readers interested in exploring and implementing 4-dimensional techniques.

Exceptional CM curves. Any one-dimensional family of Q-curves has only finitely many exceptional CM curves, up to isomorphism, and it is easy to compute them. 3. The only CM fibres in E 5,-1,s are E 5,-1,1 (defined over Q) and E 5,-1,-9/13 ; both have j-invariant 66 3 and CM by the order of discriminant -4 • 2 2 . 4. The following table lists the CM fibres in E 7,∆,s .

s √ ∆ -D 0 f 2 s √ ∆ -D 0 f 2 ∞ -7 • 1 2 ± √ 5 -35 • 1 2 0 -7 • 2 2 ± 1 3 √ 13 -91 • 1 2 ± 1 3 √ 7 -7 • 4 2 ± 5 39 √ 61 -427 • 1 2
Proof. Suppose E/Q( √ ∆) is isogenous to σ E. If E has CM by the order of discriminant -D 0 f 2 , then so does σ E; hence, both j( E) and σ j( E) = j( σ E) are roots of the Hilbert class polynomial H -D0f 2 . But H -D0f 2 is irreducible over Q, so either H -D0f 2 (T ) = T -j( E) with j( E) = j( σ E) in Q, or H -D0f 2 (T ) = (T -j( E))(T -j( σ E)). Tables 1 and2 list every quadratic imaginary discriminant -D 0 f 2 such that deg H -D0f 2 (which is the class number h(-D 0 f 2 )) is 1 or 2, along with the associated j-invariants: these can be found in the Echidna database [START_REF] Kohel | Echidna databases for elliptic curves and higher dimensional analogues[END_REF], or (re)computed using Magma ( [START_REF]Handbook of Magma functions[END_REF], [START_REF]The Magma computational algebra system[END_REF]) or Sage [START_REF] Stein | Sage Mathematics Software. The Sage Development Team[END_REF]. To find the exceptional CM curves in each of our families, we solve for rational s and squarefree ∆ such that the j-invariant of the family appears in Table 1 or Table 1. The thirteen quadratic imaginary discriminants -D0f 2 of class number 1, together with the j-invariants of the elliptic curves over Q with CM by the quadratic order of each discriminant.

-D0f 2 j-invariant -D0f 2 j-invariant -D0f 2 j-invariant -D0f 2 j-invariant

-3 • 1 2 0 -4 • 1 2 12 3 -8 • 1 2 20 3 -43 • 1 2 -960 3 -3 • 2 2 2 • 30 3 -4 • 2 2 66 3 -11 • 1 2 -2 15 -67 • 1 2 -5280 3 -3 • 3 2 -3 • 20 3 -7 • 1 2 -15 3 -19 • 1 2 -96 3 -163 • 1 2 -640320 3 -7 • 2 2 255 3

  [m]P = [a]P ⊕ [bλ ψ ]P = [a]P ⊕ [b]ψ(P )

  Corollary 2 shows that ψ acts as the eigenvalue λ ψ ≡ (p + ǫ p )/r (mod N ) (a square root of ǫ p d) on G. Given an integer m, we want to compute a decomposition m = a + bλ ψ (mod N ) so as to efficiently compute [m]P = [a]P ⊕[b]ψ(P ) for P in G. The decomposition is not unique: far from it. The set of all decompositions (a, b) of m is the lattice coset (m, 0) + L, where

Algorithm 1

 1 Given a reduced basis [b 1 , b 2 ] for L, computes a decomposition of minimal bitlength (and bitlength at most ⌈log 2 b 2 ∞ ⌉) for any given integer m. Input An integer m and a reduced basis [b 1 , b 2 ] for L = (N, 0), (-λ ψ , 1) . Output A pair of integers (a, b) such that m ≡ a + bλ ψ (mod N ) Step 1 Let α := mb 22 /N and β := -mb 12 /N .

Example 1 .

 1 ) is satisfied by b 1 := -e 2 /2 and b 2 := e 1 ± e 2 /2 (with the sign chosen according to whether ǫ p r is positive or negative), so [b 1 , b 2 ] is a reduced basis for L. The longer of the vectors is b 2 , and b 2 ∞ = p + ǫ p -|r|. ⊓ ⊔ Let p = 2 127 -1 and ∆ = -1. Taking s = 28106 in the family E 2,-1,s /F p ( √ ∆) yields a twist-secure curve at the 128-bit security level: we have ǫ p = 1 and t E2,-1,28106 = -272082382382015736940757543628153813996, so

σ φ 5 ,

 5 ∆,s • φ 5,∆,s = [5] E5,∆,s and φ 5,∆,s • σ φ 5,∆,s = [5]σ E5,∆,s .

[r]ψ 5 ,

 5 -1,s = [p] + π E5,-1,s and [r]ψ ′ 5,-1,s = [p] -π E5,-1,s ; the characteristic polynomial of ψ 5,-1,s and ψ ′ 5,-1,s is P 5,-1,s (T ) = T 2 -5rT +5p.In particular, if E 5,-1,s is ordinary and G ⊆ E 5,-1,s (F p 2 ) is a cyclic subgroup of order N such that ψ 5,-1,s (G) ⊆ G, then the eigenvalue of ψ 5,-1,s on G is λ 5,-1,s ≡ (p + 1)/r ≡ ± √ 5 (mod N ) .

ψ 2 7 ,

 7 ∆,s = [ǫ p 7]π E7,∆,s and (ψ ′ 3,∆,s ) 2 = [-ǫ p 7]π E ′ 7,∆,s where ǫ p := --7 p = +1 if p ≡ 3, 5, 6 (mod 7) , -1 if p ≡ 1, 2, 4 (mod 7) .

Theorem 6 .

 6 The exceptional CM curves in the families E 2,∆,s , E 3,∆,s , E 5,-1,s , and E 7,∆,s are as follows. (In each table, if s √ ∆ takes the given value then E d,∆,s

3 2 3 .

 33 2. ⊓ ⊔ Theorem 6 gives a simple alternative construction for some of the curves investigated by Guillevic and Ionica in [19]: the curves E 1,c and E 2,c of [19, §2] are E √ ,∆,s with c = s √ ∆ and E 3,∆,s with c = -2s √ ∆, respectively. The 255-bit curve of [19, Ex. 1] is a twist of E 2,5,4/9 by √ This curve is not twist-secure.

  this happens if and only if s 2 = -s 1 and either

	s i	√ ∆ = ±1 (which is impossible) or ± 5 9	√ -7, whence the result.

⊓ ⊔ Both E 2,∆,s (F p 2 ) and E ′ 2,∆,s (F p 2

) contain points of order 2: they generate the kernels of ψ 2,∆,s and ψ

  Montgomery models. The curve E 2,∆,s has a Montgomery model over F p 2 if and only if 2C 2,∆ (s) is a square in F p 2 by [34, Proposition 1]-or equivalently, if 1 + s

√ ∆ is a square in F p 2 (since 2 is always a square in F p 2 ). Setting

  ) . Composing with ψ 2,∆,s yields an endomorphism ψ TE 2,∆,s of E TE 2,∆,s . Optimal decompositions for cofactor 4. Every curve with a twisted Edwards or Montgomery model has order divisible by 4; indeed, C 2,∆ (s) is a square in F p 2 (so E M 2,∆,s and E TE 2,∆,s are defined over F p 2

  and s is a free parameter taking values in Q. Observe that σ E 7,∆,s = E 7,∆,-s .

	7,∆ (s)(85 + 96s B 7,∆ (s) = 14C 7,∆ (s) 9(3s 4 ∆ 2 + 130s 2 ∆ + 171) + 16(9s 2 ∆ + 163)s √ ∆ + 15s 2 ∆) ,	√ ∆ ,
	C 7,∆ (s) = 7(27 + s 2 ∆) ,

Table 2 .

 2 The twenty-nine quadratic imaginary discriminants -D0f 2 of class number 2, together with the j-invariants of the elliptic curves over Q with CM by the quadratic order of each discriminant.

	-D0f 2 j-invariants -3 • 4 2 12 • 15 3 (35010 ± 20213 √ -3 • 5 2 -96 3 (369830 ± 165393 √ 3) 5) -3 • 7 2 -3 • 480 3 (52518123 ± 11460394 √ -4 • 3 2 3 • 4 3 (399849 ± 230888 √ 3) -4 • 4 2 2 • 3 3 (761354780 ± 538359129 √ 2) 21) -4 • 5 2 12 3 (12740595841 ± 5697769392 √ 5) -7 • 4 2 15 3 (40728492440 ± 15393923181 √ 7) -8 • 2 2 10 3 (26125 ± 18473 √ 2) -8 • 3 2 20 3 (23604673 ± 9636536 √ 6) -11 • 3 2 -44 • 16 3 (104359189 ± 18166603 √ 33) -15 • 1 2 -5 • 3 3 (1415 ± 637 √ 5)/2 -15 • 2 2 5 • 3 3 (274207975 ± 122629507 √ 5)/2 -20 • 1 2 5 • 4 3 (1975 ± 884 √ 5) -24 • 1 2 12 3 (1399 ± 988 √ 2) -35 • 1 2 -5 • 32 3 (360 ± 161 √ 5) -40 • 1 2 5 • 12 3 (24635 ± 11016 √ 5) -51 • 1 2 -4 • 48 3 (6263 ± 1519 √ 17) -52 • 1 2 60 3 (15965 ± 4428 √ 13) -88 • 1 2 60 3 (14571395 ± 10303524 √ 2) -91 • 1 2 -96 3 (5854330 ± 1623699 √ 13) -115 • 1 2 -5 • 96 3 (48360710 ± 21627567 √ 5) -123 • 1 2 -480 3 (6122264 ± 956137 √ 41) -148 • 1 2 60 3 (91805981021 ± 15092810460 √ 37) -187 • 1 2 -68 • 240 3 (2417649815 ± 586366209 √ -232 • 1 2 60 3 (1399837865393267 ± 259943365786104 17) √ -235 • 1 2 -5 • 1056 3 (69903946375 ± 31261995198 √ 5) -267 • 1 2 -4 • 240 3 (177979346192125 ± 18865772964857 29) √ -403 • 1 2 -480 3 (11089461214325319155 ± 3075663155809161078 89) √ -427 • 1 2 -5280 3 (53028779614147702 ± 6789639488444631 √ 61)	13)

We are primarily interested in the large characteristic case, where q = p or p 2 , so we do not discuss τ -adic or Frobenius expansion-style techniques (see[START_REF] Smart | Elliptic curve cryptosystems over small fields of odd characteristic[END_REF],[28, §5]).

While our curves are defined over an extension field, the extension degree is only 2, so Weil descent attacks offer no advantage when solving DLP instances (cf.[16, §9]).

The reader unfamiliar with modular curves can get away with the following here: the modular curve X0(d) parametrizes isomorphism classes of (cyclic) d-isogenies. If d is prime-which is the only case we need here-then there is a unique Atkin-Lehner involution ω on X0(d): its action corresponds to exchanging isogenies φ with their duals φ † . The quotient X0(d) → X * (d) := X0(d)/ ω is a double cover, mapping (the isomorphism class of) an isogeny φ to the pair (of isomorphism classes) {φ, φ † }.

Especially since Q-curves (by definition) have no non-integer endomorphisms, while every elliptic curve over F p 2 has complex multiplication.

General bounds on the constant hidden by the O(•) appear in[START_REF] Sica | Analysis of the Gallant-Lambert-Vanstone method based on efficient endomorphisms: Elliptic and hyperelliptic curves[END_REF], but they are far from tight for inseparable endomorphisms. Lemma 1 gives much better results for our endomorphisms in cryptographic contexts.

We computed the traces for all of our examples using a new specialized variant of the SEA algorithm[START_REF] Schoof | Elliptic curves over finite fields and the computation of square roots mod p[END_REF] under development with François Morain and Charlotte Scribot, implemented in NTL[START_REF] Shoup | Number Theory Library[END_REF].

In[START_REF] Smith | Families of fast elliptic curves from Q-curves[END_REF], the author suggested that for any p ≡ 1 (mod 4) one could use ∆ = -11 with Hasegawa's parameters in[START_REF] Hasegawa | Q-curves over quadratic fields[END_REF] Table 6] in the construction of §3. This is incorrect: by Dirichlet's theorem, half of the p ≡ 1 (mod 4) are not inert in Q( √ -11).

By dense, we mean that these polynomials have many nonzero terms; the cost of their evaluation therefore depends linearly on the degree.