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.

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).

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.

Thesis (M.S.)--Worcester Polytechnic Institute. / Keywords: multiplication; OTF; optimal extension fields; finite fields; optimal tower fields; cryptography; OEF; inversion; finite field arithmetic; elliptic curve cryptography. Includes bibliographical references (p. 50-52).

Thesis (Ph. D.)--University of Wisconsin, 1967. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references.

Thesis (M.SC.) - Carleton University, 2007. / Includes bibliographical references (p. 108-109). Also available in electronic format on the Internet.