On New Perfect Binary Nonlinear Codes

 We present a new construction of binary nonlinear perfect codes with minimum distance 3 and lowerbound the number of nonequivalent such codes. Received: November 26, 1996; revised version: March 14, 1997     

Weight Distribution of the Hermitian Forms Codes

 We recall the construction of the hermitian-forms codes and some results about hermitians forms and exponential sums. With the help of these results, we give the weight distribution of the hermitian-forms codes and give some examples for which experimental computations have been made. Received: September 8, 1993; revised version: October 4, 1995     

On the Covering Radius of Long 5-ary BCH Codes with Minimum Distance 7

 We study S. D. Cohen’s method of estimating the covering radius of long primitive non-binary BCH codes with prime field alphabet. As an application we show that the covering radius is at most 7 for long 5-ary BCH codes with minimum distance seven. Received: November 13, 1996; revised version: March 11, 1997     

Bounds on the Weight Hierarchies of Extremal Non-chain Codes of Dimension 4

 The weight hierarchy of a linear [n, k; q] code C over GF(q) is the sequence (d ₁, d ₂, . . . , d _k ) where d _r is the smallest support of an r-dimensional subcode of C. An [n, k; q] code is external non-chain if for any r and s, where 1≦r<s≦k, there are no subspaces D and E, such that D⊂E, dim D=r, dim E=s, w _S (D)=d _r , and w _S (E)=d _s . Bounds on the weight hierarchies of such codes of dimension 4 are studied. Received: September 27, 1996     

Long Binary Narrow-Sense BCH Codes Are Normal

Let C be the binary narrow-sense BCH code of length where m is the order of 2 modulo n. Using characters of finite fields and a theorem of Weil, and results of Vladut-Skorobogatov and Lang-Weil we prove that the code C is normal in the non-primitive case if and in the primitive case if where the constant depends only on t. Received January 4, 1994     

F-partitions of Cyclic Groups

 An F-partition is a partition of an abelian group with the property that the linear space generated by the indicator functions of the subsets in the partition is invariant under Fourier transformation. In the present paper we study the special case of F-partitions over cyclic groups. We introduce the concept of multiplicative partitions and we show that for cyclic groups of prime orders any F-partition is necessarily multiplicative. Received: October, 1996; revised version: March 17, 1997     

An Elementary Proof to the Weight Distribution Formula of the First Order Shortened Reed-Muller Coset Code

 Let RM(m, r) be the shortened Reed-Muller code of order r and of length 2 ^m −1. A simple proof to the Kasami’s weight distribution formula (see [2] and [3, p. 441]) of the cosets of RM(m, 1) in RM(m, 2) is given. The derivation of this distribution formula (21) is based only on elementary properties of the trace map and the Dickson theory of quadratic forms (see [1, pp. 197–199] and [3, pp. 434–442]) is no longer needed. Received: September 25, 1996; revised version: March 11, 1997     

Minimal Primary Decomposition and Factorized Gröbner Bases

 This paper continues our study of applications of factorized Gr?bner basis computations in [8] and [9]. We describe a way to interweave factorized Gr?bner bases and the ideas in [5] that leads to a significant speed up in the computation of isolated primes for well splitting examples. Based on that observation we generalize the algorithm presented in [22] to the computation of primary decompositions for modules. It rests on an ideal separation argument. We also discuss the practically important question how to extract a minimal primary decomposition, neither addressed in [5] nor in [17]. For that purpose we outline a method to detect necessary embedded primes in the output collection of our algorithm, similar to [22, cor. 2.22]. The algorithms are partly implemented in version 2.2.1 of our REDUCE package CALI [7]. Received: September 29, 1995; revised version: May 23, 1996     

Cryptanalysis of ‘Less Short’ RSA Secret Exponents

 In some applications of RSA, it is desirable to have a short secret exponent d. Wiener [6], describes a technique to use continued fractions (CF) in a cryptanalytic attack on an RSA cryptosystem having a ‘short’ secret exponent. Let n=p ⋅ q be the modulus of the system. In the typical case that G=gcd(p−1, q−1) is small. Wiener’s method will give the secret exponent d when d does not exceed (approximately) n ^1/4. Here, we describe a general method to compute the CF-convergents of the continued fraction expansion of the same number as in Wiener (which has denominator d ⋅ G) up to the point where the denominator of the CF-convergent exceeds approximately n ^1/4. When d<n ^1/4 this technique determines d, p, and q as does Wiener’s method. For larger values of d there is still information available on the secret key. An estimate is made of the remaining workload to determine d, p and q. Roughly speaking this workload corresponds to an exhaustive search for about 2r+8 bit, where r=ln₂ d/n ^1/4. Received: September 30, 1996; revised version: March 7, 1997     

Safe Operators: Brackets Closed Forever Optimizing Optimal λ-Calculus Implementations

 Considerations from category theory described in [1] have permitted to add new rewriting rules for optimal reductions of the λ-calculus [19, 14]. These rules produce an impressive improvement in the performance of the reduction system, and provide a first step towards the solution of the well known and crucial problem of accumulation of control operators. In this paper, after an introduction to optimal reductions, we exhibit the aforementioned problem and prove the correctness of the new rules. Received August 28, 1995; revised version August 1, 1996     

