环Zpq上逻辑函数的分解及其应用.pdf

《环Zpq上逻辑函数的分解及其应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第27卷第3期工程数学学报Vol.27No.32010年06月CHINESEJOURNALOFENGINEERINGMATHEMATICSJune2010文章编号:1005-3085(2010)03-0521-06环Z上逻辑函数的分解及其应用¤pq赵亚群,金栋梁(信息工程大学信息工程学院，郑州450002)摘要:为克服一般剩余类环上合数值逻辑函数无统一多项式表示给函数研究工作带来的困难，本文利用中国剩余定理对环Zpq(p

2、函数在CRT-分解意义下的代数标准型；又讨论了pq值相关免疫逻辑函数在CRT-分解意义下的等价判别条件，给出了利用分解函数的代数标准型构造pq值相关免疫逻辑函数的一种方法。关键词:pq值逻辑函数；CRT-分解；代数标准型；相关免疫；分解谱分类号:AMS(2000)94C10;06E30中图分类号:TN918.1文献标识码:A1引引引言言言和和和基基基本本本概概概念念念由于实际应用的需要，近年来人们对密码学中的多值逻辑函数给予了较多的关注。由文献[1]可知，素域Zp(p为素数)上的多值逻辑函数如同布尔函数一样也具有代数表示形式(称为多项式表示)，且布尔函数的很多结论[2-4]和

3、研究方法可以直接推广到素域上。但对于一般的合数m，由于环与素域的差异，给研究合数值逻辑函数的性质及构造等工作带来了较大的困难。文献[5]给出了4值n元逻辑函数在2-基分解意义下转化为具有某类特殊性质相互关系的两个2n元布尔函数。文献[6]给出了pl(l>1)值逻辑函数的代数标准型，文献[7]研究了pl值逻辑函数与其p-基分解意义下向量函数之间的关系。文献[8]分析了pl值相关免疫逻辑函数的代数结构。文献[9]也在p-基分解意义下对pl值相关免疫逻辑函数进行了分解，将环上相关免疫逻辑函数的判定问题转化为素域上向量逻辑函数满足适定条件问题。对于环Zpq是否有类似的结论？本文首次利

4、用中国剩余定理对环Zpq上的pq值随机变量进行分解，得到了pq值逻辑函数在CRT-分解意义下的代数标准型，给出了利用分解函数的代数标准型构造pq值相关免疫逻辑函数的一种方法。结合p-基分解和CRT-分解这两种代数分析方法，我们可以给出环上任意逻辑函数的代数表示形式，为研究具有特殊密码学性质的多值逻辑函数的构造方法提供了新的理论依据和有效工具。设m¸2是任一取定的正整数，Zm=Z=(m)为整数模m的剩余类环。又设n为任一正整数，X=(X1;¢¢¢;Xn)中的X1;¢¢¢;Xn都是定义在某概率空间上相互独立、且都具有均匀p分布的m值随机变量，记m次本原单位根为u=e2¼i=m;i

5、=¡1。称Zn!Z的任一映mmm射f(x);x2Zn为Zn上的n元m值逻辑函数。对任意的a2Zn，I(x);x2Zn为a的示mmmfagm性函数，WH(a)为a的Hamming重量。逻辑函数的Chrestenson循环谱和相关免疫相关免疫性见文献[2-4]。下文总设p;q为素数，且不妨设p

6、)[10]设m;¢¢¢;m是r个两两互素的正整数，令m=m;¢¢¢;1r1m;m=mM，M0M´1(modm);1·i·r，则一次同余方程组riiiiix´x1(modm1);¢¢¢;x´xr(modmr);(1)有惟一解x´M0Mx+M0Mx+¢¢¢+M0Mx(modm):(2)111222rrr命题1设(•;F;P)是某一概率空间，Z是•到Zpq的映射，则：1)Z可以由中国剩余定理分解为Z(!)=M0MX(!)+M0MY(!);(3)1122其中M=q;M=p;M0M´1(modp);M0M´1(modq);121122X(!)2Zp;Y(!)2Zq;!2•:2)Z是概率

7、空间(•;F;P)上pq值随机变量的充要条件是X;Y都是(•;F;P)上的随机变量。证明由中国剩余定理和随机变量相互独立的定义易得。性质1设Z是某概率空间(•;F;P)上的pq值随机变量，则Z具有“均匀分布”的充分必要条件是X;Y相互独立，且都具有“均匀分布”，其中Z;X;Y满足(3)式。文献[1]指出：当m是素数时，任一m值逻辑函数可以由模m多项式表示，而当m是合数时，并不是所有m值逻辑函数都能用模m多项式表示。文献[11]只给出了多值逻辑函数具有多项式表示的条件，下面给出所有pq值逻辑函数(无论有无