Itoh-Tsujii Inversion in Standard Basis and Its Application in Cryptography and Codes

This contribution is concerned with a generalization of Itoh and Tsujii's algorithm for inversion in extension fields . Unlike the original algorithm, the method introduced here uses a standard (or polynomial) basis representation. The inversion method is generalized for standard basis representation and relevant complexity expressions are established, consisting of the number of extension field multiplications and exponentiations. As the main contribution, for three important classes of fields we show that the Frobenius map can be explored to perform the exponentiations required for the inversion algorithm efficiently. As an important consequence, Itoh and Tsujii's inversion method shows almost the same practical complexity for standard basis as for normal basis representation for the field classes considered.     

On the parallel evaluation of a sparse polynomial at a point

A new version of the Ruffini–Horner rule is presented for the evaluation of a polynomial of degree n at a point. In the PRAM model of parallel computation the new algorithm requires log n parallel steps with n/2+1 processors and the total number of arithmetic operations is n+⌈log₂(n+1)⌉ -1 multiplications and n additions. If the polynomial is sparse, i.e., the number of nonzero coefficients is k≪ n, then the total number of operations is at most k(⌈log n⌉- ⌊log k⌋)+2k+⌈log n⌉. Moreover, similarly to the customary Ruffini–Horner rule, the algorithm is backward numerically stable. In other words, the value provided by applying the algorithm in floating point arithmetic with machine precision μ coincides with the value taken on at the same point by a slightly perturbed polynomial. This revised version was published online in June 2006 with corrections to the Cover Date.     

Efficient <Emphasis Type="Italic">p</Emphasis>th root computations in finite fields of characteristic <Emphasis Type="Italic">p</Emphasis>

We present a method for computing pth roots using a polynomial basis over finite fields of odd characteristic p, p ≥ 5, by taking advantage of a binomial reduction polynomial. For a finite field extension of our method requires p − 1 scalar multiplications of elements in by elements in . In addition, our method requires at most additions in the extension field. In certain cases, these additions are not required. If z is a root of the irreducible reduction polynomial, then the number of terms in the polynomial basis expansion of z ^1/p , defined as the Hamming weight of z ^1/p or , is directly related to the computational cost of the pth root computation. Using trinomials in characteristic 3, Ahmadi et al. (Discrete Appl Math 155:260–270, 2007) give is greater than 1 in nearly all cases. Using a binomial reduction polynomial over odd characteristic p, p ≥ 5, we find always.      

A New Partition Identity Coming from Complex Dynamics

We present a new identity involving compositions (i.e., ordered partitions of natural numbers). The formula has its origin in complex dynamical systems and appears when counting, in the polynomial family periodic critical orbits with equivalent itineraries. We give two different proofs of the identity; one following the original approach in dynamics and another with purely combinatorial methods. Received October 1, 2004     

A quadratic field which is Euclidean but not norm-Euclidean

The classification of rings of algebraic integers which are Euclidean (not necessarily for the norm function) is a major unsolved problem. Assuming the Generalized Riemann Hypothesis, Weinberger [7] showed in 1973 that for algebraic number fields containing infinitely many units the ring of integersR is a Euclidean domain if and only if it is a principal ideal domain. Since there are principal ideal domains which are not norm-Euclidean, there should exist examples of rings of algebraic integers which are Euclidean but not norm-Euclidean. In this paper, we give the first example for quadratic fields, the ring of integers of .     

The growth of a C 0-semigroup characterised by its cogenerator

We characterise contractivity, boundedness and polynomial growth for a C ₀-semigroup in terms of its cogenerator V (or the Cayley transform of the generator) or its resolvent. In particular, we extend results of Gomilko and Brenner, Thomée and show that polynomial growth of a semigroup implies polynomial growth of its cogenerator. As is shown by an example, the result is optimal. For analytic semigroups we show that the converse holds, i.e., polynomial growth of the cogenerators implies polynomial growth of the semigroup. In addition, we show by simple examples in (), , that our results on the characterization of contractivity are sharp. These examples also show that the famous Foiaş-Sz.-Nagy theorem on cogenerators of contractive C ₀-semigroups on Hilbert spaces fails in () for .      

New formulas for approximation of π and other transcendental numbers

