The subject for this thesis is to find a basis which minimizes the number of bit operations involved in a finite field multiplication. The number of bases of a finite field increases quickly with the extension degree, and it is therefore important to find efficient search algorithms. Only fields of characteristic two are considered. A complexity measure is introduced, in order to compare bases. Different methods and algorithms are tried out, limiting the search in order to explore larger fields. The concept of equivalent bases is introduced. A comparison is also made between the Polynomial, Normal and Triangular Bases, referred to as known bases, as they are commonly used in implementations. Tables of the best found known bases for all fields up to GF(2^24) is presented. A list of the best found bases for all fields up to GF(2^25) is also given.

[pt] Curvas elípticas são objeto de estudo pelos matemáticos há mais de 200 anos. Por si só, é uma teoria bastante interessante por estar relacionada com diversas áreas da matemática: álgebra, equações diofantinas e geometria algébrica, dentre outras. Recentemente, diversos pesquisadores sugeriram o uso de curvas elípticas para resolver problemas práticos; como exemplos, podemos citar a criptografia, algoritmos para fatoração de números inteiros e testes de primalidade. Uma curva elíptica é definida sobre um corpo (no sentido algébrico). Essa dissertação tem por objetivo apresentar os primeiros elementos da teoria das curvas elípticas sobre corpos finitos. Como veremos, o desenvolvimento do tema aborda diversos tópicos da educação básica. Para isso, iniciaremos o trabalho com uma introdução utilizando o corpo dos números reais e, em seguida, incluiremos a teoria mais geral sobre essas curvas algébricas. Concluiremos então com algumas propriedades e resultados de curvas elípticas sobre corpos finitos, incluindo alguns exemplos e a interpretação geométrica da soma de dois pontos de curvas sobre corpos finitos específicos. / [en] Elliptic curves have been studied by mathematicians for over 200 years. By itself, it is a remarkably interesting theory as it is related to several areas of mathematics: algebra, Diophantine equations and algebraic geometry, among others. Recently, several researchers have suggested the use of elliptic curves to solve practical problems; as examples, we can mention cryptography, integer factorization algorithms and primality tests. An elliptic curve is defined over a field (in algebraic sense). This dissertation aims to present the first elements in the theory of elliptic curves on finite fields. As we will see, the development of the subject addresses a number of topics covered in basic education. In order to accomplish this, we will start the work with an introduction using the field of real numbers and then we will include the more general theory about these algebraic curves. Finally, we will present some properties and results on elliptic curves over finite fields, including some examples and a geometric interpretation of the sum of two points over specific finite fields.

No description available.

