Cryptanalysis of Rédei- and Dickson permutations on arbitrary finite rings

In the RSA public-key cryptosystem the encryption function is a permutation on the residue class ring/N induced by some polynomialX ^k (/N) [X], whereN is the product of two large primes. Variants of the RSA-scheme can be obtained, if this permutation is replaced by different types of rational permutations on/N. A more general approach is the use of arbitrary finite rings instead of residue class rings in cryptography. Since the message space is finite, in either case cryptanalysis can be effected by superenciphering. A serious weakness of those PKCs is the existence of a large number of fixedpoints. But even if there are only few fixedpoints in the message space, the elements of considerable small cyclelength are much inconvenient. Anyway an analysis of the minimal cyclelength, i.e. the minimum of cyclelengths of elements different from fixedpoints, is necessary.In this paper such an analysis will be carried out in the case of Rédei- and Dickson permutations on arbitrary finite rings. The results obtained provide a good basis to construct secure PKCs with best protection against superenciphering. Some of the problems and results in the special cases of finite fields and residue class rings have been stated earlier in the literature (see references).In this paper ring will always mean commutative unitary ring.     

Group Actions on Binary Resilient Functions

Let G_n,t be the subgroup of GL(n,₂) that stabilizes {x₂ⁿ:|x|t}. We determine G_n,t explicitly: For 1tn–2, G_n,t=S_n when t is odd and G_n,t=S_n, when t is even, where S_n<GL(n,₂) is the symmetric group of degree n and GL(n,₂) is a particular involution. Let _n,t be the set of all binary t-resilient functions defined on ₂ⁿ. We show that the subgroup ₂ⁿ(G_n,tG_n,n–1–t)<AGL(n,₂) acts on _n,t/₂. We determine the representatives and sizes of the conjugacy classes of ₂ⁿS_n and ₂ⁿS_n,. These results allow us to compute the number of orbits of _n,t/₂ under the above group action for (n,t)=(5,1) and (6,2). Keywords:General linear group, Affine linear group, Resilient function.     

Group codes on certain algebraic curves with many rational points

We construct a series of algebraic geometric codes using a class of curves which have many rational points. We obtain codes of lengthq ² over _q , whereq = 2q ₀ ² andq ₀ = 2 ⁿ , such that dimension + minimal distance q ² + 1 – q ₀ (q – 1). The codes are ideals in the group algebra _q [S], whereS is a Sylow-2-subgroup of orderq ² of the Suzuki-group of orderq ² (q ² + 1)(q – 1). The curves used for construction have in relation to their genera the maximal number of GF _q -rational points. This maximal number is determined by the explicit formulas of Weil and is effectively smaller than the Hasse—Weil bound.Supported by Deutsche Forschungsgemeinschaft while visiting Essen University     

An isomorphism theorem between the 7-adic integers and a ring associated with a hexagonal lattice

The primary goal of this paper is to prove that a ring defined by L. Gibson and D. Lucas is isomorphic to the ring of 7-adic integers. The ring, denoted byR ₂, arises naturally as an algebraic structure associated with a hexagonal lattice. The elements ofR ₂ consist of all infinite sequences in /(7). The addition and multiplication operations are given in terms of remainder and carries tables. The Generalized Balanced Ternary, denoted byG, is the subring ofR ₂ consisting of all the finite sequences ofR ₂. IfI _k is the ideal ofG consisting of all those sequences whose firstk digits are zero, then the second goal of the paper is to show that the inverse limit ofG/I _k is also isomorphic to the 7-adic integers.     

DFT-based Word Normalization in Finite Supersolvable Groups

In this paper we discuss the word normalization problem in pc presented finite supersolvable groups: given two group elements a and b in normal form the normal form of the product a·b is to be computed. As an alternative to classical collection strategies we present a new DFT-based strategy, which uses fragments of certain irreducible representations of the underlying group. This strategy allows an explicit running time analysis. For example, in the special case of a pc presented p-group G of order pⁿ one needs at most 5·p·n² additions in _e:=/e for the computation of the normal form, where e denotes the exponent of G. Interpreting pc presentations as polynomials in multivariate non-commutative polynomial rings we derive an algorithm for fast polynomial division.     

Nonlinear <Emphasis Type="Italic">p</Emphasis>-ary Sequences

Low correlation p-ary sequences with p an odd prime are constructed. They are obtained as Gray images of codewords of a subcode of the generalized Kerdock codes over the ring _p². They can be shown to be nonlinear in some precise sense. The research of this author is partially supported by NUS-ARF research grant R-146-000-029-112 and DSTA research grant R-394-000-011-422.This research was done while this author was visiting Temasek Laboratories and Department of Mathematics, NUS. The author thanks them for their hospitality.Keywords:Galois rings, Gray map, Kerdock code, CDMA.     

