一種求解有限域 Fq上線性方程組的有效算法

周曉誼,馬紀新,杜文才,陳明銳

(1.海南大學(xué)信息科學(xué)技術(shù)學(xué)院,海南海口 570228;2.格林威治大學(xué)計算與數(shù)學(xué)學(xué)院,英國倫敦 SE10 9LS)

一種求解有限域 Fq上線性方程組的有效算法

周曉誼1,2,馬紀新2,杜文才1,陳明銳1

(1.海南大學(xué)信息科學(xué)技術(shù)學(xué)院,海南?？?570228;2.格林威治大學(xué)計算與數(shù)學(xué)學(xué)院,英國倫敦 SE10 9LS)

在對重線性化方法的研究中提出的一種對有限域 Fq上線性方程組的算法,利用有限域xq-1=1的性質(zhì),可以快速地對方程組進行高斯消元,從而求出方程通解.

有限域;線性方程組;高斯消元

有限域的起源可以追溯到 17和 18世紀,許多大數(shù)學(xué)家如費爾馬 (P de Fermat)、勒讓德 (A M Legendre)、歐拉 (L Euler)和高斯 (C F Gauss),他們在研究數(shù)論的一些性質(zhì)時,得到了許多同余式的性質(zhì).這實質(zhì)上也研究了有限域的許多性質(zhì),但是他們還沒認識到“域”的概念.直到 19世紀韋伯 (H Weber)對伽羅華(E Galois)的工作給予抽象描述,才有了域的定義.韋伯提出域是群的推廣形式,并且運用當(dāng)時最一般的術(shù)語介紹了伽羅華理論,闡述了伽羅華理論不僅研究了方程的可解性問題,還研究了特殊的群與某種良好定義的域的相互作用問題.1930—1931年,威爾登 (B L Van derWaerden)出版了《近世代數(shù)學(xué)》一書,是代數(shù)學(xué)成為研究抽象代數(shù)結(jié)構(gòu)的一門結(jié)構(gòu)數(shù)學(xué).至此,有限域的理論基本成熟.

有限域具有許多優(yōu)美的特性,在組合設(shè)計、編碼理論、信息安全、代數(shù)幾何學(xué)、數(shù)論、群論、離散數(shù)學(xué)和通信系統(tǒng)等許多實際領(lǐng)域有著廣泛的應(yīng)用.特別是最近幾十年,隨著計算機技術(shù)的蓬勃發(fā)展,有限域的地位愈加重要,例如有限域的計算和算法分析對計算機代數(shù)和符號計算的影響,有限域上的離散對數(shù)問題.在密碼算法和安全協(xié)議的設(shè)計等方面有著廣泛的應(yīng)用,以及近幾年來密碼學(xué)的研究熱點——基于 MQ(Multivariate Quadratic,多元二次多項式)問題的公鑰密碼等.

實際上,許多工程計算問題和理論問題最終都可以歸結(jié)為線性方程組的求解問題,如反演問題、優(yōu)化問題、數(shù)據(jù)擬合問題、插值問題、糾錯碼設(shè)計、多元多次方程組的求解問題[1]等.鑒于線性方程組在實際中的重要應(yīng)用,多年來在探求其求解的研究上也取得了許多有價值的成果,目前求線性方程組的方法主要有直接法和迭代法.某些多元二次方程組的求解也是基于這 2種方法,如重線性化 (Relinearization)方法.該方法于 1999年由 Kipnis和 Shamir首先提出[2],其基本思想是通過對方程數(shù)量小于變元數(shù)量之方程組的通解表示,構(gòu)造出更高次的方程,從而使最終得到的高次方程的總數(shù)大于或等于新變元的數(shù)量,其次得到的高次方程中的新變元,也將視為互不聯(lián)系的一次變元,即線性方程組所看待,最后通過解該高次方程組反推出原方程組的解.

筆者在用重線性化對有限域上多元二次方程組進行密碼學(xué)分析時,發(fā)現(xiàn)利用有限域xq-1=1的性質(zhì),可以快速地對方程組進行高斯消元,從而求出方程通解.相比于整數(shù)域上的線性方程組所使用的高斯消元方法來說,該方法更加簡單易行.

1 算法設(shè)計

有限域上線性方程組的定義

令方程組增廣矩陣的秩為R(A),則關(guān)于方程組(1)的基礎(chǔ)解系有以下結(jié)論:

1)R(A)>n時,方程組(1)沒有解;

2)R(A)=n時,方程組(1)僅有零解,無基礎(chǔ)解系;

3)R(A)=r

方程組(1)的通解可表示為

求解思路:

1)用行初等變換,將方程組 (1)的增廣矩陣化為廣義上三角形矩陣,且對角線元素均為 1;

2)新增行向量,將第 1)步得到的矩陣化為單位拓展矩陣;

3)將新增行向量中帶 1的元素設(shè)為方程組的自由未知量,如xr+1,…,xn(r=R(A));

4)從第R(A)行開始,一步步往上迭代,最終求得方程組的通解.

1.1 高斯消元

定義 1[3]設(shè)(F,+,×)是一個代數(shù)系統(tǒng),+和 ×都是二元運算.F至少有 2個元素;+滿足結(jié)合律、交換律,存在單位元 0,且對任意aF,存在逆元素 -a;×滿足結(jié)合律、交換律,存在單位元素 1,且對任意a≠0,aF,均有逆元素a-1,并且 ×對 +滿足分配律,則稱(F,+,×)為域.