We derive many new formulas for the approximation of π. The formulas make use of a sequence of iteration functions called the basic family; a nontrivial determinantal generalization of Taylor's theorem; other ingredients; as well as several new results presented in the present paper. In one scheme, one evaluates members of the basic family, for an appropriately selected function, all at the same input. This scheme generates almost a fixed and preselected number of digits in each successive evaluation. The computation amounts to the evaluation of a homogeneous linear recursive formula and is equivalent to the computation of special Toeplitz matrix determinants. The approximations of π obtained via this scheme are within simple algebraic extensions of the rational field. In a second scheme, the fixed-point iteration is applied to any fixed member of the basic family, while selecting an appropriate function. In this scheme for each natural number we prove convergence of order m, starting from the initial point. We report on some preliminary computational results obtained via Maple. Analogous formulas can be used to approximate other transcendental numbers. For instance, we also give a formula for the approximation of e. In fact, our results give new formulas and arbitrary high-order methods for the approximation of roots of certain analytic functions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Towards Minimal Addition Chains Using Ant Colony Optimisation

Modular exponentiation is one of the most important operations in almost all modern cryptosystems. It is performed using a series of modular multiplications. This operation is time consuming for large operands as is always the case in cryptography. Hence fast public-key cryptography software or hardware requires optimisation of the time consumed by a single modular multiplication and/or the reduction of the total number of modular multiplications required. This paper introduces a novel idea based on the principles of ant colony optimisation for finding a minimal addition chain that allows one to reduce the number of modular multiplications so that modular exponentiation can be implemented efficiently. The best addition chain reached by the ant system is compared to the one used in the m-ary and sliding window methods as well as with the best addition chain evolved by genetic algorithms. We demonstrate that the ant system significantly outperforms all these methods for any exponent size. ^★★ Research supported by FAPERJ () and CNPq ().     

One-Parameter Plane Hyperbolic Motions

Müller [3], in the Euclidean plane , introduced the one parameter planar motions and obtained the relation between absolute, relative, sliding velocities (and accelerations). Also, Müller [11] provided the relation between the velocities (in the sense of Complex) under the one parameter motions in the Complex plane . Ergin [7] considering the Lorentzian plane , instead of the Euclidean plane , and introduced the one-parameter planar motion in the Lorentzian plane and also gave the relations between both the velocities and accelerations. In analogy with the Complex numbers, a system of hyperbolic numbers can be introduced: . Complex numbers are related to the Euclidean geometry, the hyperbolic system of numbers are related to the pseudo-Euclidean plane geometry (space-time geometry), [5,15]. In this paper, in analogy with Complex motions as given by Müller [11], one parameter motions in the hyperbolic plane are defined. Also the relations between absolute, relative, sliding velocities (and accelerations) and pole curves are discussed.      

Distribution of Nonlinear Congruential Pseudorandom Numbers Modulo Almost Squarefree Integers

The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present a new bound on the s-dimensional discrepancy of nonlinear congruential pseudorandom numbers over the residue ring modulo M for an “almost squarefree” integer M. It is useful to recall that almost all integers are of this type. Moreover, if the generator is associated with a permutation polynomial over we obtain a stronger bound “on average” over all initial values. This bound is new even in the case when M = p is prime.     

On the Complexity of Parallel Algorithms for Computing Inverses in GF(2^m) with m Prime

Inversion over a finite field is usually an expensive operation which is a crucial issue in many applications, such as cryptography and error-control codes. In this paper, three different strategies for computing the inverse over binary finite fields , called Eulerian, Gaussian, and Euclidean, respectively, are discussed and compared in terms of time and space complexity. In particular, some new upper and lower bounds to the respective complexities are evaluated.     

Analytic normal basis theorem

Let p be a prime number, ℚ _p the field of p-adic numbers, and a fixed algebraic closure of ℚ _p . We provide an analytic version of the normal basis theorem which holds for normal extensions of intermediate fields ℚ _p ⊆ K ⊆ L ⊆ .      

Error Correcting Codes, Block Designs, Perfect Secrecy and Finite Fields

The ancient difficulty for establishing a common cryptographic secret key between two communicating parties Alice and Bob is nicely summarized by the Catch-22 dictum of S.J. Lomonaco [1999], to wit: “in order to communicate in secret one must first communicate in secret”. In other words, to communicate in secret, Alice and Bob must already have a shared secret key. In this paper we analyse an algorithm for establishing such a common secret key by public discussion, under the modest and practical requirement that Alice and Bob are initially in possession of keys and , respectively, of a common length which are not necessarily equal but are such that the mutual information is non-zero. This assumption is tantamount to assuming only that the corresponding statistical variables are correlated. The common secret key distilled by the algorithm will enjoy perfect secrecy in the sense of Shannon. The method thus provides a profound generalization of traditional symmetric key cryptography and applies also to quantum cryptography. Here, by purely elementary methods, we give a rigorous proof that the method proposed by Bennett, Bessette, Brassard, Salvail, and Smolin will in general converge to a non-empty common key under moderate assumptions on the choice of block lengths provided the initial bit strings are sufficiently long. Full details on the length requirements are presented. Furthermore, we consider the question of which block lengths should be chosen for optimal performance with respect to the length of the resulting common key. A new and fundamental aspect of this paper is the explicit utilization of finite fields and error-correcting codes both for checking equality of the generated keys and, later, for the construction of various hash functions. Traditionally this check has been done by performing a few times a comparison of the parity of a random subset of the bits. Here we give a much more efficient procedure by using the powerful methods of error-correcting codes. More general situations are treated in Section 8.The research of the first and second authors is supported by grants from NSERC.     

