Let Fqt be the finite field with qt elements and let F*qt be its multiplicative group. We study the diagonal equation axq−1 + byq−1 = c, where a,b and c ∈ F*qt. This equation can be written as xq−1+αyq−1 = β, where α, β ∈ F ∗ q t . Let Nt(α, β) denote the number of solutions (x,y) ∈ F*qt × F*qt of xq−1 + αyq−1 = β and I(r; a, b) be the number of monic irreducible polynomials f ∈ Fq[x] of degree r with f(0) = a and f(1) = b. We show that Nt(α, β) can be expressed in terms of I(r; a, b), where r | t and a, b ∈ F*q are related to α and β. A recursive formula for I(r; a, b) will be given and we illustrate this by computing I(r; a, b) for 2 ≤ r ≤ 4. We also show that N3(α, β) can be expressed in terms of the number of monic irreducible cubic polynomials over Fq with prescribed trace and norm. Consequently, N3(α, β) can be expressed in terms of the number of rational points on a certain elliptic curve. We give a proof that given any a, b ∈ F*q and integer r ≥ 3, there always exists a monic irreducible polynomial f ∈ Fq[x] of degree r such that f(0) = a and f(1) = b. We also use the result on N2(α, β) to construct a new family of planar functions.

An important advantage of Elliptic Curve Cryptosystem (ECC) is the shorter key length in public key cryptographic systems. It can provide adequate security when the bit length over than 160 bits. Therefore, it has become a popular system in recent years. Scalar multiplication also called point multiplication is the core operation in ECC. In this thesis, we propose the ECC architectures of two different irreducible polynomial versions that are trinomial in GF(2167) and pentanomial in GF(2163). These architectures are based on Montgomery point multiplication with projective coordinate. We use polynomial basis representation for finite field arithmetic. All adopted multiplication, square and add operations over binary field can be completed within one clock cycle, and the critical path lies on multiplication. In addition, we use Itoh-Tsujii algorithm combined with addition chain, to execute binary inversion through using iterative binary square and multiplication. Because the double and add operations in point multiplication need to run many iterations, the execution time in overall design will be decreased if we can improve this partition. We propose two ways to improve the performance of point multiplication. The first way is Minus Cycle Version. In this version, we reschedule the double and add operations according to point multiplication algorithm. When the clock cycle time (i.e., critical path) of multiplication is longer than that of add and square, this method will be useful in improving performance. The second way is Pipeline Version. It speeds up the multiplication operations by executing them in pipeline, leading to shorter clock cycle time. For the hardware implementation, TSMC 0.13um library is employed and all modules are organized in a hierarchy structure. The implementation result shows that the proposed 167-bit Minus Cycle Version requires 156.4K gates, and the execution time of point multiplication is 2.34us and the maximum speed is 591.7Mhz. Moreover, we compare the Area x Time (AT) value of proposed architectures with other relative work. The results exhibit that proposed 167-bit Minus Cycle Version is the best one and it can save up to 38% A T value than traditional one.

No description available.

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.

The Rijndael cryptosystem uses a particular polynomial to create its constants. All calculations within the encryption and decryption layers are based on this polynomial. This arouse the curiosity to see what happens if the polynomial is substituted by other polynomials. This paper’s main area of study is to investigate the consequences of using different polynomials to construct the Rijndael cryptosystem. To do so, as a phase of this study, a Mathematica package has been created to ease the investigations. As the second phase, using the aforementioned package, some kind of diffusion analysis has been done on the newly constructed Rijndael-like cryptosystems. The fundamental challenge was to figure out the reason of having the particular polynomial chosen. By the end of the experiment, we concluded that choosing other polynomials with the same characteristics as an ingredient of the Rijndael algorithm, does not have any perceptible effects on the diffusion level.

Soit q ⩾ 2 une puissance première fixe. L’objectif principal de cette thèse est d’étudier le comportement asymptotique de la fonction arithmétique Π_q(n,k) comptant le nombre de polynômes moniques de degré n et ayant exactement k facteurs irréductibles (avec multiplicité) sur le corps fini F_q. Warlimont et Car ont montré que l’objet Π_q(n,k) est approximativement distribué de Poisson lorsque 1 ⩽ k ⩽ A log n pour une constante A > 0. Plus tard, Hwang a étudié la fonction Π_q(n,k) pour la gamme complète 1 ⩽ k ⩽ n. Nous allons d’abord démontrer une formule asymptotique pour Π_q(n,k) en utilisant une technique analytique classique développée par Sathe et Selberg. Nous reproduirons ensuite une version simplifiée du résultat de Hwang en utilisant la formule de Sathe-Selberg dans le champ des fonctions. Nous comparons également nos résultats avec ceux analogues existants dans le cas des entiers, où l’on étudie tous les nombres naturels jusqu’à x avec exactement k facteurs premiers. En particulier, nous montrons que le nombre de polynômes moniques croît à un taux étonnamment plus élevé lorsque k est un peu plus grand que logn que ce que l’on pourrait supposer en examinant le cas des entiers. Pour présenter le travail ci-dessus, nous commençons d’abord par la théorie analytique des nombres de base dans le contexte des polynômes. Nous introduisons ensuite les fonctions arithmétiques clés qui jouent un rôle majeur dans notre thèse et discutons brièvement des résultats bien connus concernant leur distribution d’un point de vue probabiliste. Enfin, pour comprendre les résultats clés, nous donnons une discussion assez détaillée sur l’analogue de champ de fonction de la formule de Sathe-Selberg, un outil récemment développé par Porrit et utilisons ensuite cet outil pour prouver les résultats revendiqués. / Let q ⩾ 2 be a fixed prime power. The main objective of this thesis is to study the asymptotic behaviour of the arithmetic function Π_q(n,k) counting the number of monic polynomials that are of degree n and have exactly k irreducible factors (with multiplicity) over the finite field F_q. Warlimont and Car showed that the object Π_q(n,k) is approximately Poisson distributed when 1 ⩽ k ⩽ A log n for some constant A > 0. Later Hwang studied the function Π_q(n,k) for the full range 1 ⩽ k ⩽ n. We will first prove an asymptotic formula for Π_q(n,k) using a classical analytic technique developed by Sathe and Selberg. We will then reproduce a simplified version of Hwang’s result using the Sathe-Selberg formula in the function field. We also compare our results with the analogous existing ones in the integer case, where one studies all the natural numbers up to x with exactly k prime factors. In particular, we show that the number of monic polynomials grows at a surprisingly higher rate when k is a little larger than logn than what one would speculate from looking at the integer case. To present the above work, we first start with basic analytic number theory in the context of polynomials. We then introduce the key arithmetic functions that play a major role in our thesis and briefly discuss well-known results concerning their distribution from a probabilistic point of view. Finally, to understand the key results, we give a fairly detailed discussion on the function field analogue of the Sathe-Selberg formula, a tool recently developed by Porrit and subsequently use this tool to prove the claimed results.