基于扩展Karatsuba算法的GF（2 m ）乘法器设计

发布时间：2021-08-08 06:37

　　有限域GF（2^m）算术运算的高效硬件实现,在编码理论和公钥密码中有着广阔的应用前景。在域GF（2^m）的诸多算术运算中,乘法是最关键的运算之一,因为其它复杂运算例如指数运算和求逆运算等均可通过乘法的迭代来实现。因此,设计高效的乘法器算法是快速实现密码算法、编码的基础。在乘法器设计中,时间复杂度和空间复杂度是衡量乘法器效率的两个重要指标,降低这两个指标是设计高效乘法器的一个主要目标。本文基于三项或n项Karatsuba算法,结合Mastrovito方法,提出了四种GF（2^m）比特并行的混合乘法器。这些乘法器在时空复杂度方面对比经典方案均有较大的改进,部分结果达到了当前已知结果的最佳指标。首先,针对由特殊的不可约三项式x^m+x^k+1,m=3k定义的GF（2^m）,利用三项Karatsuba算法和移位多项式基,设计出了一个时空复杂性更好的比特并行乘法器。该乘法器与经典乘法器相比节约了1/3左右的电路门,且其时间复杂度与经典乘法器几乎相同,这也是首次在没有增加时延的情... 

【文章来源】：信阳师范学院河南省

【文章页数】：65 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 引言
    1.1 研究背景与意义
    1.2 国内外研究现状
    1.3 研究成果
    1.4 本文的组织结构
第2章 相关知识
    2.1 有限域
        2.1.1 有限域概念
        2.1.2 有限域的类型
    2.2 多项式基和移位多项式基
        2.2.1 多项式基
        2.2.2 移位多项式基
    2.3 n距不可约三项式
    2.4 n项Karatsuba算法
    2.5 SPB下的Mastrovito矩阵
    2.6 本文通用的计算符号
    2.7 小结
第3章 基于三项Karatsuba算法的乘法器设计
    3.1 关于不可约三项式x~m+x~k+1(m=3k)的运算
        3.1.1 S_1 modf(x)的计算
        3.1.2 S_2 modf(x)的计算
        3.1.3 时空复杂度分析
    3.2 x~m+x~k+1(m=3k+1)的计算
        3.2.1 S_1 mod f(x)的计算
        3.2.2 S_2 mod x~(3k+1)+x~k+1的计算
        3.2.3 时空复杂度分析
    3.3 x~m+xk~+1 (m=3k+2)的计算
        3.3.1 S_1 mod x~(3k+2)+x~k+1的运算
        3.3.2 S_2 mod x~(3k+2)+x~k+1的运算
        3.3.3 时空复杂度分析
    3.4 比较与讨论
    3.5 小结
第4章 n项Karatsuba算法及其应用特殊三项式乘法器设计
    4.1 基于n项Karatsuba算法的高效乘法运算
    4.2 S_1 mod f(x)的运算
        4.2.1 S_1 mod f(x)的详细计算
        4.2.2 S_1 mod f(x)的示例
    4.3 S_2 mod x~(nk)+x~k+1的计算
        4.3.1 S_2 mod f(x)的详细计算
        4.3.2 S_2 mod f(x)的示例
    4.4 理论时空复杂度分析
        4.4.1 加速策略
        4.4.2 比较与讨论
    4.5 小结
第5章 总结与展望
参考文献
攻读学位期间获得与学位论文相关的科研成果目录
致谢


【参考文献】：
博士论文
[1]有限域运算和多变量公钥密码硬件的优化和设计[D]. 易海博.华南理工大学 2015
[2]椭圆曲线密码中的有限域算术运算研究[D]. 李银.上海交通大学 2011
[3]椭圆曲线加密体制的双有限域算法及其硬件实现[D]. 王健.北京大学 2008

硕士论文
[1]有限域GF（2m）高效乘法器设计[D]. 陈晴.信阳师范学院 2019
[2]高性能有限域乘法器的研究与实现[D]. 金意儿.浙江大学 2007



本文编号：3329430