Two “Dual” Families of Nearly-Linear Codes over ℤ p , p odd

Since the paper by Hammons e.a. [1], various authors have shown an enormous interest in linear codes over the ring ℤ₄. A special weight function on ℤ₄ was introduced and by means of the so called Gray map ϕ : ℤ₄→ℤ₂ ² a relation was established between linear codes over ℤ₄ and certain interesting non-linear binary codes of even length. Here, we shall generalize these notions to codes over ℤ _p2 where p is an arbitrary prime. To this end, a new weight function will be proposed for ℤ _p2 . Further, properties of linear codes over ℤ _p2 will be discussed and the mapping ϕ will be generalized to an isometry between ℤ _p2 and ℤ _p ^p , resp. between ℤ _p2 ⁿ and ℤ _p ^pn . Some properties of Galois rings over ℤ _q will be described and two dual families of linear codes of length n = p ^m − 1, gcd(m, p) = 1, over ℤ _q will be constructed. Taking q = p ², their images under the new mapping can be viewed as a generalization of the binary Kerdock and the Preparata code, although they miss some of their nice combinatorial properties. Received: June 19, 2000; revised version: November 6, 2000     

Structural properties and enumeration of quasi cyclic codes

Given any finite fieldF _q , an (N, K) quasi cyclic code is defined as aK dimensional linear subspace ofF _q ^N which is invariant underT ⁿ for some integern, 0 <n N, and whereT is the cyclic shift operator. Quasi cyclic codes are shown to be isomorphic to theF _q []-submodules ofF _q ^N where the product(gl)· is naturally defined as ₀ + ₁T ⁿ +...+ _m T ^mn if()= ₀ + ₁ +...+ _{m m} .In the case where (N/n, q)=1, all quasi cyclic codes are shown to be decomposable into the direct sum of a fixed number of indecomposable components called irreducible cyclicF _q []-submodules providing for the complete characterisation and enumeration of some subclasses of quasi cyclic codes including the cyclic codes, the quasi cyclic codes with a cyclic basis, the maximal and the irreducible ones. Finally a general procedure is presented which allows for the determination and characterisation of the dual of any quasi cyclic code.     

On minimum distance bounds for abelian codes

This paper is an exposition of two methods of formulating a lower bound for the minimum distance of a code which is an ideal in an abelian group ring. The first, a generalization of the cyclic BCH (Bose-Chaudhuri-Hoquenghem) bound, was proposed by Camion [2]. The second method, presented by Jensen [4], allows the application of the BCH bound or any of its improvements by viewing an abelian code as a direct sum of concatenations of cyclic codes. This second method avoids the mathematical analysis required for a direct generalization of a cyclic bound to the abelian case. It can produce a lower bound that improves the generalized BCH bound. We present simple algorithms for 1) deriving the generalized BCH bound for an abelian code 2) determining direct sum decompositions of an abelian code to concatenated codes and 3) deriving a bound on an abelian code, viewed as a direct sum of concatenated codes, by applying the cyclic BCH bound to the inner and outer code of each concatenation. Finally, we point out the applicability of these methods to codes that are not ideals in abelian group rings.     

A solution to Kronecker's problem

Consider [x ₁,...,x _n], the multivariate polynomial ring over integers involvingn variables. For a fixedn, we show that the ideal membership problem as well as the associated representation problem for [x ₁,...,x _n] are primitive recursive. The precise complexity bounds are easily expressible by functions in the Wainer hierarchy.Thus, we solve a fundamental algorithmic question in the theory of multivariate polynomials over the integers. As a direct consequence, we also obtain a solution to certain foundational problem intrinsic to Kronecker's programme for constructive mathematics and provide an effective version of Hilbert's basis theorem. Our original interest in this area was aroused by Edwards' historical account of theKronecker's problem in the context of Kronecker's version of constructive mathematics.Supported by an Italian grant Italian MURST 40% Calcolo Algebraico e Simbolico 1993 and an NSF grant: #CCR-9002819.     

Formally Self-Dual Codes Related to Type II Codes

Shadows play an important role in the study of self-dual codes. In this note, we give constructions of formally self-dual codes using self-dual codes and their shadows. As an example, a class of binary formally self-dual codes related to extremal Type II code is introduced. This work was partially supported by the Grant-in-Aid for Scientific Research (No. 10740044), the Ministry of Education, Science, Sports and Culture, Japan, and the Sumitomo Foundation (No. 990645), Japan.Keywords:Formally self-dual codes, Type II codes and codes over _2k.     

On strong Dickson pseudoprimes

