有限域運(yùn)算和橢圓曲線數(shù)乘運(yùn)算研究.pdf

1、本文主要研究有限域運(yùn)算算法和橢圓曲線數(shù)乘運(yùn)算算法。全文在強(qiáng)調(diào)作者所取得研究成果的同時(shí)給出了有限域運(yùn)算理論和橢圓曲線密碼體制理論的基本框架。 第一章介紹有限域運(yùn)算，橢圓曲線密碼體制及其數(shù)乘運(yùn)算的研究背景、意義和現(xiàn)狀，并指出論文的主要研究?jī)?nèi)容及作者得到的主要研究結(jié)果。 第二章給出有限域運(yùn)算和橢圓曲線密碼體制理論的基本知識(shí)和相關(guān)性質(zhì)。 第三章研究素?cái)?shù)域上取模運(yùn)算。針對(duì)具有特殊形式的模數(shù)(如Mersenne數(shù)，偽Mers

2、enne數(shù)，廣義Mersenne數(shù)等)，深入分析了其取模運(yùn)算規(guī)律，得到如下結(jié)果：對(duì)Mersenne數(shù)和偽Mersenne數(shù)，給出了取模運(yùn)算轉(zhuǎn)換為模加或模減運(yùn)算的公式；對(duì)模數(shù)為任意首一三項(xiàng)式和五項(xiàng)式產(chǎn)生的廣義Mersenne數(shù)，推導(dǎo)了相應(yīng)取模運(yùn)算的復(fù)雜度計(jì)算解析表達(dá)式。根據(jù)該表達(dá)式，對(duì)任意給定的不可約首一三項(xiàng)式和首一五項(xiàng)式，可以根據(jù)該多項(xiàng)式的系數(shù)分別得出以廣義Mersenne數(shù)為模數(shù)的取模運(yùn)算所需要的模加法(或模減法)的次數(shù)。 第

3、四章研究有限擴(kuò)域的乘法運(yùn)算算法。利用廣義Mersenne數(shù)代替?zhèn)蜯ersenne數(shù)，提出了廣義最優(yōu)擴(kuò)域的概念，并研究其上的快速乘法運(yùn)算和取模運(yùn)算，為乘法運(yùn)算給出了通用的復(fù)雜度公式，為取模運(yùn)算給出了具體的運(yùn)算公式，推廣了Bailey，Mihǎilescu和Woodbury等在最優(yōu)擴(kuò)域上的相應(yīng)結(jié)果。 第五章研究有限擴(kuò)域的求逆運(yùn)算算法。深入分析和研究了有限域GF(q)和二元擴(kuò)域GF(2m)上的各種求逆運(yùn)算算法。重點(diǎn)討論了最優(yōu)擴(kuò)域，最優(yōu)

4、塔域上的求逆算法，并對(duì)各種求逆算法的性能進(jìn)行了分析比較。 第六章研究串、并行正規(guī)基乘法器設(shè)計(jì)算法。基于正規(guī)基表示有限域GF(2m)上元素的方法，以增加異或門(XORGates，XG)個(gè)數(shù)達(dá)到減少與門(ANDGates，AG)個(gè)數(shù)的方式，提出了一個(gè)串行乘法器和一個(gè)并行乘法器。同時(shí)，得到一個(gè)Ⅱ型最優(yōu)正規(guī)基乘法器的算法設(shè)計(jì)，該乘法器要求(2m-2)個(gè)XG，m個(gè)AG。 第七章研究橢圓曲線數(shù)乘運(yùn)算算法。相同橢圓曲線，采用不同的坐標(biāo)

5、表示，對(duì)應(yīng)不同的點(diǎn)加公式，不同的點(diǎn)加公式具有不同的計(jì)算復(fù)雜度。本章分析了不同坐標(biāo)下點(diǎn)加公式的計(jì)算復(fù)雜度，并以此為基礎(chǔ)，首先分析和比較了數(shù)乘運(yùn)算的點(diǎn)加及倍加方法，加減方法和窗口方法等三種算法的計(jì)算復(fù)雜性。接著比較了點(diǎn)加及倍加方法和Montgomery方法的計(jì)算開銷，并指出，在仿射坐標(biāo)下，當(dāng)域元素求逆運(yùn)算和乘法運(yùn)算的比值大于等于2時(shí)，點(diǎn)加及倍加方法的計(jì)算開銷少于Montgomery方法；但是，在投影坐標(biāo)下，點(diǎn)加及倍加方法的計(jì)算開銷卻大于Mo