發(fā)布時間：2017-04-06 12:07

  本文關(guān)鍵詞：有限域上一元方程求解和相關(guān)問題的研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：本文中我們主要對數(shù)論和密碼學中出現(xiàn)的有限域上的一元方程求解問題和相關(guān)問題進行了探討,主要包括有限域上的平方根計算,三次根計算,高次根計算和素性判定等問題。首先,我們給出一個確定性算法來計算有限域Fq上的平方根。我們的算法通過構(gòu)造一個和Fq×Fq同構(gòu)的多項式環(huán),然后在該環(huán)上完成計算。我們算法的運行時間為O(t log t log q+log2 q),其中q-1=2st。當t=poly(log q)時,我們的算法是確定的多項式時間算法。同時我們將該算法應用到Proth素數(shù)判定中,當t為O((log q)2)時,我們的算法是目前已知的最優(yōu)Proth素性判定算法。其次,我們將Sze在有限域Fq上計算平方根的確定性算法擴展為隨機算法,其中q-1=2st。我們算法的期望運行時間為O((log q)2)。和TonelliShanks算法相反,我們的隨機算法在s越大時,其每次隨機選擇成功的概率越高,相比原始的Sze算法,我們的隨機算法不需要計算ζ4。再次,我們使用Lucas序列給出了有限域Fp上計算平方根的三個算法,我們先使用Vn(P,Q)直接構(gòu)造了一個隨機算法來計算Fp上的平方根,其期望運行時間為4.5 log p次Fp上的乘法操作。然后我們使用Vn(P,1)構(gòu)造了一個確定性算法來計算有限域上的平方根,該算法恰好能對(p-1)/4+1個二次剩余計算平方根。之后我們將該確定性算法擴展成一個隨機算法,其期望運行時間為2 log p次Fp上的乘法操作。再次,我們將Berlamp算法計算有限域Fq上平方根的隨機算法擴展到對x3=a的方程的求解,同時使用分圓理論給出其算法分析。與以往的算法不同的是,我們使用二次剩余理論對三次方程進行求解,計算的過程中并不需要尋找三次非剩余,同時我們也將這一方法擴展到對Fq上任意的三次方程x3+ax2+bx+c=0的求解。最后,我們將Cipolla-Lehmer算法計算有限域Fq上平方根的隨機算法通過計算Fq擴域Fqr上元素范數(shù)的方法擴展到對方程xr=a的求解,其中r為素數(shù)冪。我們通過構(gòu)造Fq[X]上的不可約多項式f(x)給出我們的算法,其中deg(f)=r且f(x)的常數(shù)項為(-1)ra。同時我們利用Davenport-Hasse關(guān)系和Double Counting技術(shù),給出我們構(gòu)造f(x)算法的分析。對滿足r4≤q的r,我們的算法是非常有效的。
【關(guān)鍵詞】：平方根 有限域 確定性算法 隨機算法
【學位授予單位】：上海交通大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O153.4
【目錄】：

• 摘要5-7
• ABSTRACT7-13
• 第一章 緒論13-21
• 1.1 問題概述13-14
• 1.1.1 平方根問題概述13-14
• 1.1.2 高次根問題概述14
• 1.2 研究背景及意義14-17
• 1.2.1 計算數(shù)論中的應用15
• 1.2.2 Rabin密碼系統(tǒng)中的應用15-16
• 1.2.3 橢圓曲線上點壓縮的應用16-17
• 1.3 相關(guān)工作17-20
• 1.4 內(nèi)容組織20-21
• 第二章 預備知識21-27
• 2.1 基礎(chǔ)數(shù)論21-22
• 2.2 抽象代數(shù)22-25
• 2.3 有限域25
• 2.4 算法和操作復雜性25-27
• 第三章 確定性算法計算有限域上的平方根27-35
• 3.1 同構(gòu)環(huán)介紹27-28
• 3.2 確定性算法28-32
• 3.3 素性測試中的應用32-33
• 3.4 結(jié)論33-35
• 第四章 隨機算法計算有限域上的平方根35-39
• 4.1 Sze群同構(gòu)35-36
• 4.2 隨機算法36-38
• 4.3 結(jié)論38-39
• 第五章 使用Lucas序列構(gòu)造F_p上的平方根算法39-51
• 5.1 Lucas序列背景知識介紹39-41
• 5.2 幾個重要引理41-42
• 5.3 隨機算法142-44
• 5.4 確定性算法44-48
• 5.5 隨機算法248-50
• 5.6 結(jié)論50-51
• 第六章 有限域上三次根的求解51-61
• 6.1 擴展Berlekamp算法求解三次根51-57
• 6.1.1 x~3=a全部根的求解57
• 6.2 對F_p~*上任意三次方程的求解57-59
• 6.3 結(jié)論59-61
• 第七章 有限域上高次根的求解61-67
• 7.1 Cipolla-Lehmer平方根算法61-62
• 7.2 Cipolla-Lehmer算法擴展到r次根62-63
• 7.3 構(gòu)造常數(shù)項為(-1)~ra的不可約多項式63-66
• 7.4 結(jié)論66-67
• 全文總結(jié)67-69
• 參考文獻69-77
• 致謝77-78
• 攻讀學位期間發(fā)表的學術(shù)論文目錄78-79
• 附件79

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 王澤涵;有限域上一類多項式的周期[J];電子學報;1984年05期