No description available.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第23684号 / 理博第4774号 / 新制||理||1684(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 小野 薫, 教授 玉川 安騎男, 教授 望月 拓郎 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM

Molecular nonlinear optical (NLO) properties are extensively studied using both theory and experiment because of their use in myriad applications. Experimental measurements of the most interesting molecules’ NLO properties are difficult, so experimental data for molecules with desirable NLO properties is scarce. Theoretical tools don’t suffer from the same limitations and can provide significant insights into the physico-chemical phenomena underlying the nonlinear responses, can help in interpreting response behaviour of molecules, and can guide design the materials with desirable response properties. Here, I present my work on developing methods for accurately calculating the NLO properties of molecules using the finite field (FF) approach. The first chapter provides a background for the finite field and electronic structure methods used in this dissertation. Chapter two is a thorough investigation of the finite field method. The limitations of the method are highlighted and the optimal conditions for overcoming its drawbacks and obtaining meaningful and accurate results are described. Chapter three presents the first systematic study of the dependence of optimal field strengths on molecular descriptors. The first protocol for predicting the optimal field for the second hyperpolarizability is presented and successfully tested, and the dependence of the optimal field strength for the first hyperpolarizability on the molecular structure is investigated. Chapter four is an assessment of various DFT functionals in calculating the second hyperpolarizabilities of organic molecules and oligomers. This study shows the limitations of conventional DFT methods and the importance of electron correlation to response properties. In chapter five we present a new method of calculating NLO properties using a rational function model that is shown to be more robust and have lower computational cost than the traditional Taylor expansion. Finally, chapter six includes a summary of the thesis and an overview of future work. / Thesis / Doctor of Philosophy (PhD)

L'objectif de ce mémoire est de dénombrer les polynômes irréductibles unitaires sur un corps fini en prescrivant des contraintes sur les coefficients. Dans les prochaines pages, il sera question de fixer simplement des coefficients, ou simplement de fixer leur signe, leur cubicité ou leur quarticité. / The objective of this thesis is to count monic irreducible polnomials over a finite field under some conditions on the coefficients of the polynomial. These conditions will be simply to fix some coefficients, or to fix their sign, cubicity or quarticity.

Communicating bits over a network is expensive. Therefore, cryptosystems that transmit as little data as possible are valuable. This thesis studies several cryptosystems that require significantly less bandwidth than conventional analogues. The systems we study, called torus-based cryptosystems, were analyzed by Karl Rubin and Alice Silverberg in 2003 [RS03]. They interpreted the XTR [LV00] and LUC [SL93] cryptosystems in terms of quotients of algebraic tori and birational parameterizations, and they also presented CEILIDH, a new torus-based cryptosystem. This thesis introduces the geometry of algebraic tori, uses it to explain the XTR, LUC, and CEILIDH cryptosystems, and presents torus-based extensions of van Dijk, Woodruff, et al. [vDW04, vDGP⁺05] that require even less bandwidth. In addition, a new algorithm of Granger and Vercauteren [GV05] that attacks the security of torus-based cryptosystems is presented. Finally, we list some open research problems.

With significant advances in wired and wireless technologies and also increased shrinking in the size of VLSI circuits, many devices have become very large because they need to contain several large units. This large number of gates and in turn large number of transistors causes the devices to be more prone to faults. These faults specially in sensitive and critical applications may cause serious failures and hence should be avoided. On the other hand, some critical applications such as cryptosystems may also be prone to deliberately injected faults by malicious attackers. Some of these faults can produce erroneous results that can reveal some important secret information of the cryptosystems. Furthermore, yield factor improvement is always an important issue in VLSI design and fabrication processes. Digital systems such as cryptosystems and digital signal processors usually contain finite field operations. Therefore, error detection and correction of such operations have become an important issue recently. In most of the work reported so far, error detection and correction are applied using redundancies in space (hardware), time, and/or information (coding theory). In this work, schemes based on these redundancies are presented to detect errors in important finite field arithmetic operations resulting from hardware faults. Finite fields are used in a number of practical cryptosystems and channel encoders/decoders. The schemes presented here can detect errors in arithmetic operations of finite fields represented in different bases, including polynomial, dual and/or normal basis, and implemented in various architectures, including bit-serial, bit-parallel and/or systolic arrays.

Communicating bits over a network is expensive. Therefore, cryptosystems that transmit as little data as possible are valuable. This thesis studies several cryptosystems that require significantly less bandwidth than conventional analogues. The systems we study, called torus-based cryptosystems, were analyzed by Karl Rubin and Alice Silverberg in 2003 [RS03]. They interpreted the XTR [LV00] and LUC [SL93] cryptosystems in terms of quotients of algebraic tori and birational parameterizations, and they also presented CEILIDH, a new torus-based cryptosystem. This thesis introduces the geometry of algebraic tori, uses it to explain the XTR, LUC, and CEILIDH cryptosystems, and presents torus-based extensions of van Dijk, Woodruff, et al. [vDW04, vDGP⁺05] that require even less bandwidth. In addition, a new algorithm of Granger and Vercauteren [GV05] that attacks the security of torus-based cryptosystems is presented. Finally, we list some open research problems.