有限域上線性方程組的相變現(xiàn)象*

沈 靜 李 薇 艾小川

(海軍工程大學理學院應用數(shù)學系 武漢 430033)

1 引言

求解有限域上的線性方程組是代數(shù)中的基本問題,它在實際中有很多的應用。編碼理論中的校驗矩陣、密碼學中的大整數(shù)分解問題和計算離散對數(shù)問題都要用到求解有限域上的線性方程組[4～5]。近年來文獻[1～3]都觀察到一個有趣的現(xiàn)象:在一些特定的情況下,存在一個正數(shù)r*,使得當n→∞時,隨機產生的含n個變量t=rn個方程的線性方程組在0＜r＜r*的條件下幾乎是有解的,在r＞r*的條件下幾乎是無解的。這個現(xiàn)象類似于物理中的相變現(xiàn)象,因此這種現(xiàn)象稱為線性方程組的相變現(xiàn)象,r*稱為相變點。

線性方程組相變現(xiàn)象的研究是從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-線性方程組的相變現(xiàn)象,給出了k-線性方程組相變點的上界和下界,推廣了文獻[2]中的結果,為進一步研究求解線性方程組的算法復雜性和相變現(xiàn)象之間的聯(lián)系提供依據(jù)。

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-線性方程組的相變現(xiàn)象,給出了k-線性方程組相變點的上界和下界,由定理1可知相變點的上界為1,由定理2可知相變點的下界為λk。從Matlab軟件計算的結果來看,隨著k的增加,λk越來越靠近 1。我們猜想,當 k→∞,λk→1,即上界和下界重合,得到k-線性方程組準確的相變點r*=1,這是我們下一步要繼續(xù)研究的工作。

[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