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

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

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

【相似文獻(xiàn)】

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

1 王澤涵;有限域上一類多項(xiàng)式的周期[J];電子學(xué)報(bào);1984年05期

2 李復(fù)中;關(guān)于Golomb猜想[J];科學(xué)通報(bào);1984年15期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 韓芳;有限域快速多項(xiàng)式相乘運(yùn)算核的研究[D];華東師范大學(xué);2005年

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

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

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

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

10 呂芳妮;有限域上的置換多項(xiàng)式[D];南京師范大學(xué);2014年

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

本文編號(hào)：288832