论文摘要
一个n阶拉丁方可以看作一个n×n矩阵L,L的元素来自一个n元集合S,L的每一行、每一列都是S中元素的一个排列.设L=(lij),M=(mij)分别是集合X和Y上的两个n阶拉丁方,若集合中互不相同的有序元素偶恰好有n2个,则称L与M正交,或L与M是互相正交的拉丁方.正交拉丁方理论是组合设计理论的重要组成部分,有着丰富的研究成果.与正交拉丁方的研究相对应的是比正交条件弱的各种概念及问题的研究.1782年,在构造一对6阶正交拉丁方的努力失败后,欧拉构造了一对不完全拉丁方,它们可以产生出34=62-2个不同的有序元素偶和两个空位置,后来这种拉丁方被称为欧拉型的不完全拉丁方.此后,各种比正交弱的概念被陆续提出和研究.这些概念有“接近正交”,“不完全正交”,“垂直”等等.两个n阶拉丁方,L=(lij)和M=(mij),被称为是r-正交的,如果把他们重叠起来恰好产生r个不同的有序元素偶,即Belyavskaya[1-3]在1976年首先系统地着手研究下列问题:对什么样的正整数n和r,能够有一对n阶r-正交拉丁方存在?到2002年,这个问题最终被朱烈和H.Zhang完全解决。在一对n阶r-正交拉丁方L和M中,如果M是L的转置,则我们称L是r-自正交的,并记L为r-SOLS（n）.在关于r-正交拉丁方存在性的最后一篇文章中,朱烈和H.Zhang[6]提出了一个关于r-自正交拉丁方的猜想:存在一个正整数n0,对任意整数n,当n≥n0时,对每一个r∈[n,n2]{n+1,n2-1},都存在r-SOLS（n）.这个猜想在2004年,由Yunqing Xu和Yanxun Chang[7]解决了:n0≤27,并给出了关于r-自正交拉丁方存在性问题的一个几乎完全解决结论.主要结论如下:（1）对任意的正整数n≥27,当且仅当n≤r≤n2且r∈{n+1,n2-1}时,r-SOLS（n）存在.（2）设n是任意正整数,除25个例外和26个可能的例外,当n≤r≤n2且r∈{n+1,n2-1}时,r-SOLS（n）存在.因此对完全的拉丁方自正交问题的研究已经很透彻了,本文要研究的是不完全拉丁方自正交问题.设H={H1,H2,…Hk}是S的非空子集的集合.基于S的带洞|S|×|S|拉丁方L,其中洞集为H,应满足下列性质:（1）L的每一个位置或空或含有S中的元素;（2）S中的每个元素在L中的某行或某列最多出现一次;（3）子方Hi×Hi是空的,1≤i≤k;（这些子方称作洞）（4）元素x∈S出现在第y行或第y列当且仅当（x,y）∈（S×S）∪i=1k（Hi×Hi）.带洞的拉丁方也称为不完全的拉丁方,若两个n阶带u洞的不完全拉丁方重叠后正好产生r个不同的有序对,则称它们是不完全r-正交的,记作r-IMOLS（n,u）.进一步,如果第二个拉丁方是第一个拉丁方的转置,称它们是不完全r-自正交的,记作r-ISOLS（n,u）.本文给出了不完全r-自正交拉丁方存在性的如下结论（定理2.2.4,定理2.2.9）:（1）当m≥7,对每个r∈[4m+k,（4m+k）2-k2]{4m+k+1,（4m+k）2-k2-1},则r-ISOLS（4m+k,k）存在,其中冬=1,2,3,4.（2）当m≥7,对每个r∈[4m+k,（4m+k）2-m2-（k2-k）]{4m+k+1,（4m+k）2-m2-（k2-k）-1},则r-ISOLS（4m+k,m）存在,其中k=0,1,2,3.同时考虑了正交拉丁方在消息认证码设计方面的应用.主要设计了三种消息认证码系统,分别是MOLS-MACs,SOLS-MACs和LS-MACs.在MOBS-MACs中,主要利用了两个拉丁方的正交性质和密钥k对消息串计算认证标签,并对其密钥空间,密钥储存空间和安全性做了讨论.在SOLS-MACs中,主要利用拉丁方的自正交性质,设计了一种消息认证码的算法.在LS-MACs中,我们用了两个任意的拉丁方,设计了一种消息认证码的算法.第一章在这一章中,我们介绍r-正交拉丁方问题的背景和研究发展过程,介绍r-自正交拉丁方和不完全自正交拉丁方的概念及其已有结果.证明几个不完全r-自正交拉丁方的基本递推构造方法,主要有补洞构造法和膨胀构造法等等.并介绍使用这些构造法所需的已有结论.第二章在这章中我们主要给出几个基本输入设计和主要定理.并且用4-SOLS（4）,SOLS（4）和4-ISOLS（4,1）,ISOLS（4,1）为输入设计来证明:当m≥7,r-ISOLS（4m|k,k）,（k=1,2,3,4）和r-ISOLS（4m|k,m）,（k=0,1,2,3）存在的充分条件.第三章在这章中我们给出拉丁方在消息认证码方面的应用.构造了三种基于两个拉丁方的消息认证码系统,分别是MOLS-MACs,SOLS-MACs和LS-MACs.并对MOLS-MACs的密钥空间,密钥储存空间和安全性做了一些讨论.