有限域上长为2mpn 的负循环码

设F_q 是奇数阶有限域. 本文主要借助X^2mpn+1 在F_q 上的不可约因式分解来确定有限域F_q上所有长为2^mpⁿ 的负循环码和自对偶的负循环码的生成多项式, 这里p 是q-1 的奇素因子, m 和n是正整数.     

线性流形上的广义反射矩阵反问题

设 R∈C^m×m 及 S∈C^n×n 是非平凡Hermitian酉矩阵, 即 R^H=R=R^-1≠±I_m ,S^H=S=S^-1≠±I_n.若矩阵 A∈C^m×n 满足 RAS=A, 则称矩阵 A 为广义反射矩阵.该文考虑线性流形上的广义反射矩阵反问题及相应的最佳逼近问题.给出了反问题解的一般表示, 得到了线性流形上矩阵方程AX₂=Z₂, Y₂^H A=W₂^H 具有广义反射矩阵解的充分必要条件, 导出了最佳逼近问题唯一解的显式表示.     

各向异性Besov-Wiener类的平均宽度

得到了各向异性Besov Wiener类S^r_pqθb(R^d)和S^r_pqθB((R^d))在L_q(R^d) ( 1≤q≤p <∞ )内及其对偶情形的平均σ- K宽度和平均σ- L宽度的弱渐近估计 .     

决定类数为一的(2,2,…,2)型代数函数域

设k=F_q(t)为F_q上以t为变元的有理函数域,F_q为q元域,特征不是2。设L=k(√D₁,…,√D_n~(1/2))是k的2ⁿ次扩张,常数域为F_q,D_i∈F_q[t],n>1。本文证明了:(1)除子类数为1的域L恰为k(√P₁,√P₂)和k(√P₁P₂,√P₁P₃),其中P_i∈F_q[t]为互异一次多项式。(2)理想类数为1的虚域L=k(√D₁,√D₂)(即L的整数环是唯一析因环)必是D₁=t;而D₂=t³-t-1(q=3),t²-t-1(q=3),t~2+2(q=5),或t+c,c∈F_q(或其在变换下的变形)。     

关于Bernoulli-Goss多项式的一些注记

Goss和冯克勤证明了:对q≥2,F_q[T]中存在无穷多不正规的不可约多项式。Ireland和Small给出了第n个Bernoulli-Goss多项式(1≤n≤p²—1)的明确表达式,利用这个结果,他们对于3≤p≤269求出所有形为T²—a(a∈F_P[T])的正规二次不可约多项式。本文对n有两项q-adic展开的情形,给出F_q[T]中第n个Bernoulli-Goss多项式的明确表达式。由此证明了:对任意q≥3,F_q[T]中存在无穷多不可约多项式同时是第一类和第二类不正规的,我们还给出二次不可约多项式正规性的一些等价条件。基于文献[3]中的计算结果,我们决定出特征不超过269的所有F_q[T]中二次正规不可约多项式。     

确定凸多边形可碰撞区域的快速算法

设P=(p₀,p₁,…,p_n-1)与Q=(q₀,q₁,…,q_n-1)是任二互不相交的凸多边形,本文研究了如何快速确定它们的可碰撞区域和可移动区域的问题. 文中提出了可碰撞性判定的新方法,研究了斜支撑线的基本性质,利用这些性质构造出了求斜支撑线的快速算法,其时间复杂度为O(log²(n+m)),在此基础上给出了确定可碰撞区域和可移动区域的时间复杂度为O(log²(n+m))的快速算法.     

一类新的有限域上的置换多项式

本文研究了有限域上置换多项式的构造问题.利用分段方法构造了F_q²上形如（x^q-x+c）^{（k（q2-1））/（d）+1}+x^q+x的置换多项式,其中1≤k < d且d是q-1的任意因子,推广了已有文献中的某些结果.     

偶错位图的张量幂的最大独立集和自同构群

若A_n 是X := {1, 2,..., n} 上的偶置换构成的交错群, E_n 是X 上的偶错位集, 则Cayley 图AΓ_n := Γ(A_n, E_n) 称为偶错位图. 令AΓ_n^q 为q 个AΓ_n 的张量幂. 在本文中, 我们研究了AΓ_n^q 的连通性、直径、独立数、团数、色数和最大独立集等性质. 利用AΓ_n^q 最大独立集的结果, 我们完全确定了AΓ_n^q 的自同构群的结构.     

Sobolev-Wiener空间上的无穷维宽度和最优插值问题

本文引入了一类定义在全实数轴上的Sobolev-Wiener空间,在其中讨论了点集的无穷维宽度和最优插值问题.求出了W_∞,p^r(R)在L_p(R)尺度下无穷维Ko-lmogorov宽度、线性宽度的精确值(强渐近精确值),并解决了最优插值问题.     

关于F2n中的和集

