F_2~n上4次正形置换多项式的形式与计数

分组密码是现代密码学中一个重要的研究分支,而置换理论在分组密码中有重要的地位.1995年,美国Teledyne电子技术公司的Lothrop Mittenthal博士提出了一种置换,即正形置换.正形置换是一类完全映射,完全映射是由Mann在1942年研究正交拉丁方的构造时引入的,其具有良好的密码学性质(良好的扩散性和完全平衡性),因此,正形置换常用来构造密码系统的算法,研究正形置换也就非常有必要.本文根据文章[1]的方法讨论了F2n(n=4,5)上的4次正形置换多项式的形式与计数,至于n5的情形我们将在以后的篇章中继续讨论.     

F2^n上4次正形置换多项式的形式与计数

分组峦码是现代密码学中一个重要的研究分支，而置换理论在分组密码中有重要的地位．199j年，美国Tcledyne电子技术公司的Lothrop Mittenthal博士提出了一种置换，即正形置换．止形置换是一类完全映射，完全映射是由Mann在1942年研究正交拉丁方的构造时引入的，其具有良好的密码学性质（良好的扩散性和完令平衡性），因此，正形置换常用来构造密码系统的算法，研究正形置换也就非常订必要．本文根据文章[1]的方法讨论了F2^n（n=4，5）上的4次正形置换多项式的形式与计数，至于n〉5的情形我们将在以后的篇章中继续讨论．     

具有最高代数次数的2n元n维Bent函数的构造

本文给出了代数次数达到最高的一类布尔置换的代数标准形 ;并用m序列的状态转移矩阵和所得置换 ,构造了一类代数次数达到最高的 2n元n维Bent函数 ,用这类函数所构造的S盒具有较高的安全强度 .     

坡上矩阵可逆的条件

坡S是一个元素满足条件s 1=1的交换半环．证明了坡S上n×n矩阵A可逆当且仅当∑k=1 n aik=1(i=1,2,…,n)且aikajk=0(i≠j,k=1,2,…,n)．在坡S中可定义补元,得到S上每一个可逆矩阵是一个置换矩阵当且仅当S不包含不同于0和1的有补元．     

全轮换积的存在与判别法

n元集合Q上的一个靠次轮换称为一个Q-全轮换或n元全轮换,在不致混淆时简称全轮换。本文讨论的问题是:给了一个Q-全轮换σ及Q上的一个置换x,其乘积σx是否是全轮换,证明了对于任一个n元全转换σ及任一个n元偶置换型,总有一个以此为型的置换x,使得σx为n元全轮换(存在定理)。给出了对于给定的全轮换σ及偶置换x,判断σx是否是全轮换的一个方法(判别定理),并给出了计算机方法。     

关于正态随机变量线性组合的分布

本文用不同于Rosenberg例的方法构造了两个正态随机变量之和不是正态随机变量的例子,并给出了任意n(≥2)个正态随机变量之和不是正态随机变量的例子。     

有限布尔代数上的置换矩阵

本文研究了任意有限布尔代数上的置换矩阵的特征，根据此特征可构造各种类型的置换矩阵，并给出了n阶置换矩阵个数的计数公式，然后证明了n阶矩阵A可逆的充分必要条件是A为n阶置换矩阵.     

(0,1)-方阵的置换相抵

<正> 设A和B是n阶方阵,如果方阵A可经行的置换与列的置换化为方阵B,即存在n阶置换方阵P和Q,使得B=PAQ,则方阵A和B称为是置换相抵的.1974年,B.Gordan,T.S.Motzkin和L.Welch用图论的方法,证明了当permanent为1,2和3时n阶(0,1)-方阵置换相抵标准形的定理.由于方阵的置换相抵是方阵的一种等价关系,它自然应属于矩阵论的范畴,因此有必要从矩阵论的角度重新加以讨论.本文的目的是给出B.Gordan等人的结论的一个矩阵证明,方法是构造性的,且具有一般意义.作为一个说明,     

一个在置换图中寻找DFS树的最优算法

本是通过在连通置换图中构造辅助树的方法,给出了一个在具有n个顶点的置换图G中寻找深度优先支撑树（简称,DFS树）的最优算法,并证明了该算法的时间复杂性为O(n)。     

相关免疫置换及其构造

引入了相关免疫置换的概念，给出了构造相关免疫置换的一个方法，且由该方法构造的相关免疫置换的坐标函数的非零线性组合都不是仿射函数，最后解决了该方法构造的相关免疫置换的计数问题。     

Arc permutations

