有限域上线性方程组的相变现象*

沈 静 李 薇 艾小川

(海军工程大学理学院应用数学系 武汉 430033)

1 引言

求解有限域上的线性方程组是代数中的基本问题,它在实际中有很多的应用。编码理论中的校验矩阵、密码学中的大整数分解问题和计算离散对数问题都要用到求解有限域上的线性方程组[4～5]。近年来文献[1～3]都观察到一个有趣的现象:在一些特定的情况下,存在一个正数r*,使得当n→∞时,随机产生的含n个变量t=rn个方程的线性方程组在0＜r＜r*的条件下几乎是有解的,在r＞r*的条件下几乎是无解的。这个现象类似于物理中的相变现象,因此这种现象称为线性方程组的相变现象,r*称为相变点。

线性方程组相变现象的研究是从k-SAT问题的变体k-XOR-SAT开始的,事实上k-XOR-SAT是F2上的线性方程组。1998年,Nadia Creignou给出了XOR-SAT的准确相变点为r*=1,2001年Nadia Creignou给出了k-XOR-SAT的相变点的上界和下界。2002年,Olivier Dubois给出了3-XOR-SAT的准确相变点,它是两个超越方程的解,实验结果显示3-XOR-SAT的准确相变点r*≈0.92。

本文研究了随机产生的一般有限域F上的k-线性方程组的相变现象,给出了k-线性方程组相变点的上界和下界,推广了文献[2]中的结果,为进一步研究求解线性方程组的算法复杂性和相变现象之间的联系提供依据。

2 随机k-线性方程组

设I是有限域F上的n元线性方程组,其中每个线性方程Ri恰好只含有k个变量,其形式为:ci1xi1+ci2xi2+…+cikxik=bi,ci1≠0,…,cik≠0,称这样的线性方程为k-方程。设有限域F中含有d个元素,则有Nk=(d-1)kd个不同的k-方程。

定义1 按如下方式产生的有限域F上的n元线性方程组I称为k-线性方程组:

3 随机k-线性方程组相变点的上界

4 随机k-线性方程组相变点的下界

由引理3和引理5我们可得定理2。

5 结语

本文研究了随机产生的一般有限域F上的k-线性方程组的相变现象,给出了k-线性方程组相变点的上界和下界,由定理1可知相变点的上界为1,由定理2可知相变点的下界为λk。从Matlab软件计算的结果来看,随着k的增加,λk越来越靠近 1。我们猜想,当 k→∞,λk→1,即上界和下界重合,得到k-线性方程组准确的相变点r*=1,这是我们下一步要继续研究的工作。

[1]Creignou N,Daude H.Satisfiability threshold for random XOR-CNF formulU[J].Discrete Appl.Math.96-97(1-3),1999:41～53

[2]Creignou N,Daude H.Coarse and sharp thresholds for random k-XOR-CNF satisfiability.Theoretical informatics and applications,to appear,2003

[3]Dubois O,Mandler J.The 3-XORSAT threshold[C]//Proc.FOCS,2002

[4]Rivest R L,Shamir A,Adleman L.A method for obtaining digital signatures and public-key cryptosystems webpage[EB/OL].http://mit.edu/rivest/rsapaper.ps,1978

[5]Pomerance C,Goldwasser S.Cryptology and Computational Number Theory.AMS Proc.Symp.In Applied Mathematics,1990,42:27～48

[6]Mitzenmacher M,Upfal E.Probability and Computing:Randomized Algorithm and Probabilistic Analysis.Cambridge,2005