It is known that the Lucas sequenceV _n(,c)=aⁿ + bⁿ,a, b being the roots ofx ² – x + c=0 equals the Dickson polynomial .^n–2i Lidl, Müller and Oswald recently defined a number b to be a strong Dickson pseudoprime to the parameterc (shortlysDpp(c)) if [itg_n(b, c)b modn for all b. These numbers seem to be very appropriate for a fast probabilistic prime number test. In generalizing results of the above mentioned authors a criterion is derived for an odd composite number to be ansDpp(c) for fixedc. Furthermore the optimal parameterc for the prime number test is determined.     

Bounds on the minimum distance of the duals of extended BCH codes over\mathbb{F}_p

LetC be an extended cyclic code of lengthp ^m over . The border ofC is the set of minimal elements (according to a partial order on [0,p ^m –1]) of the complement of the defining-set ofC. We show that an affine-invariant code whose border consists of only one cyclotomic coset is the dual of an extended BCH code if, and only if, this border is the cyclotomic coset, sayF(t, i), ofp ^t –1–i, with 1 t m and 0 i < p–1. We then study such privileged codes. We first make precize which duals of extendedBCH codes they are. Next, we show that Weil's bound in this context gives an explicit formula; that is, the couple (t, i) fully determines the value of the Weil bound for the code with borderF(t, i). In the case where this value is negative, we use the Roos method to bound the minimum distance, greatly improving the BCH bound.     

Linear codes with balanced weight distribution

In this paper, we study particular linear codes defined overF _q , with an astonishing property, their weight distribution is balanced, i.e. there is the same number of codewords for each nonzero weight of the code. We call these codesBWD-codes. We first study BWD-codes by means of the Pless identities and we completely characterize the two-weight projective case. We study the class of codes defined under subgroups of the multiplicative group ofF _q ^s , using the Gauss sums. Then, given a primep and an integerN dividingp – 1, we construct all theN-weight BWD-codes of that class. We conclude this paper by some tables of BWD-codes and an open problem.     

Finding connected components of a semialgebraic set in subexponential time

Let a semialgebraic set be given by a quantifier-free formula of the first-order theory of real closed fields with atomic subformulae of type (f _i 0), 1 i k where the polynomialsf _i [X ₁,..., X_n] have degrees deg(f _i <d and the absolute value of each (integer) coefficient off _i is at most 2 ^M . An algorithm is designed which finds the connected components of the semialgebraic set in time . The best previously known bound for this problem follows from Collins' method of Cylindrical Algebraic Decomposition.     

Duadic Codes over F2 + uF2

Duadic codes over F ₂ + u F ₂ are introduced as abelian codes by their zeros. This is the function field analogue of duadic codes over Z ₄ introduced recently by Langevin and Solé. They produce binary self-dual codes via a suitable Gray map. Their binary images are themselves abelian, thus generalizing a result of van Lint for cyclic binary codes of even length. We classify them in modest lengths and exhibit interesting non-cyclic examples. Received: April 26, 2000; revised version: May 5, 2001     

Construction of binary minimal product parity-check matrices

A parity-check matrix H of a given code is called minimal if it has minimum number of nonzero entries among all parity-check matrices representing . Let and be two binary linear block codes with minimal parity-check matrices H ₁ and H ₂, respectively. It is shown that, using H ₁ and H ₂, one can efficiently generate a minimal parity-check matrix for the product code .     

Toric Codes over Finite Fields

In this note, a class of error-correcting codes is associated to a toric variety defined over a finite field _q, analogous to the class of AG codes associated to a curve. For small q, many of these codes have parameters beating the Gilbert-Varshamov bound. In fact, using toric codes, we construct a (n,k,d)=(49,11,28) code over ₈, which is better than any other known code listed in Brouwers tables for that n, k and q. We give upper and lower bounds on the minimum distance. We conclude with a discussion of some decoding methods. Many examples are given throughout.     

Some remarks on strong fibonacci pseudoprimes

Necessary and sufficient conditions are given for an odd composite integern to be a Fibonacci pseudoprime of them ^th kind for allm. One consequence of this characterization is that any such pseudoprime has to be a Carmichael number.This author expresses his special thanks to the School of Information Engineering at Teesside Polytechnic, Middlesbrough, England, for its support and hospitality during a visiting appoint of 3 months in 1989, when this paper was written     

Dual codes of systematic group codes over abelian groups

For systematic codes over finite fields the following result is well known: If [I∣P] is the generator matrix then the generator matrix of its dual code is The main result is a generalization of this for systematic group codes over finite abelian groups. It is shown that given the endomorphisms which characterize a group code over an abelian group, the endomorphisms which characterize its dual code are identified easily. The self-dual codes are also characterized. It is shown that there are self-dual and MDS group codes over elementary abelian groups which can not be obtained as linear codes over finite fields. Received March 7, 1995; revised version April 3, 1996