2 李復中;關(guān)于Golomb猜想[J];科學通報;1984年15期

3 周大術(shù);有限域的一個特征性質(zhì)[J];西南師范學院學報(自然科學版);1985年02期

4 郝長亮;有限域上一類n元二次方程解的個數(shù)[J];數(shù)學的實踐與認識;1986年01期

5 劉光明;關(guān)于有限域G上的某些方程解組的計數(shù)問題[J];鄭州輕工業(yè)學院學報;1995年01期

6 王文松,孫琦;有限域上一類方程解數(shù)的直接公式[J];數(shù)學年刊A輯(中文版);2005年03期

7 李志慧;;特征為2的有限域上一類正形置換多項式的非存在性[J];陜西師范大學學報(自然科學版);2008年02期

8 曹喜望;;有限域上幾個置換多項式及一個密鑰交換協(xié)議[J];數(shù)學學報;2009年05期

9 許廣魁;;有限域上一類方程在(F~*)~n中的解數(shù)公式[J];綿陽師范學院學報;2010年02期

10 師連城;有限域上的方程[J];四平師院學報(自然科學版);1981年00期

中國重要會議論文全文數(shù)據(jù)庫 前5條

1 丁金扣;黃錚;溫巧燕;楊義先;;有限域上的多輸出正交函數(shù)[A];2005通信理論與技術(shù)新進展——第十屆全國青年通信學術(shù)會議論文集[C];2005年

2 周旋;王秋艷;端木慶峰;瞿成勤;;有限域上冪函數(shù)S盒構(gòu)造及性質(zhì)研究[A];2013年中國信息通信研究新進展論文集[C];2014年

3 張仲明;馬立波;;基于有限域的結(jié)構(gòu)化LDPC碼構(gòu)造[A];第七屆衛(wèi)星通信新技術(shù)、新業(yè)務學術(shù)年會論文集[C];2011年

4 金棟梁;趙亞群;;有限域上邏輯函數(shù)的Chrestenson譜的性質(zhì)[A];2007通信理論與技術(shù)新發(fā)展——第十二屆全國青年通信學術(shù)會議論文集（上冊）[C];2007年

5 李小平;李寧;劉彥明;董慶寬;;一種基于ONB的ECC有限域算術(shù)的設(shè)計和FPGA優(yōu)化實現(xiàn)[A];第八屆全國信號與信息處理聯(lián)合學術(shù)會議論文集[C];2009年

中國博士學位論文全文數(shù)據(jù)庫 前5條

1 鄧明立;有限域思想的歷史演變[D];河北師范大學;2004年

2 曹煒;有限域上的一些算術(shù)問題[D];四川大學;2007年

3 李銀;橢圓曲線密碼中的有限域算術(shù)運算研究[D];上海交通大學;2011年

4 王健;橢圓曲線加密體制的雙有限域算法及其硬件實現(xiàn)[D];北京大學;2008年

5 王冠軍;基于PSA和有限域理論的高級綜合研究[D];哈爾濱工程大學;2009年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 王忠有;RFID安全協(xié)議的研究與設(shè)計[D];電子科技大學;2014年

2 靳琴琴;有限域上的坐標環(huán)的性質(zhì)及三角分解[D];電子科技大學;2014年

3 李哲;有限域上一元方程求解和相關(guān)問題的研究[D];上海交通大學;2015年

4 羅艷梅;有限域上一類特殊方程的解數(shù)公式[D];南京航空航天大學;2009年

5 韓芳;有限域快速多項式相乘運算核的研究[D];華東師范大學;2005年

6 沈曉強;有限域乘除法研究與實現(xiàn)[D];國防科學技術(shù)大學;2006年

7 賈美;有限域上置換多項式的構(gòu)造[D];南京航空航天大學;2012年

8 董可靜;有限域生成元的若干性質(zhì)研究[D];南京航空航天大學;2010年

9 余杜鵑;有限域上一類方程的解數(shù)[D];寧波大學;2014年

10 呂芳妮;有限域上的置換多項式[D];南京師范大學;2014年

  本文關(guān)鍵詞：有限域上一元方程求解和相關(guān)問題的研究，由筆耕文化傳播整理發(fā)布。

本文編號：288832