Doctor of Philosophy / The Hecke character of an abelian variety A/F is an isogeny invariant and the Galois action is such that A is isogenous to its Galois conjugate A^σ if and only if the corresponding Hecke character is fixed by σ. The quadratic twist of A by an extension L/F corresponds to multiplication of the associated Hecke characters. This leads us to investigate the Galois groups of families of quadratic extensions L/F with restricted ramification which are normal over a given subfield k of F. Our most detailed results are given for the case where k is the field of rational numbers and F is a field of definition for an elliptic curve with complex multiplication by K. In this case the groups which occur as Gal(L/K) are closely related to the 4-torsion of the class group of K. We analyze the structure of the local unit groups of quadratic fields to find conditions for the existence of curves with good reduction everywhere. After discussing the question of finding models for curves of a given Hecke character, we use twists by 3-torsion points to give an algorithm for constructing models of curves with known Hecke character and good reduction outside 3. The endomorphism algebra of the Weil restriction of an abelian variety A may be determined from the Grössencharacter of A. We describe the computation of these algebras and give examples in which A has dimension 1 or 2 and its Weil restriction has simple abelian subvarieties of dimension ranging between 2 and 24.

Doctor of Philosophy / The Hecke character of an abelian variety A/F is an isogeny invariant and the Galois action is such that A is isogenous to its Galois conjugate A^σ if and only if the corresponding Hecke character is fixed by σ. The quadratic twist of A by an extension L/F corresponds to multiplication of the associated Hecke characters. This leads us to investigate the Galois groups of families of quadratic extensions L/F with restricted ramification which are normal over a given subfield k of F. Our most detailed results are given for the case where k is the field of rational numbers and F is a field of definition for an elliptic curve with complex multiplication by K. In this case the groups which occur as Gal(L/K) are closely related to the 4-torsion of the class group of K. We analyze the structure of the local unit groups of quadratic fields to find conditions for the existence of curves with good reduction everywhere. After discussing the question of finding models for curves of a given Hecke character, we use twists by 3-torsion points to give an algorithm for constructing models of curves with known Hecke character and good reduction outside 3. The endomorphism algebra of the Weil restriction of an abelian variety A may be determined from the Grössencharacter of A. We describe the computation of these algebras and give examples in which A has dimension 1 or 2 and its Weil restriction has simple abelian subvarieties of dimension ranging between 2 and 24.

This thesis aims to prove the following statement, where the Weierstrass p-function has algebraic invariants and complex multiplication by Q(alpha): "If beta_1,..., beta_n are algebraic numbers which are linearly independent over Q(alpha), then p(beta_1),...,p(beta_n) are algebraically independent over Q." This was proven by Philippon in 1983, and the proof in this thesis follows his ideas. The difference lies in the strength of the tools used, allowing certain arguments to be simplified. This thesis shows that the above result is equivalent to imposing the restriction (beta_1,...,beta_n)=(1,beta,...,beta^{n-1}), where n=[Q(alpha,beta):Q(alpha)]. The core of the proof consists of developing height estimates, constructing representations for morphisms between products of elliptic curves, and finding height and degree estimates on large families of polynomials which are small at a point in Q(alpha,beta,g_2,g_3)(p(1),p'(1),...,p(beta^{n-1}),p'(beta^{n-1})). An application of Philippon's zero estimate (1986) and his criterion of algebraic independence (1984) is then used to obtain the main result.

Thesis (PhD)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: This thesis deals with a function eld analog of the André-Oort conjecture. The (classical) André-Oort conjecture concerns the distribution of special points on Shimura varieties. In our case we consider the André-Oort conjecture for special points in the product of Drinfeld modular varieties. We in particular manage to prove the André- Oort conjecture for subvarieties in a product of two Drinfeld modular surfaces under a characteristic assumption. / AFRIKAANSE OPSOMMING: Hierdie tesis handel van 'n funksieliggaam analoog van die André-Oort Vermoeding. Die (Klassieke) André-Oort Vermoeding het betrekking tot die verspreiding van spesiale punte op Shimura varietiete. Ons geval beskou ons die André-Oort Vermoeding vir spesiale punte op die produk Drinfeldse modulvarietiete. In die besonders, bewys ons die André-Oort Vermoeding vir ondervarieteite van 'n produk van twee Drinfeldse modulvarietiete, onderhewig aan 'n karakteristiek-aanname.

