改进的多目标元素量子搜索算法

Grover量子搜索算法解决了未加排序的数据库搜索问题,在2ⁿ个元素中搜索M个目标元素,其计算复杂度为O（（2ⁿ/M）^-2）,相对于经典算法实现了二次加速,但是,当目标元素个数接近2ⁿ/2时该算法成功率只达到50%。从任意相位的Grover变换从发,给出一种改进的多目标元素量子搜索算法,该算法在目标元素个数M≥2ⁿ/4时,只用一次Grover变换就能以概率1完成搜索。     

多目标元素的量子搜索算法

Grover量子搜索算法解决了未加整理的数据库搜索问题,在2ⁿ个元素中搜索M个目标元素时,计算复杂度为O（√2ⁿ/M）,相对于经典算法实现了二次加速,但Grover算法在目标元素个数接近2ⁿ/2时成功率较低。提出了一种针对多目标元素的量子搜索算法,当目标元素个数大于2ⁿ/3时,能以不低于97.36%的概率找到目标元素。     

行满秩Toeplitz型矩阵Moore-Penrose逆的快速算法

通过构造对称分块矩阵给出了秩为m的m×n阶Toeplitz型矩阵Moore-Penrose逆的快速算法。该算法计算复杂度为O（mn）+O（m²）,而由T^T（TT^T）^-1直接求解所需运算量为O（m²n）+O（m3）。数值算例表明了该快速算法的有效性。     

修正de Bruijn序列的线性复杂度研究

n级de Bruijn-0/1序列,就是从de Bruijn序列2ⁿ个状态中去除一个全0状态（记为de Bruijn-0）或全1状态（记为de Bruijn-1）而得到的周期为2ⁿ-1的序列。研究了de Bruijn-0和de Bruijn-1（记为de Bruijn-0/1）序列的线性复杂度特性,提出了相关的定理并给出了证明,同时给出了4~6级de Bruijn-0/1序列线性复杂度的统计数据。     

扩展在上GF（3）新型自缩序列模型及研究

自收缩序列是一类重要的伪随机序列,而周期和线性复杂度是序列伪随机性的经典量度。如何构造自缩序列的新模型,使生成序列具有大的周期和高的线性复杂度是一个重要的问题。针对这一问题,构造了GF（3）上一种新型的自缩序列模型,利用有限域理论,研究了生成序列的周期和线性复杂度,得到一些主要结论：周期上界3ⁿ,下界3^2[n/3];线性复杂度上界3ⁿ,下界3^2[n/3]-1。进一步讨论了基于GF（3）上本原三项式和四项式的自缩序列的周期和线性复杂度。     

一类具有低相关特性和较大线性复杂度的序列集

对于p=3和偶数n=2k,构造了一类周期为3ⁿ-1大容量序列集S^(r),这里r与3^k-1互素。这类序列集的相关函数取-1±3^k,-1,-1+2•3^k四值,并完全确定了相关值的分布。通过选取适当的参数r,证明了这类序列集具有较大的线性复杂度下界。     

点圈并图的匹配等价图数

若两个图G和H的匹配多项式相等,称图G和H匹配等价用δ（G）表示图G的所有不同构的匹配等价图的个数。文[5]在{m₁,m₂}∩{6,9,15}=Φ准的条件下计算了δ（sK₁∪t₁C_m1∪t₂C_m2）,在该文中计算了δ（sK₁∪t₁C₃∪t₂C₆）、δ（sK₁∪t₁C₆∪t₂C₉）是文[5]的完善和补充。     

环F2+uF2+u2F2上的线性码及其Gray像

记R=F₂+uF₂+u²F₂,R₁=F₂+uF₂,定义了从Rⁿ到F³ⁿ₂的Gray映射Ф以及从Rⁿ₁到Rⁿ的映射f。通过对环R上线性码C的生成矩阵的研究,给出了线性码C的对偶码C^⊥和Gray像Ф（C）的生成矩阵,并且Ф（C）与Ф（C^⊥）是F₂上的对偶码。通过映射f将环R₁上的线性码与环R上的一类线性码对应起来。     

分组排序算法

提出了分组排序算法,详细分析了算法的原理及其时间与空间复杂度,得出了在最坏情况下的时间复杂度是θ（mn）;最好情况和平均情况下的时间复杂度均是θ（nlog（n/m^k））;在最坏情况下的空间复杂度是O（mn-m²＋m）;最好情况和平均情况下的空间复杂度均是O（m^klog（n/m^k））;并用多组随机数据与效率较高的快速算法进行仿真对比实验,试验结果说明了文中结论的正确性。这一结果,将有助于进一步设计高效的海量数据分析方法。     

一类完全非线性S-盒的构造

完全非线性S-盒在对称密码中有着重要的运用。给出有限域上完全非线性S-盒的一种构造方法。与在向量空间上构造的方法比,有限域上置换多项式的代数次数等性质更容易研究。该方法可以构造多类完全非线性S-盒,例如,通过选择幂函数形式的置换α^x,得到Satoh等人构造的S-盒;通过选取指数形式的置换x^d,所得完全非线性S-盒的分量函数的任意非零线性组合的代数次数达到最高。     

Distinguishing Attack on the NTRUCipher Encryption Scheme

