We describe novel methods for obtaining fast software implementations of the arithmetic operations in the finite field GF(p) and GF(p[superscript k]). In GF(p) we realize an extensive speedup in modular addition and subtraction routines and some small speedup in the modular multiplication routine with an arbitrary prime modulus p which is of arbitrary length. The most important feature of the method is that it avoids bit-level operations which are slow on microprocessors and performs word-level operations which are significantly faster. The proposed method has applications in public-key cryptographic algorithms defined over the finite field GF(p), most notably the elliptic curve digital signature algorithm. The new method provides up to 13% speedup in the execution of the ECDSA algorithm over the field GF(p) for the length of p in the range 161���k���256. In the finite extension field GF(p[superscript k]) we describe two new methods for obtaining fast software implementations of the modular multiplication operation with an arbitrary prime modulus p, which has less bit-length than the word-length of a microprocessor and an arbitrary generator polynomial. The second algorithm is a significant improvement over the first algorithm by using the same concepts introduced in GF(p) arithmetic. / Graduation date: 2002

Let K(q) be the finite field with q elements and characteristic p. Let f(x) be a monic polynomial of degree d with coefficients in K(q). Let C(f) denote the number of distinct values of f(x) as x ranges over K(q). It is easy to show that C(f) ≤ [|(q - 1)/d|] + 1. Now, there is a characterization of polynomials of degree d < √q for which C(f) = [|(q - 1)/d|] +1. The main object of this work is to give a characterization for polynomials of degree d < ⁴√q for which C(f) < 2q/d. Using two well known theorems: Hurwitz genus formula and Andre Weil's theorem, the Riemann Hypothesis for Algebraic Function Fields, it is shown that if d < ⁴√q and C(f) < 2q/d then f(x) - f(y) factors into at least d/2 absolutely irreducible factors and f(x) has one of the following forms: (UNFORMATTED TABLE FOLLOWS) f(x - λ) = D(d,a)(x) + c, d|(q² - 1), f(x - λ) = D(r,a)(∙ ∙ ∙ ((x²+b₁)²+b₂)²+ ∙ ∙ ∙ +b(m)), d|(q² - 1), d=2ᵐ∙r, and (2,r) = 1 f(x - λ) = (x² + a)ᵈ/² + b, d/2|(q - 1), f(x - λ) = (∙ ∙ ∙((x²+b₁)²+b₂)² + ∙ ∙ ∙ +b(m))ʳ+c, d|(q - 1), d=2ᵐ∙r, f(x - λ) = xᵈ + a, d|(q - 1), f(x - λ) = x(x³ + ax + b) + c, f(x - λ) = x(x³ + ax + b) (x² + a) + e, f(x - λ) = D₃,ₐ(x² + c), c² ≠ 4a, f(x - λ) = (x³ + a)ⁱ + b, i = 1, 2, 3, or 4, f(x - λ) = x³(x³ + a)³ +b, f(x - λ) = x⁴(x⁴ + a)² +b or f(x - λ) = (x⁴ + a) ⁱ + b, i = 1,2 or 3, where D(d,a)(x) denotes the Dickson’s polynomial of degree d. Finally to show other polynomials with small value set, the following equation is obtained C((fᵐ + b)ⁿ) = αq/d + O(√q) where α = (1 – (1 – 1/m)ⁿ)m and the constant implied in O(√q) is independent of q.

No description available.

Thesis (Ph.D.) - University of Glasgow, 2007. / Ph.D. thesis submitted to the Department of Mathematics, Faculty of Information and Mathematical Sciences, University of Glasgow, 2007. Includes bibliographical references.

No description available.

Thesis (Ph. D.)--Brigham Young University. Dept. of Mathematics, 2007. / Includes bibliographical references (p. 81-83).