Arc permutations and unimodal permutations were introduced in the study of triangulations and characters. This paper studies combinatorial properties and structures on these permutations. First, both sets are characterized by pattern avoidance. It is also shown that arc permutations carry a natural affine Weyl group action, and that the number of geodesics between a distinguished pair of antipodes in the associated Schreier graph, and the number of maximal chains in the weak order on unimodal permutations, are both equal to twice the number of standard Young tableaux of shifted staircase shape. Finally, a bijection from non-unimodal arc permutations to Young tableaux of certain shapes, which preserves the descent set, is described and applied to deduce a conjectured character formula of Regev.     

The design of composite permutations with applications to DES-like S-boxes

This paper presents an iterative construction method for building composite permutations. Its efficiency is based on the concepts of pre-computation and equivalence classes. Equivalence class representatives of permutations on four bits are pre-computed. These class representatives can serve as input to the construction method, however, the results are also of independent interest for applications in cryptography. A well-known example of a cryptosystem using composite permutations for its Substitution boxes (S-boxes) is the Data Encryption Standard (DES). Throughout the paper, DES-like S-boxes are defined as mappings satisfying all design criteria as disclosed by one of the designers of DES. All permutations on four bits with DES-like properties are identified. Starting with pre-computed representatives of classes with such permutations, two iterations of a specialized version of the algorithm are applied to obtain bounds on the minimum differential uniformity and minimum non-linear uniformity of DES-like S-boxes. It is established that the two values cannot be less than eight, and that DES-like S-boxes for which the values are both equal to 12 do exist. In addition, if the non-linear uniformity of each of the four permutations in a DES-like S-box is at most six, as in all DES S-boxes, then its non-linear uniformity cannot be less than ten and its minimum differential uniformity equals 12.     

The pure descent statistic on permutations

We introduce a new statistic based on permutation descents which has a distribution given by the Stirling numbers of the first kind, i.e., with the same distribution as for the number of cycles in permutations. We study this statistic on the sets of permutations avoiding one pattern of length three by giving bivariate generating functions. As a consequence, new classes of permutations enumerated by the Motzkin numbers are obtained. Finally, we deduce results about the popularity of the pure descents in all these restricted sets.     

A method to calculate differential uniformity for permutations

We introduce a search algorithm to find permutation S-boxes with low differential uniformity, high nonlinearity and high algebraic degree, which play important roles in block ciphers. Inspired by the results of our search algorithm, we propose a method to calculate differential uniformity for permutations. We establish a sufficient condition for differentially 4-uniform permutations based on our method and construct some example classes of differentially 4-uniform permutations.     

New differentially 4-uniform permutations from modifications of the inverse function

Finding permutations with good cryptographic parameters is a good research topic about constructing a secure S-box in substitution-permutation networks. In particular constructing differentially 4-uniform permutations has made considerable progress in recent years. In this paper, we present new differentially 4-uniform permutations from the inverse function composed by disjoint cycles. Our new differentially 4-uniform permutations have high nonlinearity and low differential-linear uniformity. We give the differential spectrum and the extended Walsh spectrum of some of our differentially 4-uniform permutations, and then we can see that they are CCZ-inequivalent to some permutations whose differential spectrum and extended Walsh spectrum are known.     

Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three

We consider the problem of enumerating the permutations containing exactly k occurrences of a pattern of length 3. This enumeration has received a lot of interest recently, and there are a lot of known results. This paper presents an alternative approach to the problem, which yields a proof for a formula which so far only was conjectured (by Noonan and Zeilberger). This approach is based on bijections from permutations to certain lattice paths with “jumps,” which were first considered by Krattenthaler.     

An arithmetic of complete permutations with constraints, I: an exposition of the general theory

We develop an arithmetic of complete permutations of symmetric, integral bases; this arithmetic is comparable to that of perfect systems of difference sets with which there are several interrelations. Super-position of permutations provides the addition of this arithmetic. Addition if facilitated by complete permutations with a certain “splitting” property, allowing them to be pulled apart and reassembled. The split permutations also provide a singular direct product for complete permutations in conjunction with the multiplication (direct product) of the arithmetic which itself derives from that for perfect systems of difference sets.

We pay special attention to complete permutations satisfying constraints both fixed and variable; this is equivalent to embedding partial complete permutations in complete permutations. In the sequel, using this arithmetic, we investigate the spectra of certain constraints with respect to central integral bases which are of interest for the purpose of giving further constructions either of complete permutations with constraints or of irregular, extremel perfect systems of difference sets.     

An arithmetic of complete permutations with constraints, II: case studies

Using the arithmetic of complete permutations developed in the first part of this paper, we investigate the spectra of certain constraints with respect to central, integral bases which are of interest for the purposes of giving further constructions either of complete permutations with constraints or of irregular, critical perfect systems of difference sets. We also present, in the appendices, catalogues of examples and enumerative data based on computer studies.