Efficient Hardware Implementation of Finite Fields with Applications to Cryptography

The paper presents a survey of most common hardware architectures for finite field arithmetic especially suitable for cryptographic applications. We discuss architectures for three types of finite fields and their special versions popularly used in cryptography: binary fields, prime fields and extension fields. We summarize algorithms and hardware architectures for finite field multiplication, squaring, addition/subtraction, and inversion for each of these fields. Since implementations in hardware can either focus on high-speed or on area-time efficiency, a careful choice of the appropriate set of architectures has to be made depending on the performance requirements and available area.     

Applications of Finite Fields to Combinatorics and Finite Geometries

We survey some applications of finite fields to finite geometries in part A and to combinatorics and error-correcting codes in parts B and C.     

Exact categories

We survey the basics of homological algebra in exact categories in the sense of Quillen. All diagram lemmas are proved directly from the axioms, notably the five lemma, the 3×3$3\times 3$-lemma and the snake lemma. We briefly discuss exact functors, idempotent completion and weak idempotent completeness. We then show that it is possible to construct the derived category of an exact category without any embedding into abelian categories and we sketch Deligne's approach to derived functors. The construction of classical derived functors with values in an abelian category painlessly translates to exact categories, i.e., we give proofs of the comparison theorem for projective resolutions and the horseshoe lemma. After discussing some examples we elaborate on Thomason's proof of the Gabriel–Quillen embedding theorem in an appendix.     

Fields of quotients of lattice-ordered domains

It is not known whether the field of fractions of an integral domain with a compatible lattice order has a compatible lattice order that extends the given order on the integral domain. The polynomial ring over the real numbers has a natural compatible lattice order, viz, the coordinatewise order . We describe circumstances in which the field of fractions of has no archimedean lattice order that extends .Received May 2, 2003; accepted in final form June 4, 2004.     

Parametrized Partitions of Products of Finite Sets*

For every infinite sequence of positive integers and every Borel partition c : ×[]{0, 1} there is H[] and a sequence of subsets of , with |H_i|=m_i for every i, such that c is constant on .* Research partially supported by CNRS-FONACIT Project PI 2000001471. This author thanks the University of Paris VII for hospitality.     

Applications of proximal calculus to fixed point theory on Riemannian manifolds

We prove a general form of a fixed point theorem for mappings from a Riemannian manifold into itself which are obtained as perturbations of a given mapping by means of general operations which in particular include the cases of sum (when a Lie group structure is given on the manifold) and composition. In order to prove our main result we develop a theory of proximal calculus in the setting of Riemannian manifolds.     

The Asymptotic Behavior of Conformal Modules of Quadrilaterals with Applications to the Estimation of Resistance Values

We consider the conformal mapping of ``strip-like' domains and derive a number of asymptotic results for computing the conformal modules of an associated class of quadrilaterals. These results are then used for the following two purposes: (a) to estimate the error of certain engineering formulas for measuring resistance values of integrated circuit networks; and (b) to compute the modules of complicated quadrilaterals of the type that occur frequently in engineering applications. April 17, 1997. Date revised: September 10, 1997.     

Spaces of p-integrable Functions with Respect to a Vector Measure

We study several properties of the Banach lattices L^p (m) and L^p_w (m) of p-integrable scalar functions and weakly p-integrable scalar functions with respect to a countably additive vector measure m. The relation between these two spaces plays a fundamental role in our analysis. This research has been partially supported by La Consejería de Educatión y Ciencia de la Junta de Andalucía.     

Generalizing a theorem of Richard Brauer

There exists a function such that for every positive integer d, every quasi-finite field K and every projective hypersurface X of degree d and dimension ?f(d), the set X(K) is non-empty. This is a special case of a more general result about intersections of hypersurfaces of fixed degree in projective spaces of sufficiently high dimension over fields with finitely generated Galois groups.     

The Zassenhaus filtration,Massey products,and representations of profinite groups