In this dissertation, I discuss bounds for the set of possible number of zeros of a homogeneous linear recurring sequence over a finite field of q elements, based on an irreducible minimal polynomials of degree d and order m as the characteristic polynomial. I prove upper and lower bounds on the cardinality of the set of number of zeros. The set is determined when t= (qd-1)/m has the form qa+1 or q2a-qa+1 where a is a positive integer. The connection with coding theory is a key ingredient. Also it is proved that the upper bound defined here is the best bound for the cardinality of the set of zeros, in the sense that it is reached infinitely often.

This thesis focuses on a class of Galois field used to achieve fast finite field arithmetic which we call Optimal Extension Fields (OEFs), first introduced in cite{baileypaar98}. We extend this work by presenting an adaptation of Itoh and Tsujii's algorithm for finite field inversion applied to OEFs. In particular, we use the facts that the action of the Frobenius map in $GF(p^m)$ can be computed with only $m-1$ subfield multiplications and that inverses in $GF(p)$ may be computed cheaply using known techniques. As a result, we show that one extension field inversion can be computed with a logarithmic number of extension field multiplications. In addition, we provide new variants of the Karatsuba-Ofman algorithm for extension field multiplication which give a performance increase. Further, we provide an OEF construction algorithm together with tables of Type I and Type II OEFs along with statistics on the number of pseudo-Mersenne primes and OEFs. We apply this new work to provide implementation results for elliptic curve cryptosystems on both DEC Alpha workstations and Pentium-class PCs. These results show that OEFs when used with our new inversion and multiplication algorithms provide a substantial performance increase over other reported methods.

Mak, Kit Ho. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 78-81). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.7 / Chapter 2 --- Preliminaries on Number Theory --- p.10 / Chapter 2.1 --- Finite Fields --- p.10 / Chapter 2.2 --- p-adic Numbers --- p.13 / Chapter 2.3 --- The Teichmuller Representatives --- p.16 / Chapter 2.4 --- Character Theory --- p.18 / Chapter 3 --- Basic Calabi-Yau Geometry --- p.26 / Chapter 3.1 --- Definition and Basic Properties of Calabi-Yau Manifolds --- p.26 / Chapter 3.2 --- Calabi-Yau Manifolds of Low Dimensions --- p.29 / Chapter 3.3 --- Constructions of Calabi-Yau Manifolds --- p.32 / Chapter 3.4 --- Importance of Calabi-Yau Manifolds in Physics --- p.35 / Chapter 4 --- Number of Points on Calabi-Yau Manifolds over Finite Fields --- p.39 / Chapter 4.1 --- The General Method --- p.39 / Chapter 4.2 --- The Number of Points on a Family of Calabi-Yau Varieties over Finite Fields --- p.45 / Chapter 4.2.1 --- The Case ψ = 0 --- p.45 / Chapter 4.2.2 --- The Case ψ ß 0 --- p.50 / Chapter 4.3 --- The Number of Points on the Affine Mirrors over Finite Fields --- p.55 / Chapter 4.3.1 --- The Case ψ = 0 --- p.55 / Chapter 4.3.2 --- The Case ψ ß 0 --- p.56 / Chapter 4.4 --- The Number of points on the Projective Mirror over Finite Fields --- p.59 / Chapter 4.5 --- Summary of the Results and Related Conjectures --- p.61 / Chapter 5 --- The Relation Between Periods and the Number of Points over Finite Fields modulo q --- p.67 / Chapter 5.1 --- Periods of Calabi-Yau Manifolds --- p.67 / Chapter 5.2 --- The Case for Elliptic Curves --- p.69 / Chapter 5.2.1 --- The Periods of Elliptic Curves --- p.69 / Chapter 5.2.2 --- The Number of Fg-points on Elliptic Curves Modulo q --- p.70 / Chapter 5.3 --- The Case for a Family of Quintic Threefolds --- p.73 / Chapter 5.3.1 --- The Periods of Xψ --- p.73 / Chapter 5.3.2 --- The Number of F9-points on Quintic Three- folds Modulo q --- p.75 / Bibliography --- p.78

Includes bibliography.