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.

The random Fibonacci sequence is defined by t_1 = t_2 = 1 and t_n = ± t_{n–1} + t_{n–2} , for n ? 3, where each ± sign is chosen at random with P(+) = P(–) = 1/2. We can think of all possible such sequences as forming a binary tree T. Viswanath has shown that almost all random Fibonacci sequences grow exponentially at the rate 1.13198824.... He was only able to find 8 decimal places of this constant through the use of random matrix theory and a fractal measure, although Bai has extended the constant by 5 decimal places. Numerical experimentation is inefficient because the convergence is so slow. We will discuss a new computation of Viswanath's constant which is based on a formula due to Kalmár-Nagy, and uses an interesting reduction R of the tree T developed by Rittaud. Also, we will focus on the growth rate of the expected value of a random Fibonacci sequence, which was studied by Rittaud. This differs from the almost sure growth rate in that we first find an expression for the average of the n^th term in a sequence, and then calculate its growth. We will derive this growth rate using a slightly different and more simplified method than Rittaud, using the tree R and a Pascal-like array of numbers, for which we can further give an explicit formula. We will also consider what happens to random Fibonacci sequences when we remove the randomness. Specifically, we will choose coefficients which belong to the set {1, –1} and form periodic cycles. By rewriting our recurrences using matrix products, we will analyze sequence growth and develop criteria based on eigenvalue, trace and order, for determining whether a given sequence is bounded, grows linearly or grows exponentially. Further, we will introduce an equivalence relation on the coefficient cycles such that each equivalence class has a common growth rate, and consider the number of such classes for a given cycle length. Lastly we will look at two ways to completely characterize the trace, given the coefficient cycle, by breaking the matrix product up into blocks.

This licentiate consists of two papers treating polynomial sequences defined by linear recurrences. In paper I, we establish necessary and sufficient conditions for the reality of all the zeros in a polynomial sequence {P_i} generated by a three-term recurrence relation P_i(x)+ Q_1(x)P_{i-1}(x) +Q_2(x) P_{i-2}(x)=0 with the standard initial conditions P_{0}(x)=1, P_{-1}(x)=0, where Q_1(x) and Q_2(x) are arbitrary real polynomials. In paper II, we study the root distribution of a sequence of polynomials {P_n(z)} with the rational generating function \sum_{n=0}^{\infty} P_n(z)t^n= \frac{1}{1+ B(z)t^\ell +A(z)t^k} for (k,\ell)=(3,2) and (4,3) where A(z) and B(z) are arbitrary polynomials in z with complex coefficients. We show that the roots of P_n(z) which satisfy A(z)B(z)\neq 0 lie on a real algebraic curve which we describe explicitly.

In 1939, I.M. Sheffer proved that every polynomial sequence belongs to one and only one type. Sheffer extensively developed properties of the B-Type 0 polynomial sequences and determined which sets are also orthogonal. He subsequently generalized his classification method to the case of arbitrary B-Type k by constructing the generalized generating function A(t)exp[xH1(t) + · · · + xk+1Hk(t)] = ∑∞n=0 Pn(x)tn, with Hi(t) = hi,iti + hi,i+1t i+1 + · · · , h1,1 ≠ 0. Although extensive research has been done on characterizing polynomial sequences, no analysis has yet been completed on sets of type one or higher (k ≥ 1). We present a preliminary analysis of a special case of the B-Type 1 (k = 1) class, which is an extension of the B-Type 0 class, in order to determine which sets, if any, are also orthogonal sets. Lastly, we consider an extension of this research and comment on future considerations. In this work the utilization of computer algebra packages is indispensable, as computational difficulties arise in the B-Type 1 class that are unlike those in the B-Type 0 class.

在這篇論文裡，我們將要討論一類古典的問題，這類問題已經經由許多方法解決，例如：遞迴關係式、差分方程式、尤拉公式等等。接著我們歸納低維度的特性，並藉由定義出一組方程式-標準n維空間分割系統-來推廣這些特性到一般的$n$維度空間中。然後我們利用演算法來提供一個更直接的組合論證法。最後，我們會把問題再細分成有界區域與無界區域的個數。 / In this article, we will discuss a class of classical questions had been solved by Recurrence Relation, Difference Equation, and Euler's Formula, etc.. And then, we construct a system of equations -Standard Partition System of n-Dimensional Space- to generalize the properties of maximizing the number of regions made up by k partitioner in an n-dimensional space and look into the construction of each dimension. Also, we provide a more directly Combinatorial Argument by Algorithm for this kind of question. At last, we focus on the number of bounded regions and unbounded regions in sense of maximizing the number of regions.

O principal objetivo deste trabalho 6 estudar o comportamento dos zeros de polinômios ortogonais e similares. Inicialmente, consideramos uma relação entre duas sequências ele polinômios ortogonais, onde as medidas associadas estão relacionadas entre si. Usamos esta relação para estudar as propriedades de monotonicidade dos zeros dos polinômios ortogonais relacionados a uma medida obtida através da generalização da medida associada a uma outra sequência de polinômios ortogonais. Apresentamos, como exemplos, os polinômios ortogonais obtidos a partir da generalização das medidas associadas aos polinômios de Jacobi, Laguerre e Charlier. Em urna segunda etapa, consideramos polinômios gerados por uma certa relação de recorrência de três termos com o objetivo de encontrar limitantes, em termos dos coeficientes da relação de recorrência, para as regiões onde os zeros estão localizados. Os zeros são estudados através do problema de autovalor associado a uma matriz de Hessenberg. Aplicações aos polinômios de Szegó, polinômios para-ortogonais e polinômios com coeficientes complexos não-nulos são consideradas. / The main purpose of this work is to study the behavior of the zeros of orthogonal and similar polynomials. Initially, we consider a relation between two sequences of orthogonal polynomials, where the associated measures are related to each other. We use this relation to study the monotonicity propertios of the zeros of orthogonal polynomials related with a measure obtained through a generalization of the measure associated with other sequence of orthogonal polynomials. As examples, we consider the orthogonal polynomials obtained in this way from the measures associated with the Jacobi, Laguerre and Charlier polynomials. We also consider the zeros of polynomials generated by a certain three term recurrence relation. Here, the main objective is to find bounds, in terms of the coefficients of the recurrence relation, for the regions where the zeros are located. The zeros are explored through an eigenvalue representation associated with a Hessenberg matrix. Applications to Szegõ polynomials, para-orthogonal polynomials anti polynomials with non-zero complex coefficients are considered.