À partir du théorème d’André en 1998, qui est la première contribution non triviale à la conjecture de André-Oort sur les sous-variétés spéciales des variétés de Shimura, la principale problématique de cette thèse est d’étudier les propriétés diophantiennes des modules singuliers, en caractérisant les points de multiplication complexe (x; y) satisfaisant un type d’équation donné de la forme F(x; y) = 0, pour un polynôme irréductible F(X; Y ) à coefficients complexes. Plus spécifiquement, nous traitons deux équations impliquant des puissances de modules singuliers. D’une part, nous montrons que deux modules singuliers x; y tels que les nombres 1, xm et yn soient linéairement dépendants sur Q, pour des entiers strictement positifs m; n, doivent être de degré au plus 2, ce qui généralise un résultat d’Allombert, Bilu et Pizarro-Madariaga, qui ont étudié les points de multiplication complexe appartenant aux droites de C2 définies sur Q. D’autre part, nous montrons que, sauf cas “évidents”, le produit de n’importe quelles puissances entières de deux modules singuliers ne peut être un nombre rationnel non nul, ce qui généralise un résultat de Bilu, Luca et Pizarro- Madariaga, qui ont ont étudié les points de multiplication complexe appartenant aux hyperboles xy = A, où A 2 Qx. Les méthodes que nous développons reposent en grande partie sur les propriétés des corps de classes engendrés par les modules singuliers, les estimations de la fonction j-invariant et les estimations des formes linéaires logarithmiques. Nous déterminons également les corps engendrés par les sommes et les produits de deux modules singuliers x et y : nous montrons que le corps Q(x; y) est engendré par la somme x + y, à moins que x et y soient conjugués sur Q, auquel cas x + y engendre un sous-corps de degré au plus 2 ; le même résultat demeure pour le produit xy. Nos preuves sont assistées par le logiciel PARI/GP, que nous utilisons pour procéder à des vérifications dans des cas particuliers explicites. / Starting for André’s Theorem in 1998, which is the first non-trivial contribution to the celebrated André-Oort conjecture on the special subvarieties of Shimura varieties, the main purpose of this thesis is to study Diophantine properties of singular moduli, by characterizing CM-points (x; y) satisfying a given type of equation of the form F(x; y) = 0, for an irreducible polynomial F(X; Y ) with complex coefficients. More specifically, we treat two different equations involving powers of singular moduli. On the one hand, we show that two distinct singular moduli x; y such that the numbers 1, xm and yn are linearly dependent over Q, for some positive integers m; n, must be of degree at most 2. This partially generalizes a result of Allombert, Bilu and Pizarro-Madariaga, who studied CM-points belonging to straight lines in C2 defined over Q. On the other hand, we show that, with “obvious” exceptions, the product of any two powers of singular moduli cannot be a non-zero rational number. This generalizes a result of Bilu, Luca and Pizarro-Madariaga, who studied CM-points belonging to hyperbolas xy = A, where A 2 Qx. The methods we develop lie mainly on the properties of ring class fields generated by singular moduli, on estimations of the j-function and on estimations of linear forms in logarithms. We also determine fields generated by sums and products of two singular moduli x and y : we show that the field Q(x; y) is generated by the sum x + y, unless x and y are conjugate over Q, in which case x + y generate a subfield of degree at most 2 ; the same holds for the product xy. Our proofs are assisted by the PARI/GP package, which we use to proceed to verifications in particular explicit cases.