An Inequality About the Largest Roots of a Polynomial

 We present an upper bound for the product of the k largest roots of a monic polynomial of degree n with complex coefficients. For that, we use the theory of compound matrices and the localization of the eigenvalues of matrices. Received: February 26, 1996; revised version: March 20, 1997     

Properness and Inversion of Rational Parametrizations of Surfaces

 In this paper we characterize the properness of rational parametrizations of hypersurfaces by means of the existence of intersection points of some additional algebraic hypersurfaces directly generated from the parametrization over a field of rational functions. More precisely, if V is a hypersurface over an algebraically closed field ? of characteristic zero and is a rational parametrization of V, then the characterization is given in terms of the intersection points of the hypersurfaces defined by x _i q _i (tˉ)−p _i (tˉ), i=1,...,n over the algebraic closure of ?(V). In addition, for the case of surfaces we show how these results can be stated algorithmically. As a consequence we present an algorithmic criteria to decide whether a given rational parametrization is proper. Furthermore, if the parametrization is proper, the algorithm also computes the inverse of the parametrization. Moreover, for surfaces the auxiliary hypersurfaces turn to be plane curves over ?(V), and hence the algorithm is essentially based on resultants. We have implemented these ideas, and we have empirically compared our method with the method based on Gr?bner basis. Received: November 20, 2000; revised version: November 20, 2001     

The Matroid of Supports of A Linear Code

 A relation between the Hamming weight enumerator of a linear code and the Tutte polynomial of the corresponding matroid has been known since long ago. It provides a simple proof of the MacWilliams equation (see D. Welsh, Matroid Theory (1976)). In this paper we prove analogous results for the support weight distributions of a code. Received March 5, 1996; revised version October 28, 1996     

Integral Bases for Subfields of Cyclotomic Fields

 Integral bases of cyclotomic fields are constructed that allow to determine easily the smallest cyclotomic field in which a given sum of roots of unity lies. For subfields of cyclotomic fields integral bases are constructed that consist of orbit sums of Galois groups on roots of unity. These bases are closely related to the bases of the enveloping cyclotomic fields mentioned above. In both situations bases over the rationals and over cyclotomic fields are treated. Received: March 22, 1995; revised version: July 3, 1996     

Universal Sequences

 An (n, k)-universal sequence is a binary sequence with the property that each window of size k and span at most n is covered by the sequence, i.e., each sequence of length k occurs as the content of a shift of the window. We derive upper and lower bounds on the minimum length of universal sequences, both for the linear case and the circular case. Received: November 4, 1996     

On the Number of Special Permutation-Invariant Orbits and Terms

 This note presents a lower and an upper bound for the cardinality of the set of special permutation-invariant orbits and a formula for the number of special terms. Received: August 24, 1994; revised version: October 17, 1996/March 21, 1997     

On the Uniformity of Distribution of the ElGamal Signature

 We show that, under some natural conditions,the pairs (r,s) produced by the ElGamal signature scheme are uniformly distributed. In particular this implies that values of r and s are not correlated. The result is based on some new estimates of exponential sums. Received: May 17, 2000; revised version: August 23, 2001     

Extended Classical Goppa Codes

We construct extended classical Goppa codes that can have unrestricted block length. The parameters of the codes are estimated, and the standard Berlekamp–Massey error processor is adapted to the codes. Received: July 5, 1999; revised version: February 25, 2000     

Linear Bijections and the Fast Fourier Transform

 Fast Fourier transform algorithms rely upon the choice of certain bijective mappings between the indices of the data arrays. The two basic mappings used in the literature lead to Cooley–Tukey algorithms or to prime factor algorithms. But many other bijections also lead to FFT algorithms, and a complete classification of these mappings is provided. One particular choice leads to a new FFT algorithm that generalizes the prime factor algorithm. It has the advantage of reducing the floating point operation count by reducing the number of trigonometric function evaluations. A certain equivalence relation is defined on the set of bijections that lead to FFT algorithms, and its connection with isomorphism classes of group extensions is studied. Under this equivalence relation every equivalence class contains bijections leading to an FFT algorithm of the new type. Received October 27, 1994; revised version January 25, 1996     

Prefix-Rewriting on Context-Free Groups

 A class of groups that has received much attention is the class of context-free groups. This class of groups can be characterized algebraically as well as through some language-theoretical properties as well as through certain combinatorial properties of presentations. Here we use the fact that a finitely generated group is context-free if and only if it admits a finite complete presentation of a certain form that we call a virtually free presentation. It is known that the generalized word problem for context-free groups is decidable. Here we show how prefix-rewriting systems can be used to solve this problem. In fact, we show that the Knuth-Bendix completion procedure always terminates when applied to prefix-rewriting systems on virtually free presentations of context-free groups. In addition, we present a specialized completion algorithm for prefix-rewriting systems on virtually free presentations which has polynomial-time complexity. Thus, the uniform generalized word problem for virtually free presentations of context-free groups is decidable in polynomial-time. Since finitely generated subgroups of context-free groups are again context-free, they admit presentations of the same form. We present a polynomial-time algorithm that, given a virtually free presentation of a context-free group G and a finite subset U of G as input, computes a virtually free presentation for the subgroup of G that is generated by U. Received: January 13, 1995; revised version: June 24, 1996