设F₂为两个元素组成的有限域, F₂ⁿ 为F₂上的n维向量空间. 对于集合A, B ⊆ F₂ⁿ , 它们的和集定义为所有两两互异的和a+b所组成的集合, 其中a∈A, b∈B. Green 和Tao 证明了: 设K > 1,如果A, B ? F₂ⁿ 且|A + B|≤K|A|^1/2|B|^1/2, 则存在一个子空间H?F₂ⁿ 满足
|H|>>exp(-O(√KlogK))|A|
以及x,y∈F₂ⁿ, 使得
|A∩(x+H)|^1/2|B∩(y+H)|^1/2≥1/2K|H|.
本文我们将使用Green 和Tao 的方法并作一些修改, 证明如果|H|>>exp(-O(√K))|A|,
则以上的结论仍然成立.     

Successive minima profile,lattice profile,and joint linear complexity profile of pseudorandom multisequences

In this paper we use the successive minima profile to measure structural properties of pseudorandom multisequences. We show that both the lattice profile and the joint linear complexity profile of a multisequence can be expressed in terms of the successive minima profile.     

The expectation and variance of the joint linear complexity of random periodic multisequences

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. By using the generalized discrete Fourier transform for multisequences, Meidl and Niederreiter determined the expectation of the joint linear complexity of random N-periodic multisequences explicitly. In this paper, we study the expectation and variance of the joint linear complexity of random periodic multisequences. Several new lower bounds on the expectation of the joint linear complexity of random periodic multisequences are given. These new lower bounds improve on the previously known lower bounds on the expectation of the joint linear complexity of random periodic multisequences. By further developing the method of Meidl and Niederreiter, we derive a general formula and a general upper bound for the variance of the joint linear complexity of random N-periodic multisequences. These results generalize the formula and upper bound of Dai and Yang for the variance of the linear complexity of random periodic sequences. Moreover, we determine the variance of the joint linear complexity of random periodic multisequences with certain periods.     

Remarks on the <Emphasis Type="Italic">k</Emphasis>-error linear complexity of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic sequences

Recently the first author presented exact formulas for the number of 2 ⁿ -periodic binary sequences with given 1-error linear complexity, and an exact formula for the expected 1-error linear complexity and upper and lower bounds for the expected k-error linear complexity, k ≥ 2, of a random 2 ⁿ -periodic binary sequence. A crucial role for the analysis played the Chan–Games algorithm. We use a more sophisticated generalization of the Chan–Games algorithm by Ding et al. to obtain exact formulas for the counting function and the expected value for the 1-error linear complexity for p ⁿ -periodic sequences over prime. Additionally we discuss the calculation of lower and upper bounds on the k-error linear complexity of p ⁿ -periodic sequences over .      

Error linear complexity measures for multisequences

Complexity measures for sequences over finite fields, such as the linear complexity and the k-error linear complexity, play an important role in cryptology. Recent developments in stream ciphers point towards an interest in word-based stream ciphers, which require the study of the complexity of multisequences. We introduce various options for error linear complexity measures for multisequences. For finite multisequences as well as for periodic multisequences with prime period, we present formulas for the number of multisequences with given error linear complexity for several cases, and we present lower bounds for the expected error linear complexity.     

On the Linear Complexity of the Naor–Reingold Pseudo-random Function from Elliptic Curves

We show that the elliptic curve analogue of the pseudo-random number function, introduced recently by M. Naor and O. Reingold, produces a sequence with large linear complexity. This result generalizes a similar result of F. Griffin and I. E. Shparlinski for the linear complexity of the original function of M. Naor and O. Reingold. The proof is based on some results about the distribution of subset-products in finite fields and some properties of division polynomials of elliptic curves.     

How Many Bits have to be Changed to Decrease the Linear Complexity?

The k-error linear complexity of periodic binary sequences is defined to be the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. For the period length p ⁿ, where p is an odd prime and 2 is a primitive root modulo p ², we show a relationship between the linear complexity and the minimum value k for which the k-error linear complexity is strictly less than the linear complexity. Moreover, we describe an algorithm to determine the k-error linear complexity of a given p ⁿ-periodic binary sequence.     

用迹表示研究序列的线性复杂度

本文用迹表示式证明了序列的线性复杂度等于其秩矩阵的秩，并由此导出了正规基的计数公式．     

On the limit of maximal density of sequences with a Perfect Linear Complexity Profile

A binary sequence with a Perfect Linear Complexity Profile (PLCP) has all the jumps in its linear complexity profile of height exactly 1. We prove the conjecture made in Ho that the limit of the maximum density (proportion of ones) over all PLCPs of a particular length is 2/3 as the length tends to infinity.     

On the Linear Complexity Profile of Nonlinear Congruential Pseudorandom Number Generators with Dickson Polynomials

Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and Monte-Carlo methods. The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. Recently, a weak lower bound on the linear complexity profile of a general nonlinear congruential pseudorandom number generator was proven by Gutierrez, Shparlinski and the first author. For most nonlinear generators a much stronger lower bound is expected. Here, we obtain a much stronger lower bound on the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials.     

相关攻击与相关免疫函数

本文首先介绍了如何采用ＤＣ攻击法对一类流密码体制进行相关攻击，从而说明在密码学中有必要研究相关免疫（ＣＩ）函数。在综述了域Ｆ２上相关免疫（ＣＩ）函数的研究进展的同时，给出了ＣＩ函数在一般有限域上的特性和构造，并进一步研究有限环Ｚ／（ｍ）时的情景，本文详尽描述了ＣＩ函数的五种充要条件。最后提出了几个值得研究的未解决的问题。