Nous démontrons une version pour la caractéristique p d'un cas spécial de la conjecture d'André-Oort. Plus précisement, soit Z le produit de n courbes modulaires de Drinfeld, et soit X une sous-variété algébrique irréductible de Z. Alors nous démontrons que X contient un ensemble Zariski-dense de points CM (c.a.d. points correspondant aux n-uples de A-modules de Drinfeld de rang 2 avec mulitplications complexes, où A=F_q[T], et q est une puissance d'un nombre prémier impair) si et seulement si X est une sous-variété dite modulaire. Notre approche répose sur une approche (en caractéristique 0) due à Edixhoven.

In this thesis, we explore the pairing-based cryptography on elliptic curves from the theoretical and implementation point of view. In this respect, we first study so-called pairing-friendly elliptic curves used in pairing-based cryptography. We classify these curves according to their construction methods and study them in details. Inspired of the work of Koblitz and Menezes, we study the elliptic curves in the form $y^{2}=x^{3}-c$ over the prime field $F_{q}$ and compute explicitly the number of points $#E(mathbb{F}_{q})$. In particular, we show that the elliptic curve $y^{2}=x^{3}-1$ over $mathbb{F}_{q}$ for the primes $q$ of the form $27A^{2}+1$ has an embedding degree $k=1$ and belongs to Scott-Barreto families in our classification. Finally, we give examples of those primes $q$ for which the security level of the pairing-based cryptographic protocols on the curve $y^{2}=x^{3}-1$ over $mathbb{F}_{q}$ is equivalent to 128-, 192-, or 256-bit AES keys. From the implementation point of view, it is well-known that one of the most important part of the pairing computation is final exponentiation. In this respect, we show explicitly how the final exponentiation is related to the linear recurrence relations. In particular, this correspondence gives that finding an algoritm to compute final exponentiation is equivalent to finding an algorithm to compute the $m$-th term of the associated linear recurrence relation. Furthermore, we list all those work studied in the literature so far and point out how the associated linear recurrence computed efficiently.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第24389号 / 理博第4888号 / 新制||理||1699(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 玉川 安騎男, 教授 並河 良典, 教授 望月 新一 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM

Let K be an imaginary quadratic field with class number one and let [Special characters omitted.] be a degree one prime ideal of norm p not dividing 6 d K . In this thesis we generalize an algorithm of Schoof to compute the class number of ray class fields [Special characters omitted.] heuristically. We achieve this by using elliptic units analytically constructed by Stark and the Galois action on them given by Shimura's reciprocity law. We have discovered a very interesting phenomena where p divides the class number of [Special characters omitted.] . This is a counterexample to the elliptic analogue of a well-known conjecture, namely the Vandiver's conjecture.

Με την αύξηση της χρήσης του διαδικτύου σε εφαρμογές από απλή μεταφορά δεδομένων μέχρι ηλεκτρονικό εμπόριο, υπάρχει ανάγκη για ασφάλεια, η οποία έχει δώσει ώθηση στην έρευνα για κρυπτογραφικά πρωτόκολλα. Σήμερα είναι απαραίτητα πλέον τα πρωτόκολλα ασφαλείας σε όλες σχεδόν τις σημαντικές συναλλαγές, είτε είναι πρόσβαση σε κάποιο δίκτυο είτε για ηλεκτρονικό εμπόριο ή επικοινωνίες. Η κρυπτογραφία ελλειπτικών καμπυλών προσφέρει μια εναλλακτική λύση με εμφανή πλεονεκτήματα έναντι των παραδοσιακών συστημάτων ασφαλείας. Το βασικό τους πλεονέκτημα είναι ότι απαιτούν μικρότερο μήκος κλειδιού για επίτευξη ίδιου επιπέδου ασφαλείας με πιο παραδοσιακά κρυπτογραφικά συστήματα (όπως το RSA). Αυτή ακριβώς η ιδιότητα καθιστά τα κρυπτογραφικά συστήματα ελλειπτικών καμπυλών ιδιαίτερα ελκυστικά για εφαρμογή σε ενσωματωμένα συστήματα τα οποία εξορισμού έχουν περιορισμένους πόρους. Η παρούσα διπλωματική εργασία παρουσιάζει την μεταφορά μιας βιβλιοθήκης ελλειπτικών καμπυλών σε ένα ενσωματωμένο σύστημα. Ιδιαίτερο βάρος δόθηκε στην δημιουργία ελλειπτικών καμπυλών κατάλληλων για χρήση σε κρυπτογραφικά συστήματα. Η κατασκευή των ελλειπτικών καμπυλών οι οποίες θεωρούνται ασφαλείς γίνονται με την μέθοδο του μιγαδικού πολλαπλασιασμού, Παρουσιάζεται η διαδικασία μεταφοράς, τα προβλήματα καθώς και τα πειραματικά αποτελέσματα. Επίσης παρουσιάζεται μια εφαρμογή η οποία επιδεικνύει τις δυνατότητες δημιουργίας ασφαλούς ελλειπτικής καμπύλης καθώς και την χρήση της καμπύλης αυτής για ασφαλή μετάδοση δεδομένων. Έτσι έχουμε ένα ενσωματωμένο σύστημα, με περιορισμένες δυνατότητες, το οποίο όχι μόνο υλοποιεί τα κατάλληλα πρωτόκολλα ελλειπτικών καμπυλών, αλλά έχει την δυνατότητα να δημιουργεί ασφαλείς ελλειπτικές καμπύλες κατάλληλες για χρήση από άλλες συσκευές. / Over the last years there has been a rapid growth in Internet use and its benefits. Applications depending on connectivity range from simple networks to e-commerce and e-banking. Furthermore the nature of the hardware used in these transactions has been altered significally. Instead of high-end desktop computers laptops, PDAs and cell phones are widely used both in wired and wireless networks. In an environment as open as the Internet users may be in danger and their transactions may be compromised. There is an immediate need for safe cryptographic systems even for devices that meet hardware restrictions (i.e. processing power or memory and space limitations) without compromising the security levels required. Elliptic curve cryptography offers an interesting alternative in this direction instead of more traditional public key cryptosystem such as RSA. The main reason for this is the mathematical problems on which Elliptic Curve Cryptography (ECC) is based. ECC is based on the elliptic Curve Discrete Logarithm Problem (ECDLP). ECDLP is the ECC equivalent to DLP which is used in most public key cryptosystems and was introduced by Koblitz and Miller in 1985. So far the best algorithms for attacking the ECDLP take exponential time while for the DLP the time required is sub-exponential. This means that an ECC system can use smaller key size than traditional cryptosystems to achieve the same results. As an example, an ECC system with a key size of 160 bits is roughly equivalent to an RSA system with a key size of 1024 bits. Since the key size is significally smaller, so are requirements in space and memory, making ECC an excellent candidate for implementation in devices with limited resources. In this thesis we present an ECC library (ECC-LIB) in an embedded device with hardware limitations. ECC-LIB was developed by Elisavet Konstantinou, Yiannis Stamatiou, and Christos Zaroliagis as a tool to provide users with a modular library that allows development of various cryptographic protocols. We decided to use this library not on a desktop computer but on an embedded device to try and address any problems that might occur in such a limited environment. The device we selected is the AT76C520 chip, which can be used either as a wireless Access Point or as a network processor, with a microprocessor capable of running ucLinux, which is a Linux distribution for embedded devices. Our effort was focused on importing the library without changing the source code to ensure portability. We focused on the implementation of Complex Multiplication method for generating secure elliptic curves, which is not supported by most of the other implementations in embedded systems. Our experimental results demonstrate such an implementation is feasible and can produce efficiently elliptic curves suitable for use in cryptographic systems. Also, our implementation is highly portable. It can be used as is, or with minor changes, on practically any embedded system, since it is written exclusively in standard ANSI C, and there are no device specific optimizations (like assembly). We also implemented an application to support a working scenario. In this scenario our device is used as server from which other devices (wired or wireless, embedded or high end systems) can request an elliptic curve to use in order to achieve security in their communication. The client can request an elliptic curve of specific security level and our application can generate a suitable curve (using the Complex Multiplication method) and distribute it. This means that in a suitable environment plethora of devices can communicate safely, with devices types ranging from desktop computers to mobile phones and PDAs.