A distinguishing attack on the NTRUCipher symmetric encryption scheme defined over the residue ring modulo a cyclotomic polynomial over a finite field of prime order is proposed. The attack is based on the existence of a homomorphism from this ring into the specified field and can be quite effective under sufficiently general conditions.

     

Sequential machines realized by group representations

Well-known results yield a decomposition of a sequential machine into permutation and reset machines. This paper presents a methodology for the realization of the permutation machines; this methodology involves group representation theory. In the worst case, any permutation machine can be realized by a set of matrices multiplied modulo three. Bounds on the dimensions of these matrices are given. It is further shown that realization can always be performed over roots of unity, and that appropriate fields for realization can be found by solving a very simple equation.     

几类基于0-线性转换的置换多项式

有限域上的置换多项式在密码学,编码理论和序列设计等领域中有着广泛的应用.至今,对于置换多项式的研究已取得一系列的进展,研究者提出利用AGW准则、分段函数等来构造和证明置换,而对于置换多项式的分类仅有少数几种被提出,因此构造不同类型的置换多项式是一个值得研究的问题.本文利用迹函数和线性化多项式构造了一类有限域上具有特殊形式的无限类置换多项式.首先,我们对一类线性化多项式和一类二次齐次多项式进行讨论,当其存在线性转换时,给出其需要满足的条件.进一步地,当这两类多项式存在0-线性转换时,我们利用这两类函数构造出了有限域上具有特殊形式的两类置换多项式.     

模N具有给定周期的变换方阵的构造

置乱技术在数字图像信息隐藏和图像加密中都具有重要的作用;而变换方阵因其理论简洁、实现简单而得到了广泛的关注和研究,但已有工作主要集中在对给定方阵周期的研究方面.分析了变换方阵模素数幂周期的上确界,得到了变换方阵模素数幂的周期达到上确界的充要条件.在此基础上给出了模素数幂具有最大周期的变换方阵的构造方法及两个改进方案.进而分析了变换方阵模一般整数N周期的上界,并使用中国剩余定理给出了两种算法,可构造模一般整数N具有给定周期的变换方阵.     

List decoding codes on Garcia–Stictenoth tower using Gröbner basis

An account of the interpolation and the root-finding steps of list decoding of one-point codes is given. The interpolation step is reduced to the problem of finding the minimal element of the Gröbner basis of a submodule of a free module over a polynomial ring of one variable. The procedure for root-finding of the interpolation polynomial going modulo a large degree place is described from the tower point of view.     

Algorithms for solving systems of linear diophantine equations in residue rings

Algorithms are proposed that construct the basis of the set of solutions to a system of homogeneous or inhomogeneous linear Diophantine equations in a residue ring modulo n when the prime factors of n are known. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 27–40, November–December 2007.     

一种基于高维矩阵变换的混沌图像加密

提出了一种基于Henon混沌系统和高维准对角矩阵变换的图像加密算法.由初始密钥控制二维Henon混沌映射生成两个置换矩阵和多个环上二阶可逆矩阵.利用获得的置换矩阵结合两类平移变换置乱原始图像;进一步,以二价可逆矩阵为子矩阵构造高维准对角矩阵,再对置乱密文进行高维矩阵变换(模运算)实现灰度值替代二次加密.仿真实验结果表明,该算法易于实现,加密效果理想,对密钥和明文具有敏感依赖性,安全性高。     

P值逻辑函数的扩散性质

满足K次扩散准则的p值逻辑函数在密码设计中有重要应用。该文采用Znp上的置换定出了一类满足2n次扩散准则的p值逻辑函数,即Bent函数;定出了级联函数满足K次扩散准则的充要条件和n元2次p值逻辑函数满足m阶K次扩散准则的充要条件。     

环Fp uFp vFp uvFp上的二次剩余码

针对环Fp+ uFp+ vFp+ uvFp上的二次剩余码进行了研究,其中u2=u,v2=v,uv=vu,p是一个奇素数.首先引入了环Fp+ uFp+vFp+ uvFp上长为n的循环码的相关知识,用幂等元的形式定义了环Fp+ uFp+vFp+uvFp上的二次剩余码,给出了其定义和性质,并讨论了它们与其扩展码之间的关系和对偶性质.最后,给出了环F3+uF3+vF3+uvF3上长为11的二次剩余码的幂等生成元的具体形式.     

Quantum one-way permutation over the finite field of two elements

In quantum cryptography, a one-way permutation is a bounded unitary operator \(U:\mathcal {H} \rightarrow \mathcal {H}\) on a Hilbert space \(\mathcal {H}\) that is easy to compute on every input, but hard to invert given the image of a random input. Levin (Probl Inf Transm 39(1):92–103, 2003) has conjectured that the unitary transformation \(g(a,x)=(a,f(x)+ax)\), where f is any length-preserving function and \(a,x \in \hbox {GF}_{{2}^{\Vert x\Vert }}\), is an information-theoretically secure operator within a polynomial factor. Here, we show that Levin’s one-way permutation is provably secure because its output values are four maximally entangled two-qubit states, and whose probability of factoring them approaches zero faster than the multiplicative inverse of any positive polynomial poly(x) over the Boolean ring of all subsets of x. Our results demonstrate through well-known theorems that existence of classical one-way functions implies existence of a universal quantum one-way permutation that cannot be inverted in subexponential time in the worst case.