超椭圆曲线上Montgomery标量乘的快速计算公式

软件学报ＩＳＳＮ　１０００－９８２５．ＣＯＤＥＮ　ＲＵＸＵＥＷ　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ，２０１３，２４（１０）：２２７５—２２８８［ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１００１．２０１３．０４３７０］　◎中国科学院软件研究所版权所有．　Ｅ—ｍａｉｌ：ｊｏｓ＠ｉｓｃａｓ．ａｃ．ｃｎ　ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃａ　Ｔｅｌ／Ｆａｘ：＋８６一ｌ０—６２５６２５６３　超椭圆曲线上Ｍｏｎｔｇｏｍｅｒｙ标量乘的快速计算公式　李明１，３，孔凡玉　，朱大铭　（山东大学计算机科学与技术学院，山东济南（山东大学网络信息安全研究所，山东济南（国网山东省电力公司，山东济南２５０１００）　２５０１００）　２５０１００）　通讯作者：李明，Ｅ—ｍａｉｌ：ｌｕａｍｉｎ８：＠ｍｓｎ．ｔｏｍ　摘要：　超椭圆曲线密码体制与椭圆曲线密码体制相比，具有安全性高、密钥短的特点．标量乘计算是这两个密码　体制中最为核心和重要的计算，其中，Ｍｏｎｔｇｏｍｅｒｙ阶梯算法是计算标量乘的一种重要算法，且因为其可以抵抗简单　的边带信道攻击，而被广泛研究和应用．近几年，椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法和相应的点运算公式一直在不　断改进，但是在超椭圆曲线上，直接设计快速运算公式来提高Ｍｏｎｔｇｏｍｅｒｙ阶梯算法的速度，却一直没有太大的进展．　Ｌａｎｇｅ曾经探讨过这种快速公式存在的可能性，但却并没有得到一个实用、有效的计算公式．在特征为２的域上，通　过改进超椭圆曲线上的除子类加法公式来提高超椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ阶梯标量乘计算，提出了一种新的思路　来改进多种坐标系下的加法公式．分析和仿真结果表明，在特征为２的域上，新的运算公式的运行速度比之前的标准　公式均有所提高．在某类常用曲线上，新的公式比之前的公式快了４％～８．３％．这说明，直接设计快速除子运算公式来　提高Ｍｏｎｔｇｏｍｅｒｙ阶梯算法的速度是可行的．同时，使用新的公式实现的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法可以抵抗简单边带信　道攻击．　关键词：　超椭圆曲线；标量乘；Ｍｏｎｔｇｏｍｅｒｙ　Ｌａｄｄｅｒ；Ｌ￣算公式；除子类　中图法分类号：ＴＰ３０１　文献标识码：Ａ　中文引用格式：李明，孔凡玉，朱大铭．超椭圆曲线上Ｍｏｎｔｇｏｍｅｒｙ标量乘的快速计算公式．软件学报，２０１３，２４（１０）：２２７５—２２８８．　ｈａｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｒｄｌＯ００－９８２５／４３７０．ｈｔｍ　英文引用格式：Ｌｉ　Ｍ，Ｋｏｎｇ　ＦＹ，Ｚｈｕ　ＤＭ．Ｆａｓｔ　ａｄｄｉｔｉｏｎ　ｆｏｒｍｕｌａｅ　ｆｏｒ　Ｍｏｎｔｇｏｍｅｒｙ　Ｌａｄｄｅｒ　ｓｃａｌａｒ　ｍｕｌｔｉｐｌｉｃａｔｉｏｎ　ｏｎ　ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｕｒｖｅｓ．Ｒｕａｎ　Ｊｉａｎ　Ｘｕｅ　Ｂａｏ／Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，２０１３，２４（１０）：２２７５－２２８８（ｉｎ　Ｃｈｉｎｅｓｅ）．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／ｌＯ００—９８２５／　４３７０．ｈｔｍ　Ｆａｓｔ　Ａｄｄｉｔｉｏｎ　Ｆｏｒｍｕｌａｅ　ｆｏｒ　Ｍｏｎｔｇｏｍｅｒｙ　Ｌａｄｄｅｒ　Ｓｃａｌａｒ　Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ　ｏｎ　Ｈｙｐｅｒｅｌｌｉｐｔｉｃ　Ｃｕｒｖｅｓ　ＬＩ　Ｍｉｎｇ　，ＫＯＮＧ　Ｆａｎ．Ｙｕ　，ＺＨＵ　Ｄａ—Ｍｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈａｎｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｊｉ’ｎａｎ　２５０１００，Ｃｈｉｎａ）　（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｎｅｔｗｏｒｋ　Ｓｅｃｕｒｉｔｙ，Ｓｈａｎｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｊｉ’ｎａｎ　２５０　１　００，Ｃｈｉｎａ）　（Ｓｔａｔｅ　Ｇｒｉｄ　Ｓｈａｎｄｏｎｇ　Ｅｌｅｃｔｒｉｃ　Ｐｏｗｅｒ　Ｃｏｍｐａｎｙ，Ｊｉ’ｎａｎ　２５０１００，Ｃｈｉｎａ）　Ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ａｕｔｈｏｒ：ＬＩ　Ｍｉｎｇ，Ｅ—ｍａｉｌ：ｌｕａｍｉｎｇ＠ｍｓｎ．ｃｏｍ　Ａｂｓｔｒａｃｔ：Ｃｏｍｐａｒｉｎｇ　ｗｉｔｈ　ｅｌｌｉｐｔｉｃ　ｃｕｒｖｅ（ＥＣ）ｃｒｙｐｔｏｓｙｓｔｅｍ，ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｕｒｖｅ（ＨＥＣ）ｃｒｙｐｔｏｓｙｓｔｅｍ　ｏｆｆｅｒｓ　ｈｉｇｈ　ｌｅｖｅｌ　ｏｆ　ｓｅｃｕｒｉｔｙ　ｗｉｔｈ　ｓｈｏｒｔｅｒ　ｋｅｙ　ｓｉｚｅ　Ｓｃａｌａｒ　ｍｕｌｔｉｐｌｉｃａｔｉｏｎ　ｉｓ　ｔｈｅ　ｍｏｓｔ　ｉｍｐｏｒｔａｎｔ　ａｎｄ　ｋｅｙ　ｏｐｅｒａｔｉｏｎ　ｉｎ　ｃｒｙｐｔｏｓｙｓｔｅｍｓ　ｂｕｉｌｔ　ｏｎ　ＨＥＣ　ａｎｄ　ＥＣ．Ｍｏｎｔｇｏｍｅｒｙ　Ｌａｄｄｅｒ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｎ　ｅｆｉｃｉｆｅｎｔ　ａｎｄ　ｉｍｐｏｒｔａｎｔ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｉｍｐｌｅｍｅｎｔ　ｓｃａｌａｒ　ｍｕｌｔｉｐｌｉｃａｔｉｏｎｓ　ｆｏｒ　ｄｅｆｅｎｄｉｎｇ　ａｇａｉｎｓｔ　ｓｉｄｅ　ｃｈａｎｎｅｌ　ａｔｔａｃｋｓ　Ｗｈｉｌｅ　Ｍｏｎｔｇｏｍｅｒｙ　Ｌａｄｄｅｒ　ａｌｇｏｒｉｔｈｍ　ｏｎ　ｅｌｌｉｐｔｉｃ　ｃｕｒｖｅ　ｉｓ　ｂｅｉｎｇ　ｉｍｐｒｏｖｅｄ　ｉｎ　ｒｅｃｅｎｔ　ｙｅａｒｓ，ｔｈｅｒｅ　ｉｓ　ｎｏｔ　ｍｕｃｈ　ａｄｖａｎｃｅ　ｏｎ　ｈｙｐｅｒｅｌｌｉｐｔｉｃ　・基金项目：国家自然科学￣（２００８ＢＳ０１０１１１　（６１０７００１９，６０７０３０８９）；山东省自然科学基金（ｚＲ２０１ＯＦＱ０１５）；山东省优秀中青年科学家科研奖　励￣收稿时间：２０１１－１０．２６；定稿时间：２０１２．１２—２７　２２７６　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．１０，Ｏｃｔｏｂｅｒ　２０１３　ｃｕｒｖｅｓ．Ｌａｎｇｅ　ｐｒｏｐｏｓｅｄ　ａ　ｗａｙ　ｔｏ　ｄｅｓｉｇｎ　ｆａｓｔｅｒ　ａｄｄｉｔｉｏｎ　ｆｏｒｍｕｌａ　ｏｎ　ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｕｒｖｅｓ　ｂｕｔ　ｄｉｄ　ｎｏｔ　ｒｅｓｕｌｔ　ｉｎ　ａ　ｐｒａｃｔｉｃａｌ　ｓｏｌｕｔｉｏｎ．Ｔｈｉｓ　ｐａｐｅｒ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ａｄｄｉｔｉｏｎ　ｆｏｒ　ｄｉｖｉｓｏｒ　ｃｌａｓｓｅｓ　ｆｏｒ　ｔｈｅ　ｆｉｒｓｔ　ｔｉｍｅ　ｔｏ　ｉｍｐｌｅｍｅｎｔ　ｆａｓｔｅｒ　Ｍｏｎｔｇｏｍｅｒｙ　Ｌａｄｄｅｒ　ａｌｇｏｒｉｔｈｍ．Ｎｅｗ　ｔｅｃｈｎｉｑｕｅ　ｉｓ　ａｐｐｌｉｅｄ　ｆｏｒ　ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｆｏｒｍｕｌａｅ　ｏｎ　ｖａｒｉｏｕｓ　ｃｏｏｒｄｉｎａｔｅｓ．Ｔｈｅ　ａｎａｌｙｓｉｓ　ａｎｄ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｎｅｗ　ｆｏｒｍｕｌａｅ　ａｒｅ　ｆａｓｔｅｒ　ｔｈａｎ　ｐｒｅｖｉｏｕｓ　ｏｎｅｓ．Ｏｖｅｒ　ｉｅｌｆｄｓ　ｏｆｃｈａｒａｃｔｅｒ　ｔｗｏ　ａｎｄ　Ｔｙｐｅ　ＩＩ　ｃｕｒｖｅｓ．ｔｈｅ／ｌｅｗ　ｆｏｒｍｕｌａｅ　ｉｓ　４％－８．４％ｆａｓｔｅｒ　ｔｈａｎ　ｔｈｅ　ｏｎｅｓ　ｋｎｏｗｎ　ｂｅｆｏｒｅ．Ａｎｄ　ｔｈｅ　Ｍｏｎｔｇｏｍｅｒｙ　Ｌａｄｄｅｒ　ａｌｇｏｒｉｔｈｍ　ｉｍｐｌｅｍｅｎｔｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ｉｓ　ｓｅｃｕｒｅ　ａｇａｉｎｓｔ　ｓｉｄｅ　ｃｈａｎｎｅｌ　ａｔｔａｃｋｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｕｒｖｅ；ｓｃａｌａｒ　ｍｕｌｔｉｐｌｉｃａｔｉｏｎ；Ｍｏｎｔｇｏｍｅｒｙ　ｌａｄｄｅｒ；ａｄｄｉｔｉｏｎ　ｆｏｒｍｕｌａｅ；ｄｉｖｉｓｏｒ　ｃｌａｓｓｅｓ　超椭圆曲线（ＨＥＣ）与椭圆曲线（ＥＣ）类似，也可以用来建立密码体制．自从ＫｏｂｌｉｔｚＩ　】于１９８８年提出了在超椭　圆曲线上建立密码体制以来，超椭圆曲线上的运算公式和标量乘计算方法也在不断地发展和改进．与椭圆曲线　密码体制相比，超椭圆曲线密码体制的安全性更高，其上的运算参数及密钥长度都更短．对应于参数为ｌ　０２４ｂｉｔｓ　长度的ＲＳＡ密码体制，现在推荐在椭圆曲线和超椭圆曲线上建立阶为２　。大小的群，就可以满足我们的安全需　求【２１．在使用椭圆曲线时，操作数的长度为１６０ｂｉｔｓ即可满足要求．在亏格ｇ＝２的超椭圆曲线上，操作数的长度约为　１６０／ｇ＝８０ｂｉｔｓ；在亏格为３的超椭圆曲线上，操作数的长度约为５５ｂｉｔｓ．已经证明，在亏格大于３的超椭圆曲线上建　立密码体制，安全性有所降低．当使用亏格为３的超椭圆曲线时，也要小心地选择安全曲线以避免攻击．本文讨论　亏格为２的超椭圆曲线上的运算．　虽然超椭圆曲线上的操作数大多很短，但其运算公式却很复杂．随着研究的深入，各种高效的除子类的运算　公式陆续被提出［３－５］，并且使得超椭圆曲线上的标量乘运算速度越来越接近于椭圆曲线上的标量乘计算．　Ｍｏｎｔｇｏｍｅｒｙ阶梯算法［２，６１是计算标量乘的一种重要算法，且因为其一定程度上可以抵抗简单边带信道攻　击［２】而被广泛应用．这种算法在加解密计算和利用椭圆曲线（超椭圆曲线）分解大素数等应用中，都有重要的作用　和意义．近几年，椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法和相应的点运算公式一直在不断地得以改进，比如２０１０年　的密码年会上，Ｂｅｒｎｓｔｅｉｎ等人【　在ｂｉｎａｒｙ　Ｅｄｗａｒｄｓ曲线上使用Ｍｏｎｔｇｏｍｅｒｙ阶梯算法实现了一般椭圆曲线上至　今最快的标量乘计算．在超椭圆曲线上，人们利用Ｋｕｍｍｅｒ　ｓｕｒｆａｃｅ设计Ｍｏｎｔｇｏｍｅｒｙ计算方案ｌ　ｊ．直接在一般曲　线上设计快速除子类的运算公式来实现较为高效的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法，是另一条改进途径，但在这个方向上　却一直没有太大进展．Ｌａｎｇｅ曾经探讨过这种快速公式存在的可能性Ｌ９Ｊ，却并未得到一个实用、有效的计算公式，　本文提出了更为快速和高效的除子类加法公式来加快超椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法的计算．首先　给出了新的思路来进行公式上的代数变换，然后在多种坐标系下优化设计出了新的公式．对于特征为２的域上　的超椭圆曲线，根据不同的参数取值【　】可将其分类，分为类型Ｉ、类型ＩＩ、类型ＩＩＩ曲线．分析和比较结果表明，新　的公式在投影坐标系（ｐｒｏｊｅｃｔｉｖｅ　ｃｏｏｒｄｉｎａｔｅ）、Ｎ坐标系（ｎｅｗ　ｃｏｏｒｄｉｎａｔｅ）和Ｒ坐标系（ｒｅｃｅｎｔ　ｃｏｏｒｄｉｎａｔｅ）下，在类型　ＩＩ和类型ＩＩＩ的曲线上，速度与之前的公式相比都有明显提高．在类型ＩＩ的曲线上提高最为明显，而类型ＩＩ曲线　正好也是我们在构建超椭圆曲线密码体制时最为常用的一种曲线．当域上的平方和乘法之间的运算量的比率　满足０．８比１时，类型ＩＩ的曲线上新的公式比之前的公式快了７．７％～７．８％．当我们用正规基来表示域上的元素时，　平方的计算量町以忽略不计，这时新的公式快了４％～８－３％．当然，新的技术也可以进一步应用于参数更为特殊的　曲线上，以得到更快的算法．本文的研究结果表明，超椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法可以直接在公式层面　提高效率．本文最后使用新的公式实现了超椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法，在保持高效的同时可以抵抗简　单边带信道攻击．　本文第１节介绍相关基本概念和基础知识，主要是已有的运算公式．第２节提出新的代数变换方法和思路，　并设计出新的运算公式．第３节是性能分析和仿真实验．最后一节对本文进行总结，并对进一步的工作进行探讨．　１基础知识　１．１超椭圆曲线上的运算　本节对亏格为２的超椭圆曲线进行简要介绍，具体内容可参考文献［２，６，１０，１１１．设　是一个特征为Ｐ的有　限域，其中，ｇ　，　是Ｆｑ的代数闭包，下面定义了亏格为ｇ的超椭圆曲线：　李明等：超椭圆曲线上Ｍｏｎｔｇｏｍｅｒｙ标量乘的快速计算公式　２２７７　Ｃ：ｙ　＋　），　其中　）∈　］首项系数为１，次数为２ｇ＋１；　）∈Ｆｑ　］是一个次数最大为ｇ的多项式，对于二元组（日，６）∈　×　，　没有合适的解满足ｂ２＋ｈ（ａ）ｂ＝Ｊ（ａ）和偏微分等式２ｂ＋ｈ（ａ）＝Ｏ，ｈ　（ａ）６－厂　（口）：０．这是为了保证超椭圆曲线不是超奇异　的．曲线Ｃ／　就叫作定义在　上的亏格为ｇ的超椭圆曲线．　设　是　的一个子域，超椭圆曲线Ｃ在　上所有的点构成了一个点集：　Ｃ（　＝｛　）：ｘ　∈Ｋ　＋　＝：，　））ｕ｛ｏ。），　其中，Ｏ０表示无穷远点．Ｃ（　上是没有合适的群运算的，我们构建超椭圆曲线上的Ｊａｃｏｂｉａｎ来获得一个实用的离　散对数系统．首先定义超椭圆曲线Ｃ上的一个除子（ｄｉｖｉｓｏｒ）：Ｄ＝∑ｍ，Ｐ，其中，ｒｎｐＥＺ，尸∈ｃ（　，而除子的次数　ｄｅｇ（Ｄ）＝∑ｍ　．其中，所有次数为０的除子构成了一个集合ＤｉｖｏＣ（Ｄ）．我们再通过函数域Ｇ［ｘ，ｙ］／（ｙ　＋　）＿＝，　）），　构造出主除子群（ｇｒｏｕｐ　ｏｆ　ｐｒｉｎｃｉｐｌｅ　ｄｉｖｉｓｏｒｓ）：Ｐｃ（　）＝｛Ｄ　Ｖ（　：Ｆ∈　（　）．最后，即得到了Ｃ在域　上的Ｊａｃｏｂｉａｎ　Ｊｃ（Ｆｑ）＝Ｄｉｖ０Ｃ（Ｆｑ）／Ｐｃ（Ｇ）．超椭圆曲线的安全性即建立在Ｊａｃｏｂｉａｎ的离散对数问题上．　下一步，Ｊａｃｏｂｉａｎ上的每一个元素，都可以用唯一的ｒｅｄｕｃｅｄ　ｄｉｖｉｓｏｒ来表示，ＭｕｍｆｏｒｄＩ　１给出了表示方法：　（１）Ｕ是首项系数为１的；　（２）ｄｅｇ　ｖ＜ｄｅｇ”≤ｇ；　（３）ｕｌｖ　＋ｖｈ－ｆ　ｃａｎｔｏｒ㈣在此基础上提出了如何计算两个除子类的加法，但是Ｃａｎｔｏｒ算法中含有求多项式的最大公约数　的运算以及多个求逆运算．之后，有人使用各种技巧改进了Ｃａｎｔｏｒ算法．最近的导出公式是Ｌａｎｇｅｌ６】提出的，如下　所示：　ｋ＝（ｆ—ｖｚｈ—ｖ￣）／ｕ　，　ｉ（Ｖ１一ｖ２）／ｕ２　ｍｏｄ”１，，＝ＳＵ２，”＝（ｋ—ｓ（１＋ｈ＋２ｖ２））／ｕ１，　Ｕ　＝Ｕ　ｍａｄｅｍｏｎｉｃ，ｖ　＝一ｈ一（，＋Ｖ２）ｍｏｄ“　．　这就将Ｃａｎｔｏｒ算法中计算ｓｅｍｉ．ｒｅｄｕｃｅｄ　ｄｉｖｉｓｏｒ的过程和计算ｒｅｄｕｃｅｄ　ｄｉｖｉｓｏｒ的过程合并且简化了，并去掉　了计算最大公约数的步骤．其中，Ｓ的计算可以利用Ｓｙｌｖｅｓｔｅｒ　ｒｅｓｕｌｔａｎｔ来实现．具体的计算公式如算法１所示．算　法中的Ｍ表示域上的乘法，Ｓ表示平方计算，而Ｉ表示元素求逆．　算法１．一般情况下除子类加法公式［　，　】　Ｉｎｐｕｔ　０ｕｔｐｕｔ　Ｓｔｅｐ　１　Ｃｏｍｐｕｔｅ　ｒｅｓｕｌｔａｎｔ，ｏｆ／／１，“２：　ＺＩ　ｇ／Ｉ１一Ｕ２１，Ｚ２　／＊／２０一／ｄｌＯ，Ｚ３＝ＵＩ１ＺＩ＋Ｚ２；，　＝　２ｚ３＋ｚ　Ｕｌ０；　。ＲＩ，ｖｌ】，［　２，　２］，ｌ￣ｉ＝Ｘ　＋“　１　＋甜ｆ０，ｖｒ＝ｖｌｌｘ＋Ｖｉｏ；　“　，ｖ　１＝［　ｌ，ｖｄ＋［ｕ２，ｖ２］．　Ｅｘｐｒｅｓｓｉｏｎ　Ｏｐｅｒａｔｉｏｎｓ　１Ｓ＋３Ｍ　２　３　Ｃｏｍｐｕｔｅ　ａｌｍｏｓｔ　ｉｎｖｅｒｓｅ　ｏｆ／４２　ｍｏｄｕｌｏ　ｕｌ（ｉｎｖ　ｒ／ｕ２　ｒｏｏｄ“１）：　ｆ＂ｖ１　２１，ｉｎｖｏ＝Ｚ３；　Ｃｏｍｐｕｔｅ　Ｓｔ＝ｒｓ＝－（ｖｌ—ｖ￣）ｉｎｖ　ｏｏｄ　ｌｒ：　Ｗ０＝Ｉ）１０—１）２０，Ｗｌ＝Ｖｌｌ—ｖ２１，ｗ２＝ｉｎｖｏｗｏ，ｗ３＝ＤｌＶｌＷｌ；　５Ｍ　Ｓ　（ｆ　Ｖｏ＋ｆ　Ｖ１）（ｗｏ＋ｗ１）一Ｗ２一Ｗ３（Ｉ＋ｕｌＩ），　４　Ｃｏｍｐｕｔｅ　”　＋　０　ｌ　＋Ｓ　／ｓ　ａｎｄ　Ｓｌ：　Ｗ２一ＵｌＯＷ３；ｉｆ　Ｓ　０　ｓｅｅ　ｂｅｌｏｗ　１Ｉ＋２Ｓ＋５Ｍ　Ｗｌ＝（ｒｓ；）～（＝ｌ／ｒ２ｓ１），ｗ２＝ｒｗｌ（＝１］Ｓ￣），Ｗ３＝Ｓ￣　ｗ１（　１）；Ｗ４＝ｒｗＲ＝ｌ／ｓｔ），　＝　，　；＝　ｗ２；　５　６　Ｃｏｍｐｕｔｅ，　＝　“２＝＝　＋　＋和＋　：　＝Ｕ２１＋　，　＝／＇／２１　＋“２０，　＝Ｕ２０Ｓ　；　２Ｍ　３Ｍ　Ｃｏｍｐｕｔｅ”　＝　（？＋　＋２ｖ２）一的／“１＝＝　＋“　ｘ＋“　：　“　＝（　；一Ｉ＇ｌｌＩ）（　一ｚｌ＋　“　＝２ｓ　一Ｚｌ＋ｈ２ｗ４一ｗｓ；　）一ｂｔ１０＋　＋（ｈｌ＋２Ｖ２１）ｗ４＋（２ｕ２１＋２１—　）ｗ５；　４Ｍ　７　Ｃｏｍｐｕｔｅ　Ｖ　三一ｈ一（ｆ＋Ｖ２）ｍｏｄ　＝ｖ；ｘ＋Ｖ’０：　＝　一“　，ｗ２＝“　＋　一　，　＝¨　一ｖ２ｌ一向＋　“　；　ｗ２＝“　一　，　＝　ｗ］一　一‰＋　；　Ｔｏｔａｌ　１Ｉ＋３Ｓ十２２Ｍ　２２７８　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．１０，Ｏｃｔｏｂｅｒ　２０１３　算法１．一般情况下除子类加法公式　，　（续）　４　Ｃｏｍｐｕｔｅ　：　ｉｎｖ　１／ｒ，ＳＯ　Ｓ　ｉｎｖ；　ｌＩ＋ｌＭ　５　Ｃｏｍｐｕｔｅ　Ｕ　ｒ＝（　—　（，＋＾＋２Ｖ２））／　ｌ　ｉ　＋Ｕ：：　“　＝　一“２ｌ一“ｌｌ—Ｓ　一　０，　；　ｌＳ　６　Ｃｏｍｐｕｔｅ　ｖ，ｉ—ｈ一（『＋　２）ｍｏｄ　Ｕ　＝　：　２Ｍ　＝ＳＯ　２ｌ＋“　）＋　＋　ｌ＋　Ｔｏｔａｌ　，ＷＥ＝Ｓｏ＋Ｖ２０＋％，　＝“　一Ｗ２；　１Ｉ＋２Ｓ＋ｌ１Ｍ　我们这里只讨论绝大多数情况下的加法公式，也就是Ｕ　和Ｕ２的次数均为２且互素时的公式．其他情况出现　的概率非常小，且计算过程简单很多，这里不再赘述，具体过程参考文献［２，９】．　１．２　Ｍｏｎｔｇｏｍｅｒｙ阶梯算法　Ｍｏｎｔｇｏｍｅｒｙ阶梯算法如算法２所示．实际上，算法中的Ｄｌ总是存储了目前为止所求出的结果，而Ｄ２中总是　存储了Ｄ　＋Ｄ的值．这样，最后输出的Ｄ　就是要求的结果．在算法的循环体中，由于每次循环都需要做一次二倍运　算和一次除子类的加法运算，这就使得每次执行循环体时的运算量是一样的．所以，Ｍｏｎｔｇｏｍｅｒｙ阶梯标量乘算　法一定程度上可以抵抗简单边带信道攻击．　算法２．Ｍｏｎｔｇｏｍｅｒｙ标量乘算法　输入：ｒｅｄｕｃｅｄ　ｄｉｖｉｓｏｒ　Ｄ和整数Ｓ＝（ＳＩ　…，Ｓ０）　输出：　Ｄ．　１．Ｄ　＝Ｏ．Ｄ２＝Ｄ　２．　３．　４．　５．　Ｆｏｒｆ＝ｌ－ｌ　ｄｏｗｎｔｏ　０　ｄｏ　ＩｆＳｉ＝Ｏ　ｔｈｅｎ　ＤＩ：２Ｄ１，Ｄ２＝Ｄｌ＋Ｄ２　Ｅｌｓｅ　Ｄ１：Ｄ１＋Ｄ２，Ｄ２＝２Ｄ２　ＲｅｔｕｒｎＤ１　可以看到，算法２中的加法运算是特殊的加法，其中的变量总是满足Ｄ２－Ｄｌ＿Ｄ，且Ｄ是固定、己知的．在椭圆　曲线密码体制中也有类似的性质，人们利用这一点设计出了高效的点运算公式　，　．２０１０年的密码年会上，　Ｂｅｒｎｓｔｅｉｎ等人　使用Ｍｏｎｔｇｏｍｅｙ阶梯算法，ｒ在一般的ｂｉｎａｒｙ　Ｅｄｗａｒｄｓ曲线上实现了较快的椭圆曲线标量乘计　算．上述ｂｉｎａｒｙ　Ｅｄｗａｒｓ曲线其实是Ｂｅｒｎｓｔｅｉｎ等人仿照大素数域上的Ｅｄｗａｒｄｓ曲线设计出来的，但是二元域上所　有的椭圆曲线方程都可以有理变换成为ｂｉｎａｒｙ　Ｅｄｗａｒｄｓ曲线的形式．　在超椭圆曲线上如何应用Ｍｏｎｔｇｏｍｅｒｙ阶梯算法，也是人们长久以来不断考虑的问题．Ｌａｎｇｅ［９】设计适用于　Ｍｏｎｔｇｏｍｅｒｙ标量乘算法的快速除子类加法公式，但是没有得到最终的公式．在文献［２１ｑ￣，Ｌａｎｇｅ从另外一个角　度，仿照椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ形式，设计出一种特殊的超椭圆曲线的Ｍｏｎｔｇｏｍｅｒｙ形式．而后，她利用　Ｋｕｍｍｅｒ　ＳＵｒｆａｃｅ设计出较为高效的除子类运算公式．但是只有某类超椭圆曲线可以等价变换到这种特殊的　Ｍｏｎｔｇｏｍｅｒｙ形式，并且算法的空间复杂性较大．在计算中，还需要额外的预计算和预存储，进行坐标表示的转换．　我们在下一节介绍设计出的新的超椭圆曲线上的快速加法公式．新的技术适用于普通的超椭圆曲线，特别　是在特征为２的域上，可以明显提高公式的运算效率．　１．３域　上的同态曲线　根据文献［２］中的描述，在特征为偶数的域上，超椭圆曲线中的Ａｘ）￣Ｄ　）就定义在　可分为如下３类：　Ｉ．ＩＩ．ＩＩＩ．ｄｅｇ　＝２：　ｄｅｇ　＝１：　ｄｅｇ　ｈ＝０．　上，这样的超椭圆曲线　对于所有形如类型１的曲线，均可以变换成如下两种形式：　李明等：超椭圆曲线上Ｍｏｎｔｇｏｍｅｒｙ标量乘的快速计算公式　２２７９　Ｉａ．　ｙ２＋　＋ｈ　ｌｘ＋ｔ　）ｙ：　＋　＋ｆｌｘ＋ｆｏ；　Ｉｂ．　ｙ２＋ｘ（ｘ＋ｈＯｙ＝ｘ　＋　￣ｘ＋ｆｏ．　其中，　∈Ｆ２，ｔ表示一个ｔｒａｃｅ为Ｉ的元素（当　为奇数时，户１）．　对于类型ＩＩ，曲线均可以有理变换为如下两种形式：　。　ｙ　＋　＋尉　＋　，ｎ为奇数时；　＋　ｌ　＋ｇｘ　＋　砰　ｌ，ｎ为偶数时．　类型ＩＩＩ中的曲线是超奇异的，在Ｆｒｅｙ．Ｒｕｃｋ攻击下其安全强度会有所降低，所以不能直接用来构建基于离　散对数的超椭圆曲线密码体制．但是，这种曲线可以用来构建基于双线性对的密码体制．所以，设计这种曲线上　的快速加法公式依然具有重要意义．　我们在下一节针对不同的情况，设计快速的加法公式．本文主要是对类型ＩＩ和类型ＩＩＩ推导快速加法公式．　为了方便起见，在下一节中始终假设　２＝Ｏ．由于通过等价变化，所有的超椭圆曲线都可以变换到　２＝Ｏ，１的形式，　所以类型ＩＩ和类型ＩＩＩ的曲线可以占总曲线数目的一半．而为了更方便地得到阶很大的Ｊａｃｏｂｉａｎ［　．通常选取　域　，其中，ｄ为奇数，而这种情况也是我们着重研究的对象．此外，下一节中的代数变换技术在ｈ２＝ｌ时也是适　用的，只是在这里不再专门对这种情况进行优化了．　２新的运算公式　２．１设计快速加法公式　由于－（ｕｌ，Ｖ１）＝一（“１，－ｈ－ｖｌ　ｍｏｄ　ｕ１）且　２　｛Ｏ，１｝，所以当ｈ的次数为２时，我们有　－（ｕｌ，　１）＝一（“１，－ｈ－ｖｌ＋ｕ１）；　而当ｈ的次数小于２时，就有　－（ｕｌ，ｖ０＝－（２／１，－ｈ－Ｖ１）．　我们先来讨论最为通用的加法公式，这时ｈ为２次多项式．　对于Ｄ＝＝Ｄ２—Ｄ１＝一（　ｌ，Ｖ１）＋（甜２，　２）＝（甜１，一　一ｖ１）＋（　２，ｖ２）：　・ｋ＝（ｆ－ｖ２ｈ一　）／ｕ２，　Ｅ（一ｈ—Ｖ１一Ｙ２）／Ｕ２　ｍｏｄ／ｄＩ，ｌ＝ｓｕ２，ｕ＝（ｋ－ｓ（１＋ｈ＋２１，＇２））／２／１；　・　Ｕ　ｍａｄｅ　ｍｏｎｉｃ，ｖ，＝－ｈ一（『＋　２）ｍｏｄ　．　可以得到Ｕｌｕ＝ｋ－ｓ（１＋ｈ＋２ｖ２）．　我们需要计算Ｄ３＝Ｄ２＋Ｄ１＝（“ｌ，ｖ１）＋（“２，ｖ２）：　・ｋ３＝（ｆ－ｖ２ｈ一　）／ｕ２，　３ｉ（Ｖ１一Ｖ２）／Ｕ２　ｍｏｄ／２１，１３＝￥３Ｕ２，Ｕ３＝（ｋ－ｓ３（１３＋ｈ＋２ｖ２））／Ｕｌ；　・　Ｕ；＝“ｍａｄｅ　ｍｏｎｉｃ，　＝一ｈ一（，３＋Ｖ２）ｍｏｄ“；．　可以得到／２１　３＝ｋ３　３（ｆ３＋ｈ＋２ｖ２）．　由于有　如，所以，　２／１（２／一／２３）＝ｓ３（１３＋ｈ＋２ｖ２）－ｓ（１＋ｈ＋２ｖ２）＝ｓ３１３－ｓｌ＋（ｈ＋２ｖ２）（ｓ３－ｓ）＝（ｓ３—　）（　３＋　）　２＋ｈ＋２ｖ２）　因为　３　＝（一ｈ一２ｖ２　ｅ２　ｍｏｄ”１，ＳｍＳ３＝（一ｈ一２ｖ１　ｅ２　ｍｏｄ　Ｕｌ，所以有，　ｕｔ（ｕ—ｕ３）：（ｓ３一　）（（（一矗一２　２）　２＋ｆ“１）“２＋．ｉｌ＋２ｖ２），　其中，ｊ＝一ｈ２ｅ２１ｘ＋ｅ２ｌ（　２　ｌ１一ｈ１—２ｖ２１）一ｈ２ｅ２ｏ．　于是．　ｕｆｆｕ一“３）＝（　３一　）（（一ｈ－２ｖ２）ｅ２ｕ２＋ｉ２／１ｕ２＋ｈ＋２ｖ２）．　因为ｅ２２／２＝１一ｅ１２／ｌ，所以，　ｕｌ（ｕ—ｕ３）　（ｓ３－ｓ）（（ｈ＋２ｖ２）ｅｌｕｌ＋ｉｕｌｕ２）．　最后可得：　一甜３＝（　３一　）（（　＋２　２）８１＋ｆ　２）．　２２８０　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．１０，Ｏｃｔｏｂｅｒ　２０１３　因为ｄｅｇ（（ｈ＋２ｖ２）ｅ１＋ｉｕ２）＝１，所以，　（ｈ＋２ｖ２）ｅｌ＋ｉｕ２＝（　＋２ｖ２）Ｐ１　ｍｏｄ　Ｕ２．　这样，ｕ－ｕ３＝（（－ｈ－２ｖ１）ｅ２　ｍｏｄ　Ｕ１）（（　＋２　２）　１　ｍｏｄ　Ｕ２）．　我们现在来推导其在仿射坐标系下的导出公式以求出Ｄ　：　・首先，计算ｅ２ｍｏｄ　１和ｅｌ　ｍｏｄ／，／２１计算Ｕｌ和Ｕ２的ｒｅｓｕｌｔａｎｔ，和ｒｅ２，ｒｅ１：　・　ｌ　”Ｉ１一ｕ２１，２２　ｕ２０一ＵｌＯ，Ｚ３　Ｕｌ１Ｚ１－｝＇－Ｚ２；　・ｔｅｌ１　－ｚ１，ｒｅｌｏ＝Ｌ／２１（Ｕ２１一Ｕｌ１）＋Ｕｌｏ—Ｕ２０，ｒｅ２１＝２１，ｒｅ２ｏ＝Ｚ３．　・其次，我们来计算ｓｔ＝　和Ｓ：＝ｒｓ　．　・　然后，我们计算Ｃｌ：ｃ１１Ｘ＋Ｃ１０＝　＋Ｓ　和Ｃ２＝ｃ２１ｘ＋ｃ２ｏ＝　ｒ＿Ｓ；：　１．　注意到ｒ（ｓ＋ｓ３）＝（一ｈ一２ｖ２）ｒｅ２　ｍｏｄ　Ｕｂ而我们想要求ｒ（ａｘ＋ｂ）＝（ｈ＋２ｖ２）ｒｅｌ　ｍｏｄ　Ｕ２．这两个等式分别可　以写为一ｒ（ｓ＋ｓ３）＝（　＋２ｖ２）ｒｅ２＋ｉｕ１和ｒ（ａｘ＋ｂ）＝（ｈ＋２ｖ２）ｒｅｌ＋ｊｕ２．其中，　ｆ＝　２Ｐ２１　＋　２已２０＋已２１（　１一ｈ２ｕｌｌ＋２ｖ２１），ｊ＝ｈ２ｅ１ｌｘ＋ｈ２ｅｌｏ＋ｅｎ（ｈ１一ｈ２Ｕ２ｌ＋２ｖ２１）．　２．　两个等式的等号两边分别乘以Ｕｚ和”　，可以得到：　－ｒ（ｓ＋ｓ３）ｕ２＝（ｈ＋２ｖ２）ｒｅ２ｕ２＋ｉｕｌＵ２，ｒ（ａｘ＋ｂ）ｕｌ＝（ｈ＋２ｖ２）ｒｅｌＵｌ＋ｊｕ２Ｕ１．　＋　３）“２）　ｌ＿　因为ｅｌｕｌ＋ｅ２ｕ２＝ｌ并且ｉ＋ｊ＝０，所以两个等式相加可以得到ｒ（ａｘ＋ｂ）ｕ厂ｒ（ｓ＋ｓ３）“２＝（　＋２ｖ２　ｒ．　于是有ｒ（ａｘ＋ｂ）ｕ１＝（　＋２ｖ２）ｒ＋ｒ　＋　３）“２，也即ｒ（　＋６）＝（（　＋２ｖ２）　可以得至０　ｒａ＝ｃｌｌ，ｒｂ＝ｈ２＋ｃ１ｏ＋口（　２１－Ｕ１１）．　・最后，我们计算Ｕ　（ｃ　。　＋Ｃ２。）（　＋ｂ＋　Ｕ　）／　．由于上面等式的参数中均有　这个因子，所以最后除　以　的时候就约掉了．具体运算公式见算法３．至于　的计算，与算法１中的一样．　算法３．通用的加法公式　Ｉｎｐｕｔ　Ｓｔｅｐ　１　１　，ｖ］，［“１，ｖ１］，［　２，Ｖ２］，其中，　，　］＝［“２，ｖ２卜［“１，ｖ１］，“ｆ　＋蜥１ｘ＋ｕ　Ｐｉ＝ｖ“肘ｖ　０；　Ｅｘｐｒｅｓｓｉｏｎ　Ｃｏｍｐｕｔｅ　ｅｌ＝ｒ／Ｕｌ　ｍｏｄ　Ｕ２　ａｎｄ　ｅ２＝ｒ／ｕ２　ｍｏｄ／２１：　ｚ１　“２ｌ一１１１１，Ｚ２　／＇／１０—１１２０￣Ｚ３　ｚ　；　ｅ２１一　，　０＝　１１ｅ２１一ｚ２，ｅｌ１＝ｚ１，　１Ｏ　３一ｅ２０；　Ｏｕｔｐｕｔ　［“；，　】＝［ｕｌ，Ｖ１］＋［Ｕ２，ｖ２］．　Ｏｐｅｒａｔｉｏｎｓ　３Ｍ＋ｌＳ　ｒ＝ｚ２ｅｌｏ＋ｚ３１１２ｏ；　２　Ｃｏｍｐｕｔｅ　Ｓ，＿ｒｓ３　（ｖｌ—ｖ２）ｅ２　ｍｏｄ　ＵＩ：　Ｗ０＝ｅ２１（Ｖｌｌ—Ｙ２１），Ｗ１　ｅ２ｏ（ｖｌ０一ｖｚ０），Ｗ２＝（Ｖｌｌ—Ｖ２１＋Ｙ１０一ｖ２ｏ）（ｅ２１＋ｅ２ｏ），ｗ３＝ｗ２一Ｗｏ—ｗ１；　５Ｍ　；ｌ＝ｗｓ—ＷｏＵ１１，　ｏ＝　一　ｌ０ｗｏ；　３　Ｃｏｍｐｕｔｅ　ｓ￣＝ｒｓ＝ｒ—ｈ—Ｖｌ—ｖ２）ｅ２　ｍｏｄ　１１１：　Ｗｏ＝ｅ２１（一ｈ】一Ｖ１１一Ｖ２１），　１＝　２０（（一ｈ０－Ｖｌ０一Ｖ２ｏ），　Ｗ２＝（一＾ｌ—ｖ１１—１２２，一ｈ０一ＶｌＯ—ｖ２ｏ）（ｅ２１＋ｅ２ｏ），ｗ３＝ｗ２一ｗ０一ｗｉ；　ｓ　：ｗ３一　１，ｓ　＝　一Ｕ１０Ｗｏ；　５Ｍ　ｅ１：ｃＩｌ　＋ｃ１０＝ｓ　＋　；，ｃ２＝ｃ２ｌ　＋Ｃ２０＝Ｓ　一　；　４　Ｃｏｍｐｕｔｅ　１／ｒ　ａｎｄ　ｌ／ｓ，：　１Ｉ＋３Ｍ＋１Ｓ　ｗｏ＝（　）～，　＝ｗｏｒ，　＝　，ｗ２＝ＷｏＳ　；　５　Ｃｏｍｐｕｔｅ　；＝（（ｃ２ｌＸ＋Ｃ２０）（ｃｌｌ　＋ｃｌ０＋ｃｌ１（　２ｌ一１２１１））＋　）／　＝　＋　；１　＋　０：　Ｗ４￣Ｃ１，Ｃ２，，’　５＝ｃ２ｏ（ｃ１０＋ｃｌ１（　２１一“ｌ１）），ｗ６＝（（ｃ２１＋ｃ２ｏ）（ｃＩｌ＋ｃ１０＋ｃＩｌ（”２ｌ一“ｌ１）），　８Ｍ　“　：（　一ｗ４一ｗ５＋　“　）　；　“；０＝（　＋　１２“０ｆ　Ｊ　，．　６　Ｃｏｍｐｕｔｅ如　Ｓ；／ｒ：　Ｓ３１＝　；１ｗ２，Ｓ３ｏ　ｏＷ２；　２Ｍ　７　Ｃｏｍｐｕｔｅ　兰一ｈ一（　Ｕ２＋Ｖ２）ｍｏｄ　；＝　ｌ　＋　０：　Ｗ，￣Ｓ３１（１１２１一　３１），Ｗ２￣Ｓ３０（Ｕ２０一Ｕ３ｏ），Ｗ３＝（　３ｌ＋　３０）（“２１一／１３，＋１１２０一Ｕ３０）；　ｏ＝一　一　一Ｖ２０，　１＝一ｗ３一Ｖ２ｌ一　；　５Ｍ　Ｔｏｔａｌ　１Ｉ十２Ｓ＋３１Ｍ　李明等：超椭圆曲线上Ｍｏｎｔｇｏｍｅｒｙ标量乘的快速计算公式　２２８ｌ　上面的推导都是等价的代数变换，所以推导过程也就是算法３的正确性证明，于是我们得到如下定理：　定理１．算法３的输出结果与算法１是相同的．　注意到，当Ｓ＝Ｓ。时，我们仍然将其作为特殊情况，如算法１所示进行处理，所以我们就不再将其包括在算法３　中了．特殊情况出现的概率很低，一次标量乘计算中平均最多出现一次特殊情况；且如果出现了，按照已有的公　式可以很高效地进行计算．所以本文中设计其他算法时也这样处理，只讨论普通情况下的算法公式．　与算法１相比，算法３不足够快，但在特征为２的域上，我们可以改进其中某几步运算来推导除子类的快速　加法公式，这是原有的算法１所不具有的特点．我们首先给出类型ＩＩ的曲线上的加法运算公式．为了方便寻　找合适阶的群，我们都是在域Ｆ　（　为奇数）上建立密码体制，所以只考虑这种域上的公式即可．　在这种情况下，算法３的第３步中有ｃｌ＝ｃ２＝ｃｌｌｘ＋ｃｌｏ＝　＋Ｓ　（　１ｏ＋“２ｏ　＋”１０（　１ｌ＋“２１），　而第５±　有Ｕ　＝（（ｃｌ＋Ｃ１ｌ（／１１ｌ一／＇／２１））ｃ２—１／）／ｓ；　＝（（（　１０＋　２０）　＋　ｌ０（　１ｌ＋Ｕ２１））（（ｚ，１ｏ＋　２０）　＋　２０（　１ｌ＋　２１））＋　）／　．　因为Ｕ　＋１／　ａｘ＋ｂ，可以得到：　科　＝（（／１１ｏ＋１／２０）　ｘ　＋（１ｆ１ｏ＋１／２０）　（／１１１＋１／２１）ｘ＋ｌｌ１０“２０（“１ｌ＋“２１）　）＋（　ｏ＋Ｕ２ｏ）　“）／　＋“　．　也就是说，我们可以先计算　；＋　＝（ａｘ＋ｂ）ｌｓ；　，然后计算”　（ａｘ＋ｂ）／ｓ；　＋Ｕ　　．综上所述，我们有Ｕ３　ｌ：（　１ｏ＋ｚｆ２０）　（　ｌ１＋　２Ｉ＋　１）　＋Ｕ１，　＝（ＵｌＯ　２０（　ｌ１＋　２１）　＋（甜１０＋　２０）　）　＋　．　具体计算过程见算法４．　算法４．在域　上的Ｍｏｎｔｇｏｍｅｒｙ阶梯加法公式（类型ＩＩ，月为奇数）　Ｉｎｐｕｔ　［　，ｖ］，［　ｌ，　ｌ】，［“２，　】，其中，　，ｖｒＪ：一［　ｌ，ｖｌ】＋［“２，ｖ２］，ＩＡｉ＝Ｘ２＋￣ｌｆ１ｘ＋ｕ　Ｖｉ＝ｖｌ１ｘ＋ｖｌ０；　Ｏｕｔｐｕｔ　，　】＝［ｕｌ，ｖｄ＋［ｕ２，ｖ２］．　Ｓｔｅｐ　Ｅｘｐｒｅｓｓｉｏｎ　Ｏｐｅｒａｔｉｏｎｓ　１　Ｃｏｍｐｕｔｅ　ｅｌ　ｒ／ｕｉ　ｍｏｄ　Ｕ２　ａｎｄ　ｅ２＝ｒ／ｕ２　ｍｏｄ／／１：　ＺＩ。＝Ｕ２ｌ＋２／１１，Ｚ２　ｌ／ｌＯ＋Ｕ２０，ｚ３　ｚ　，３Ｍ＋２Ｓ　ｚ４＝ｚ；，ｚ５＝ｚ３ｕｌｏ；　５Ｍ　８２１　２ｌ，ｅ２０＝Ｕｌｉｅ２１＋Ｚ２，ｅｌ１　ｚ１，ｅｌｏ＝Ｚ３＋ｅ２ｏ；　ｒ＝ｚ２ｅ２￣＋ｇ５；　２　Ｃｏｍｐｕｔｅ　（Ｖｌ＋Ｖ２）ｅ２　ｍｏｄ“１：　ＷＯ＝ｅ２１（１；１１＋ｖ２１），ＷＩ＝ｅ２０（ｖｌＯ＋Ｖ２０），ｗ２＝（ｖ１１＋Ｖ２１＋Ｖｌｏ＋Ｖ２０）（ｅ２１＋ｅ２０），ｗ３＝ｗ２＋　０＋ｗ１；　；ｌ＝　＋ｗｏｕｌ１’　０：　＋ＭｌＯＷｏ；　３　Ｃｏｍｐｕｔｅ　Ｗ２　１／ｒ　ａｎｄ　＝１／ｓ；　：　１Ｉ＋３Ｍ＋１Ｓ　Ｗｏ＝（　；１），ｗｔ＝ｗｏｒ，ｗｌ＝嵋，ｗ２＝Ｗｏ４１；　４　Ｃｏｍｐｕｔｅ　；：（（ｃ１＋（　１＋　１）（　１＋“２１））ｃ２＋　）／　：　ｌ＝Ｚ４（￣／１ｌ＋　２１＋　）　＋“　；　“　ｏ＝（／／２０ｚ５＋Ｚ４Ｕｔｏ）Ｗｌ＋Ｕｏ；　５Ｍ　５　６　Ｃｏｍｐｕｔｅ　Ｓ３＝Ｓ；／ｒ：　Ｓ３ｉ＝　１ｗ２，Ｓ３０＝　；０Ｗ２；　Ｃｏｍｐｕｔｅ　三ｈ＋（　３　２＋ｖ２）ｍｏｄ　；＝　ｌ　＋　０：　２Ｍ　５Ｍ　＝￥３１（　２ｌ＋　；１），ｗ　＝ｓ３０（　２０＋　０），ｗ３＝（ｓ３１＋　３０）（“２１十Ⅳ　ｌ＋　２０＋　；ｏ）；　ｏ＝ｗ２＋　ｏ＋Ｖ２０，嵋ｌ＝ｗ３＋　＋ｗ２＋Ｖ２ｌ＋Ⅵ“　１＋１；　Ｔｏｔａｌ　ｌＩ＋３Ｓ＋２３Ｍ　当在域Ｆ　为偶数数）上进行计算时，有ｈ＝ｈｌ　，这时，ｃ１＝ｃ２＝ｃ１１Ｘ＋Ｃｌ０＝　＋　１　（（　１ｏ＋Ｕ２０　＋“１０（　１１＋　２１））．　于是，我们只需将第３步中Ｗｌ的运算变为　＝砰ｗ０２即可保证算法正确．同时，将第６步中　．的计算变为　。＝ｗ３＋ｖ２ｌ＋　１．当我们选取的ｈｌ是非零比特非常稀疏的随机数时，有关的ｈ１计算是可以忽略不计的．这样，算　法的运算量依然是ｌｉ＋３Ｓ＋２３Ｍ．　当ｈ＝ｈ０时，超椭圆曲线的形式为类型ＩＩＩ，这时也有高效的公式，见算法５．注意到，我们也选取ｈ０是稀疏的二　进制数．　２２８２　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．１０，Ｏｃｔｏｂｅｒ　２０１３　算法５．在域Ｆ　上的Ｍｏｎｔｇｏｍｅｒｙ阶梯加法公式（类型ＩＩＩ）　Ｉｎｐｕｔ　Ｓｔｅｐ　【“，ｖ】，［　ｂｖ１］，［　２，ｖ２］，其中，［“，ｖ］＝一［”Ｉ，ｖ１］＋［“２，ｖ２］，／／ｉ＝Ｘ２＋“儿ｘ＋ｕ　０，Ｖｉ＝ｖ】１Ｘ＋Ｖｆｏ；　Ｅｘｐｒｅｓｓｉｏｎ　Ｏｐｅｒａｔｉｏｎｓ　Ｏｕｔｐｕｔ　［“；，　］＝［／ｌ，ｖｄ＋［ｕ２，ｖ２］．　１　Ｃｏｍｐｕｔｅ　ｅｌ＝ｒ／ｕｌ　ｍｏｄ　ｌ／２　ａｎｄ　ｅ２＝ｒ／ｕ２　ｍｏｄ／４１：　３Ｍ＋１Ｓ　Ｚ１　／／２１＋Ｕｌｌ，Ｚ２＝／／１０＋Ｕ２０，ｚ３＝ｚ　ｚ４＝ｚ；；　Ｐ２Ｉ　＿２ｌ，ｅ２ｏ＝ｕｌｌｅ２１＋ｚ２，ｅｌｌ　Ｉｚ｝，ｅｌ０＝ｚ３＋ｅ２ｏ；　ｒ＇＝ｚ２ｅｌｏ＋Ｚ３／／２０：　２　Ｃｏｍｐｕｔｅ　ｓ　（Ｖｌ＋Ｖ２）ｅ２　ｍｏｄ　ＵＩ：　ＷＯ＝ｅ２１（Ｖｌｌ＋Ｖ２１），Ｗ１＝ｅ２ｏ（Ｖｌｏ＋ｖ２ｏ），Ｗ２＝（ＶＩｌ＋Ｖ２１＋ｖｌＯ＋ｖＺｏ）（ｅ２１＋ｅ２ｏ），Ｗ３＝Ｗ２＋Ｗｏ＋ＷＩ；　５Ｍ　１＝ｗ３＋ｗｏｕｌ１，　；０＝Ｗｌ＋“１０Ｗｏ；　３　Ｃｏｍｐｕｔｅ　ｗ２＝ｌ／ｒ　ａｎｄ　＝ｈ／Ｓ；　：　ｏｌＩ＋３Ｍ＋１Ｓ　５Ｍ　Ｗｏ＝（　；１）～，　＝ｗｏｒ，　：　，ｗ２＝　；ｌ；　４　Ｃｏｍｐｕｔｅ　＝（（ｃ【＋（邑Ｉ＋　）　ＩＩ一　１））ｃ２一ｕ）／ｓ；　：　“；ｌ＝Ｚ３（　ｌ＋“２１＋“　）　＋“　；　“；０：（ｅｌｏｅ２０＋（Ｕ１１＋Ｕ２１）　）　＋　；　５　Ｃｏｍｐｕｔｅ　ｓ３＝　／ｒ：　２Ｍ　１＝　；１ＷＥ，Ｓ３０：　；ｏＷ２；　６　Ｃｏｍｐｕｔｅ　ｖ　三－ｈ一（Ｓ３Ｕ２＋Ｖ２）ｍｏｄ　＝ｑｘ＋Ｖ＇ｏ：　ＷＩ＝Ｓ３１（／２１ｑ－／３１），Ｗ２＝Ｓ３０（Ｕ２０＋Ｕ３０），Ｗ３＝（曲ｌ＋　３ｏ）（“２１＋　３１＋　２０＋　３０）；　５Ｍ　嵋０＝ＷＥ＋　＋ｈ０，嵋１＝ｗ３＋Ｖ２ｌ；　Ｔｏｔａｌ　ｌＩ＋２Ｓ＋２３Ｍ　２．２在投影坐标系上的加法公式　求逆运算是以上公式中最为耗时的运算，且一般情况下是普通乘法运算的８倍（大素数域）或者１５倍（特征　为２的域）【　．在椭圆曲线和超椭圆曲线密码体制中，我们为了避免求逆运算，经常采用一些特殊的坐标系，如投影　坐标系、Ｊａｃｏｂｉａｎ坐标系、ＬＤ坐标系等等［６］．在超椭圆曲线密码体制上，出现的可以避免求逆运算的坐标系有　投影坐标系和Ｌａｎｇｅ提出的Ｎ坐标系、Ｒ坐标系．我们在本节设计算法４和算法５在投影坐标系下的公式．　算法６的正确性也很好验证，只要满足　／　：“３和　／Ｚ３＝ｖ３即可．注意到算法中的Ｄ是仿射坐标系下的，也　就说有Ｚ＝Ｉ，且在计算过程中Ｄ的值一直未变．以下定理就是算法６的正确性证明．　定理２．算法６的输出结果正是算法４输出的除子类的投影坐标系上的形式．　证明：我们需要验证Ｕ３／２３＝Ｕ；和　／Ｚ３＝　，其中，　，　和Ｚ３是算法６的输出，而Ｕ　和　是算法４的输出．首　先验证Ｕ３１／ｚ３＝　和　０／ｚ３＝ｕ３０　．由于算法６与算法４中的ｅ２１相比满足ｅ２ｌ／ＺｌＺ２＝“２１＋“　则称算法６中的ｅ２１与　算法４中的ｅ２ｌ相比包含有因子ｚ１ｚ２．我们可以依次确定ｅ２ｏ，ｒ和ｓ３ｌ的因子分别为ｚ？ｚ２，ｚ　ｚ；和ｚ　３　２２．ｓ３ｏ中包含　的因子与ｓ３１相等．算法６第４步中求出Ｚ３＝Ｚ；Ｒ．下面来验证　和　的值（ｆ＝０，１），只需将每步的变量逐步代入　即可：　・　・　１／ｚ３＝（　３＋　（ｚ　十　３Ｒ２））／ｚ；＝ｚ４Ｒｌ（ｚ１＋　２）／ｚ　＋　＝（甜１０＋Ｕ２０）　（　１ｌ＋　２ｌ＋　）／　；１＋“　：　；ｌ；　０／Ｚ３＝（Ｕ２０ｚ５Ｒ２＋（Ｒ３＋　）　）：（Ｕ２０ｚ５＋　ｏＩ　Ｊ，　２１＋　＝Ｕ３　０．　和　ｏ中的每一项进行处理：　分别对　・　首先看　。／Ｚ３＝（（　。ｗＯ／（ｓ　Ｚ３））　＝Ｓ３１（“：。＋“；　）　；。，其中，等式最右边是算法４的第６步里的一项；　・　Ｉ司样，（ｗ２＋Ｒ　Ｖ２ｏ）／Ｚ３＝ｗ２＋ｖ２ｏ．　这样，我们验证完每～项后，可以得到　＝ｖ３ｌ／Ｚ３和ｖ３。　＝　０／Ｚ３．　综上，定理２得证．　个乘法．　口　Ｌａｎｇｅ提出的在投影坐标系上的　上的加法公式为　４９Ｍ＋４Ｓ．这样，我们的公式就比之前的公式少用了４　李明等：超椭圆曲线上Ｍｏｎｔｇｏｍｅｒｙ标量乘的快速计算公式　２２８３　算法６．在投影坐标系上的Ｍｏｎｔｇｏｍｅｒｙ阶梯加法公式（类型ＩＩ，ｎ为奇数）　Ｉｎｐｕｔ　Ｏｕｔｐｕｔ　Ｓｔｅｐ　１　ＤＩ＝［ＵＨ，Ｕｌｏ，Ｖ１１，ＶＩｏ，ｚｄ，Ｄ２＝［　１，　０，　ｌ，ｇ２ｏ，２］，Ｄ　Ｄ２一Ｄｌ＝［　，【，０，　，　，ｚ】；　Ｄ３＝　ｌ＋Ｄ２．　Ｅｘｐｒｅｓｓｉｏｎ　Ｃｏｍｐｕｔｅ　ｅｌ＝ｒ／ｕｌ　ｍｏｄ　１／２　ａｎｄ　ｅ２　ｒ／ｕ２　ｍｏｄ　Ｕｌ：　Ｏｐｅｒａｔｉｏｎｓ　８Ｍ＋２Ｓ　ＺＩ＝ＵＩ１Ｚ２＋Ｕ２１ＺＩ，ｚ２＝Ｕ２ｏＺｌ＋Ｕｌｏ２，Ｚ３＝　，Ｚ４＝　２，ｚ５＝Ｚ３Ｕｌｏ；　ｅ２１＝ｚ１，ｅ２ｏ＝Ｕ１１ｚｌ＋ｚ２Ｚｔ；　ｒ＝ｚ２ｅ２ｏ＋Ｚ５；　２　Ｃｏｍｐｕｔｅ　３＝（ｖｔ＋ｖ２）ｅ２　ｍｏｄ“ｌ：　Ｗ０＝ｅ２１（　ｌ　Ｚ２＋　ｌｚ１），Ｗｌ＝ｅ２ｏ（　ｏＺ１＋Ｖ１ｏｚ２）；　（Ｖｌｌｚ２＋Ｖ２１Ｚｔ＋　０ｚ１＋　ｏＺ：！）（Ｚｔｅ２１＋ｅ２ｏ）；　＝１０Ｍ　￥３１＝ｗ２＋ｗｌ＋ｗｏ（Ｚ１＋ＵＩ１），￥３０＝Ｗｌ＋Ｕ１ｏＷｏ；　３　Ｃｏｍｐｕｔｅ　＝（（ｃ１＋（　１＋　１）（　ｌ＋　２１））ｃ２＋４ｕ）／４１：　Ｒ２　ＺＩＺ２，　＝　２Ｒｉ＝　，１２Ｍ＋２Ｓ　，ＲＩ＝Ｒ１Ｒ２，Ｒ３＝ｚ４Ｒｔ；　Ｒ　ＦＳ３１，Ｒ　Ｒ　Ｚ２，Ｒ　＝ｒｚ；；　Ｕ３１＝ｚｌＲ３＋ＵＩ（ｚ；＋Ｒ３Ｒ２），　Ｕ３ｏ　Ｕ２ｏｚｓＲｔ＋Ｕｏ（　＋Ｒ３Ｒ２）；　４　Ｃｏｍｐｕｔｅ　Ｖ３￣－ｈ＋（ｓ３ｕ２＋ｖ２）ｍｏｄ／１３　ｌ　＋　：　１３Ｍ　Ｗｌ＝Ｕ２】　＋　１ｚ２，ｗ２＝￥３０（ｕ２０Ｚ　＋Ｕ３０ｚ２），ｗ３＝（Ｓ３ｌ＋　３０）（　ｌ　＋　ｌＺ２＋　０　＋　ｏＺ２）；　Ｚ３　５　Ｔｂｔａｌ　Ｒ，１１３ｏ　（ｗ２＋Ｖ２ｏＲ　）Ｓ３１＋ＷＩ　Ｕ３ｏ，　１　（ｗ３＋ｗＩ＋Ｗ２＋Ｖ２１Ｒ　）Ｓ３１＋ＷＩ　Ｕ３１＋Ｚ３；　２Ｍ　４Ｓ＋４５Ｍ　Ａｄｊｕｓｔ：　Ｕ３１＝Ｕ３１Ｒ，Ｕ３０＝Ｕ３ｏＲ；　此外，对于类型ＩＩＩ的曲线上的加法运算公式，其在投影坐标系下的算法形式列在算法７中．这个公式的计算　量也比Ｌａｎｇｅ给出的公式少用了１个乘法．由于算法７与算法６在大多数步骤中是相同的，因此只需验证第３　步中Ｕ３ｏ＝　∞ｔ即可验证算法的正确性．　算法７．在投影坐标系上的Ｍｏｎｔｇｏｍｅｒｙ阶梯加法公式（类型ＩＩＩ）　Ｉｎｐｕｔ　Ｏｕｔｐｕｔ　Ｄ１＝［Ｕｌ１，Ｕｌｏ，Ｖ１１，Ｖｌ０，ｚｄ，Ｄ２＝［【，２１，Ｕ２ｏ，　１，　０，　】，Ｄ＝Ｄ２一Ｄｌ＝［Ｕ１，Ｕｏ，　，Ｖｏ，ｚ】；　Ｄｓ＝ＤＩ＋Ｄ２．　Ｓｔｅｐ　１　Ｅｘｐｒｅｓｓｉｏｎ　Ｃｏｍｐｕｔｅ　ｅｌ＝ｒ／ｕＩ　ｍｏｄ／１２　ａｎｄ　ｅ２　ｒ／ｕ２　ｍｏｄ／＇ｌｌ：　Ｏｐｅｒａｔｉｏｎｓ　１０Ｍ＋ｌＳ　ＺＩ。ＵＩｌ￣＋Ｕ２１Ｚｌ，Ｚ２　Ｕ２ｏＺ１＋Ｕ１ｏＺ２，ｚ３　ｚ　；　Ｐ２ｌ＿Ｚ１，ｅ２ｏ＝ＵＩ１ＺＩ＋Ｚ２ＺＩ，ｅ１１＝２：１，ｅｌ０＝Ｕ２１ＺＩ＋Ｚ２Ｚ２；　ｒ＝ｚ２ｅ２０＋ｚ３　ＵＩＯ；　２　Ｃｏｍｐｕｔｅ　Ｓ３＝（ｖｌ＋ｖ２）ｅ２　ｍｏｄ／１１：　Ｗ０　ｅ２１（　１Ｚ２＋　ＩＺ１），Ｗｌ＝ｅ２ｏ（　ｏＺｌ＋Ｖａｏ２２）；　Ｗ２　（Ｖ１ＩＺ２＋　１Ｚ１＋　ｏｚ１＋Ｖ１ｏＺ２）（ＺＩｅ２１＋ｅ２０）；　Ｓ３１＝Ｗｚ＋Ｗｌ＋ｗｏ（Ｚｌ＋ＵＩ１），Ｓ３０＝ＷＩ＋Ｕ１ｏＷｏ；　ｌＯＭ　３　Ｃｏｍｐｕｔｅ　；＝（（ｃｌ＋（　１＋Ｓ１）（ｇｇＩ１＋“２１））ｃ２＋４ｕ）ｌｄ，：　Ｒ２　Ｚ１２，　＝　２，ＲＩ＝Ｚｌ２，ＲＩ＝Ｒ１Ｒ２，Ｒｓ＝ｚ３Ｒ１；　Ｒ　ＦＳ３１，Ｒ　Ｒ　Ｚ２，Ｒ　＝ｒＺ；；　ｌ＝Ｒ３（Ｚｍ＋恐　）＋　，　０＝ｑ０ｅ２０Ｒ１＋　（　＋　）；　１３Ｍ＋２Ｓ　４　Ｃｏｍｐｕｔｅ　Ｖ３＝－ｈ＋（ｓｓＵ２＋Ｖ２）ｍｏｄ　ｌｄ３　ｌｚ＋　ｏ：　ｌ３Ｍ　＝Ｕ２ｌ　＋ｃ，３ｌＺ２，ｗ２＝￥３０（ｕ２０　＋　０ｚ２），ｗ３＝（ｓ３ｌ＋ｓ３０）（【，２ｌ　＋　ｌＺ２＋　０　＋　０Ｚ２）；　Ｚ３＝Ｚ；Ｒ，　Ｄ＝（ｗ２＋Ｖ２ｏＲ　）ｓ３１＋ｗ￣Ｕ３ｏ，　ｌ＝（ｗ３＋ｗ１＋ｗ２＋　１Ｒ　）ｓｓｌ＋ｗｉＵ３￣＋Ｚ３；　５　Ｔｏｔａｌ　Ａｄｊｕｓｔ：　Ｉ＝　１　，　０＝　ｏＲ；　２Ｍ　４Ｓ＋４８Ｍ　２．３在Ｎ坐标系下的加法公式　Ｌａｎｇｅ为了得到更高效的除子类运算公式，提出了Ｎ坐标系（ｎｅｗ　ｃｏｏｒｄｉｎａｔｅ）．在这种坐标系下，二倍运算和　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．１０，Ｏｃｔｏｂｅｒ　２０１３　加法运算的计算量变为３４Ｍ＋７Ｓ和４８Ｍ＋４Ｓ［　．Ｎ坐标系的形式为一个六元组［ｕｌ，Ｕｏ，　，Ｖｏ，Ｚｌ，Ｚ２】，其对应于仿射　坐标系下的坐标值为［Ｕｌ／ｚ？，　／　，　／（Ｚｌ３Ｚ　），Ｖｏ／（ｚ？ｚ　）］．当在特征为偶数的域上进行计算时，我们需要几个辅　助的变量来提高计算效率．这时，可将Ｎｅｗ坐标系上的一个点表示为［Ｕ１，Ｗｏ，ＶＩ，Ｚｏ，Ｚ１，ｚ２，Ｚ１，ｚ２，Ｚ３，Ｚ４］，其中，　ｚ　＝ｚ　，ｚ２＝ｚ　，Ｚ３＝Ｚ１ｚ　Ｚ４＝ＺＩＺ３．　当然，在下面的计算中可以看到，公式中并没有用到变量ｚ　和Ｚ２，所以我们在实际计算时可以将这两个变量　去掉以节省空间．而为了保证算法的清晰和可读，我们在本节的推导和分析中将这两个变量保留下来．算　法中的输入［　ｌ，　，　，　，１，１，１，ｌ】不发生改变，也就是说一直有　Ｕ　和　＝　（ｉ＝０，１）．　定理３．算法８的输出结果相对应的仿射坐标是算法４的输出．　证明：对于　３ｌ，Ｚ３　２，Ｚ３　３和　３４的正确性，在第４步的计算过程中已经表示了出来．下面只需验证有　“　。＝Ｕ３　／蜀，　＝Ｕｓ。／蜀，　＝　／（　。Ｚ３：）和　。＝　／（乏。Ｚ３：）即可，其中，“；　，“；。，Ｖ３　和　是算法４中的输出．我　们首先来确定几个中间变量中的因子．由于算法８中的　２１　１ｌＺ２ｌ＝“２ｌ＋“…则称为算法８中的ｅ２１与算法４中　的ｅ２ｌ相比包含有因子ｚｌｌｚ２１．我们可以依次确定ｅ２０，ｒ和妁１的因子分别为ｚ　ｚ２ｌ，ｚ１３ｌｚ２２ｌ和ｚ　ｚ２ｌｚ１４ｚ２４．Ｓ３０中包含的　因子与Ｓ３１是相等的．算法中求出Ｚ３ｌ＝　３１，ｚ３２＝　３Ｚ２　．下面来验证　和　的值（卢０，１）：　・　・　ｌ／ｚｓ１＝（Ｒ３Ｙ１＋（Ｒ３＋Ｚ３１）　）／ｚ３ｌ＝Ｙ４Ｒ２（Ｙｌ＋甜　）／ｚ３ｌ＋Ｕ　＝（　ｌ０＋Ｕ２０）　（ｚ，１１＋　２ｌ＋　１ｒＪ，　２１＋Ｕ　：ｚｆ；ｌ；　０／ｚｓｌ＝Ｕ２ｏＹｓＲ２＋（Ｒ３＋Ｚ３１）　＝（Ｕ１０ｚ５＋ｚ４　０ｔ　Ｊ，　２ｌ＋　＝ｚｆ；０．　分别对　】和　ｏ中的每一项进行处理：　・　首先来看　ｏ／ｚ３　＝（（　１Ｗ１）／（ｓ３ｌＺ３２））　＝￥３１（　２　＋　；。）“　，等式最右边是算法４中第６步里的一项；　・　Ｉ司样，（ｗ２＋Ｒ　Ｖ２ｏ）ｇ３ｌ＝Ｗ２＋Ｖ２０．　这样，我们验证完每一项后可以得到　＝　／（　Ｚ３２）和　＝　。／（ｚ３　Ｚ３：）．　综上，定理得证．　口　算法８．在Ｎ坐标系下的Ｍｏｎｔｇｏｍｅｒｙ阶梯加法公式（类型ＩＩ，ｎ为奇数）　Ｉｎｐｕｔ　Ｄｔ＝［Ｕ１ｌ，Ｕ１０，　１，Ｖ１０，Ｚｕ，Ｚ１２，Ｚｌｌ，ＺＩ２，Ｚ１３，ｚ１４］，Ｄ２＝［　１，Ｕ２ｏ，　Ｉ，ｇ２ｏ，Ｚ２１，Ｚ２２，Ｚ２ＤＺ２２￣２３，ｚ２４］，　Ｄ＝Ｄ２—Ｄ１＝［己＾，　，　，　，ｚ１，Ｚ２，ｚ１，　，ｚ３，ｚ４］；　Ｏｕｔｐｕｔ　Ｄｓ＝ＤＩ＋Ｄ２．　Ｓｔｅｐ　ｌ　Ｅｘｐｒｅｓｓｉｏｎ　Ｃｏｍｐｕｔｅ　ｅｌ　ｒ／ｕｌ　ｍｏｄ　Ｕ２　ａｎｄ　ｅ２　ｒ／ｕ２　ｍｏｄ／＇／１：　Ｏｐｅｒａｔｉｏｎｓ　８Ｍ＋２Ｓ　Ｙｌ　Ｕ２１ＺｌＩ＋ＵＩ１Ｚ２１，Ｙ２＝ＵＩＯＺ２１＋Ｕ２ｏｚＩ１，Ｙ３＝　，Ｙ４＝Ｙ；，ｙｓ＝ｙ３Ｕｌｏ；　ｅ２１＝ｙｔ，ｅ２０　Ｕｌｌｅ２１　２Ｚ１ｌ；　ｒ＝ｙ２ｅｌｏ　５；　２　Ｃｏｍｐｕｔｅ　（Ｖｌ＋Ｖ２）ｅ２　ｏｏｄ／ｒｄｌ：　ｌ０Ｍ　ＷＯ＝ｅ２１（　１Ｚ２４＋　１２１４），ＷＩ＝ｅ２ｏ（Ｖ１０Ｚ２４＋　０Ｚｔ４），Ｗ２＝（Ｖｊ１Ｚ２４＋　ＩＺＩ４＋Ｖ１０Ｚ２４＋　ｏｚｌ４）（ｅ２Ｉｚ１１＋８２０）；　￥３１￣ｗ２＋ｗＩ＋ｗｏ（ＵＩＩ＋ＺＩ１），　３０；ｗ１＋Ｕ１ｏＷｏ，　３　Ｃｏｍｐｕｔｅ　；＝（（ｃ１＋（　１＋　）（　ｌ１＋Ｕ２１））ｃ２＋Ⅳ　）／　：　Ｚ３１　￥３１，ｚ３ｌ＝　３２ｌ，９Ｍ＋２Ｓ　ＲＩ　Ｚ１１ｚ２１，Ｒ２＝Ｚ１４ｚ２３，Ｒ２＝Ｒ；，Ｒ２＝ＲＩＲ２，Ｒ３＝ｙ４Ｒ２；　Ｕｓｌ＝Ｒｓｙｌ＋（Ｒ３＋Ｚ３１）　；　Ｕｓ０＝Ｕ２ｏＹ５Ｒ２＋（Ｒｓ＋ｚ３Ｉ）Ｕｏ；　４　Ｃｏｍｐｕｔｅ　兰ｈ＋（Ｓ３Ｚ／２＋Ｖ２）ｍｏｄＵ；＝　１　＋　ｏ：　Ｒｔ　ｒｚｌ３，Ｚ３２＝ｚ２４Ｒｌ，Ｚ３２＝　，ｚ３３＝Ｚ３１Ｚ３２，ＲＩ＝ｚ３１Ｒ１，Ｚ３４＝Ｚ３１Ｚ３３；　１７Ｍ＋１Ｓ　Ｗ１＝Ｕ２１２３１＋Ｕ３１Ｚ２１，Ｗ２＝Ｓ３０（Ｕ２０Ｚ３１＋Ｕｓ０Ｚ２１），Ｗ３＝（ＳＳｌ＋ＳＳｏ）（ｕ２ｌＺ３１＋Ｕ３１２２１＋Ｕ２０Ｚ３１＋Ｕ３ｏＺ２１）；　ｏ＝（ｗ２＋Ｒ１　Ｖ２ｏ）Ｚｓｌ＋Ｗ１　Ｕｓｏ，　１＝（　３＋　２＋Ｒ１　１）Ｚ３Ｉ＋Ｗｌ（Ｕ３１＋Ｚ３１）－４－Ｚ３４；　Ｔｏｔａｌ　４Ｓ＋４４Ｍ　在Ｎ坐标系下，我们设计类型ＩＩＩ的曲线上的加法公式如算法９所示．算法９与算法８的区别在于第１步中　多计算了Ｐｌｌ和ｅｌｏ，且第３步中ｕ３０的计算发生了变化．由于有　ｏ＝（　０ｅ２ｏ＋（　１ｌ＋“２１）　Ｕｏ）Ｗ￣＋“　＝Ｕ３０　，而等号最　右边为算法５中的一项，所以算法９也是正确的，其输出变换为仿射坐标系后正是算法５的输出．　李明等：超椭圆曲线上Ｍｏｎｔｇｏｍｅｒｙ标量乘的快速计算公式　２２８５　算法９．在Ｎ坐标系下的Ｍｏｎｔｇｏｍｅｒｙ阶梯加法公式（类型ＩＩＩ，　为奇数）　Ｉｎｐｕｔ　Ｏｕｔｐｕｔ　Ｄ１＝【　１，Ｕｌｏ，　ｌ，Ｖｌｏ，Ｚ１，Ｚ１２，Ｚｎ，ｚｔ２，ｚｔ￣，ｚ１４］，Ｄ２＝【Ｕ２１，Ｕ２ｏ，　ｌ，　ｏ，ｚ２ｌ，Ｚ２２’ｚ２ｌ，ｚ２２　２３，ｚ２４】，　Ｄ＝Ｄ２一ＤＩ＝［【＾，Ｌ　，　，　，ｚ１，Ｚ２’ｚｌ，ｚ２，２３，ｚ４】；　Ｄ３＝ＤＩ＋Ｄ２．　Ｓｔｅｐ　１　Ｅｘｐｒｅｓｓｉｏｎ　Ｃｏｍｐｕｔｅ　ｅｌ　“１　ｍｏｄ　Ｕ２　ａｎｄ　ｅ２　ｒ／ｕ２　ｍｏｄ／／１：　Ｏｐｅｒａｔｉｏｎｓ　１０Ｍ＋２Ｓ　Ｙｌ＝Ｕ２１ｚＩＩ＋ＵＩｌＺ２１，Ｙ２　Ｕｉ０ｚ２１＋Ｖ２０Ｚｌ１，Ｙ３＝　，Ｙ４＝Ｙ；，Ｙ５＝Ｙ３Ｕ１０；　ｅ２１￣Ｙｌ，ｅ２ｏ　ＵＩｌｅ２１　２２１１，ｅｌＩ－Ｙ　ｚ，ｅｌｏ　Ｕ２ｌｅｌ１＋ｙ２２２１；　，一ｙ２ｅ１０　５；　２　Ｃｏｍｐｕｔｅ　（Ｖｌ＋Ｖ２）ｅ２　ｍｏｄ／／１：　１ＯＭ　ｗ０＝ｅ２１（　１ｚ２４＋Ｖ２ＩＺ１４），ＷＩ＝ｅ２ｏ（Ｖ１０２２４＋　ｏＺ１４），Ｗ２＝（Ｖ１１Ｚ２４＋　１２１４＋Ｖ１０２＂２４＋　ｌ４）（口２ｌｚ１Ｉ＋Ｐ２０）；　￥３１＝Ｗ２＋ＷＩ＋ＷＯ（ＵＩＩ＋Ｚｌ１）．￥３０＝Ｗｌ＋ＵｌｏＷｏ；　３　Ｃｏｍｐｕｔｅ　；＝（（ｃｌ＋（　ｌ＋　１）（　ｌｌ＋“２１））ｃ２＋　）／　：　Ｚ３１＝ｓ３１，ｚ３ｌ＝　２ＲＩ＝ＺＩｌＺ２１，Ｒ２＝Ｚ１４ｚ２３，Ｒ２＝　ｌ，，Ｒ２＝ＲＩＲ２，Ｒ３＝ｙ４Ｒ２；　ｌＯＭ＋２Ｓ　Ｕ３１＝Ｒ３Ｙｌ＋（Ｙ４Ｒ２＋ｚ３１）　；　０＝ｅＩｏｅ２ｏＲ２＋（乃　＋Ｚ３１）　；　４　Ｃｏｍｐｕｔｅ　三ｈ＋（　２＋１）２）ｍｏｄ“；＝　１　＋　０：　ＲＩ　ｒＺ１３，Ｚ３２　ｚｚ４Ｒｉ，Ｚ３２　，２３３＝２３１Ｚ３２，Ｒ１＝ｚ３１Ｒ１，２３４＝２３１２３３；　１７Ｍ＋ｌＳ　Ｗ１＝Ｕ２１Ｚ３１＋Ｕ３１Ｚ２１，Ｗ２＝Ｓ３０（Ｕ２ｏＺ３１＋Ｕ３ｏＺ２１），Ｗ３　３ｌ＋　３ｏ）（ｕ２１２３１＋Ｕ３ＩＺ２１＋Ｕ２０Ｚ３１＋Ｕ３０２２１）；　１３ｏ＝（ｗ２＋Ｒ１　ｏ）１３Ｉ＋Ｗｌ　Ｕ３ｏ，Ｖ３１＝（ｗ３＋ｗ２＋ＲＩ　１）Ｚ３Ｉ＋ＷＩ（ｕ３ｌ＋Ｚ３１）＋Ｚ３４；　Ｔｏｔａｌ　４Ｓ＋４７Ｍ　２．４在Ｒ坐标系下的加法公式　本文主要研究的是＾２＝０的情况，在文献［２］中，Ｌａｎｇｅ提出了一种Ｒ坐标系，我们称其为Ｒ坐标系，以加快这　种情况下的二倍运算；但同时，加法计算会大大变慢．由于二倍计算加快的速率比加法计算变慢的速率要高，所　以最后还是得到了一种较快的计算标量乘的方法．下面我们使用本文中提出的技术来改进Ｒ坐标系下的加法　计算．在Ｒ坐标系下，一个点的坐标可以表示为［　，　，　，　，ｚ，ｚ］，其相对应的仿射坐标系上的点为（　／Ｚ，　／Ｚ’　／ｚ，Ｖｏ／０，其中，Ｚ＝Ｚ２．具体的运算公式见算法１Ｏ和算法１１．　算法１０．在Ｒ坐标系下的加法公式（类型ＩＩ１　Ｉｎｐｕｔ　Ｏｕｔｐｕｔ　Ｓｔｅｐ　ｌ　Ｄｉ　Ｕ１１，Ｕ１０，　１，Ｖ１０，Ｚｂ２１］，ＤＥ＝［　１，　０，　１，Ｖ２ｏ，　Ｄ３＝ＤＩ＋Ｄ２．　Ｅｘｐｒｅｓｓｉｏｎ　Ｃｏｍｐｕｔｅ　ｅｌ＝ｒ／ｕ１　ｍｏｄ／／２　ａｎｄ　ｅ２＝ｒ／ｕ２　ｍｏｄ／ｄ１：　ｙｌ　Ｕ２１ＺＩ＋ＵｌｌＺ２，Ｙ２　ＵｌｏＺ２＋Ｕ２ｏＺ￣，Ｙ３＝　ｅ２１＝Ｙｌ，ｅ２ｏ　ＵＩＩｅ２１＋ｙ２Ｚ１；　ｒ＝Ｙ２ｅｌｏ　５；　，］，Ｄ＝Ｄ２－ＤＩ＝［ＵＩ，Ｕｏ，Ｖ１，Ｖｏ，ｚ，ｚ］；　Ｏｐｅｒａｔｉｏｎｓ　８Ｍ＋２Ｓ　，ｙｓ＝Ｙ３Ｕｌｏ；　Ｙ４＝　２　Ｃｏｍｐｕｔｅ　ｓ　（Ｖｌ＋ｖ２）ｅ２　ｍｏｄ／／１：　Ｗ０＝ｅ２１（Ｖｌ１Ｚ２＋Ｖ２ｌＺ１），Ｗ１＝ｅ２ｏ（Ｖ１０Ｚ２＋　０２１），Ｗ２＝（ＶｌｌＺ２＋　１ＺＩ＋　ｏＺ２＋　ｏｚ１）（Ｐ２１０１＋Ｐ２ｏ）；　ｓ３Ｉ￣Ｗ２＋Ｗｌ＋ＷＯ（ＵＩＩ＋ＺＩ），Ｓ３０＝Ｗ１＋Ｕ１０ｗ０；　１０Ｍ　３　Ｃｏｍｐｕｔｅ／／；＝（（ｃｌ＋（　ｌ＋　１）（　ｌ＋／／２１））ｃ２＋“　）／　：　２＝　，１０Ｍ＋２Ｓ　Ｒ１＝Ｚ１Ｚ２，Ｒ２＝ｚ　ｚ２，Ｒ３＝Ｒ１Ｒ２，Ｒ５＝ｙ４Ｒ３，Ｒ４　ＲｓＲ１；　。＝　。＋（心＋　）　；　Ｕ３ｏ＝Ｕ２０Ｙ５Ｒ３＋（Ｒ４＋　）　；　４　Ｃｏｍｐｕｔｅ　Ｅ　ｈ＋（　３”２＋ｖ２）ｍｏｄ”；＝　ｌ　＋　０：　Ｒ＝　１，　２　ｌ，Ｒ３＝Ｒ２　，ｚ］＝ＲＺ；，Ｚ３＝　；　Ｗ１＝ｓ３１（Ｕ２１２３１＋Ｕ３１Ｚ２１），Ｗ２＝￥３０（Ｕ２０２３１＋Ｕ３０２＂２１），Ｗ３＝　３１＋　３０）（Ｕ２ｌＺ３１＋Ｕ３ＩＺ２１＋Ｕ２０Ｚ３１＋Ｕ３０２２１）；　Ｒ４＝ｗＩＲ２，　０＝（ｗ２＋１３　ｏ）Ｒ３＋Ｕ３ｏＲ４，Ｖ３１＝（Ｗｌ＋Ｗ３＋Ｗ２＋Ｚ３　Ｉ）Ｒ３＋Ｕ３ＩＲ４＋ｚ３，　１８Ｍ＋１Ｓ　５　ｌ＝　１　，　ｏ＝Ｕ３ｏＲ；　２Ｍ　Ｔｏｔａｌ　５Ｓ＋４８Ｍ　２２８６　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．１０，Ｏｃｔｏｂｅｒ　２０１３　算法ｌ１．在Ｒ坐标系下的加法公式（类型ＩＩＩ）　Ｉｎｐｕｔ　Ｏｕｔｐｕｔ　Ｄｌ　［ｕＩｌ，Ｕｍ０，Ｖ１１，Ｖ１０，Ｚ１，ｚ１］，Ｄ２　［Ｕ２１，Ｕ２ｏ，　１，Ｖ２ｏ，Ｚｚ，ｚ２］，Ｄ＝Ｄ２－ＤＩ＝［Ｕ１，Ｕｏ，Ｖｌ，Ｖｏ，Ｚ，ｚ］；　Ｄ３＝ＤＩ＋Ｄ２．　Ｓｔｅｐ　１　Ｅｘｐｒｅｓｓｉｏｎ　Ｃｏｍｐｕｔｅ　ＣＩ＝ｒ／ｕｌ　ｍｏｄ　Ｉｇ２　ａｎｄ　ｅ２＝ｒ／ｕ２　ｍｏｄ“ｌ：　Ｏｐｅｒａｔｉｏｎｓ　８Ｍ＋２Ｓ　Ｙｌ　Ｕ２１Ｚｌ＋ＵｌＩＺ２，Ｙ２　ＵｌｏＺ２＋Ｕ２ｏＺ１，Ｙ３＝　，Ｙ４＝　；，ｙｓ＝ｙ３Ｕｌｏ；　ｅ２１＝ｙｌ，ｅ２ｏ＝Ｕｔｌｅ２１＋ｙ２Ｚ１，ｅｌｌ＝ｙ１，ｅｌｏ＝　ｌｅｌｌ＋ｙ２Ｚ２；　，‘＝ｙ２ｅｌ０　５；　２　Ｃｏｍｐｕｔｅ　Ｓ　（ｖｉ＋ｖ２）ｅ２　ｍｏｄ　ＷＯ＝ｅ２１（Ｖ１ｌＺ２＋　ｌＺ１），Ｗ１＝ｅ２ｏ（ＶｌｏＺ２＋　ｏｚ０，Ｗ２：（Ｖｌ１Ｚ２＋　ＩＺＩ＋ＶＩｏＺ２＋　ｏＺ１）（ｅ２１ｚｌ＋ｅ２ｏ）；　￥３１＝　２＋ｗｌ＋ｗ０（Ｕｌｌ＋Ｚ１），￥３０＝Ｗｌ＋Ｕａ０Ｗｏ；　ｌＯＭ　３　Ｃｏｍｐｕｔｅ“；＝（（ｃ１＋（　ｌ＋　）（　１＋Ⅳ２１））ｃ２＋“　）／　：　＝　１２Ｍ＋２Ｓ　２，Ｒ１＝ＺＩＺ２，Ｒ２＝ｚ　ｚ２，Ｒ３＝Ｒ１Ｒ２，Ｒｓ＝ｙ４Ｒ３，Ｒ４＝ＲｓＲＩ，Ｒ２　ＲＩＲ３；　Ｕ３１＝　Ｙｌ＋（Ｒ４＋　）ｕ　Ｕ３０＝ｅ１０ｅ２０Ｒ３＋（ｙ３　２＋　）　；　４　Ｃｏｍｐｕｔｅ　三ｈ＋（Ｓ３Ｕ２＋Ｖ２）ｍｏｄ甜；＝Ｖ３　】　＋　０：　＝　１，　２　Ｉ，Ｒ３＝ＲＥ　，Ｚ３＝Ｒｚ；，ｚ３＝　；　ＷＩ＝Ｓ３１（　１Ｚ３１－１－Ｕ３１Ｚ２１），Ｗ２＝Ｓ３０（Ｕ２０２３１＋Ｕ３０７，２１），　３　（旬ｌ＋　３ｏ）（Ｕ２ＩＺ３１＋Ｕ３ＩＺ２１＋Ｕ２ＯＺ３１＋Ｕ３ｏｚ２１）；　Ｒ４＝　１　２，Ｚ３ｏ＝（ｗ２＋Ｚ３　ｏ）Ｒ３＋Ｕ３ｏＲ４，　１＝（ｗＩ＋ｗ３＋ｗ２＋Ｚ３Ｖ２ｔ）Ｒ３＋Ｕ３ｉＲ４＋ｚ３；　１８Ｍ＋１Ｓ　５　Ｔｂｔａｌ　Ｕ３１＝Ｕ３　ａＲ，Ｕ３０＝Ｕ３ｏＲ；　２Ｍ　５Ｓ＋５０Ｍ　对定理４的证明，也即证明了算法１０的正确性．　定理４．算法１０的输出结果相对应的仿射坐标是算法４的输出．　证明：通过验证下面的等式来证明：　・　・　１／Ｚ３＝（Ｒ５Ｙ１＋（Ｒ４＋　）　）／Ｚ３＝（　ｌ０＋Ｕ２０）　（　１１＋“２ｌ＋　１ｔＪ，　２１＋Ｕ　Ｕ；　ｏ／Ｚ３＝（Ｕ２０Ｙ５Ｒ３＋（Ｒ４＋ｚ；）Ｖｏ）／Ｚ３＝（ＵｌＯＺ５＋ｚ４　０ｔ　Ｊ，　２ｌ＋　＝　；　口　・　ｖ３ｌ／Ｚ３＝（（ｗ２＋Ｒ４Ｖ２ｏ）Ｒ３＋Ｗ１ｕ３ｏＲ２）／ｚ３＝　】；　・　ｖ３ｏ／Ｚ３＝（（ｗ３＋ｗ２＋Ｒ４　１）Ｒ３＋ｗＩ（ｕ３ｉＲ２＋ｚ３）＋ｚ３）／ｚ３＝　０．　同样，对于算法１１的验证也只需要验证第３步中的　０就可以了．　３算法分析和仿真　本节首先比较分析各种算法的效率，然后使用算法实现超椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法．各个坐标系　下的加法公式的运算量列在表１中．表中的Ｍ，Ｓ和１分别表示域上的乘法、平方和求逆．　Ｔａｂｌｅ　１　Ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　Ｍｏｎｔｇｏｍｅｒｙ　Ｌａｄｄｅｒ　ａｌｇｏｒｉｔｈｍ　ｏｖｅｒ　表１在域　上的Ｍｏｎｔｇｏｍｅｒｙ阶梯加法公式的运算量　可以看到．本文中提出的新的公式在投影坐标系、Ｎ坐标系和Ｒ坐标系下都比之前的公式计算速度要快．　提高幅度最大的是在类型ＩＩ的曲线上，在投影坐标系和Ｎ坐标系下分别比之前的公式少用了４个乘法，在Ｒ坐　标系下少用了２个乘法和３个平方．由于在不同的实现函数库中，域上的平方和乘法计算之间的速度比值是不　同的，这样就造成新的算法运行效率提高的比率也会有所不同Ｉ２】．在一些实现中，Ｓ＝０．８Ｍ，那么新的加法公式在　类型ＩＩ的曲线上，在投影、Ｎ坐标系和Ｒ坐标系下分别比之前的公式快了７．７％，７．８％和７．８％．当１Ｓ＝Ｏ．５Ｍ时，　本文中的公式在类型ＩＩ的曲线上比之前的公式快了７．８％，８％和６．５％．当我们用正规基来表示域　上的元素时，　李明等：超椭圆曲线上Ｍｏｎｔｇｏｍｅｒｙ标量乘的快速计算公式　２２８７　一次平方计算只是一次移位操作，这样，平方计算的运算量与乘法相比可以忽略不计．这时，我们的公式在类型ＩＩ　的曲线上比之前的公式快了８．２％，８．３％￣Ｆ１　４％．本文提出的公式在类型ＩＩＩ的曲线上的效率与之前的相比也有明　显的提高，在投影坐标系和Ｎ坐标系下分别少用了１个乘法，而在Ｒ坐标系下少用了３个平方．　我们对各个公式进行了仿真实验．最终的运算结果证明了算法的正确性，各种算法的运行时间列在了表２　中．我们的仿真平台是在Ｔｉｎｋｐａｄ　Ｔ５００（ＣＰＵ　Ｐ８８００，ＤＤＲ２　４０）上，使用了ＮＴＬ５．４．２和Ｍａｇｍａ　ｏｎｌｉｎｅ两个函数库　分别进行了实验，选择的域是　‘　．在这两个函数库中，在特征为２的域上的乘法和平方计算之间的比值满足　１Ｓ＝０．８Ｍ一０．７５Ｍ．每次仿真选择１００　０００个随机参数，然后取运行时间的平均值．　Ｔａｂｌｅ　２　Ｔｈｅ　ｓｕｍｕｌａｔｉｏｎ　ｏｆ　ａｌｇｏｒｉｔｈｍｓ　ｏｆ　ａｄｄｉｔｉｏｎ　ｆｏｒｍｕｌａ（ｎ＝２５５ｂｉｔｓ，Ｕｎｉｔ：ｍｓ）　表２加法公式的仿真实验结果（ｎ＝２５５ｂｉｔｓ，单位＂ｍｓ）　已有算法［２，５１　ＮＴＬ　Ｍａｇｍａ　类型ＩＩ的曲线上　ＮＴＬ　Ｍａｇｍａ　类型ＩＩ１的曲线上　ＮＴＬ　Ｍａｇｍａ　投影坐标系　Ｎ坐标系　Ｒ坐标系　１．Ｏ６　１．０４　１．１５　０．０２９　１　０．０２９　０　０．０３１　Ｏ　０．９８　０．９６　１．Ｏ５　０．０２６　２　０．０２６　ｌ　０．０２８　８　１．０４　１．０２　１．０９　０．０２８　ｌ　０．２７６　０．２９２　本文的加法公式是为了实现超椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法而设计的．Ｍｏｎｔｇｏｍｅｙ阶梯算法实现　ｒ的标量乘计算，可以抵抗简单边带信道攻击．而当使用之前的常规公式时，只有“总是二倍加法”标量乘算法可以　实现这个功能．在特征为偶数的域上，投影坐标系下计算二倍除子类的运算量为３８Ｍ＋７Ｓ，但是，当　＝０时降低为　２５Ｍ＋６Ｓ．这也是为什么虹：０的曲线特别适合Ｍｏｎｔｇｏｍｅｒｙ阶梯算法的实现．在域　上实现Ｍｏｎｔｇｏｍｅｒｙ阶梯　算法时，需要做２５４次：二倍和加法运算．如果在类型ＩＩ的曲线上实现Ｍｏｎｔｇｏｍｅｙ阶梯标量乘算法，ｒ我们将各种　坐标系下的运算量列入表３．根据文献［２］，类型ＩＩ的曲线上Ｎ坐标系和Ｒ坐标系下的二倍计算的运算量为　３９Ｍ＋６Ｓ和２３Ｍ＋８Ｓ．表４中是不同情况下标量乘计算的仿真结果，该结果也证明了我们的算法的正确性和有效　性．可以看到，在投影坐标系下，类型为ＩＩ的超椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法最为高效．　Ｔａｂｌｅ　３　Ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　Ｍｏｎｔｇｏｍｅｙ　ｒＬａｄｄｅｒ　ａｌｇｏｒｉｔｈｍ　ｏｖｅｒ　Ｆ２５５（Ｔｙｐｅ　ｉｉ）　表３在域Ｆｚｓｓ上的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法的运算量（类型ＩＩ）　Ｔａｂｌｅ　４　Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｏｆ　Ｍｏｎｔｇｏｍｅｒｙ　Ｌａｄｄｅｒ　ａｌｇｏｒｉｔｈｍ　ｏｖｅｒ　Ｆ２５５（Ｔｙｐｅ　ＩＩ，Ｕｎｉｔ：ｓ）　表４在域　：　上对Ｍｏｎｔｇｏｍｅｒｙ阶梯算法的仿真结果（类型ＩＩ，单位：ｓ）　４结论　本文研究了如何在超椭圆曲线上为Ｍｏｎｔｇｏｍｅｒｙ阶梯算法设计高效的除子类加法计算公式．本文通过代数　变换技术，使得超椭圆曲线上的Ｍｏｎｔｇｏｍｅｒｙ阶梯算法在公式层面上有了改进和提高．分析和比较结果表明，新　的公式在投影坐标系、Ｎ坐标系和Ｒ坐标系下，在类型ＩＩ和类型ＩＩＩ的曲线上，速度都有明显提高．在类型ＩＩ曲　线上的提高最为明显．当域上的平方和乘法之间运算速度的比率满足１Ｓ＝０．８Ｍ时，类型ＩＩ的曲线上新的公式比　之前的公式快了７．７％～７．８％；当１Ｓ＝０．５Ｍ时，新的公式快了６．５％～８％．当我们用正规基来表示域上的元素时，新的　公式快了４％～８．３％．　本文中提出的技术还可以与其他技术结合使用，以进一步提高公式的运行速度．比如，文献［１４１中将二倍和　加法结合起来，而减少乘法个数的技术．当然，椭圆曲线上出现的很多其他变换技术，比如有理变换曲线来设计　公式的技术［１５１，也可以拿来运用到超椭圆曲线上．至于如何应用，有待于我们进一步的研究．　２２８８　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２４，Ｎｏ．１０，Ｏｃｔｏｂｅｒ　２０１３　致谢　非常感谢Ａｌｉ　Ｍｉｒｉ教授对本文提出的建议和意见　Ｒｅｆｅｒｅｎｃｅｓ：　【１】Ｋｏｂｌｉｔｚ　Ｎ．Ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｒｙｐｔｏｓｙｓｔｅｍｓ．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｒｙｐｔｏｌｏｇｙ，１９８９，１：１３９—１５０．【ｄｏｉ：１Ｏ．１００７／ＢＦ０２２５２８７２】　［２］　Ａｖａｎｚｉ　Ｒ，Ｃｏｈｅｎ　Ｈ，Ｄｏｃｈｅ　Ｃ，Ｆｒｅｙ　Ｇ，Ｌａｎｇｅ　Ｔ，Ｎｇｕｙｅｎ　Ｋ，Ｖｅｒｃａｕｔｅｒｅｎ　Ｆ．Ｈａｎｄｂｏｏｋ　ｏｆ　Ｅｌｌｉｐｔｉｃ　ａｎｄ　Ｈｙｐｅｒｅｌｌｉｐｔｉｃ　Ｃｕｒｖｅ　Ｃｒｙｐｔｏｇｒａｐｈｙ．Ｂｏｃａ　Ｒａｔｏｎ：Ｃｈａｐｍａｎ＆Ｈａｌ１．２００５　旦ｉｃｉｆｅｎｔ　ｄｏｕｂｌｉｎｇ　ｏｎ　ｇｅｎｕｓ　ｔｗｏ　ｃｕｒｖｅｓ　ｏｖｅｒ　ｂｉｎａｒｙ　ｉｅｌｆｄｓ．Ｉｎ：Ｈａｄｄａｄ　Ｈ，Ｏｍｉｃｉｎｉ　Ａ，Ｗａｉｎｗｒｉｇｈｔ　ＲＬ，Ｌｉｅｂｒｏｃｋ　ＬＭ，ｅｄｓ．　［３］　Ｌａｎｇｅ　Ｔ．ＥｆＰｒｏｃ　ｏｆｔｈｅ　Ｓｅｌｅｃｔｅｄ　Ａｒｅａｓ　ｉｎ　Ｃｒｙｐｔｏｇｒａｐｈｙ（ＳＡＣ　２００４）．ＬＮＣＳ　３３５７，２００５．１７０—１８１　ｌ【ｄｏｉ：１０．１００７／９７８—３—５４０—３０５６４—４—１２］　ｌｉｎｇｅｒ　Ｔ，Ｐｅｌｚｌ　Ｊ，Ｐａａｒ　Ｃ．Ｃａｎｔｏｒ　ｖｅｒｓｕｓ　Ｈａｒｌｅｙ：Ｏｐｔｉｍｉｚａｔｉｏｎ　ａｎｄ　ａｎａｌｙｓｉｓ　ｏｆ　ｅｘｐｌｉｃｉｔ　ｆｏｒｍｕｌａｅ　ｆｏｒ　ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｕｒｖｅ　［４］　Ｗｏｌｃｒｙｐｔｏｓｙｓｔｅｍｓ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｃｏｍｐｕｔｅｒｓ，２００５，５４（７）：８６１－８７２ｌ【ｄｏｉ：１０　１　１０９／ＴＣ．２００５．１０９】　ａｅ　ｆｏｒ　ａｒｉｔｈｍｅｔｉｃ　ｏｎ　ｇｅｎｕｓ　２　ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｕｒｖｅｓ．Ａｐｐｌｉｃａｂｌｅ　Ａｌｇｅｂｒａ　ｉｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｏｍｍｕｎｉｃａｔｉｏｎ　ａｎｄ　［５】　Ｌａｎｇｅ　Ｔ．ＦｏｒｍｕｌＣｏｍｐｕｔｉｎｇ，２００５，１５（５）：２９５—３２８．［ｄｏｉ：１０．１００７／ｓ００２００－００４一Ｏｌ５４・８］　［６］　Ｂｌａｋｅ　Ｉ，Ｓｅｒｏｕｓｓｉ　Ｇ，Ｓｍａｒｔ　Ｎ，ｅｄｓ．Ａｄｖａｎｃｅｓ　ｉｎ　Ｅｌｌｉｐｔｉｃ　Ｃｕｒｖｅ　Ｃｒｙｐｔｏｇｒａｐｈｙ．Ｌｏｎｄｏｎ　Ｍａｔｈｅｍａｔｉｃａｌ　Ｓｏｃｉｅｔｙ　３　１　７，Ｃａｍｂｒｉｄｇｅ　Ｕｎｉｖｅｒｓｉｔｙ　Ｐｒｅｓｓ，２００５．　ｎｓｔｅｉｎ　Ｄ．Ｂａｔｃｈ　ｂｉｎａｒｙ　Ｅｄｗａｒｄｓ．Ｉｎ：Ｈａｌｅｖｉ　Ｓ．ｅｄ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ　ＣＲＹＰＴＯ　２００９．ＬＮＣＳ　５６７７．Ｓｐｒｉｎｇｅｒ－　［７］　ＢｅｒＶｅｒｌａｇ，２００９．３１７－３３６．【ｄｏｉ：１０．１００７／９７８－３－６４２－０３３５６—８１９］　ｙ　Ｌａｄｄｅｒ　ｆｏｒ　ａｌｌ　ｇｅｎｕｓ　２　Ｃｕｒｖｅｓ　ｉｎ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　２．ＬＮＣＳ　５　１３０（Ａｒｉｔｈｍｅｔｉｃ　ｏｆ　Ｆｉｎｉｔｅ　Ｆｉｅｌｄｓ），２００８．　［８］　Ｄｕｑｕｅｓｎｅ　Ｓ．Ｍｏｎｔｇｏｍｅｒ１７４—１８８ｌ【ｄｏｉ：１０．１００７／９７８－３－５４０—６９４９９－１１５］　ｙ　ａｄｄｉｔｉｏｎ　ｆｏｒ　ｇｅｎｕｓ　ｔｗｏ　ｃｕｒｖｅｓ．ＬＮＣＳ　３０７６（Ａｌｇｏｒｉｔｈｍｉｃ　Ｎｕｍｂｅｒ　Ｔｈｅｏｒｙ），２００４．３０９～３１７ｌ【ｄｏｉ：１０．１００７／　［９］　Ｌａｎｇｅ　Ｔ．Ｍｏｎｔｇｏｍｅｒ９７８—３—５４０—２４８４７　７２３］　　Ａ，Ｗｕ　ＹＨ，Ｚｕｃｃｈｅｒａｔｏ　Ｒ．Ａｎ　ｅｌｅｍｅｎｔａｒｙ　ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｕｒｖｅｓ．Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　Ａｌｇｅｂｒａｉｃ　Ａｓｐｅｃｔｓ　ｏｆ　［１０］　ＭｅｎｅｚｅｓＣｒｙｐｔｏｇｒａｐｈｙ．１９９８　ｈｔｔｐ：／／ｃａｃｒ．ｕｗａｔｅｒｌｏｏ．ｃａ／ｔｅｃｈｒｅｐＯｒｔｓ／１９９７／ｃｏｒｒ９６—１９．ｐｓ　Ｗｏｌｌｉｎｇｅｒ　Ｔ　Ｓｏｆｔｗａｒｅ　ａｎｄ　ｈａｒｄｗａｒｅ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｕｒｖｅ　ｃｒｙｐｔｏｓｙｓｔｅｍｓ［Ｐｈ．Ｄ．Ｔｈｅｓｉｓ］Ｂｏｃｈｕｍ：Ｒｕｈｒ－　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｂｏｃｈｕｍ，２００４．　［１２］　［１３］　Ｍｕｍｆｏｒｄ　Ｄ．Ｔａｔａ　Ｌｅｃｔｕｒｅｓ　ｏｎ　Ｔｈｅｔａ　ＩＩ．Ｂｉｒｋｈ￣．ｕｓｅｒ　Ｂｏｓｔｏｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，１　９９３　Ｃａｎｔｏｒ　ＤＧ．Ｃｏｍｐｕｔｉｎｇ　ｉｎ　ｔｈｅ　Ｊａｃｏｂｉａｎ　ｏｆａ　ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｕｒｖｅ．Ｍａｔｈｅｍａｔｉｃｓ　ｏｆＣｏｍｐｕｔａｔｉｏｎ，１９８７，４８：９５—１０１．　ｉｃｉｆｅｎｔ　ｅｘｐｌｉｃｉｔ　ｆｏｒｍｕｌａｅ　ｆｏｒ　ｇｅｎｕｓ　２　ｈｙｐｅｒｅｌｌｉｐｔｉｃ　ｃｕｒｖｅｓ　ｏｖｅｒ　ｐｒｉｍｅ　ｆｉｅｌｄｓ　ａｎｄ　ｔｈｅｉｒ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ．Ｉｎ：　［１４］　Ｆａｎ　ＸＸ，Ｇｏｎｇ　Ｇ．ＥｆＡｄａｍｓ　Ｃ，Ｍｉｒｉ　Ａ，Ｗｉｅｎｅｒ　Ｍ，ｅｄｓ．Ｐｒｏｃ．ｏｆｔｈｅ　Ｓｅｌｅｃｔｅｄ　Ａｒｅａｓ　ｉｎ　Ｃｒｙｐｔｏｇｒａｐｈｙ　２００７．ＬＮＣＳ，Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００７．１　５５—１７２．【ｄｏｉ：　１０．１００７／９７８—３—５４０—７７３６０—３１　１］　ｅｉｎ　Ｄ．Ｌａｎｇｅ　Ｔ．Ｆａｒａｓｈａｈｉ　Ｒ．Ｂｉｎａｒｙ　Ｅｄｗａｒｄｓ　ｃｕｒｖｅｓ．１ｎ：Ｐｒｏｃ　ｏｆ　ｔｈｅ　１０ｔｈ　Ｉｎｔ’１　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｃｒｙｐｔｏｇｒａｐｈｉｃ　Ｈａｒｄｗａｒｅ　ａｎｄ　［１５］　ＢｅｒｎｓｔＥｍｂｅｄｄｅｄ　Ｓｙｓｔｅｍｓ（ＣＨＥＳＳ　２００８）．ＬＮＣＳ　５１５４，２００８．２４４—２６５．［ｄｏｉ：１０．１００７／９７８・３—５４０—８５０５３—３—１６］　李明（１９８２一），男，山东肥城人，博士，工程　师，主要研究领域为算法分析与设计，密　码学．　Ｅ—ｍａｉｌ：ｌｕａｍｉｎｇ＠ｍｓｎ．ｃｏｍ　朱大铭（１９６３一），男，博士，教授，博士生导　师，ＣＣＦ高级会员，主要研究领域为算法分　析与设计，生物计算．　Ｅ－ｍａｉｌ：ｄｍｚｈｕ＠ｓｄｕ．ｅｄｕ．ｃｎ　孔凡５Ｅ（１９７８一），男，博士，副教授，ＣＣＦ会　员，主要研究领域为密码学，信息安全．　Ｅ—ｍａｉｌ：ｆａｎｙｕｋｏｎｇ＠ｓｄｕ．ｅｄｕ．ｅｎ