有限域运算和椭圆曲线数乘运算研究

论文摘要

本文主要研究有限域运算算法和椭圆曲线数乘运算算法。全文在强调作者所取得研究成果的同时给出了有限域运算理论和椭圆曲线密码体制理论的基本框架。全文共分八章，具体内容如下： 第一章介绍有限域运算，椭圆曲线密码体制及其数乘运算的研究背景、意义和现状，并指出论文的主要研究内容及作者得到的主要研究结果。 第二章给出有限域运算和椭圆曲线密码体制理论的基本知识和相关性质。 第三章研究素数域上取模运算。针对具有特殊形式的模数（如Mersenne数，伪Mersenne数，广义Mersenne数等），深入分析了其取模运算规律，得到如下结果：对Mersenne数和伪Mersenne数，给出了取模运算转换为模加或模减运算的公式；对模数为任意首一三项式和五项式产生的广义Mersenne数，推导了相应取模运算的复杂度计算解析表达式。根据该表达式，对任意给定的不可约首一三项式和首一五项式，可以根据该多项式的系数分别得出以广义Mersenne数为模数的取模运算所需要的模加法（或模减法）的次数。 第四章研究有限扩域的乘法运算算法。利用广义Mersenne数代替伪Mersenne数，提出了广义最优扩域的概念，并研究其上的快速乘法运算和取模运算，为乘法运算给出了通用的复杂度公式，为取模运算给出了具体的运算公式，推广了Bailey，Mihailescu和Woodbury等在最优扩域上的相应结果。 第五章研究有限扩域的求逆运算算法。深入分析和研究了有限域GF（q）和二元扩域GF（2m）上的各种求逆运算算法。重点讨论了最优扩域，最优塔域上的求逆算法，并对各种求逆算法的性能进行了分析比较。 第六章研究串、并行正规基乘法器设计算法。基于正规基表示有限域GF（2m）上元素的方法，以增加异或门（XOR Gates，XG）个数达到减少与门（AND Gates，AG）个数的方式，提出了一个串行乘法器和一个并行乘法器。同时，得到一个Ⅱ型最优正规基乘法器的算法设计，该乘法器要求（2m-2）个XG，m个AG。 第七章研究椭圆曲线数乘运算算法。相同椭圆曲线，采用不同的坐标表示，对应不同的点加公式，不同的点加公式具有不同的计算复杂度。本章分析了不同坐标下点加公式的计算复杂度，并以此为基础，首先分析和比较了数乘运算的点加及倍加方法（add and double methods），加减方法和窗口方法等三种算法的计算复

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 研究动机和意义
• 1.2 研究现状
• 1.2.1 有限域运算算法的研究现状
• 1.2.2 椭圆曲线密码体制（ECC）的研究现状
• 1.2.3 数乘运算的研究现状
• 1.3 论文的主要工作
• 1.4 论文的章节安排
• 第二章 有限域和ECC
• 2.1 群和域
• 2.2 有限域
• 2.2.1 有限域上的多项式
• 2.2.2 有限域的性质
• 2.2.3 有限域的类型
• 2.2.4 有限域的基
• 2.3 椭圆曲线密码体制（ECC）
• 2.3.1 椭圆曲线
• 2.3.2 有限域上的椭圆曲线
• 2.3.3 椭圆曲线有理点群
• 2.3.4 椭圆曲线有理点群结构
• 2.4 小结
• 第三章 素数域上的取模运算
• 3.1 取模运算
• 3.1.1 以正整数为模数
• 3.1.2 以多项式为模数
• 3.1.3 取模运算的运算律
• 3.2 现有算法及其分析
• 3.2.1 经典取模算法
• 3.2.2 Barrett取模算法
• 3.2.3 Montgomery取模乘法
• 3.2.4 三种算法的性能比较
• 3.3 特殊模数的取模运算
• 3.3.1 Mersenne数的取模运算
• 3.3.2 伪Mersenne数的取模运算
• 3.3.3 广义Mersenne数的取模运算
• 3.4 小结
• 第四章 有限扩域上的乘法运算
• 4.1 最优扩域（OEFs）
• 4.1.1 OEFs的性质
• 4.1.2 OEFs的性能优势
• 4.1.3 OEFs上的乘法运算
• 4.2 最优塔域（OTFs）
• 4.2.1 OTFs的基本性质
• 4.2.2 OTFs和OEFs间的转换
• 4.2.3 OTFs和OEFs的复杂性比较
• 4.3 广义最优扩域（GOEFs）
• 4.3.1 GOEFs的基本概念
• 4.3.2 GOEFs的乘法运算
• 4.3.3 GOEFs的取模运算
• 4.3.4 性能比较
• 4.4 小结
• 第五章 有限域上的求逆运算
• 5.1 GF（p）上的求逆运算
• 5.1.1 扩展欧氏求逆算法
• 5.1.2 Montgomery求逆算法
• m）上的求逆运算'>5.2 二元扩域GF（2^m）上的求逆运算
• 5.2.1 三种经典求逆算法
• 5.2.2 除法运算
• m）上的求逆运算'>5.3 扩域GF（p^m）上的求逆运算
• 5.3.1 通用的求逆算法—ITI算法
• 5.3.2 OEFs上的求逆运算
• 5.4 小结
• 第六章 串、并行乘法器设计
• 6.1 并行性设计
• 6.2 多项式基乘法器
• 6.2.1 Mastrovito并行PB乘法器
• 6.2.2 基于特殊多项式的Mastrovito并行PB乘法器
• 6.2.3 Karatsuba乘法器
• 6.3 正规基乘法器
• 6.3.1 实例
• 6.3.2 并行正规基乘法器
• 6.3.3 串行正规基乘法器
• 6.3.4 Reyhani-Masoleh和Anwar Hasan所做工作
• 6.3.5 改进的正规基乘法器
• 6.4 Ⅱ型最优正规基串行乘法器算法设计
• 6.4.1 相关工作
• 6.4.2 算法设计
• 6.4.3 算法复杂性分析
• 6.4.4 实例
• 6.5 小结
• 第七章 椭圆曲线数乘运算
• 7.1 素数域上椭圆曲线点的表示
• 7.1.1 仿射坐标
• 7.1.2 投影坐标
• 7.1.3 计算复杂性
• 7.2 二元扩域上椭圆曲线点的表示
• 7.2.1 仿射坐标
• 7.2.2 投影坐标
• 7.2.3 性能分析和比较
• 7.3 计算一个数乘运算
• 7.3.1 典型算法
• 7.3.2 算法性能分析
• 7.4 计算多个数乘运算
• 7.4.1 现有算法
• 7.4.2 算法性能分析
• 7.5 其它相关方法
• 7.5.1 重复计算倍乘
• 7.5.2 基于折半的数乘计算
• 7.6 小结
• 第八章 全文总结和未来工作
• 8.1 全文总结
• 8.2 未来工作
• 参考文献
• 攻博期间取得的研究成果
• 一、科研项目
• 二、发表和录用的论文
• 三、教学实践