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

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

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

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

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

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