An analysis of a class of algorithms for S-box construction

We analyze a very general class of algorithms for constructingm-bit invertible S-boxes called bit-by-bit methods. The method builds an S-box one entry at a time, and has been proposed by Adams and Tavares [2] and Forre [11] to construct S-boxes that satisfy certain cryptographic properties such as nonlinearity and the strict avalanche criterion. We prove, both theoretically and empirically, that the bit-by-bit method is infeasible form>6. The author is currently employed by the Distributed System Technology Center (DSTC), Brisbane, Australia. Correspondence should be sent to ISRC, QUT Gardens Point, 2 George Street, GPO Box 2434, Brisbane, Queensland 4001, Australia.     

Restricted compositions and permutations: From old to new Gray codes

Any Gray code for a set of combinatorial objects defines a total order relation on this set: x is less than y if and only if y occurs after x in the Gray code list. Let ? denote the order relation induced by the classical Gray code for the product set (the natural extension of the Binary Reflected Gray Code to k-ary tuples). The restriction of ? to the set of compositions and bounded compositions gives known Gray codes for those sets. Here we show that ? restricted to the set of bounded compositions of an interval yields still a Gray code. An n-composition of an interval is an n-tuple of integers whose sum lies between two integers; and the set of bounded n-compositions of an interval simultaneously generalizes product set and compositions of an integer, and so ? put under a single roof all these Gray codes.As a byproduct we obtain Gray codes for permutations with a number of inversions lying between two integers, and with even/odd number of inversions or cycles. Such particular classes of permutations are used to solve some computational difficult problems.     

Sorting by Short Block-Moves

Sorting permutations by operations such as reversals and block-moves has received much interest because of its applications in the study of genome rearrangements and in the design of interconnection networks. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. This paper investigates the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation. A 4/3 -approximation algorithm for this problem is presented. Woven double-strip permutations are defined and a polynomial-time algorithm for this class of permutations is devised that employs graph matching techniques. A linear-time maximum matching algorithm for a special class of grid graphs improves the time complexity of the algorithm for woven double-strip permutations. Received June 1, 1997; revised July 25, 1998.     

Scaled and permuted string matching

The goal of scaled permuted string matching is to find all occurrences of a pattern in a text, in all possible scales and permutations. Given a text of length n and a pattern of length m we present an O(n) algorithm.     

A generalized constructive algorithm using insertion-based heuristics

In this paper, a generalized constructive algorithm referred to as GCA is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework, referred to as PERMGEN, forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of GCA are identified. Features and benefits of the generalized algorithm are presented through the extension of the NEH heuristic, a successful heuristic solution approach of Nawaz, Enscore, and Ham for the permutation flowshop problem (PFSP). The goal of the experimental study is to improve the performance of the NEH heuristic on the PFSP. To achieve this goal, the space of algorithmic control arguments is searched for a combination of values that define an algorithm providing lower makespan solutions than NEH, in a linear increase of CPU time. Computational experiments on a set of 120 benchmark problem instances, originally proposed by Taillard, are performed to establish a more robust version of the original NEH constructive heuristic. The proposed procedures outperform NEH, preserving its efficiency and simplicity.     

Shorter strings containing all k-element permutations

We consider the problem of finding short strings that contain all permutations of order k over an alphabet of size n, with k?n. We show constructively that k(n−2)+3 is an upper bound on the length of shortest such strings, for n?k?10. Consequently, for n?10, the shortest strings that contain all permutations of order n have length at most n²−2n+3. These two new upper bounds improve with one unit the previous known upper bounds.     

提高梳棉机盖板分梳能力的技术措施

总结提高A186型梳棉机盖板分梳能力的技术措施。分析了A186梳棉机盖板分梳中存在的问题,提出了相应的改进措施。采用多台梳棉机盖板重组或单台盖板优化排列的方法以保证盖板梳理区梳理隔距的准确性;对盖板进行双区分梳改造以提高盖板的分梳效果;加强生产中盖板的维护保养,可有效提高盖板平整度和针布锋利度。认为:采取以上三项措施,可保证梳理隔距的准确,减少盖板充塞、提高盖板分梳效果及排杂能力,能有效减少棉结杂质,提高成纱质量。     

Image encryption based on the finite field cosine transform

In this paper, a novel image encryption scheme is proposed. The technique involves two steps, where the finite field cosine transform is recursively applied to blocks of a given image. In the first step, the image blocks to be transformed result from the regular partition of subimages of the original image. The transformed subimages are regrouped and an intermediate image is constructed. In the second step, a secret-key determines the positions of the intermediate image blocks to be transformed. Besides complying with the main properties required by image encryption methods, the proposed scheme provides benefits related to computational complexity and encoding of the ciphered-images.     

On the combinatorics of suffix arrays

We present a bijective characterization of suffix array permutations obtained from a characterization of Burrows–Wheeler arrays given in [1]. We show that previous characterizations [2], [3], [4], or their analogs, can be obtained in a simple and elegant way using this relationship. To demonstrate the usefulness of our approach, we obtain simpler proofs for some known enumeration results about suffix arrays [3]. Our characterization of suffix arrays is the first based on their relationship with Burrows–Wheeler permutations.