關於錯排列(Derangements)│D_n│=n│D_n-1│+(-1)ⁿ 的證明可用代數方法證出，甚至│D_n│的個數亦可由生成函數求出，因此我們希望能藉用更直接的觀點加以探討和證明，並找出彼此的對應。 　　當我們確定了D_n→n D_n-1的對應方式，它可以做為密碼的利用，當我們傳送一個D_n中的碼，可由譯碼的過程（即對應方式），對應到D_n-1中的一個碼（而且是1對1），因此在機密性方面有很大的幫助。 　　本文章節安排如下： 　　第一章錯排列的簡介 　　第二章如何製造錯排列 　　第三章錯排列的對應

當我們解一個遞迴關係的特徵方程式時，不管解得的根是相異根或者是重根，皆視這些跟產生的解之線性獨立為理所當然，因此很容易寫出此遞迴關係的通解乃是這些解的線性組合。在本文中，我們將透過廣義的范德蒙行列式(Generalized Vandermonde Determinant)的計算，很清楚地看出這些解之間的線性獨立。 / When we solve a characteristic equation of a recurrence relation, no matter what the roots are distinct or not, we take the linear independence of these solutions producing by each root for granted. Basing on this fact, we can easily write out the general solutions of this recurrence relation by using linear combination of these solutions. In this paper, we will see the linear independence of these solutions very clearly through the calculation of Generalized Vandermonde Determinant.

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-02-27Bitstream added on 2014-06-13T20:16:04Z : No. of bitstreams: 1 nunes_jb_me_sjrp.pdf: 1005590 bytes, checksum: 7da54a97a1f2ab452a315062071f2c4e (MD5) / Este trabalho trata do estudo da localização dos zeros dos polinômios gerados por uma determinada relação de recorrência de três termos. O objetivo principal é estudar limitantes, em termos dos coeficientes da relação de recorrência, para as regiões onde os zeros estão localizados. Os zeros são explorados atravé do problema de autovalor associado a uma matriz de Hessenberg. As aplicações são consideradas para polinômios de Szego fSng, alguns polinômios para- ortogonais ½Sn(z) + S¤n (z) 1 + Sn(0) ¾ e ½Sn(z) ¡ S¤n (z) 1 ¡ Sn+1(0) ¾, especialmente quando os coeficientes de reflexão são reais. Um outro caso especial considerado são os zeros do polinômio Pn(z) = n Xm=0 bmzm, onde os coeficientes bm; para m = 0; 1; : : : ; n, são complexos e diferentes de zeros. / In this work we studied the localization the zeros of polynomials generated by a certain three term recurrence relation. The main objective is to study bounds, in terms of the coe±cients of the recurrence relation, for the regions where the zeros are located. The zeros are explored through an eigenvalue representation associated with a Hessenberg matrix. Applications are considered to Szeg}o polynomials fSng, some para-orthogonal polyno- mials ½Sn(z) + S¤n (z) 1 + Sn(0) ¾and ½Sn(z) ¡ S¤n (z) 1 ¡ Sn+1(0) ¾, especially when the re°ection coe±cients are real. As another special case, the zeros of the polynomial Pn(z) = n Xm=0 bmzm, where the non-zero complex coe±cients bm for m = 0; 1; : : : ; n, were considered.

Orientador: Eliana Xavier Linhares de Andrade / Banca: Alagacone Sri Ranga / Banca: Andre Piranhe da Silva / Resumo: Este trabalho trata do estudo da localização dos zeros dos polinômios gerados por uma determinada relação de recorrência de três termos. O objetivo principal é estudar limitantes, em termos dos coeficientes da relação de recorrência, para as regiões onde os zeros estão localizados. Os zeros são explorados atravé do problema de autovalor associado a uma matriz de Hessenberg. As aplicações são consideradas para polinômios de Szeg"o fSng, alguns polinômios para- ortogonais ½Sn(z) + S¤n (z) 1 + Sn(0) ¾ e ½Sn(z) ¡ S¤n (z) 1 ¡ Sn+1(0) ¾, especialmente quando os coeficientes de reflexão são reais. Um outro caso especial considerado são os zeros do polinômio Pn(z) = n Xm=0 bmzm, onde os coeficientes bm; para m = 0; 1; : : : ; n, são complexos e diferentes de zeros. / Abstract: In this work we studied the localization the zeros of polynomials generated by a certain three term recurrence relation. The main objective is to study bounds, in terms of the coe±cients of the recurrence relation, for the regions where the zeros are located. The zeros are explored through an eigenvalue representation associated with a Hessenberg matrix. Applications are considered to Szeg}o polynomials fSng, some para-orthogonal polyno- mials ½Sn(z) + S¤n (z) 1 + Sn(0) ¾and ½Sn(z) ¡ S¤n (z) 1 ¡ Sn+1(0) ¾, especially when the re°ection coe±cients are real. As another special case, the zeros of the polynomial Pn(z) = n Xm=0 bmzm, where the non-zero complex coe±cients bm for m = 0; 1; : : : ; n, were considered. / Mestre