We consider the p  -Zassenhaus filtration (_Gn)$(G_n)$ of a profinite group G  . Suppose that G=S/N$G=S/N$ for a free profinite group S and a normal subgroup N of S   contained in _Sn$S_n$. Under a cohomological assumption on the n-fold Massey products (which holds, e.g., if G has p  -cohomological dimension ≤ 1), we prove that _Gn+1$G_{n+1}$ is the intersection of all kernels of upper-triangular unipotent (n+1)$(n+1)$-dimensional representations of G   over _Fp${\mathbb{F}}_p$. This extends earlier results by Miná?, Spira, and the author on the structure of absolute Galois groups of fields.     

$L^2$-Approximations of power and logarithmic functions with applications to numerical conformal mapping

Summary. For a bounded Jordan domain G with quasiconformal boundary L, two-sided estimates are obtained for the error in best polynomial approximation to functions of the form , and , where . Furthermore, Andrievskii's lemma that provides an upper bound for the norm of a polynomial in terms of the norm of is extended to the case when a finite linear combination (independent of n) of functions of the above form is added to . For the case when the boundary of G is piecewise analytic without cusps, the results are used to analyze the improvement in rate of convergence achieved by using augmented, rather than classical, Bieberbach polynomial approximants of the Riemann mapping function of G onto a disk. Finally, numerical results are presented that illustrate the theoretical results obtained. Received September 1, 1999 / Published online August 17, 2001     

Local cohomology modules with respect to an ideal containing the irrelevant ideal

Let R=?_n≥0R_n be a homogeneous Noetherian ring, let M be a finitely generated graded R-module and let R₊=?_n>0R_n. Let b?b₀+R₊, where b₀ is an ideal of R₀. In this paper, we first study the finiteness and vanishing of the n-th graded component of the i-th local cohomology module of M with respect to b. Then, among other things, we show that the set becomes ultimately constant, as n→−∞, in the following cases:

(i)

and (R₀,m₀) is a local ring;

(ii)

dim(R₀)≤1 and R₀ is either a finite integral extension of a domain or essentially of finite type over a field;

(iii)

i≤g_b(M), where g_b(M) denotes the cohomological finite length dimension of M with respect to b.

Also, we establish some results about the Artinian property of certain submodules and quotient modules of .     

Ratliff-Rush closures of ideals with respect to a Noetherian module

Let R be a commutative Noetherian ring, E a non-zero finitely generated R-module and I a E-proper ideal of R. The purpose of this paper is to provide some new characterizations of when all powers of I are Ratliff-Rush closed with respect to E and to answer a question raised by W. Heinzer et al. in (The Ratliff-Rush Ideals in a Noetherian Ring: A Survey, in Methods in Module Theory, Dekker, New York, 1992, pp. 149-159).     

Efficient Computation of Roots in Finite Fields

We present an algorithm to compute rth roots in $\mathbb{F}_{q^m}We present an algorithm to compute rth roots in with complexity ?[(log m + r log q) m log q] if (m,q) = 1 and either (q(q−1),r) = 1 or r|(q−1) and ((q−1)/r,r) = 1. This compares well to previously known algorithms, which need O(r m³ log³ q) steps. Paulo S. L. M. Barreto: Supported by Scopus Tecnologia S. A. José Felipe Voloch: Supported by NSA grant MDA904-03-1-0117.     

Sequences of elliptical distributions and mixtures of normal distributions

Two conditions are shown under which elliptical distributions are scale mixtures of normal distributions with respect to probability distributions. The issue of finding the mixing distribution function is also considered. As a unified theoretical framework, it is also shown that any scale mixture of normal distributions is always a term of a sequence of elliptical distributions, increasing in dimension, and that all the terms of this sequence are also scale mixtures of normal distributions sharing the same mixing distribution function. Some examples are shown as applications of these concepts, showing the way of finding the mixing distribution function.     

Some Measurability Results and Applications to Spaces with Mixed Family-norm

A space with mixed family-norm consists of all functions x on a product space such that the function belongs to V (here, U(t) and V denote given Köthe spaces). Conditions for the measurability of y are given, and the Köthe dual of such spaces is determined. For this purpose a generalization of the Luxemburg-Gribanov theorem for ‘uniformly measurable’ functions is proved. This result is also formulated for vector functions.