1 |
Certain Diagonal Equations over Finite FieldsSze, Christopher 29 May 2009 (has links)
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.
|
2 |
High Speed Scalar Multiplication Architecture for Elliptic Curve CryptosystemHsu, Wei-Chiang 28 July 2011 (has links)
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.
|
3 |
Dénombrement des polynômes irréductibles unitaires dans les corps finis avec différentes contraintes sur les coefficientsLarocque, Olivier 09 1900 (has links)
No description available.
|
4 |
Étude du nombre de polynômes irréductibles dans les corps finis avec certaines contraintes imposées aux coefficientsBeauchamp Houde, Gabriel 08 1900 (has links)
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.
|
5 |
Alternative Polynomials for Rijndael : Diffusion AnalysisNoroozi, Hamid January 2014 (has links)
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.
|
6 |
On the distribution of polynomials having a given number of irreducible factors over finite fieldsDatta, Arghya 08 1900 (has links)
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.
|
Page generated in 0.0631 seconds