從以上定義可知,對于有限域F,每個元素a都存在a-1使得a×a-1=1.

因此,對于有限域上線性方程組的系數(shù)aij,總存在另一個元素bij=使得aijbij=1.利用這一性質(zhì)可以對線性方程中的任意系數(shù)進行求逆設(shè)置,使其為 1.

另 Ab為線性方程組 (1)的增廣矩陣.求解思路如流程圖 1所示.

1.2 求通解

定義 3[4-5]設(shè)Am×n(m

求通解算法如下

定義 2[3]只含有限個元素的域稱為有限域.

方程的解只由 Z表示,因此從最后一行開始,依次求得各未知數(shù)的值,將其存放到 Z:for i=1to r

將原方程 r-i+1行等式右邊的值存放到 Z(r-i+1,M+1)中,即 Z(r-i+1,M+1)=Ab(r-i+1,C)

圖1 有限域 Fq上高斯消元的流程圖

1.3 算法復(fù)雜度分析

時間復(fù)雜度:該算法主要由高斯消元和求通解 2個部分構(gòu)成.

在高斯消元中,由圖 1可知該過程有 2個循環(huán)語句,在最壞情況下,即對角線元素為 0,此時該程序所運行到的行需要和其下面的行進行比較交換,直到對角線元素不為 0或者比較到最后一行為止.假設(shè)每種情況的出現(xiàn)概率為p,則改算法平均時間復(fù)雜度為與輸入方程組的方程個數(shù)m,以及方程的秩有關(guān).即復(fù)雜度為

最差時間復(fù)雜度:O(R(A)3).

最優(yōu)時間復(fù)雜度:O(R(A)),即對角線元素都不為 0,不用與其他行進行比較.

平均時間復(fù)雜度:O(R(A)3/m).

求通解的過程由 3條循環(huán)語句構(gòu)成,與方程的秩R(A)和未知數(shù)的個數(shù)n有關(guān),因此時間復(fù)雜度為R(A)×(n-R(A))×n(n-1)(n-2)/6.

空間復(fù)雜度:算法的空間復(fù)雜度只考慮在運行過程中為局部變量分配的存儲空間的大小,它包括為參數(shù)表中形參變量分配的存儲空間和為在函數(shù)體中定義的局部變量分配的存儲空間 2個部分[6].因此該算法的空間復(fù)雜度主要由方程組的未知數(shù)個數(shù)n、方程系數(shù)矩陣的秩R(A)以及方程個數(shù)m有關(guān),因此有

2 應(yīng)用實例

3 小 結(jié)

從方法的計算原理、過程和算例結(jié)果來看,本文提出的算法對于計算有限域上的線性方程組具有算法簡單、編程容易的特點.計算結(jié)果表明,此方法適用于任何線性方程組.但是算法的時間空間復(fù)雜度分析表明,在高斯消元過程中,判定對角線元素是否為 0并且進行行交換時耗費了較多時間,該方法可通過增設(shè)一個一維數(shù)組來記錄某行元素特點適合交換到第幾行,一旦交換后數(shù)組中與行數(shù)相對應(yīng)的元素設(shè)為1,則表明該行之后不用再交換.本文算法作為一種求解有限域上線性方程組的方法,具有一定的理論意義和實用價值.

[1]徐勤花,史文譜,陳瑞平,等.求解線性方程組的超幾何球法[J].煙臺大學(xué)學(xué)報:自然科學(xué)與工程版,2007,20(2):92-94.

[2]KIPN ISA,SHAM IR A.Cryptanalysis of the HFE Public Key Cryptosystem byLinearization:ProceedingsAdvances in Cryptogoly-CRYPTO′99,19th Annual International Cryptology Conference,Santa Barbara,August 15-19,1999[C].London:Springer-Verlag,1999.

[3]朱平天,李伯葓,鄒園.近世代數(shù)[M].北京:科學(xué)出版社,2003.

[4]王文賢.線性代數(shù)及其應(yīng)用[M].大連:大連理工大學(xué)出版社,1993.

[5]陳建莉.線性方程組解法新探[J].紡織高?；A(chǔ)科學(xué)學(xué)報,2008,21(2):238-241.

[6]嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,2000.

An Efficient Algorithm to Solve L inear Equations over F inite Field Fq

ZHOU Xiao-yi1,2,MA Ji-xin2,DU Wen-cai1,CHEN Ming-rui1

(1.College of Information Science and Technology,Hainan University,Haikou 570228,China;2.School of Computing andMathematical Science,University of Greenwich,London,UK,SE10 9LS)

In our report,an effective algorithm for linear equations over finite field Fqwas proposed,and with the property ofxq-1=1 over finite fields,the algorithm could conduct Gaussian elimination and obtain common solution.

finite field;linear equation;Gaussian elimination

O 241.6 < class="emphasis_bold">文獻標志碼:A

A

1004-1729(2010)04-0306-05

2010-06-12

海南省高等學(xué)?？茖W(xué)研究項目 (Hjkj2010-10)

周曉誼 (1979-),女,海南?？谌?海南大學(xué)信息科學(xué)技術(shù)學(xué)院講師.

陳明銳 (1960-),男,海南大學(xué)信息科學(xué)技術(shù)學(xué)院教授.