Geometric progressions in sumsets over finite fields

Given two sets , the set of d dimensional vectors over the finite field with q elements, we show that the sumset contains a geometric progression of length k of the form vΛ ^j , where j = 0,…, k − 1, with a nonzero vector and a nonsingular d × d matrix Λ whenever . We also consider some modifications of this problem including the question of the existence of elements of sumsets on algebraic varieties.     

Quadratic-Residue Codes and Cyclotomic Fields

We present an exposition of quadratic-residue codes through their embedding in codes over the quadratic subfield of the th cyclotomic field, the algebraic number field of th roots of unity. This representation allows the development of effective syndrome decoding algorithms that can fully exploit the code’s error-correcting capability. This is accomplished via Galois automorphisms of cyclotomic fields. For each fixed , the general results hold for all pairs , with a finite number of exceptions that depends on . A complete discussion of the set of quadratic-residue codes of length and dimension illustrates these results. This set includes the Golay code, the only perfect binary three-error-correcting code.A preliminary version of this paper was presented at the International Conference on Statistics, Combinatorics and Related Areas, October 3–5, 2003, University of Southern Maine, Portland, ME, USA.     

Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization

We introduce a new method for solving box-constrained mixed-integer polynomial problems to global optimality. The approach, a specialized branch-and-bound algorithm, is based on the computation of lower bounds provided by the minimization of separable underestimators of the polynomial objective function. The underestimators are the novelty of the approach because the standard approaches in global optimization are based on convex relaxations. Thanks to the fact that only simple bound constraints are present, minimizing the separable underestimator can be done very quickly. The underestimators are computed monomial-wise after the original polynomial has been shifted. We show that such valid underestimators exist and their degree can be bounded when the degree of the polynomial objective function is bounded, too. For the quartic case, all optimal monomial underestimators are determined analytically. We implemented and tested the branch-and-bound algorithm where these underestimators are hardcoded. The comparison against standard global optimization and polynomial optimization solvers clearly shows that our method outperforms the others, the only exception being the binary case where, though, it is still competitive. Moreover, our branch-and-bound approach suffers less in case of dense polynomial objective function, i.e., in case of polynomials having a large number of monomials. This paper is an extended and revised version of the preliminary paper [4].     

Surfaces with high contact number and their characterization

The notion of contact number of a Euclidean submanifold was introduced in an earlier article (Proc. Edinb. Math. Soc. 47:69–100, 2004) as the highest order of contact of geodesics and normal sections on the submanifold. It was proved in (Proc. Edinb. Math. Soc. 47:69–100, 2004) that the contact number relates closely with the notions of isotropic submanifolds and holomorphic curves. One important problem concerning contact number is to construct Euclidean submanifolds with high contact number. The purpose of this article is thus to construct Euclidean surfaces with high contact number and to provide simple geometric characterization of such surfaces. Mathematics Subject Classification (2000) Primary 53C40, 53A10 Secondary 53B25, 53C42     

Une Remarque sur une Formule Sommatoire liée à la Somme des Chiffres

Let g ≥ 2 be an integer, and let s(n) be the sum of the digits of n in basis g. Let f(n) be a complex valued function defined on positive integers, such that . We propose sufficient conditions on the function f to deduce the equality . Applications are given, for instance, on the equidistribution mod 1 of the sequence (s(n))^α, where α is a positive real number.     

\lambda-presentable Morphisms, Injectivity and (Weak) Factorization Systems

We show that in a locally -presentable category, every -injectivity class (i.e., the class of all the objects injective with respect to some class of -presentable morphisms) is a weakly reflective subcategory determined by a functorial weak factorization system cofibrantly generated by a class of -presentable morphisms. This was known for small-injectivity classes, and referred to as the ‘small object argument.’ An analogous result is obtained for orthogonality classes and factorization systems, where -filtered colimits play the role of the transfinite compositions in the injectivity case. -presentable morphisms are also used to organize and clarify some related results (and their proofs), in particular on the existence of enough injectives (resp. pure-injectives). Finally, locally -presentable categories are shown to be cellularly generated by the set of morphisms between -presentable objects.