加密计算方法、加密系统和计算机程序的制作方法

专利名称：：加密计算方法、加密系统和计算机程序的制作方法
技术领域：
：本发明涉及加密计算方法、加密系统和计算机程序。更具体地说，本发明涉及在超椭圆曲线加密术(hyperellipticcurvecryptography)中实现较快的标量乘法的加密计算方法、加密系统和计算机程序。
背景技术：
：随着在网络通信和电子商务交易方面的最新进步，确保通信的安全变得越来越重要。用于确保安全的一种方法是加密术。现在，通过使用各种加密技术来进行通信。例如，已经将这样的系统投入到实际使用中将加密模块嵌入在诸如IC卡之类的小型装置中，并且在IC卡和作为数据读/写装置的读/写器之间执行数据传送/接收，从而执行验证处理、或者对所传送/接收的数据进行加密/解密。例如，在诸如火车站或购物中心的入口门之类的各种门口广泛使用执行加密处理的IC，而且，对于更小尺寸和更快处理速度的需求正在变得越来越迫切。将加密方案大致分为公用密钥方案(commonkeyscheme)和公开密钥方案(publickeyscheme)。也将公用密钥方案称为对称加密术。在公用密钥方案中，发送者和接收者都拥有共同密钥。公用密钥方案的典型应用是DES(数据加密标准)。DES算法的特征特点是可以使用基本上相同的算法来执行加密和解密。采用与上述公用密钥方案不同的、由发送者拥有的密钥与由接收者拥有的密钥不相同的配置的方案是公开密钥方案、或者非对称加密术。与将共同密钥用于加密和解密的共同密钥加密术不同，公共密钥加密术在密钥管理方面更加优越，这是因为只有一个特定的人需要拥有必须被秘密保存的秘密秘钥。然而，与共同密钥加密术相比较，公共密钥加密术具有较低的数据处理速度。因此，总体来说，经常将公共密钥加密术用于秘密密钥、数字签名等的分发，因为这样的应用具有较小的数据量。公共密钥加密术的公知例子包括RSA(Rivest-Shamir-Adleman)加密术和ECC(EllipticCurveCryptograph，椭圆曲线加密术)。椭圆曲线加密术使用素域上的椭圆曲线y2＝x3+ax+b(其中4a3+27b2≠0)、两个扩展域上的椭圆曲线y2+xy＝x3+ax2+b(其中b≠0)等。包括被加到这些曲线的每一个上的点上的无限点(O)的集合形成针对加法的有限群，而无限点O变为其单位元。在下面的描述中，由运算符+来表示在该有限群中的点的加法。将在有限群中的两个不同点P、Q的加法P+Q称为“点加法”，而将有限群中的两个点P的加法P+P＝2P称为“点加倍(pointdoubling)”。将点P与其自己加法k次的运算，也就是，寻找点P+P++P＝kP的运算，称为“点的标量乘法”。众所周知，可以用点加法和点加倍来计算点的标量乘法。在针对公共密钥加密术的IEEEp1363/D13标准规范中描述了在素域上在椭圆曲线上以及在两个扩展域上的椭圆曲线上、在仿射坐标(x，y)或者射影坐标(X，Y，Z)中的点的标量乘法。将椭圆曲线加密术进行推广的方案例子是Koblitz和Cantor所提议的HECC(超椭圆曲线加密术)系统。在非专利文献1和2中描述了超椭圆曲线加密术。在椭圆曲线加密术中，如果P代表在有限域Fq上所定义的椭圆曲线上的点，而Q代表点kP(k∈Z)，也就是，作为点P的标量乘法的结果而获得的点，则可以作为离散对数问题来解从Q中求解k的问题。在另一方面，在超椭圆曲线加密术中，如果D1代表与点的形式和(formalsum)相等的除数而D2代表被定义为标量乘法kD1的除数，则作为公共密钥加密术问题，从D2中求解k的问题可以被当作在超椭圆曲线上在雅可比簇中的离散对数问题来处理。在超椭圆曲线的情况中，对该曲线定性的值是亏格(genus)g。让q等于pn(q＝pn)，其中p代表素数而n代表正整数。在这种情况下，由下面等式来定义作为亏格g的曲线在有限域Fq上定义的超椭圆曲线Cy2+h(x)y＝f(x)其中h(x)，f(x)∈Fq[x]，f(x)是2g+1次的首一多项式。将超椭圆曲线C上与点P＝(x，y)相对的点-P定义为-P＝(x，y+h(x))。将P＝-P的点称为分歧点(ramificationpoint)。众所周知，假设与椭圆曲线加密术的安全性的等级相同，则可以将超椭圆加密术的定义域的处理规模(位数量)减少到椭圆曲线加密术的定义域的处理规模的1/g。从实施的角度来说，小处理规模是有利的，所以将此作为超椭圆加密术的一个优点。下面，将描述超椭圆加密术的基本原理。如上所述，在超椭圆加密术中，可以将从D2中求解k的问题作为超椭圆曲线上的雅可比簇中的离散对数问题处理，因此可以作为公共密钥加密术中的问题处理，其中D1是与点的形式和相等的除数，而D2是被定义为标量乘积kD1的除数。在这种情况下，除数等于点的形式和并且可以以下面形式表示[公式1]D=ΣimiPi]]>进一步，可以以下面形式表示减半的除数[公式2]D=ΣimiPi-(Σimi)P∞,mi≥0]]>然而，对于Pi＝(xi，yi)和i≠j，关系Pi≠Pj为真。将上述等式中的∑mi称为除数D的权重。进一步，将具有不超过亏格g的权重的减半的除数称为减小的除数。使用多项式U和V∈Fq[x]，可以将超椭圆曲线上在雅可比簇中的任何减半除数D表示为D＝(U，V)。将该表达式称为Mumford表达式。在例如非专利文献3中描述了Mumford表达式。U=Π(x-xi)mi]]>V(xi)＝yiV(x)2+V(x)h(x)-f(x)≡0modU(x)，degV＜degU通过使用Mumford表达式，可以有多项式集合来表示针对亏格为2的任何减小的除数D，所述每一个多项式具有在多项式系数中所设定的有限域上的元素并且具有不超过2的阶数。也就是，可以将减小的除数表示为(U，V)＝(x2+u1x+u0，v1x+v0)，或者(U，V)＝(x+x0，y0)。进一步，将零元素表示为(U，V)＝(1，0)＝O下面，将描述在超椭圆曲线加密术中使用的除数的标量乘法。可以将除数的标量乘法执行为除数的加法的组合，将其称为加法算法，以及除数的加倍。将在下面描述主要的加法算法。第一个所提出的实际算法是Cantor算法。在例如非专利文献1和2中描述了Cantor算法。可以将该Cantor算法应用于在任何亏格的超椭圆曲线上的除数。然而，与椭圆曲线算法相比较，这种Cantor算法的缺点是该算法较复杂并且具有较高的复杂度。哈利(Harley)提出了一种算法，在其中通过将算法限制到亏格为2的超椭圆曲线，根据除数的权重来进行逐个情况的分化(differentiation)，并且针对每个独立情况执行优化以实现复杂度的降低。从那时起，哈利算法已经成为关于HECC(超椭圆曲线加密术)中的计算算法的改进和扩展所进行的最近的广泛研究的主题。(a)根据哈利算法，将定义域用于素域，并且采用Mumford表达式作为在带有亏格为2的曲线上的除数的表达式。目标是减小这种算法的复杂度的研究的例子包括在非专利文献4、非专利文献5、非专利文献6等中所公开的那些。(b)此外，在非专利文献7和非专利文献8的每一个中都报导了关于两个扩展域来扩展定义域的处理的例子。(c)进一步，非专利文献11、12、6和13公开了这样的研究根据该研究，通过使用Mumford表达式来表示除数并且采用加权的坐标来实现复杂性降低。将参照图1描述使用哈利算法的处理。应该注意，本发明涉及在特征为2的有限域上所定义的亏格为2的超椭圆曲线。在下面的描述中，假设曲线的亏格为2而且定义域的特征为2。图1A是示出除数的加法D1+D2的处理示例，其中D1和D2每一个都表示带有亏格为2的除数。应该注意，将除数D1和D2表示如下D1＝(U1，V1)，D2＝(U2，V2)。首先，根据除数的权重值进行逐情况的分化。也就是，根据[D1+D2]的相应权重的值，针对下面情况对该处理进行分化(1)权重1+权重2(2)权重2+权重1(3)例外处理1随后，在将权重2加到权重2自身的情况中，即在情况(1)中权重1+权重2，如果针对两个除数D1＝(U1，V1)和D2＝(U2，V2)的最大公分母gcd(U1，U2)是1(gcd(U1，U2)＝1)，则两个除数D1＝(U1，V1)和D2＝(U2，V2)不包括公共点或者彼此相反的点。在这种情况下，根据下面进行加法(1a)HarleyADD也就是，执行哈利算法。参照在例如非专利文献7中所公开的最频繁情况(MostFrequentCase)来处理(1a)HarleyADD的处理。最频繁情况是在用于球针对亏格为2的除数之和D1+D2的处理之外具有最高发生概率的情况。(1a)HarleyADD的处理发生的概率非常高。一些其他例外处理发生的概率非常低。如果不满足最频繁情况的条件，也就是，如果不满足针对两个除数D1＝(U1，V1)和D2＝(U2，V2)的最大公分母gcd(U1，U2)＝1，则(1b)执行例外处理2。此外，针对权重2+权重1的情况(2)，以相同的方式，检查是否有gcd(U1，U2)＝1，如果满足gcd(U1，U2)＝1，则执行ExHarADD2+1→2(2a)，而如果不满足gcd(U1，U2)＝1，则执行(2b)ExceptionalProcessing3(2b)针对除了上述情况(1)和(2)的那些之外的权重设定的情况执行在情况(3)中的例外处理1。应该注意，在非专利文献8(表1、2)中详细公开了上述针对亏格为2的加法处理的算法。在图1(B)中示出了针对亏格为2的加倍操作的流程。将加倍运算处理表示为D+D＝2D。使得D1＝(U1，V1)是输入，而D2＝[2]D1是输出。当在加法的情况中，根据除数D的权重来执行不同种类的处理，如下(4)权重2(5)权重1(6)权重0在权重2的情况(4)中，检查除数是否包括分歧点。如果不包括分歧点，则执行(4a)HarleyDBL的处理。如果除数包括分歧点，则执行(4b)例外处理6。在例如非专利文献7中将HarleyDBL处理的算法公开为最频繁情况。下面示出HarleyDBL处理的算法。Algorithm1HarleyDBLInputD1＝(U1，V1)OutputD2＝(U2，V2)Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，U1)＝11.U1′←U122.S←h-1(f+hV1+V12)/U1modU13.V1′←SU1+V14.U2′←(f+hV1′+V1′2)/U′5.U2←MakeMonic(U2′)6.V2←V1′+hmodU27.returnD2＝(U2，V2)如将在后面描述的那样，该处理发生概率非常高。一些其他例外处理的发生概率非常低。如上所述，如果不满足最频繁情况的条件，则执行例外处理6。此外，在权重1的情况中，检查是否有gcd(U1，U2)＝1，并且执行(5a)的处理、ExHarDBL1+1→2、或者例外处理7作为处理(bb)。在非专利文献8[4.12.(a)]中公开了ExHarDBL1+1→2的算法。如上所述，将HarleyADD和HarleyDBL当作最频繁情况。如果除数被随机产生并且经历加法或者加倍，则HarleyADD或者HarleyDBL处理发生的概率非常高。应该注意，在例如非专利文献14中给出了关于HarleyADD和HarleyDBL变为最频繁情况的描述。根据非专利文献14，除了上述最频繁情况以外的处理发生的概率是O(1/q)，其中q表示定义域中的元素数量。由于qg是在安全加密应用中带有大约160的所需要大小的大数，所以实际上可以认为只有HarleyADD或者HarleyDBL发生。因此，当通过使用哈利算法或者其改进算法，实施HECC(超椭圆曲线加密)的加法算法作为诸如IC之类的加密计算装置时，经常是这样的情况只实施HarleyADD，和HarleyDBL，不执行其他类型的具有几乎为零的发生概率的复杂例外处理。应用于这种情况中的例外处理的方法的例子包括不需要依据权重值进行逐情况的分化的Cantor算法的执行。由于较大的亏格，所以复杂的例外处理的负载较大，在非专利文献9和10中具体描述了这种实施方法。下面将描述在HECC(超椭圆曲线加密)的算法中的除数的标量乘法。在HECC(超椭圆曲线加密)的算法中，将除数的标量乘法作为超椭圆加法和超椭圆加倍的组合来执行。将通过采用基本二进制方法和基本的总是加倍与加法方法(basicdouble-and-add-alwaysmethod)作为例子来描述标量加法的算法。如上所述，在椭圆曲线加密术中，假设P表示在有限域Fq上所定义的椭圆曲线上的点，Q表示点kP(k∈Z)，也就是，作为点P的矢量乘法的结果而获得点，则可以将从Q中找到k的问题解为离散对数问题。在另一方面，在超椭圆曲线加密术中，假设D1表示与点的形式和相等的除数，而D2表示被定义为标量乘法kD1的除数，则作为公共密钥加密术问题，从D2中找到k的问题可以被作为在超椭圆曲线上在雅可比簇中的离散对数问题对待。在这种情况下，标量值的二进制表示d作为要被应用标量乘法(D＝dD)的乘数被如下给出d＝(dl-1，...，d0)其中dl-1＝1，以及dl-2，...，0＝1或0作为针对标量乘法的算法，基本二进制方法的计算算法包括下面二进制(左到右)方法；和二进制(右到左)方法根据二进制(右到左)方法，从最低有效位中扫描d，并且如果di＝1，则加入[2i]D。下面示出二进制(右到左)的算法(算法2)。Aleorithm2binary(right-to-left)methodInputD0OutputD＝dD0T←D0D←Oforifrom0tol-1{ifdi＝1thenD←D+T//AdditionHarleyADDT←2T//DoublingHarleyDBL}returnD在另一方面，根据二进制(左到右)方法，从最高有效位扫描d，针对每个位将D加倍，而且如果di＝1，则加入基点(basepoint)。下面示出二进制(左到右)方法的算法(算法3)。Algorithm3binary(left-to-right)methodInputD0OutputD＝dD0D←D0forifroml-2downto0{D←[2]D//DoublingHarleyDBLifdi＝1thenD←D+D0//AdditionHarleyADD}returnD下面，将描述基点产生处理。当将标量乘法应用到加密术时，将输入所需要的除数D0分为下面两种类型(1)事先确定除数；和(2)除数不可事先确定并且随机地产生在事先确定除数的类型(1)的情况中，将输入除数称为基点。将用于产生基点的一般算法描述如下。(a)随机选择在定义域Fq上的g个元素并且产生在超椭圆曲线上的g个点Pi(其中i＝1，...，g)。(a1)随机选择的元素每个都被用作x坐标xi(其中i＝1...g)。然后，确定与xi对应的y坐标，从而将每个点(x，y)都放置在超椭圆曲线上。(b)使得D0＝(U(x)，V(x))表示基点的除数。(b1)U(x)＝(x-x1)(x-x2)...(x-xg)(b2)确定等式V(x)＝vg-1xg-1+Vg-2xg-2+...+v0的系数vi。例如，如果所产生的点全部彼此不同，则可以从等式V(xi)＝yi中找到系数vi。(c)根据上述算法所产生的除数每个都是带有权重g的除数。如果将标量乘法的计算应用于加密术，则产生输入所需要的除数D0，也就是基点。如果将事先所确定的除数应用于产生基点，则可能通过执行上述处理(a)到(c)来找到带有权重g的除数作为可以被用作基点的除数。进一步，关于椭圆曲线加密术，已经提出了二等分有理点。例如，在非专利文献15中公开了在椭圆曲线加密术中二等分有理点。在所公开的处理中，当计算有理点的标量乘法时，替代于使用加法和加倍，使用加法和二等分。通常可以比加倍更快地计算椭圆曲线加密术中的二等分。作为结果，可以更快地计算使用二等分的标量乘法。非专利文献16报告了这样的情况使用英特尔公司提供的[IntelPentiumIII800MHz]作为处理的软件实施，关于定义域Fq，q＝2163，二等分比加倍快大约2.1倍，而且关于定义域Fq，q＝2233，二等分比加倍大约快2.6倍。由于超椭圆曲线加密术代表椭圆曲线加密术的一般情况，所以可能存在将椭圆曲线加密术中所使用的操作扩展到超椭圆曲线加密术的情况。例如，非专利文献17和18公开了将Montgomery方法(由于y坐标不用于椭圆曲线加密术中的计算所以该方法实现快速计算)扩展到超椭圆曲线加密术的情况。可以预计，如果在超椭圆曲线加密术中也可以实现比加倍更快的二等分，则可以比现有技术更快地计算除数的标量乘法。然而，在现有技术中不知道这种二等分运算的使用。应该注意，非专利文献19是呈现了使用加密的快速计算技术的公开文献的例子。E.Knudsen.COMPUTINGMETHODFORELLIPTICCURVECRYPTOGRAPHY，WO01/04742A1，18Jan2001[专利文献2]R.Schroeppel.Ellipticcurvepointambiguityresolutionapparatusandmethod，WO01/35573A1，17May2000[非专利文献1]N.Koblitz.Hyperellipticcurvecryptosystems.J.Cryptology,vol.1，No.3，pp.139-150，1989[非专利文献2]D.G.Cantor.ComputingintheJacobianofhyperellipticcurve.Math.Comp.，Vol.48，No.177，pp，95-101，1987″D.Mumford，TatalecturesonthetaII，ProgressinMathematics，no.43，Birkhauser，1984.″[非专利文献4]K.Matsuo，J.Chao，andS.Tsujii.FastGenustwohyperellipticcurvecryptosystems.TechnicalReportISEC2001-31，IEICEJapan，2001[非专利文献5]M.Takahashi.ImprovingHarleyalgorithmsforJacobiansofgenus2hyperellipticcurves.SCIS2002.(日语)[非专利文献6]T.Lange.Inversionoperation-freearithmeticongenus2hyperellipticcurves.CryptologyePrintArchive，2002/147，IACR，2002[非专利文献7]T.Sugizaki，K.Matsuo，J.Chao，andS.Tsujii.AnextensionofHarleyadditionalgorithmforhyperellipticcurvesoverfinitefieldsofcharacteristictwo.ISEC2002-9，IEICE，2001[非专利文献8]T.Lange，Efficientarithmeticongenus2hyperellipticcurvesoverfinitefieldsviaexplicitformulae.CryptologyePrintArchive，2002/121，IACR，2002[非专利文献9]J.Kuroki，M.Gonda，K.Masuo，J.ChaoandS.Tsujii.Fastgenusthreehyperellipitccurvecryptosystems.SCIS2002[非专利文献10]J.Pelzl，T.Wollinger，J.Guajardo，andC.Paar.HyperellipticcurveCryptosystemsClosingthePerformanceGaptoEllipticCurves.CryptologyePrintArchive，2003/026，IACR，2003[非专利文献11]Y.Miyamoto，H.Doi，K.Matsuo，J.ChaoandS.Tsujii.Afastadditionalgorithmofgenustwohyperellipticcurves.SCIS2002.(日语)[非专利文献12]N.Takahashi，H.MorimotoandA.Miyaji.Efficientexponentiationongenustwohyperellipticcurves(II).ISEC2002-145，IEICE，2003.(日语)[非专利文献13]T.Lange.Weighedcoordinateongenus2hyperellipitccurve.CryptologyePrintArchive，2002/153，IACR，2002N.Nagao.ImprovinggrouplawalgorithmsforJacobiansofhyperellipticcurves.ANTS-IV，LNCS1838，pp.439-448，Springer-Verlag，2000[非专利文献15]E.Knudsen.EllipticScalarMultiplicaionUsingPointHalving.ASIACRYPTO′99，LNCS1716，pp.135-149，Springer-Verlag，1999[非专利文献16]K.Fong，D.Hankerson，J.Lopez，andA.Menezes.Fieldinversionoperationandpointhalvingrevised.TechnicalReportCORR2003-18，http//www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf[非专利文献17]S.Dquesne.MontgomeryScalarMultiplicationforGenus2Curves.ANTS-VI，LNCS3076，pp.153-168，2004.T.Lange.MontgomeryAdditionforGenusTwoCurves.ANTS-VI，LNCS3076，pp.309-317，2004.T.Lange.EfficientDoublingonGenusTwoCurvesoverBinaryFields，SAC2004，pre-proceedings，pp.189-202，2004.
发明内容与现在进入商业阶段的ECC(椭圆曲线加密术)算法相反，作为ECC(椭圆曲线加密术)算法的扩展概念的HECC(超椭圆曲线加密术)，当前正在学术范围的层面上关于快速算法的构件和它们的实施方法进行研究。然而，基于HECC(超椭圆曲线加密术)的标量乘法的计算时间还与ECC(椭圆曲线加密术)的计算时间相近，所以需要进一步增加计算速度。已经在考虑到上述情况提出了本发明，因此本发明的目的是提供能够使得HECC(超椭圆曲线加密术)中的标量乘法的计算时间缩短以实现快速HECC(超椭圆曲线加密术)处理的加密计算方法、加密系统和计算机程序。本发明的另一个目的是提供加密计算方法、加密系统和计算机程序，它们能够找到允许椭圆曲线加密术中的二等分被扩展到超椭圆曲线加密术中以实现快速计算的算法、曲线参数和定义域，从而通过将二等分应用到超椭圆曲线加密术的计算处理来实现快速计算处理。根据本发明的第一方面，提供用于基于超椭圆曲线加密术执行加密计算的加密计算方法，该方法包括计算步骤在超椭圆曲线上关于除数D的标量乘法计算中，执行包括二等分作为计算处理的计算运算。进一步，在根据本发明的加密计算方法的实施方式中，计算步骤是执行计算运算的步骤，包括关于在具有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数D的标量乘法中的二等分。进一步，在根据本发明的加密计算方法的实施方式中，计算步骤是执行计算运算的步骤，包括关于在具有h(x)＝x2+x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。进一步，在根据本发明的加密计算方法的实施方式中，计算步骤是执行计算运算的步骤，包括关于在具有h(x)＝x2+h1x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。进一步，在根据本发明的加密计算方法的实施方式中，计算步骤是执行计算运算的步骤，包括关于在具有h(x)＝x作为参数的特征为2中在亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。进一步，在根据本发明的加密计算方法的实施方式中，加密计算方法还包括查询表的表查询步骤，该表根据关于事先固定的除数D所计算的[1/2iD]的值记录k1、k1′、(k0，k0′)中的哪个是正确的，而且计算步骤通过基于表的查询的确定处理来执行其中降低二等分的复杂度的计算处理。进一步，在根据本发明的加密计算方法的实施方式中，计算步骤包括通过应用下面关系表达式，通过乘法和加法处理而不执行倒数运算(inversion)来计算倒数1/k1的值的步骤1/k1＝h2+k1u21该表达式从二等分计算算法中得出，在该二等分计算算法中InputD2＝(U2，V2)，和OutputD1＝(U1，V1)＝[1/2]D2，其中Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，2。进一步，在根据本发明的加密计算方法的实施方式中，加密计算方法执行根据具有不应用1/u21作为输入值的设定的算法的计算，在二等分计算算法中有InputD2＝(U2，V2)；和OutputD1＝(U1，V1)＝[1/2]D2，其中Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，2。进一步，在根据本发明的加密计算方法的实施方式中，加密计算方法是用于执行关于在具有h(x)＝x2+h1x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D的标量乘法的计算方法，并且计算步骤包括步骤将作为之前所计算的值的1/h12设定为输入值；以及应用之前所计算的输入值1/h12而不执行计算倒数1/h12的处理。进一步，根据本发明的第二方面，提供基于超椭圆曲线加密术执行加密计算的加密系统，包括在关于在超椭圆曲线上的除数D计算标量乘法中执行包括二等分作为计算处理的计算运算的计算执行部分。进一步，在根据本发明的加密系统的实施方式中，将计算执行部分配置为执行计算运算，包括关于在具有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。进一步，在根据本发明的加密系统的实施方式中，将计算执行部分配置为执行计算运算，包括关于在具有h(x)＝x2+x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。进一步，在根据本发明的加密系统的实施方式中，将计算执行部分配置为执行计算运算，包括关于在具有h(x)＝x2+h1x+h0、f4＝0作为参数的特征为2中在亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。进一步，在根据本发明的加密系统的实施方式中，将计算执行部分配置为执行计算运算，包括关于在具有h(x)＝x作为参数的特征为2中在亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分进一步，在根据本发明的加密系统的实施方式中，加密系统进一步包括存储部分，其存储根据关于事先固定的除数D所计算的[1/2iD]的值记录k1、k1′、(k0，k0′)中的哪个是正确的表，而且计算执行部分被配置为通过基于表的查询的确定处理来执行其中降低二等分的复杂度的计算处理。进一步，在根据本发明的加密系统的实施方式中，将计算执行部分配置为通过应用下面关系表达式，通过乘法和加法处理而不执行倒数运算(inversion)来计算倒数1/k1的值1/k1＝h2+k1u21该表达式从二等分计算算法中得出，在该二等分计算算法中InputD2＝(U2，V2)，和OutputD1＝(U1，V1)＝[1/2]D2，其中Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，2。进一步，在根据本发明的加密系统的实施方式中，将计算执行部分配置为执行二等分计算算法，其中InputD2＝(U2，V2)；和OutputD1＝(U1，V1)＝[1/2]D2，其中Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，2，并且执行根据具有不应用1/u21作为输入值的设定的算法的计算。进一步，在根据本发明的加密系统的实施方式中，将计算执行部分配置为执行关于在具有h(x)＝x2+h1x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D的标量乘法的计算方法，并且执行这样的计算将作为之前所计算的值的1/h12设定为输入值，应用之前所计算的输入值1/h12而不执行计算倒数1/h12的处理。进一步，根据本发明的第三方面，提供用于使得根据超椭圆曲线加密术的加密计算在计算机上被执行的计算机程序，包括步骤在关于在超椭圆曲线上的除数D的标量乘法的计算中，执行包括二等分作为计算处理的计算运算。应该注意，根据本发明的计算程序是关于计算机系统提供的计算机程序，所述计算机系统能够通过以计算机可读格式提供的存储介质或者通信介质执行各种程序代码，记录介质是例如CD、FD或者MO，而通信介质例如是因特网。通过以计算机可读格式提供这种程序，在计算机系统上实现与该程序对应的处理。通过下面对本发明的实施方式的详细描述和附图，本发明的其他目的、特点和优点将变得明显。应该注意，在本说明书中所使用的术语系统指的是多个装置的逻辑组合，而不限于相应结构的装置位于相同的机箱内的情况。根据本发明的配置，将对椭圆曲线加密术的二等分扩展到超椭圆曲线加密术以实现快速计算。在使用对超椭圆曲线上的除数的计算的加密计算中，对处理施加较大负荷的计算运算是除数的标量乘法。因此，通过借助于根据上述本发明的处理来实现较快的标量乘法，从超椭圆曲线加密术的处理角度来，能够实现显著的改进。根据本发明的实施方式，在关于在超椭圆曲线加密术的除数D的标量乘法中，可以通过执行包括二等分作为计算处理的计算操作来实现较快的标量乘法。例如，通过执行计算运算来实现快速计算，该计算运算包括关于在具有h(x)＝x2+x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上、在具有h(x)＝x2+h1x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上、或者在具有h(x)＝x作为参数的特征为2下、亏格为2的超椭圆曲线上的除数在标量乘法中的二等分。根据本发明的配置，可以通过应用表来实现除数的标量乘法的复杂性的进一步降低以及因此带来的更快的计算，所述表根据关于事先固定的除数D所计算的[1/2iD]的值记录k1、k1′、(k0，k0′)中的哪个是正确的。根据本发明的配置，在关于超椭圆曲线加密术中的除数D的标量乘法中，执行包括二等分的计算运算作为计算处理，并且应用用于减少在二等分计算处理中所执行的倒数运算的数量的算法，从而使得能够进一步降低除数的标量乘法的复杂度因此产生更快的计算。图1是示出用于在亏格为2的曲线上在超椭圆曲线加密术中在标量乘法中的加法和加倍的处理的算法的示意图；图2是示出在亏格为2的曲线上在超椭圆曲线加密术中在逐情况的基础上如何对加倍运算进行分化的示意图；图3是示出HEC_HLV的算法的流程图；图4是示出HEC_HLV2→1+1的算法的流程图；图5是示出HEC_HLV2→2+2的算法的流程图；图6是示出HEC_HLV1→2+2的算法的流程图；图7是示出执行根据本发明的加密计算的加密系统的功能配置的框图；和图8是示出IC模块的配置的例子的示意图，该IC模块作为执行根据本发明的加密计算的加密处理执行装置的例子。具体实施例方式下面将参照附图详细描述根据本发明的加密系统和加密计算方法以及计算机程序。本发明提供关于HECC(超椭圆曲线加密术)的快速计算方法，HECC表示椭圆曲线加密术的推广。如上所述，在超椭圆曲线的情况中，将曲线定性的值是亏格g。假设p代表素数，n代表正整数，并且q＝pn。在这种情况下，由下面等式来表示作为亏格g的曲线的在有限域Fq上所定义的超椭圆曲线Cy2+h(x)y＝f(x)其中h(x)，f(x)∈Fq[x]，f(x)是2g+1次的首一多项式。将在超椭圆曲线C上与点P＝(x，y)相对的点-P定义为-P＝(x，y+h(x))。将P＝-P的点称为分歧点。众所周知，假设与椭圆曲线加密术相同等级的安全性，可以将超椭圆曲线加密术的定义域的处理规模(或者位数)减少到椭圆曲线加密术的定义域的处理规模的1/g。从实施的角度来说，小处理规模是有利的，这是超椭圆曲线加密术的一个优点。下面，将描述超椭圆曲线加密术的基本原理。如上所述，在超椭圆加密术中，可以将从D2中求解k的问题当作在超椭圆曲线上的雅可比簇中的离散对数问题，因此可以将该问题当作公共密钥加密术中的问题对待，其中D1是与点的形式和相等的除数，而D2是被定义位标量乘法kD1的除数。在这种情况中，除数等于点的形式和并且可以用下面形式表示[公式7]D=ΣimiPi]]>进一步，可以由下面形成表示减半的除数[公式8]D=ΣimiPi-(Σimi)P∞,mi≥0]]>然而，对于Pi＝(xi，yi)和i≠j，关系Pi≠Pj为真。将上面等式中的∑mi称为除数D的权重。进一步，将具有不超过亏格g的权重的减半的除数称为减小的除数。使用多项式U和V∈Fq[x]，可以将在超椭圆曲线上在雅可比簇上的减半的除数D表示为D＝(U，V)。可以将该表达式称为Mumford表达式。U=Π(x-xi)mi]]>V(xi)＝yiV(x)2+V(x)h(x)-f(x)≡0modU(x)，degV＜degU通过使用Mumford表达式，可以由多项式的集合来表示针对亏格为2的减小的除数D，所述多项式的每一个都具有在该多项式的系数中所设定的有限域上的元素并且具有不超过2的阶数。也就是，可以将减小的除数表示为(U，V)＝(x2+u1x+u0，v1x+v0)，or(U，V)＝(x+x0，y0)。进一步，将零元素表示为(U，V)＝(1，0)＝O。根据本发明，将在椭圆曲线加密术中的二等分运算扩展到超椭圆曲线加密术中，并且找到允许比加倍运算更快的计算的算法、曲线参数和定义域，从而实现将比加倍运算更快的二等分运算应用到超椭圆曲线加密术中的计算处理。下面，将把对本发明的实施方式的描述组织到两个部分中。首先，将在第一部分中描述根据处理示例1到6的技术。(处理示例1提出的方法A1)计算在带有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分的方法。(处理示例2提出的方法F1)计算在带有参数h(x)＝x2+h1x+h0，f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分的方法。(处理示例3提出的方法B1)计算在带有参数h(x)＝x2+x+h0，f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分的方法。(处理示例4提出的方法E1)计算在带有参数h(x)＝x的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分的方法。(处理示例5提出的方法C1)当计算在带有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分时，产生所二等分指的两个候选者，在带有参数h(x)＝x2+h1x+h0，f4＝0的特征为2下、亏格为2的超椭圆曲线、和在带有参数h(x)＝x2+x+h0，f4＝0的特征为2下、亏格为2的超椭圆曲线。在这种情况下，需要从两个候选者中选择带有正确值的一个。当选择正确的一个时，需要计算轨迹、乘法和有限域的平方根。两个候选者中的哪一个是正确的取决于除数D。因此，如果除数D固定，则事先在表中保留关于两个候选者中的哪一个正确的信息，并且当选择正确值时对该表进行查询，从而省略上述额外的计算。(处理示例6提出的方法D1)通过使用在处理示例1到5的每一个中所述的计算除数的二等分的方法来计算除数的标量乘法的方法。进一步，第二部分涉及对下面技术的描述，该技术显示出对处理示例1到3和处理示例5和6的改进。(处理示例7提出的方法A2)计算在带有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分的方法。(处理示例8提出的方法F2)计算在带有参数h(x)＝x2+h1x+h0，f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分的方法。(处理示例9提出的方法B2)计算在带有参数h(x)＝x2+x+h0，f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分的方法。(处理示例10提出的方法C2)当计算在带有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分时，产生所二等分指的两个候选者，在带有参数h(x)＝x2+h1x+h0，f4＝0的特征为2下、亏格为2的超椭圆曲线、和在带有参数h(x)＝x2+x+h0，f4＝0的特征为2下、亏格为2的超椭圆曲线。在这种情况下，需要从两个候选者中选择带有正确值的一个。当选择正确的一个时，需要计算轨迹、乘法和有限域的平方根。两个候选者中的哪一个正确的取决于除数D。因此，如果除数D固定，则事先在表中保留关于两个候选者中的哪一个正确的信息，并且当选择正确值时对该表进行查询，从而省略上述额外的计算。(处理示例11提出的方法D2)通过使用在处理示例7到10的每一个中所述的计算除数的二等分的方法来计算除数的标量乘法的方法。将在下面顺序地详细描述上述的各个处理示例。处理示例1(提出的方法A1)涉及计算在带有随机参数的特征为2中在亏格为2的超椭圆曲线上的除数D的二等分的方法。进一步，假设在下面处理中所使用的除数的阶数为r。也就是，除数不具有分歧点。假设输入除数如下D2＝(U2，V2)；U2＝u22x2+u21x+u20；和V2＝v21x+v20，其中如果除数D2的权重为2则u22＝1；和如果除数D2的权重为1则u22＝1，u21＝1，和v21＝0。由于不包括分歧点，所以作为二等分运算，足以考虑四种倒数运算ExHarDBL1+1→2、ExHarDBL2+2→1、ExHarDBL2+2→2、和HarleyDBL。除了HarleyDBL之外的那些代表例外情况。这里，ExHarDBL2+2→1代表这种情况中的计算输入除数的权重为2，并且输出除数的权重为1。进一步，ExHarDBL2+2→2代表这种情况中的计算输入除数的权重为2，而且U2的第一次项的系数满足u21＝0并且输出除数的权重为2。然而，当通过HarleyDBL计算ExHarDBL2+2→2时，由于作为其倒数运算的二等分变为例外情况，所以这里将ExHarDBL2+2→2当作例外情况对待。将与上述ExHarDBL1+1→2、ExHarDBL2+2→1、ExHarDBL2+2→2和HarleyDBL对应的二等分运算分别定义为ExHEC_HLV2→1+1，ExHEC_HLV1→2+2、ExHEC_HLV2→2+2和HEC_HLV。当执行除数的二等分运算时，首先，根据图2中所示的输入除数进行逐情况的分化。如果输入除数的权重为2，并且U2的第一次项的系数满足u21≠0，则通过HEC_HLV执行计算。进一步，如果输入除数的权重为2，并且U2的第一次项的系数满足u21＝0，则通过ExHEC_HLV2→2+2或者ExHEC_HLV2→1+1来执行计算。进一步，如果输入除数的权重为1，则通过ExHEC_HLV1→2+2来执行计算。将参照图3来描述HEC_HLV的算法。图3是示出HEC_HLV的算法的流程图。在步骤S101中，将输入定义如下D2＝(U2，V2)；U2＝x2+u21x+u20；和V2＝v21x+v20。在步骤S102中，求出的k1h2+k12u21+1＝0的根k1、k1′，并且在步骤S103中，设定c1←f3+h2v21+u20+(f4+u21)u21。在步骤S104中，确定k1h0+k0h1+k02u21+c1＝0是否具有根。如果其不具有根，则在步骤S105设定k1←k1′，而如果其具根，则流程前进到步骤S106，在其中求出k1h0+k0h1+k02u21+c1＝0的根k0、k0′。随后，流程前进到步骤S107，在其中计算u11并且在步骤S108中确定xh2+x2u11+1＝0是否有根。如果其没有根，则在步骤S109中设定k0←k0′，而如果其有根，则流程前进到步骤S110，在其中计算u10。进一步，在步骤S111中，计算v11、v10，并且在步骤S112中，通过进行下面设定U1←x2+u11x+u10；heV1←v11x+v10，并且在步骤S113中，获得输出D1←(U1，V1)。通过执行除数的加倍运算(也就是，下面的算法1[Algorithm1HarleyDBL])的算法的逆运算来实现除数的二等分运算，[公式10]Algorithm1HarleyDBLInputD1＝(U1，V1)OutputD2＝(U2，V2)Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，U1)＝11.U1′←U122.S←h-1(f+hV1+V12)/U1modU13.V1′←SU1+V14.U2′←(f+hV1′+V1′2)/U′5.U2←MakeMonic(U2′)6.V2←V1′+hmodU27.returnD2＝(U2，V2)在算法1的步骤6中，存在唯一的多项式k(x)＝k1x+k0，其满足V1′+h＝(k1x+k0)U2+V2。将其进行下面变换V1′＝h+(kix+k0)U2+V2。将其代入步骤4中出现的表达式中，(f+hV1′+V1′2)，产生下面结果U2′U1＝f+h(kU2+V2)+k2U22+V22表达式(1)在上面的表达式中，由于(U2，V2)已知，所以从表达式(1)中可以获得k和U1′之间的关系表达式。在这种情况下，应该注意U2＝k12U2。将上面表达式(1)进行扩展并且重新排列以产生下面的表达式U1′＝x4+((k1h2+k12u21+1)/k12)x3+((k1h1+k0h2+k12u20+k02+c2)/k12)x2+((k1h0+k0h1+k02u21+c1)/k12)x+(k0h0+k02u20+c0)/k12表达式(2)这里，满足c2＝f4+u21，c1＝f3+h2v21+u21+c2u21，和c0＝f2+h2v20+h1v21+v212+c2u20+c1u21。进一步，从步骤1，U1′＝U12，也就是，下面表达式成立U1′＝x4+u112x2+u102表达式(3)通过比较上述表达式(2)和(3)的相应系数以得出关系表达式，并且可以通过解这个关系表达式来计算二等分运算。将描述上述过程的算法在下面作为算法4示出[Algorithm4概略(sketch)HEC_HLV][公式11]Algorithm4SketchHEC_HLVInputD2＝(U2，V2)OutputD1＝(U1，V1)＝[1/2]D2Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.reconstructk0，k11.1V1′←V2+h+kU2，k(x)＝k1x+k01.2U1′←(f+hV1′+V1′2)/(k12U2)1.3derivek0，k1fromcoeff(U1′，3)＝0，coeff(U1′，1)＝02.computeu11bysubstitutingk0，k1incoeff(U1′，2)3.computeu10bysubstitutingk0，k1incoeff(U1′，0)4.U1←x2+u11x+u105.V1←V2+h+kU2modU16.returnD1＝(U1，V1)具体地说，可以获得下面关系表达式。k1h2+k12u21+1＝0表达式(4)k1h0+k0h1+k02u21+c1＝0表达式(5)u11=k1h1+k0h2+k12u20+k02+c2/k1]]>表达式(6)u10=k0h0+k02u20+c0/k1]]>表达式(7)需要从这些关系表达式中计算k0、k1的正确值。可以使用下面所述的引理(lemma)来对其进行计算。假设h(x)是不可约多项式。在这种情况下，仅仅存在一个满足表达式(4)和(5)的k1。进一步，表达式(5)具有仅仅关于正确k1的根。进一步，仅仅存在一个允许在算法4中被二等分的除数D1的计算的k0。进一步，下面表达式xh2+x2u11+1＝0具有仅仅针对正确k0的根。将上述引理1应用于算法4。将二等分的详细计算方法作为下面算法5[Algorithm5概略(sketch)HEC_HLV]示出。Algorithm5HEC_HLVInputD2＝(U2，V2)OutputD1＝(U1，V1)＝[1/2]D2Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.Solvek1h2+k12u21+1＝0α←h2/u21，γ←1/(u21α2)/*1/(u21α2)＝u21/h22*/k1←H(γ)α，k1′←k1+α2.Selectcorrectk1bysolvingk1h0+k0h1+k02u21+c1＝0c2←f4+u21，c1←f3+h2v21+u20+c2u21c0←f2+h2v20+h1v21+v212+c2u20+c1u21α←h1/u21，γ←(c1+k1h0)/(u21α2)ifTr(γ)＝1thenk1←k1′，γ←(c1+k1h0)/(u21α2)k0←H(γ)α，k1′←k1+α3.Selectcorrectk0bycheckingtraceofxh2+x2u11+1＝0u11←k1h1+k0h2+k12u20+k02+c2/k1,]]>γ←u11/h22ifTr(γ)＝1thenk0←k0′，u11←k1h1+k0h2+k12u20+k02+c2/k1]]>4.ComputeU1u10←k0h0+k02u20+c0/k1]]>5.ComputeV1＝V2+h+kU2modU1w←h2+k1u21+k0+k1u11v11←v21+h1+k1u20+k0u21+u10k1+u11wv10←v20+h0+k0u20+w6.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)在上述算法5[Algorithm5]中，如果k1′、k0′是正确值(换句话说，如果k1、k0不是正确值)，则该算法的复杂度为32M+5S+6I+3SR+2H+2T。这里，M、S、I、SR、H和T分别表示乘法、平方、倒数、平方根运算、半迹(half-trace)(用于找到二次等式的根的运算)和迹(确定二次方程的根是否存在)。如果这些k1′、k0′是正确的值，则复杂度变得最大。随后，如果k1、k0是正确的值(换句话说，如果k1′、k0′不是正确的值)，则复杂度变得最小，所以在步骤2中可以将复杂度以2M减小，并且在步骤3中可以以2M+1SR将复杂度减小。也就是说，在这种情况中的复杂度是28M+5S+6I+2SR+2H+2T，并且复杂度变为最小。之后，如果k1、k0′是正确值(换句话说，如果k1′、k0不是正确的值)，则在步骤3中可以以2M+1SR降低复杂度。也就是，在这种情况下复杂度变为30M+5S+6I+2SR+2H+2T。最后，如果k1′、k0是正确的值(换句话说，如果k1、k0′不是正确的值)，则在步骤2中可以以2M来减小复杂度。也就是，在这种情况下复杂度变为30M+5S+6I+3SR+2H+2T。当通过计算机试验检查上述四种情况发生的概率时，确认了它们以基本上相同的比例发生。在下面的描述中，假设上述四种情况发生的概率基本相等。将在上述四种情况中的复杂度进行平均得出30M+5S+6I+2.5SR+2H+2T。下面，将考虑下面的例外情况ExHEC_HLV2→1+1；ExHEC_HLV1→2+2和ExHEC_HLV2→2+2。由于这些例外情况发生的概率低到可以被忽略的程度，所以将不进行关于复杂度的评估。首先，将参照图4的流程来描述ExHEC_HLV2→1+1的算法。通过ExHarDBL1+1→2的逆运算来实现ExHEC_HLV2→1+1。假设ExHarDBL1+1→2的输入除数是D1＝(U1，V1)，U1＝x+u10，V1＝v10，输出除数D2＝(U2，V2)＝2D1，U2＝x2+u20x，V2＝v21x+v20，可以被计算如下U2＝x2+u20＝(x+u10)2，v12＝(u104+f3u102+f1+h1v10)/h(u10)，和v20＝v10+v21u10。使用这些关系表达式，计算ExHEC_HLV2→1+1。让输入除数为D2＝(U2，V2)，U2＝x2+u20x，V2＝v21x+v20(图4的流程步骤S201)。为了获得输出除数D1＝(U1，V1)＝[1/2]D2，U1＝x+u10，V1＝v10，在步骤S202中，使得u10＝√u20，并且在步骤S203中，使得v10＝(v21h(u10)+u104+f3u102+f1)/h1，并且在步骤S204中，使得U1＝x+u10，V1＝v10。然后，在步骤S205中，获得输出除数D1＝(U1，V1)。随后，将参照图5的流程来描述ExHEC_HLV2→2+2的处理过程。在步骤S301，将输入除数假设为D2＝(U2，V2)，U2＝x2+u20，V2＝v21x+v20。在步骤S302，关于k1解k1h2+1＝0以得出k1←1/h2。在步骤S303，使得c2←f4，和c1←f3+h2v21+u20+u21c2，并且在步骤S304，关于k0解k1h0+k0h1＝0以给出k0←(k1h0+c1)/h1。随后，在步骤S305中，计算u11，并且在步骤S306中，确定xh2+x2u11+1＝0是否具有根。如果其不具有根，则在步骤S307中，通过D1←HEC_HLV2→1(D2)来确定输出D1(步骤S308)。在另一方面，如果xh2+x2u11+1＝0有根，则流程前进到步骤S309，在其中计算u10，并且进一步在步骤S310中，计算v11、v10。然后，在步骤S311中，使得U1←x2+u11x+u10，和V1←v11x+v10，并且在步骤S312中，获得输出D1←(U1，V1)。通过下面过程具体地执行ExHEC_HLV2→2+2的处理。假设输入除数为D2＝(U2，V2)，U2＝x2+u20，V2＝v21x+v20如果U2＝x2+u20，也就是，如果U2的第一次项为0，则存在两个输出除数候选者，将它们表示为D1＝(x+u20，V2(u20))，和D1′＝(x2+u11x+u10，v11x+v10)。如果D1是正确的，则使用ExHEC_HLV2→1+1来执行计算。如果D1′是正确的，则使用ExHEC_HLV2→2+2来执行计算。根据下面过程来进行关于要使用哪个算法的确定。1.假设D1′是正确的。2.计算u11。3.计算xh2+x2u11+1＝0的迹Tr(h2/u112)。如果Tr(h2/u112)＝0，则D1′是正确的，所以使用ExHEC_HLV2→2+2来执行计算。否则，也就是，如果Tr(h2/u112)＝1，则是D1正确的，所以使用ExHEC_HLV2→1+1来执行计算。将ExHEC_HLV2→2+2的计算算法作为算法6[Algorithm6]在下面示出。Algorithm6ExHEC_HLV2→2+2InputD2＝(U2，V2)＝(x2+u20，v21x+v20)OutputD1＝(U1，V1)＝(x2+u11x+u10，v11x+v10)＝[1/2]D2gcd(h，Ui)＝1，i＝1，21.Solvek1h2+1＝0k1←1/h22.Selectcorrectk1bysolvingk1h0+k0h1+k02+c1＝0c2←f4，c1←f3+h2v21+u20+c2u21c0←f2+h2v20+(h1+v21)v21+c2u20+c1u21k0←(k1h0+c1)/h13.Selectcorrectalgorithmbycheckingtraceofxh2+x2u11+1＝0u11←k1h1+k0h2+k12u20+k02+c2/k1,γ←u11/h22]]>ifTr(γ)＝1thenD1←ExHEC_HLV2→1+1(D2)，returnD14.ComputeU1u10←k0h0+k02u20+c0/k1]]>5.ComputeV1＝V2+h+kU2modU1w←h2+k1v11←h1+k1u20+k0+u11wv10←v20+h0+k0u20+u10w6.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)下面，将参照图6来描述ExHEC_HLV1→2+2的处理过程。在步骤S401中，假设输入除数为D2＝(U2，V2)；U2＝x+u20；和V2＝v20。在步骤S402中，使得c3←f4+u20，并且在步骤S403中，求出的k1h2+k12u21+c3＝0的根k1、k1′，并且在步骤S404中，使得c1←f3+c3u20，和c1←f2+h2v20+c2u20，并且在步骤S405中，确定k1h0+k0h1+k02+c1＝0是否有根。如果其没有根，则在步骤S406中设定k1←k1′之后流程前进到步骤S407，而如果其有根，则流程就原样前进到步骤S407。在步骤S407中，求出k1h0+k0h1+k02+c1＝0的根k0，k0′。然后，流程前进到步骤S408，其中计算u11并且在步骤S409中，确定xh2+x2u11+1＝0是否有根。如果其没有根，则在步骤S410中设定k0←k0′之后流程前进到步骤S411，而如果其有根，则流程原样前进到步骤S411，并且计算u10。进一步，在步骤S412中，计算v11、v10。在步骤S413中，使得U1←x2+u11x+u10，和V1←v11x+v10，并且在步骤S414中，获得输出D1←(U1，V1)。虽然ExHEC_HLV1→2+2的计算过程于HEC_HLV的计算过程类似，但是在输入除数的权重方面存在很大不同。因此，ExHEC_HLV1→2+2的f+hV1′+V1′2变为五次首一多项式(quinticmonicpolynomial)。因此，与在HEC_HLV的情况中不同，U1′←(f+hV1′+V1′2)/U2不除以k12。将ExHEC_HLV1→2+2的计算算法如下示出[Algorithm7]。Algorithm7ExHEC_HLV1→2+2InputD2＝(U2，V2)＝(x+u20，v20)OutputD1＝(U1，V1)＝(x2+u11x+u10，v11x+v10)＝[1/2]D2gcd(h，Ui)＝1，i＝1，21.Solvek1h2+k12u21+c3＝0c3←f4+u20，α←h2，γ←c3/(u21α2)k1←H(γ)α，k1′←k1+α2.Selectcorrectk1bysolvingk1h0+k0h1+k02+c1＝0c2←f3+c3u20，c1←f2+h2v20+c2u20，c0←f1+h1v20+c1u20α←h1，γ←(c1+k1h0)/α2ifTr(γ)＝1thenk1←k1′，γ←(c1+k1h0)/α2k0←H(γ)α，k1←k1+α3.Selectcorrectk0bycheckingtraceofxh2+x2u11+1＝0u11←k1h1+k0h2+k12u20+c2,γ←u11/h22]]>ifTr(γ)＝1thenk0←k0′,u11←k1h1+k0h2+k12u20+c2]]>4.ComputeU1u10←k0h0+k02u20+c0]]>5.ComputeV1＝V2+h+kU2modU1w←h2+k1v11←h1+k1u20+k0+u11wv10←v20+h0+k0u20+u10w6.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)[处理示例2提出的方法F1]处理示例2[提出的方法F1]涉及计算在带有参数h(x)＝x2+h1x+h0，f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分。对算法5的仔细研究将揭示算法5包含大量通过系数h(x)的乘法运算以及系数h(x)的倒数运算。这意味着可以通过操控系数h(x)来减小乘法和倒数运算的复杂度。应该注意，根据文献(非专利文献19T.Lange.EfficientDoublingonGenusTwoCurvesoverBinaryFields，SAC2004，pre-proceedings，pp.189-202，2004)，使用h2＝1，f4＝0来实现快速计算。在使用这些参数的情况下HarleyDBL的复杂度为21M+5S+1I。虽然也与上述的那些一致地设定这里所描述的处理示例2(提出的方法2)的条件，但是由于因为引理1导致针对h(x)假设不可约的多项式，所以假设h(x)＝x2+h1x+h0，和Tr(h0/h12)＝1(二次方程ax2+bx+c＝0为不可约多项式的充分必要条件是Tr(ac/b2)＝1)。在这种情况中的计算方法在算法8[Algorithm8]HEC_HLV(h2＝1，f4＝0)中示出。Algorithm8HEC_HLV(h2＝1，f4＝0)InputD2＝(U2，V2)，invu＝1/u21，1/h12OutputD1＝(U1，V1)＝[1/2]D2，invu＝1/u11Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.Solvek1+k12u21+1＝0α←invu，k1←H(u21)α，k1′←k1+α2.Selectcorrectk1bysolvingk1h0+k0h1+k02u21+c1＝0c1←f3+v21+u20+u212c0←f2+v20+v21(h1+v21)+u21(u20+c1)w0←u21/h12，α←h1α，γ←(c1+k1h0)w0ifTr(γ)＝1thenk1←k1′，γ←(c1+k1h0)w0k0←H(γ)α，k0′←k0+α3.Selectcorrectk0bycheckingtraceofx+x2u11+1＝0w0←k12，w1←w0u20+k1h1+u21w2←k0+w1+k0,]]>w3←k0′+w1+k0′,]]>w4←w2w3w1←1/(w4k1)，w4←w1w4，u11←w2w4ifTr(γ)＝1thenk0←k0′，u11←w3w4，w2w3invu←w0w1w34.ComputeU1w1←k0u20，w5←k1u21，w6←(k0+k1)(u20+u21)u10←w4k0(w1+h0)+c0]]>5.ComputeV1＝V2+h+kU2modU1w4←w5+k0+1，w5←w1+w5+w6+v21+h1w6←w1+v20+h0，w7←k1u11+w4w1←w7u10，w3←(k1+w7)(u10+u11)v11←w1+w3+w4+w5+w7v10←w1+w66.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)，invu进一步，为了消除倒数运算的数量，使用所谓Montgomery技巧(trick)的技术。根据该技术，例如，当需要找到三个有限域元素a、b和c的倒数时，首先，找到这三个元素的积，并且找到其倒数为w＝1/(a*b*c)等。然后，为了找到a的倒数，计算w*b*c。类似地，对于b、c的倒数，分别计算w*a*c和w*a*b。通常，倒数运算的复杂度比乘法运算的复杂度高几倍(如将在后面描述的，软件实施的结果指示找到倒数的复杂度大约比乘法运算高8倍)。因此，为了找到三个元素的倒数，例如，如果以直接的方式执行三次倒数运算，假设I＝8M，则所产生的复杂度是24M。相反地，如果使用上述Montgomery技巧，则所产生的复杂度为I+8M＝16M，因此使得比三个倒数运算更快的计算成为可能。根据所述的处理例子2(提出的方法F1)，使用这种Montgomery技巧来求u11的倒数。给出u11的倒数作为随后二等分运算的输入。因此，算法8允许[1/2i]D的计算，并且当执行除数D的标量乘法时，可以将算法8应用于右到左方法，也就是，加入[1/2i]D的方法。将在后面描述使用二等分运算的标量乘法。进一步，此时所需要的复杂度如下。(a)如果k1，k0是正确的值24M+2S+1I+3SR+2H+2T(b)如果k1，k0′是正确的值26M+2S+1I+3SR+2H+2T(c)如果k1′，k0是正确的值25M+2S+1I+3SR+2H+2T(d)如果k1′，k0′是正确的值27M+2S+1I+3SR+2H+2T将所有上述情况(a)到(d)进行平均产生25.5M+2S+1I+3SR+2H+2T。HarleyDBL的复杂度为21M+5S+1I。这里，根据文献(非专利文献15)E.Knudsen.EllipticScalarMultiplicationUsingPointHalving.ASIACRYPTO′99，LNCS1716，pp.135-149，Springer-Verlag，1999.]，已知当以正规基(normalbasis)定义有限域时，可以忽略S(平方)、SR(平方根运算)、H(半迹(用于找到二次等式的根的运算))和T(迹(确定二次等式是否存在根))的复杂度，并且仅仅需要考虑M(乘法)和I(倒数)的复杂度。因此，当使用正规积时，算法8比HarleyDBL慢4.5M。进一步，当以多项式基(polynomialbasis)来定义有限域时，根据文献(非专利文献16)K.Fong，D.Hankerson，J.Lopez，andA.Menezes.Fieldinversionoperationandpointhalvingrevised.TechnicalReportCORR2003-18，http//www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf18]，已知与M(乘法)的复杂度相比较，通常SR(平方根运算)和H(半迹(用于找到二次方程的根的运算))是大约SR＝H＝0.5M。进一步，可以忽略T(迹(确定针对二次等式是否有根))的复杂度。进一步，已知S(平方)的复杂度仅仅大约是M(乘法)的十分之几。然而，还已知根据选择多项式基的方式，SR的复杂度可以变为小于0.5M。应该注意，可以根据上述处理示例1(提出的方法A1)中的例外情况来计算例外情况。处理示例3(提出的方法B1)涉及计算带有参数h(x)＝x2+x+h0、f4＝0的特征为2中在亏格为2的超椭圆曲线上的除数D的二等分的方法。如参照上述处理示例2(提出的方法F1)已经描述的那样，对参照处理示例1(提出的方法A1)所描述的二等分的计算算法的仔细研究，也就是，算法5[Algorithm5HEC_HLV]揭示算法5包含大量系数h(x)的乘法运算和系数h(x)的倒数运算。这意味着可以通过操控系数h(x)来减少乘法和倒数运算的复杂度。在文档[J.Pelzl，T.Wollinger，J.Guajardo，andC.Paar.HyperellipticcurveCryptosystemsClosingthePerformanceGaptoEllipticCurves.CryptologyePrintArchive，2003/026，IACR，2003]中，公开了使用h2、h1∈{0，1}、f4＝0来实现快速计算的例子。在使用这些参数的情况下HarleyDBL的复杂度为18M+7S+1I。虽然也与上述的那些一致地设定处理示例3(提出的方法B1)的条件，但是由于因为上述引理1所以针对h(x)假设不可约多项式，因此设定h(x)＝x2+x+h0，和Tr(h0)＝1(二次方程ax2+bx+c＝0为不可约的充分和必要条件为Tr(ac/b2)＝1)。将这种情况下的计算方法在下面作为算法10[Algorithm10HEC_HLV(h2＝h1＝1，f4＝0)]示出。Algorithm10HEC_HLV(h2＝h1＝1，f4＝0)InputD2＝(U2，V2)，invu＝1/u21OutputD1＝(U1，V1)＝[1/2]D2，invu＝1/u11Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.Solvek1+k12u21+1＝0α←invu，k1←H(u21)α，k1′←k1+α2.Selectcorrectk1bysolvingk1h0+k0+k02u21+c1＝0c1←f3+v21+u20+u212c0←f2+v20+v21+v212+u21(u20+c1)γ←(c1+k1h0)u21ifTr(γ)＝1thenk1←k1′，γ←γ+h0k0←H(γ)α，k0′←k0+α3.Selectcorrectk0bycheckingtraceofx+x2u11+1＝0w0←k12，w1←w0u20+k1+u21w2←k0+w1+k0,w3←k0′+w1+k0′,w4←w2w3]]>w1←1/(w4k1)，w4←w1w4，u11←w2w4ifTr(u11)＝1thenk0←k0′，u11←w3w4，w2w34.ComputeU1w0←w0w1，w1←k0u20，w5←k1u21，w6←(k0+k1)(u20+u21)u10←w4k0(w1+h0)+c0]]>5.ComputeV1＝V2+h+kU2modU1w4←w5+k0+1，w5←w1+w5+w6+v21+1，w6←w1+v20+h0invu←w0w3w0←w2+w4，w1←w0u10，w3←(k0+k1)(u10+u11)v10←w1+w2+w3+w5v11←w1+w66.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)，invu进一步，为了消除倒数运算的数量，如在上述处理示例2(提出的方法F1)中一样，使用Montgomery技巧来求u11的倒数。将给出u11的倒数作为随后二等分运算的输入。根据这种处理示例的复杂度如下。(a)如果k1，k0是正确的值19M+3S+1I+3SR+2H+2T(b)如果k1，k0′是正确的值20M+3S+1I+3SR+2H+2T(c)如果k1′，k0是正确的值19M+3S+1I+3SR+2H+2T(d)如果k1′，k0′是正确的值20M+3S+1I+3SR+2H+2T将所有上述情况(a)到(d)进行平均得出19.5M+3S+1I+3SR+2H+2T。HarleyDBL的复杂度为18M+7S+1I。这里，如上所述，根据文献[(非专利文献15)E.Knudsen.EllipticScalarMultiplicationUsingPointHalving.ASIACRYPTO′99，LNCS1716，pp.135-149，Springer-Verlag，1999]，已知当以正规基定义有限域时，可以忽略S(平方)、SR(平方根运算)、H(半迹(用于找到二次方程的根的运算))和T(迹(确定二次方程是否存在根))的复杂度，并且仅仅需要考虑M(乘法)和I(倒数)的复杂度。因此，当使用正规积时，上述算法10[Algorithm10]比传统算法[HarleyDBL]慢1.5M。进一步，当以多项式基来定义有限域时，根据文献[K.Fong，D.Hankerson，J.Lopez，andA.Menezes.Fieldinversionoperationandpointhalvingrevised.TechnicalReportCORR2003-18，http//www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf18]，已知通常SR和H是大约SR＝H＝0.5M。进一步，可以忽略T的复杂度。进一步，已知S的复杂度仅仅大约是M的十分之几。然而，还已知根据选择多项式基的方式，SR的复杂度可以变为小于0.5M。上述算法10[Algorithm10]的曲线还要受到h0＝1的约束。由于通过设定为h0＝1，上述算法10[Algorithm10]涉及h0的一个乘法运算，可以以1M减小该复杂度。通过将所有上述情况(a)到(d)进行平均所得出的复杂度为18.5M+3S+1I+3SR+2H+2T。在另一方面，HaryleyDBL的复杂度为15M+7S+11。应该注意，可以根据上述处理示例1(提出的方法A1)中的例外情况来计算例外情况。处理示例4(提出的方法E1)涉及计算在带有参数h(x)＝x的特征为2中在亏格为2的超椭圆曲线上的除数D的二等分的方法。如处理示例3(提出的方法B1)那样，在算法5中，通过设定h(x)＝x，可以减小除数的二等分运算所需要的在有限域上的元素的乘法和倒数运算的复杂度。作为具体的例子，在f(x)＝x5+f1x+f0的情况中的算法在下面作为算法12(Algorithm12)示出。Algorithm12HEC_HLV(h(x)＝x，f(x)＝x5+f1x+f0)InputD2＝(U2，V2)OutputD1＝(U1，V1)＝[1/2]D2Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.Solvek12u21+1＝0w0←1/u21,k1←w0]]>2.Solvek0+k02u21+c1＝0c1←u20+u212，w1←c1u21c0←v21+v212+u21u20+w1invk1←u21,]]>w2←H(w1)，w3←w2+1k0←w0w2，k0′←k0+w03.ComputeU1u11←invk1+k0,u10←(k0+c1)u20+c0u21]]>ifTr(u11(u10+invk1+k0))＝1thenk0←k′0,w2←w3,u11←u11+k1,u10←u10+w0+u20]]>4.ComputeV1＝V2+h+kU2modU1w1←k1(u21+u11)+k0v11←k1(u20+u10)+w2+v21+1+u11w1v10←k0u20+v20+u10w15.U1(x)←x2+u11x+u10，V1(x)←v11x+v106.returnD1＝(U1，V1)如在处理示例3(提出的方法B1)那样，评估上述算法12(Algorithm12)的复杂度。与处理示例3(提出的方法B1)不同，在h(x)＝x类型的超椭圆曲线的情况下，由于在步骤1中唯一地确定k1，所以仅仅存在针对k0的选择步骤(步骤3)。当在步骤3中的if语句中迹为0时，具有最低复杂度的最佳情况发生，而当迹为1时，最差情况发生。由于两者发生的概率相同，所以平均复杂度为11.5M+2S+1I+4.5SR+1H+1T。该复杂度低于上述处理示例3的复杂度，因此实现了快速计算。应该注意，可以根据上述处理例子1(提出的方法A1)中的例外情况来计算例外情况。处理示例5(提出的方法C1)涉及下述方法。也就是，当计算在带有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分时，出现经二等分的值的两个候选者，在带有参数h(x)＝x2+h1x+h0、f4＝0的特征为2下、亏格为2的超椭圆曲线，和在带有参数h(x)＝x2+x+h0、f4＝0的特征为2下、亏格为2的超椭圆曲线。当选择正确的一个时，需要计算有限域的迹、乘法和平方根。两个候选者中哪一个是正确的取决于除数D。因此，如果将除数D固定，则事先将关于两个候选者中哪一个正确的信息保存在表中，并且当选择正确的值时查询该表，从而省略上述额外的计算。k1、k1′(k0，k0′)中的哪一个是正确的依赖于输入除数D。因此，如果将D固定，例如，当作为ECDH密钥交换、ECDSA签名产生或者验证等的阶段1的情况之前确定基点时，计算[1/2i]D并且事先将关于k1、k1′(k0，k0′)中的哪一个正确的信息记录在表中。例如，准备与基点的阶数(order)的相同位大小的两个表T1、T0，并且将这些表的二进制表达式表示为T1＝(t1，r-1，---，t1，0)，和T0＝(t0，r-1，---，t0，0)。当求[1/2i]D时，如果这样的信息存储在表中如果k1是正确的，则t1，i＝0否则如果k1′是正确的，则t1，i＝1；以及如果k0是正确的，则t1，i＝0，否则如果k0′是正确的，则t1，i＝1，，则仅仅大约有基点的阶数的大小两倍的位串作为表大小就足够了。通过查询这些表，可以减小二等分的复杂度。将作为应用到算法8[Algorithm8]HEC_HLV(h2＝1，f4＝0)的上述方法表示为算法9[Algorithm9]HEC_HLV(h1＝1，f4＝0，withtable-lookup)。该算法的复杂度为22M+2SR+1I+2SR+2H。Algorithm9HEC_HLV(h2＝1，f4＝0，table-lookup)InputD2＝(U2，V2)，invu＝1/u21，1/h12，t0，t1OutputD1＝(U1，V1)＝[1/2]D2，invu＝1/u11Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.Solvek1+k12u21+1＝0ift1＝0thenk1←H(u21)invuelsek1←H(u21)invu+invu2.Solvek1h0+k0h1+k02u21+c1＝0c1←f3+v21+u20+u212c0←f2+v20+v21(h1+v21)+u21(u20+c1)α←h1invu，γ←(c1+k1h0)u21/h12ift0＝0thenk0←H(γ)αelsek0←H(γ)α+α3.ComputeU1w0←k12，w1←w0u20+k1h1+u21，w2←k0+w1+k0]]>w1←1/(w2k1)，w3←w1w2u11←w2w3，invu←w0w1w1←k0u20，w5←k1u21，w6←(k0+k1)(u20+u21)u10←w3k0(w1+h0)+c0]]>4.ComputeV1＝V2+h+kU2modU1w4←w5+k0+1，w5←w1+w5+w6+v21+h1w6←w1+v20+h0，w7←k1u11+w4w3←(k1+w7)(u10+u11)，w1←w7u10v11←w1+w3+w4+w5+w7v10←w1+w66.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)，invu具体地说，将作为应用于上述算法10[Algorithm10HEC_HLV(h2＝h1＝1，f4＝0)]的上述方法表示为下面的算法11[Algorithm11HEC_HLV(h2＝h1＝1，f4＝0，withtable-lookup)]。Algorithm11HEC_HLV(h2＝h1＝1，f4＝0，withtable-lookup)InputD2＝(U2，V2)，invu＝1/u21，t0，t1OutputD1＝(U1，V1)＝[1/2]D2，invu＝1/u11Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，U1)＝11.Solvek1+k12u21+1＝0andselectcorrectk1viat1α←invu，k1←H(u21)αift1＝0thenk1←k1+α2.Solvingk1h0+k0+k02u21+c1＝0andselectcorrectk0viat0c1←f3+v21+u20+u212c0←f2+v20+v21+v212+u21(u20+c1)γ←(c1+k1h0)u21k0←H(γ)αift1＝0k0thenk0←k0+α3.ComputeU1w0←k12，w1←w0u20+k1+u21w2←k0+w1+k0]]>w1←1/(w2k1)，w4←w1w2u11←w2w4w0←w0w1，w1←k0u20，w5←k1u21，w6←(k0+k1)(u20+u21)u10←w4k0(w1+h0)+c0]]>5.ComputeV1＝V2+h+kU2modU1w4←w5+k0+1，w5←w1+w5+w6+v21+1，w6←w1+v20+h0invu←w0w0←w2+w4，w1←w0u10，w3←(k0+k1)(u10+u11)w10←w1+w2+w3+w5w11←w1+w66.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)，invu＝1/u11算法11[Algorithm11HEC_HLV(h2＝h1＝1，f4＝0，withtable-lookup)]的复杂度为18M+3S+1I+2SR+2H，并且进一步，通过设定h0＝1，可以以1M来减小复杂度。在这种情况中的复杂度变为17M+3S+1I+2SR+2H。进一步，将作为应用到上述算法12[HEC_HLV(h(x)＝x，f(x)＝x5+f1x+f0]的上述方法表示为下面的算法13[HEC_HLV(h(x)＝x，f(x)＝x5+f1x+f0，withtable-lookup)]。Algorithm13HEC_HLV(h(x)＝x，f(x)＝x5+f1x+f0，withtable-lookup)InputD2＝(U2，V2)，t0OutputD1＝(U1，V1)＝[1/2]D2Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝11.Solvek12u21+1＝0w0←1/u21，k1←w0]]>2.Solvek0+k02u21+c1＝0c1←u20+u212，w1←c1u21c0←v21+v212+u21u20+w1invk1←u21,]]>w2←H(w1)ift0＝0thenk0←w0w2elsek0←w0w2+w0，w2←w2+13.ComputeU1u11←invk1+k0,]]>u10←(k0+c1)u20+c0u21]]>4.ComputeV1＝V2+h+kU2modU1w1←k1(u21+u11)+k0v11←k1(u20+u10)+w2+v21+1+u11w1v10←k0u20+v20+u10w15.U1(x)←x2+u11x+u10，V1(x)←v11x+v106.returnD1＝(U1，V1)上述算法的复杂度为9.5M+3S+1I+3.5SR+1H，因此可以实现更快的计算。处理示例6(提出的方法D1)涉及通过使用在处理示例1到5中的每一个中所述的计算除数的二等分的方法来计算除数的标量乘法的方法。在文献[E.Knudsen.EllipticScalarMultiplicationUsingPointHalving.ASIACRYPTO′99，LNCS1716，pp.135-149，Springer-Verlag，1999]中描述了使用椭圆曲线上的有理点的二等分来计算标量乘法的方法。在该文档中所公开的标量乘法来执行使用超椭圆曲线上的除数的二等分的标量乘法的计算方法。然而，应该注意，使用计算和加入[1/2i]D的右到左方法。将该算法表示为下面算法14[ScalarMultiplication]。Algorithm14ScalarMultiplicationInputD∈J(F2n)suchthat2D≠O,]]>d∈Z，rorderofD，OutputscalarmultiplicationdD2.Σi=0mdi/2i←Σi=0md^i2i-m,di∈{0,1}]]>3.Q←O，R←D，invu←1/u14.forifrom0tomdoifdi＝1thenQ←Q+R(R，invu)←HEC_HLV(R，invu)5.returnQ在上述算法14[Algorithm14ScalarMultiplication]的步骤4中出现的HEC_HLV可以是使用随机曲线的上述算法5[Algorithm5]的HEC_HLV、带有提供给算法8[Algorithm8]的曲线参数的约束h2＝1、f4＝0的HEC_HLV、带有应用于算法8[Algorithm8]的曲线参数的查表方法的HEC_HLV、带有提供给算法10[Algorithm10]的曲线参数的约束h2＝h1＝1、f4＝0的HEC_HLV、带有提供给算法10[Algorithm10]的曲线参数的约束h2＝h1＝h0＝1、f4＝0的HEC_HLV、或者带有应用于算法10[Algorithm10]的曲线参数的查表方法的HEC_HLV。进一步，上述HEC_HLV可以是算法12[Algorithm12]的曲线参数的HEC_HLV、或者带有应用于算法12[Algorithm12]的查表方法的HEC_HLV。下面，找到应用于上述处理示例1到6的每一个的计算的复杂度，并且进行关于计算速度增加的验证。在HEC_HLV(h2＝1，f4＝0)的情况中，所需要的复杂度平均为25.5M+2S+1I+3SR+2H+2T。首先，考虑通过正规基定义有限域的情况。如上所述，当使用正规基时，仅仅考虑M和I的复杂度。根据文献[A.Menezes.EllipticCurvePublicKeyCryptosystems.KluwerAcademicPublishers，1993.]，假设有限域为Fq，q＝2n，一个倒数运算等效于通过下面不等式所计算的乘法运算的数量，也就是[公式23]在这种情况下，w(n-1)表示在n-1的二进制表达式中1的数量。例如，如果n＝83、89、113，则I＝8M，而如果n＝103，则I＝9M。这里，假设I＝8M，则将复杂度HEC_HLV(h2＝1，f4＝0)表示为25.5M+1I＝33.5M。在另一方面，在HarleyDBL的情况中，其复杂度表示为21M+1I＝29M，所以HarleyDBL比HEC_HLV快13％。进一步，当使用查表时，复杂度变为22M+1I＝30M，所以HarleyDBL比HEC_HLV快大约3％。进一步，在HEC_HLV(h2＝h1＝1，f4＝0)的情况中，复杂度平均为19.5M+3S+1I+3SR+2H+2T。在这种情况中，19.5M+1I＝27.5M。在另一方面，在HarleyDBL的情况中，复杂度表示为18M+1I＝26M，所以HarleyDBL比HEC_HLV快5％。进一步，当使用查表方法时，复杂度变为18M+1I＝26M，所以HarleyDBL和HEC_HLV在复杂度方面相等。进一步，HEC_HLV(h2＝h1＝h0＝1，f4＝0)的复杂度平均为18.5M+3S+1I+3SR+2H+2T。在这种情况下，18.5M+1I＝26.5M。在另一方面，在HarleyDBL的情况中，其复杂度为15M+1I＝23M，所以HarleyDBL比HEC_HLV快13％。进一步，当使用查询表方法时，复杂度变为17M+1I＝25M，所以HarleyDBL比HEC_HLV快8％。进一步，通过软件实施针对多项式基的情况执行速度比较。在下面指示的环境下执行软件实施CPUPentiumII300MHxOSRedHat7.3编译程序gcc2.96。分别以下面文档中所公开的方式执行M(乘法)和S(平方)、I(倒数)、SR(平方根运算)和T(迹(确定对于二次等式是否存在根))、和H(半迹)(用于找到二次等式的根的运算)的运算[D.Hankerson，J.Hemandez，andA.Menezes.SoftwareImplementationofEllipticCurveCryptographyoverBinaryFields.CHES2000，LNCS1965，pp.1-24，2000.Algorithm4.6，4.7]；[S.Shantz.FromEuclid′sGCDtoMontgomeryMultiplicationtotheGreatDivide.TR-2001-95，SunMicrosystems，Inc.，2001.]；[K.Fong，D.Hankerson，J.Lopez，andA.Menezes.Fieldinversionoperationandpointhalvingrevised.TechnicalReportCORR2003-18，http//www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf]；and[K.Fong，D.Hankerson，J.Lopez，andA.Menezes.Fieldinversionoperationandpointhalvingrevised.TechnicalReportCORR2003-18，http//www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdfAlgorithm4.7]。关于n＝83、89、113的三个有限域来实施M、S、I、SR、H、T，并且找到对于M的比率。在这种情况下，使用下面的不可约多项式在n＝83的情况中，z83+z7+z4+z2+1＝0；在n＝89的情况中，z89+z38+1＝0；和在n＝113的情况中，z113+z9+1＝0。在相应情况中的复杂度如下。n＝83S/M＝0.12，I/M＝7.96，SR/M＝0.57，H/M＝0.58n＝89S/M＝0.05，I/M＝8.74，SR/M＝0.14，H/M＝0.61n＝113S/M＝0.06，I/M＝8.56，SR/M＝0.10，H/M＝0.50将这些应用到HarleyDBL的复杂度21M+5S+1I，得出下面n＝83HarleyDBL29.56Mn＝89HarleyDBL29.99Mn＝113HarleyDBL29.86M。将这些应用到HEC_HLV(h2＝1，f4＝0)的复杂度25.5M+2S+1I+3SR+2H+2T，得出下面n＝83HEC_HLV(h2＝1，f4＝0)36.57Mn＝89HEC_HLV(h2＝1，f4＝0)35.98Mn＝113HEC_HLV(h2＝1，f4＝0)35.48M。在这种情况下，当n＝83、89、113时，HarleyDBL比HEC_HLV分别快20％、17％、16％。进一步，将这些应用到应用表查询方法的HEC_HLV(h2＝1，f4＝0)的复杂度22M+2S+1I+2SR+2H，得出下面n＝83HEC_HLV(h2＝1，f4＝0withtable-lookup)32.5Mn＝89HEC_HLV(h2＝1，f4＝0withtable-lookup)32.34Mn＝113HEC_HLV(h2＝1，f4＝0withtabIe-lookup)31.88M。在这种情况下，当n＝83、89、113时，HarleyDBL比HEC_HLV分别快9％、7％、6％。进一步，在h2＝h1＝1、f4＝0的情况中，将这些应用到HarleyDBL的复杂度18M+7S+1I，得出下面n＝83HarleyDBL27.4Mn＝89HarleyDBL27.09Mn＝113HarleyDBL26.98M。随后，将这些应用到HEC_HLV(h2＝h1＝1，f4＝0)的复杂度19.5M+3S+1I+3SR+2H+2T，得出下面n＝83HEC_HLV(h2＝h1＝1，f4＝0)30.69Mn＝89HEC_HLV(h2＝h1＝1，f4＝0)30.03Mn＝113HEC_HLV(h2＝h1＝1，f4＝0)29.54M。在这种情况下，当n＝83、89、113时，HarleyDBL比HEC_HLV分别快13％、12％、9％。进一步，将这些应用到应用表查询方法的HEC_HLV(h2＝h1＝1，f4＝0)的复杂度18M+3S+1I+2SR+2H，得出下面n＝83HEC_HLV(h2＝h1＝1，f4＝0withtable-lookup)28.62Mn＝89HEC_HLV(h2＝h1＝1，f4＝0withtable-lookup)28.39Mn＝113HEC_HLV(h2＝h1＝1，f4＝0withtable-lookup)27.94M。在这种情况下，当n＝83、89、113时，HarleyDBL比HEC_HLV分别快4％、5％、3％。进一步，在h2＝h1＝h0＝1、f4＝0的情况下，将这些应用到HarleyDBL的复杂度，15M+7S+1I，得出下面n＝83HarleyDBL23.8Mn＝89HarleyDBL24.09Mn＝113HarleyDBL23.98M。随后，将这些应用到HEC_HLV(h2＝h1h0＝1，f4＝0)的复杂度，18.5M+3S+1I+3SR+2H+2T，得到下面n＝83HEC_HLV(h2＝h1＝h0＝1，f4＝0)29.69Mn＝89HEC_HLV(h2＝h1＝h0＝1，f4＝0)29.03Mn＝113HEC_HLV(h2＝h1＝h0＝1，f4＝0)28.54M。在这种情况下，当n＝83、89、113时，HarleyDBL比HEC_HLV分别快20％、17％、6％。进一步，将这些应用到应用了表查询方法的HEC_HLV(h2＝h1＝h0＝1，f4＝0)的复杂度，17M+3S+1I+2SR+2H，得出下面n＝83HEC_HLV(h2＝h1＝h0＝1，f4＝0withtable-lookup)27.62Mn＝89HEC_HLV(h2＝h1＝h0＝1，f4＝0withtable-lookup)27.39Mn＝113HEC_HLV(h2＝h1＝h0＝1，f4＝0withtable-lookup)26.94M。在这种情况下，当n＝83、89、113时，HarleyDBL比HEC_HLV分别快14％、12％、11％。随后，关于上述算法12[Algorithm12](也就是，[Algorithm12HEC_HLV(h(x)＝x，f(x)＝x5+f1x+f0)])和应用了表查询方法的算法13[Algorithm13](也就是，[Algorithm13HEC_HLV(h(x)＝x，f(x)＝x5+f1x+f0，withtable-lookup)])的每一个，进行与HarleyDBL的比较。的复杂度为11.5M+2S+1I+4.5SR+1H+1T，而[Algorithm13HEC_HLV(h(x)＝x，f(x)＝x5+f1x+f0，withtable-lookup)]的复杂度为9.5M+2S+1I+3.5SR+1H。根据文档[(非专利文档19T.Lange.EfficientDoublingonGenusTwoCurvesoverBinaryFields，SAC2004，pre-proceedings，pp.189-202，2004.)]，HarleyDBL的复杂度为6M+5S+1I。如上所述，当通过正规基定义有限域时，可以忽略S(平方)、SR(平方根)、H(半迹(用于找到二次等式的根的运算)、和T(迹(确定对于二次等式是否存在根))，并且只需要考虑M(乘法)和I(倒数)的复杂度。因此，算法12[Algorithm12HEC_HLV(h(x)＝x，f(x)＝x5+f1x+f0)]的复杂度变为1.5M+2S+1I+4.5SR+1H+1T，＝11.5M+1I。进一步，算法13[Algorithm13HEC_HLV(h(x)＝x，f(x)＝x5+f1x+f0，withtable-lookup)]的复杂度变为9.5M+2S+1I+3.5SR+1H＝9.5M+1I。HarleyDBL的复杂度变为6M+1I。因此，HarleyDBL比HEC_HLV快。如上所述，在曲线参数h2＝h1＝1、f4＝0的情况中，将表查询方法应用到HEC_HLV的情况中的复杂度18M+3S+1I+2SR+2H与HarleyDBL的复杂度18M+7S+1I基本相等，并且表示在等效条件下在HEC_HLV和HarleyDBL之间比较时最快的算法。随后，考虑使用算法14[Algorithm14scalarmultiplication]的标量乘法的复杂度。关于使用允许在等效条件下与HarleyDBL相比较的最快算法的h2＝h1＝1、f4＝0作为参数、并且针对HEC_HVL使用表查询方法的方法，来考虑标量乘法的复杂度。由于步骤1、2对于算法14中的整个标量乘法过程的比率非常小，所以忽略其复杂度。这里，针对正规基和多项式基的两者针对n＝83、89、113的情况考虑复杂度。进一步，假设基点的阶数关于n＝83、89、113分别为165位、177位、225位。进一步，在步骤4的重复部分中，针对基点的阶数的位数进行重复。在文献[T.Lange，Efficientarithmeticongenus2hyperellipticcurvesoverfinitefieldsviaexplicitformulae.CryptologyePrintArchive，2002/121，IACR，2002]中所公开的方式执行除数加法。应该注意，曲线参数为h2＝h1＝1、f4＝0。在这种情况中除数加法所需要的复杂度为21M+3S+1I。假设标量值的二进制表示导致0、1以相等比率出现。将复杂度计算如下((加法的复杂度)/2+(二等分或者加倍的复杂度))x(基点的阶数的位数)。首先，将考虑正规基的情况。假设I＝8M。在h2＝h1＝1、f4＝0的情况中，n＝83加法·加倍6682.5Mn＝89加法·加倍7168.5Mn＝113加法·加倍9112.5M在h2＝h1＝1、f4＝0的情况中，n＝83加法·二等分6930Mn＝89加法·二等分7434Mn＝113a加法·二等分9450M在h2＝h1＝1、f4＝0+表查询方法的情况中(复杂度等于加法·加倍的情况中的复杂度)n＝83加法·加倍6682.5Mn＝89加法·加倍7168.5Mn＝113加法·加倍9112.5M随后，考虑多项式的情况。在h2＝h1＝1、f4＝0的情况中，n＝83加法·加倍6913.5Mn＝89加法·加倍7361.3Mn＝113加法·加倍9333M在h2＝h1＝1，f4＝0的情况中，n＝83加法·二等分7456.35Mn＝89加法·二等分7881.8Mn＝113加法·二等分9909M在h2＝h1＝1、f4＝0+表查询方法的情况中(复杂度与加法·加倍的情况的复杂度相等)n＝83加法·加倍7114.8Mn＝89加法·加倍7591.53Mn＝113加法·加倍9540M如上所述，根据所述本发明的处理示例，将椭圆曲线加密术上的二等分扩展到超椭圆曲线加密术，从而实现快速计算。在使用对超椭圆曲线上的除数的计算的加密计算的情况中，对处理产生较大负载的算术计算是除数的标量乘法。从这个角度来说，根据上述本发明的处理使得标量形成在与现有技术的速度等效的速度上进行计算。结果，即使当使用二等分时，可以在与现有技术的速度等效的速度上处理超椭圆曲线加密术。随后，将描述对于上述处理示例，也就是(处理示例1提出的方法A1)(处理示例2提出的方法F1)(处理示例3提出的方法B1)(处理示例5提出的方法C1)(处理示例6提出的方法D1)显示出改进的处理示例7到11。具体地说，处理示例7到11指的是下面方法。(处理示例7提出的方法A2)目的是进一步增加上述的处理示例(处理示例1提出的方法A1)的运算速度的技术，其包括计算在带有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分。(处理示例8提出的方法F2)目的是进一步增加上述的处理示例(处理示例2提出的方法F1)的运算速度的技术，其包括计算在带有参数h(x)＝x2+h1x+h0、f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分。(处理示例9提出的方法B2)目的是进一步增加上述的处理示例(处理示例2提出的方法B1)的运算速度的技术，其包括计算在带有参数h(x)＝x2+x+h0、f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分。(处理示例10提出的方法C2)目的是进一步增加上述的处理示例(处理示例2提出的方法C1)的运算速度的技术。也就是，当计算在带有随机参数的特征为2下、亏格为2的超椭圆曲线上、在带有参数h(x)＝x2+h1x+h0、f4＝0的特征为2下、亏格为2的超椭圆曲线上和在带有参数h(x)＝x2+x+h0、f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数的二等分时，出现所二等分值的两个候选者。在这种情况下，需要从两个候选者中选择带有正确的值的一个。当选择正确的一个时，需要计算有限域的迹、乘法和平方根。两个候选者中哪一个是正确的依赖于除数D。因此，如果固定除数D，则实现在表中保留关于两个候选者中的哪一个正确的信息，并且当选择正确的值时查询该表，因此省略上述额外的计算。(处理示例11提出的方法D2)目的是进一步增加上述的处理示例(处理示例2提出的方法D1)的运算速度的技术，其包括使用在处理示例7到10的每一个中所述的计算产生的二等分的方法来计算除数的标量乘法。将在下面顺序地详细描述上述各个处理示例。处理示例7(提出的方法A2)涉及目的是进一步增加上述的处理示例(处理示例1提出的方法A1)的运算速度的技术，其包括计算在带有随机参数的特征为2中的亏格为2的超椭圆曲线上的除数D的二等分。也在下面的处理示例中，假设在下面处理中所使用的除数的阶数为r。也就是，除数没有分歧点。假设输入除数如下D2＝(U2，V2)；U2＝u22x2+u21x+u20；和V2＝v21x+v20，其中如果D2的权重为2则u22＝1；和如果D2的权重为1则u22＝1，u21＝1，和v21＝0。由于不包括分歧点，所以作为二等分运算，考虑四种倒数运算，ExHarDBL1+1→2、ExHarDBL2+2→1、ExHarDBL2+2→2和HarleyDBL，就足够了。除了HarleyDBL之外的那些是例外情况。这里，ExHarDBL2+2→1表示在输入除数的权重为2并且输出除数的权重为1的情况下的计算。进一步，ExHarDBL2+2→2表示在输入除数为2，并且U2的第一次项的系数满足u21＝0而且输出除数的权重为2的情况下的计算。然而，虽然可以通过HarleyDBL来计算ExHarDBL2+2→2，但是由于作为其倒数运算的二等分变为例外情况，所以这里将ExHarDBL2+2→2作为例外情况。将与上述ExHarDBL1+1→2、ExHarDBL2+2→1、ExHarDBL2+2→2和HarleyDBL对应的二等分运算分别定义为ExHEC_HLV2→1+1、ExHEC_HLV1→2+2、ExHEC_HLV2→2+2和HEC_HLV。当执行除数的二等分运算时，首先，如上面参照(处理示例1提出的方法A)所描述的那样，如图2所示地根据输入除数进行逐情况的分化。如果输入除数的权重为2，并且U2的第一次项的系数满足u21≠0，则通过HEC_HLV执行继续。进一步，如果U2的该项的系数满足u21＝0，则通过ExHEC_HLV2→2+2或ExHEC_HLV2→1+1来执行计算。进一步，如果输入除数的权重为1，则通过ExHEC_HLV1→2+2来执行计算。HEC_HLV的算法如上面参照图3所述。通过用于执行除数的加倍运算的算法，即下面的[Algorithm1HarleyDBL]，的逆运算来实现除数的二等分运算。Algorithm1HarleyDBLInputD1＝(U1，V1)OutputD2＝(U2，V2)Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，U1)＝11.U1′←U122.S←h-1(f+hV1+V12)/U1modU13.V1′←SU1+V14.U2′←(f+hV1′+V1′2)/U′5.U2←MakeMonic(U2′)6.V2←V1′+hmodU27.returnD2＝(U2，V2)在算法1的步骤6中，存在唯一多项式k(x)＝k1x+k0，其满足V1′+h＝(k1x+k0)U2+V2。将其进行变换如下V1′＝h+(kix+k0)U2+V2。将其带到步骤4中出现的表达式中，(f+hV1′+V1′2)，得出下面U2′U1′＝f+h(kU2+V2)+k2U22+V22表达式(1)。在上述表达式中，由于(U2，V2)已知，所以从表达式(1)中，可以获得k和U1′之间的关系表达式。在这种情况下，应该注意U2＝k12U2。将上述等式(1)进行扩展并且重新排列以产生下式U1′＝x4+((k1h2+k12u21+1)/k12)x3+((k1h1+k0h2+k12u20+k02+c2)/k12)x2+((k1h0+k0h1+k02u21+c1)/k12)x+(k0h0+k02u20+c0)/k12表达式(2)这里，满足c2＝f4+u21，c1＝f3+h2v21+u21+c2u21，和c0＝f2+h2v20+h1v21+v212+c2u20+c1u21。进一步，从步骤1，U1′＝U12。也就是，下面表达式成立U1′＝x4+u112x2+u102表达式(3)通过上述表达式(2)和(3)之间的相应系数的比较得出关系表达式，并且通过解该关系表达式计算二等分运算。将描述上述过程的算法在下面示出作为算法4[Algorithm4SketchHEC_HLV]。Algorithm4SketchHEC_HLVInputD2＝(U2，V2)OutputD1＝(U1，V1)＝[1/2]D2Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.reconstructk0，k11.1V1′←V2+h+kU2，k(x)＝k1x+k01.2U1′←(f+hV1′+V1′2)/(k12U2)1.3derivek0，k1fromcoeff(U1′，3)＝0，coeff(U1′，1)＝02.computeu11bysubstitutingk0，k1incoeff(U1′，2)3.computeu10bysubstitutingk0，k1incoeff(U1′，0)4.U1←x2+u11x+u105.V1←V2+h+kU2modU16.returnD1＝(U1，V1)具体地说，可以获得下面关系表达式。k1h2+k12u21+1＝0表达式(4)k1h0+k0h1+k02u21+c1＝0表达式(5)u11=k1h1+k0h2+k12u20+k02+c2/k1]]>表达式(6)u10=k0h0+k02u20+c0/k1]]>表达式(7)必须从这些关系表达式中计算正确的k0、k1。这可以使用下面描述的引理进行计算。假设h(x)是不可约多项式。在这种情况下，只存在一个满足表达式(4)和(5)的k1。进一步，表达式仅仅针对正确的k1具有根。进一步，只存在允许算法4中的经二等分的除数D1的计算的一个k0。进一步，下面表达式xh2+x2u11+1＝0仅仅针对正确的k0具有根。将上述引理1应用到算法4。将二等分的详细计算方法在下面示出作为算法5a[Algorithm5aSketchHEC_HLV]。Algorithm5aHEC_HLVInputD2＝(U2，V2)OutputD1＝(U1，V1)＝[1/2]D2Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.Solvek1h2+k12u21+1＝0invu←1/u21，invh←1/h22，α←h2invu，γ←u21invhk1←H(γ)α，k1′←k1+α2.Selectcorrectk1bysolvingk1h0+k0h1+k02u21+c1＝0c2←f4+u21，c1←f3+h2v21+u20+c2u21c0←f2+h2v20+h1v21+v212+c2u20+c1u21α←h1invu，w←u21/h12，γ←(c1+k1h0)wifTr(γ)＝1thenk1←k1′，γ←(c1+k1h0)wk0←H(γ)α，k0′←k0+α3.Selectcorrectk0bycheckingtraceofxh2+x2u11+1＝0invk←1/k1，u11←invkk1(h1+k1u2)+k0(h2+k0)+c2,]]>γ←u11invhifTr(γ)＝1thenk0←k0′，u11←u11+invkα(h2+α)]]>4.ComputeU1u10←invkk0(h0+k0u20)+c0]]>5.ComputeV1＝V2+h+kU2modU1w←h2+k1(u11+u21)+k0v11←v21+h1+k1(u10+u20)+k0u21+u11wv10←v20+h0+k0u20+w6.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)在上述算法5a[Algorithm5a]中，如果k1′、k0′是正确的值(换句话说，如果k1、k0不是正确的值)，则该算法的复杂度为29M+1S+4I+3SR+2H+2T。这里，M、S、SR、H和T分别表示乘法、平方、倒数、平方根、半迹(用于找到二次方程的根的运算)和迹(确定针对二次方程是否存在根)。如果这些k1′、k0′是正确的值，则复杂度变为最大。随后，如果k1、k0是正确的值(换句话说，如果k1′、k0′不是正确的值)，则复杂度变为最小，所以在步骤2中可以以2M减小复杂度，并且可以在步骤3中以2M+1SR减小复杂度。也就是，在这种情况中的复杂度为25M+1S+4I+2SR+2H+2T，并且复杂度变为最小。随后，如果k1、k0′是正确的值(换句话说，如果k1′、k0不是正确的值)，则复杂度在步骤3中可以以2M+1SR减小。也就是，在这种情况中的复杂度变为27M+1S+4I+2SR+2H+2T。最后，如果k1′、k0是正确的值(换句话说，如果k1、k0′不是正确的值)，则可以在步骤2中以2M减小复杂度。也就是，在这种情况下的复杂度变为27M+1S+4I+3SR+2H+2T。当通过计算机试验检查上述四种情况发生的概率时，确认它们以基本上相同的比率发生。在下面的描述中，假设上述四种情况发生的概率基本上相同。将上述四种情况的复杂度进行平均得出27M+1S+4I+2.5SR+2H+2T。随后，考虑例外情况ExHEC_HLV2→1+1；ExHEC_HLV1→2+2；和ExHEC_HLV2→2+2由于这四种例外情况发生的概率低到可以被忽略，所以不对复杂度进行评估。应该注意，这些例外情况的计算算法是在上述(处理示例1提出的方法A1)的部分中参照图4到6所示的流程图所描述的那些相同的处理，也就是对于ExHEC_HLV2→1+1的算法，流程图在图4中示出；对于ExHEC_HLV1→2+2的算法，流程图在图5中示出；和对于ExHEC_HLV2→2+2的算法，流程图在图6中示出。进一步，也关于针对ExHEC_HLV2→2+2的计算过程，该处理与在(处理示例1提出的方法A1)的部分中在上面所描述的算法6[Algorithm6]的处理相同，该处理与在(处理示例1提出的方法A1)的部分中在上面所描述的算法7[Algorithm7]的处理相同。处理示例8(提出的方法F2)涉及目的是进一步增加上述的处理示例(处理示例2提出的方法F1)的运算速度的技术，其包括计算在带有参数h(x)＝x2+h1x+h0、f4＝0的特征为2中的亏格为2的超椭圆曲线上的除数D的二等分。对于算法5a的仔细研究应用于上述处理示例(处理示例7提出的方法A2)将揭示算法5a包含大量系数h(x)的乘法运算和系数h(x)的倒数运算。这意味着可以通过操控系数h(x)来降低形成和倒数运算的复杂度。应该注意，根据文献(非专利文献19T.Lange.EfficientDoublingonGenusTwoCurvesoverBinaryFields，SAC2004，pre-proceedings，pp.189-202，2004.)，使用h2＝1、f4＝0来实现快速计算。在使用这些参数的情况下的HarleyDBL的复杂度为21M+5S+1I。虽然与上述那些一致地设定在这里描述的针对处理示例8(提出的方法F2)的条件，但是由于移位引理1导致针对h(x)假设不可约多项式，所以设定h(x)＝x2+h1x+h0，和Tr(h0/h12)＝1(二次方程ax2+bx+c＝0为不可约多项式的充分必要条件是Tr(ac/b2)＝1)。将这种情况中的计算方法在算法8[Algorithm8]HEC_HLV(h2＝1，f4＝0)中示出。Algorithm8aHEC_HLV(h2＝1，f4＝0)InputD2＝(U2，V2)，1/h12OutputD1＝(U1，V1)＝[1/2]D2Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.Solvek1+k12u21+1＝0α←1/u21，k1←H(u21)α，k1′←k1+α2.Selectcorrectk1bysolvingk1h0+k0h1+k02u21+c1＝0c1←f3+v21+u20+u212c0←f2+v20+v21(h1+v21)+u21(u20+c1)w0←u21/h12，α←h1α，γ←(c1+k1h0)w0ifTr(γ)＝1thenk1←k1′，γ←(c1+k1h0)w0k0←H(γ)α，k0′←k0+α3.Selectcorrectk0bycheckingtraceofx+x2u11+1＝0w0←k12，w1←w0u20+k1h1+u21w2←k0+w1+k0,]]>w4←k1u21+1，u11←w2w4ifTr(u11)＝1thenk0←k0′,w2←k0+w1+k0,]]>u11←w2w44.ComputeU1w1←k0u20，w5←w4+1，w6←(k0+k1)(u20+u21)u10←w4k0(w1+h0)+c0]]>5.ComputeV1＝V2+h+kU2modU1w4←w5+k0+1，w5←w1+w5+w6+v21+h1w6←w1+v20+h0，w7←w2+w4w1←w7u10，w3←(k1+w7)(u10+u11)v11←w1+w2+w3+w5v10←w1+w66.U1(x)←x2+u11x+u10，V1(x)←V11x+V107.returnD1＝(U1，V1)这里，考虑减少倒数运算的数量的方法。虽然算法5a[Algorithm5a]需要四个倒数运算1/u21、1/h22、1/h12、1/k1，但是这里通过设定为h2＝1，将所需要的倒数运算的数量减少到三个。进一步，由于h1是曲线参数，所以通过计算1/h12和将此事先作为输入给出，可以将所需要的倒数运算的数量减少到两个1/u21和1/k1。进一步，关于1/k1，可以基于参照上述[处理示例7提出的方法A2]所描述的表达式4通过一个乘法运算和一个加法运算来找到它，也就是，1/k1＝h2+k1u21。由于这些运算，上述算法8a[Algorithm8a]HEC_HLV(h2＝1，f4＝0)所需要的倒数运算的数量仅仅为一个，1/u21。作为结果，上述算法8a[Algorithm8a]HEC_HLV(h2＝1，f4＝0)的复杂度如下。(a)如果k1，k0是正确的值18M+2S+1I+2SR+2H+2T(b)如果k1，k0′是正确的值19M+2S+1I+3SR+2H+2T(c)如果k1′，k0是正确的值20M+2S+1I+2SR+2H+2T(d)如果k1′，k0′是正确的值21M+2S+1I+3SR+2H+2T将所有上述情况(a)到(d)进行平均得出19.5M+2S+1I+2.5SR+2H+2T。HarlyeDBL的复杂度为21M+5S+1I。这里，根据文献[(非专利文献15)E.Knudsen.EllipticScalarMultiplicationUsingPointHalving.ASIACRYPTO′99，LNCS1716，pp.135-149，Springer-Verlag，1999.]，已知当以正规基定义有限域时，可以忽略S(平方)、SR(平方根运算)、H(半迹(用于找到二次等式的根的运算))、和T(迹(确定二次等式是否存在根))的复杂度，并且仅仅需要考虑M(乘法)和I(倒数)的复杂度。因此，当使用正规积时，算法8a比HarleyDBL快1.5M。进一步，当以多项式基(polynomialbasis)来定义有限域时，根据文献(非专利文献16)K.Fong，D.Hankerson，J.Lopez，andA.Menezes.Fieldinversionoperationandpointhalvingrevised.TechnicalReportCORR2003-18，http//www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf18]，已知与M(乘法)的复杂度相比较，通常SR(平方根运算)和H(半迹(用于找到二次方程的根的运算))是大约SR＝H＝0.5M。进一步，可以忽略T(迹(确定针对二次方程是否有根))的复杂度。进一步，已知S(平方)的复杂度仅仅大约是M(乘法)的十分之几。然而，还已知根据选择多项式基的方式，SR的复杂度可以变为小于0.5M。应该注意，可以根据上述处理示例7(提出的方法A2)中的例外情况来计算例外情况。处理示例9(提出的方法B2)涉及目的是进一步增加上述的处理示例(处理示例2提出的方法B1)的运算速度的技术，其包括计算在带有参数h(x)＝x2+x+h0、f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数D的二等分。如已经参照上述处理示例8(提出的方法F2)所描述的那样，对参照处理示例7(提出的方法A2)所描述的二等分的计算算法，也就是算法5a[Algorithm5aHEC_HLV]，的仔细研究，将揭示算法5a包含大量的系数h(x)的乘法运算和系数h(x)的倒数运算。这意味着可以通过操控系数h(x)来减小乘法和倒数运算的复杂度。在文献[J.Pelzl，T.Wollinger，J.Guajardo，andC.Paar.HyperellipticcurveCryptosystemsClosingthePerformanceGaptoEllipticCurves.CryptologyePrintArchive，2003/026，IACR，2003]中，公开了使用h2、h1∈{0，1}、f4＝0来实现快速计算的例子。在使用这些参数的情况下HarleyDBL的复杂度为18M+7S+1I。虽然也与上述的那些一致地设定处理示例9(提出的方法B2)的条件，但是由于上述引理1导致针对h(x)假设不可约多项式，所以设定h(x)＝x2+x+h0，和Tr(h0)＝1(二次方程ax2+bx+c＝0为不可约的充分必要条件是Tr(ac/b2)＝1)。将这种情况下的计算方法在下面作为算法10a[Algorithm10aHEC_HLV(h2＝h1＝1，f4＝0)示出。Algorithm10aHEC_HLV(h2＝h1＝1，f4＝0)InputD2＝(U2，V2)OutputD1＝(U1，V1)＝[1/2]D2Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.Solvek1+k12u21+1＝0α←1/u21，k1←H(u21)α，k1′←k1+α2.Selectcorrectk1bysolvingk1h0+k0+k02u21+c1＝0c1←f3+v21+u20+u212c0←f2+v20+v21+v212+u21(u20+c1)γ←(c1+k1h0)u21ifTr(γ)＝1thenk1←k1′，γ←γ+h0k0←H(γ)α，k0′←k0+α3.Selectcorrectk0bycheckingtraceofx+x2u11+1＝0w0←k12，w1←w0u20+k1+u21w2←k0+w1+k0,]]>w4←k1u21+1，u11←w2w4ifTr(u11)＝1thenk0←k0′，w2←k0+w1+k0,u11←w2w4]]>4.ComputeU1w1←k0u20，w5←w4+1，w6←(k0+k1)(u20+u21)u10←w4k0(w1+h0)+c0]]>5.ComputeV1＝V2+h+kU2modU1w4←w5+k0+1，w5←w1+w5+w6+v21+1w6←w1+v20+h0，w7←w2+w4w1←w7u10，w3←(k0+w7)(u10+u11)v11←w1+w2+w3+w5v10←w1+w66.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)上诉算法10a[Algorithm10aHEC_HLV(h2＝h1＝1，f4＝0)的复杂度如下。a)如果k1，k0是正确的值14M+3S+1I+2SR+2H+2T(b)如果k1，k0′是正确的值15M+3S+1I+3SR+2H+2T(c)如果k1′，k0是正确的值14M+3S+1I+2SR+2H+2T(d)如果k1′，k0′是正确的值15M+3S+1I+3SR+2H+2T将所有上述情况(a)到(d)进行平均得出14.5M+3S+1I+3SR+2H+2T。HarleyDBL的复杂度为18M+7S+1I。这里，如上所述，根据文献[E.Knudsen.EllipticScalarMultiplicationUsingPointHalving.ASIACRYPTO′99，LNCS1716，pp.135-149，Springe-Verlag，1999.]，已知当以正规基(normalbasis)定义有限域时，可以忽略S(平方)、SR(平方根运算)、H(半迹(用于找到二次等式的根的运算))、和T(迹(确定二次等式是否存在根))的复杂度，并且仅仅需要考虑M(乘法)和I(倒数)的复杂度。因此，当使用正规基时，上述算法10a[Algorithm10a]比传统算法[HarleyDBL]快3.5M。进一步，当以多项式基定义有限域是，根据文献[K.Fong，D.Hankerson，J.Lopez，andA.Menezes.Fieldinversionoperationandpointhalvingrevised.TechnicalReportCORR2003-18，http//www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf18]，已知与M(乘法)的复杂度相比较，通常SR(平方根运算)和H(半迹(用于找到二次等式的根的运算))是大约SR＝H＝0.5M。进一步，可以忽略T(迹(确定针对二次等式是否有根))的复杂度。进一步，已知S(平方)的复杂度仅仅大约是M(乘法)的十分之几。然而，还已知根据选择多项式基的方式，SR的复杂度可以变为小于0.5M。上述算法10a[Algorithm10a]的曲线还要受到h0＝1的约束。由于上述算法10a[Algorithm10a]涉及h0的乘法运算，所以通过设定为h0＝1，可以以1M减小复杂度。通过将所有上述情况(a)到(d)进行平均得出复杂度13.5M+3S+1I+2.5SR+2H+2T。在另一方面，HarleyDBL的复杂度为15M+7S+11。应该注意，当以正规基定义有限域时，可以忽略S、SR、H、T的复杂度，并且当使用正规基时，算法10a[Algorithm10a]变为比传统算法[HarleyDBL]快1.5M。应该注意，可以根据上述处理示例7(提出的方法A2)中的例外情况来计算例外情况。处理示例10(提出的方法C2)涉及目的是进一步增加上述的处理示例(处理示例2提出的方法C1的运算速度的技术。也就是，当计算在带有随机参数的特征为2下、亏格为2的超椭圆曲线上、在带有参数h(x)＝x2+h1x+h0、f4＝0的特征为2下、亏格为2的超椭圆曲线上和在带有参数h(x)＝x2+x+h0、f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数的二等分时，出现二等分值的两个候选者。在这种情况下，需要从两个候选者中选择带有正确的值的一个。当选择正确的一个时，需要计算有限域的迹、乘法和平方根。两个候选者中哪一个是正确的依赖于除数D。因此，如果固定除数D，则实现在表中保留关于两个候选者中的哪一个正确的信息，并且当选择正确的值时查询该表，因此省略上述额外的计算。k1、k1′(k0，k0′)中的哪一个是正确的依赖于输入除数D。因此，如果例如D固定，则当之前将基点确定为在ECDH密钥交换、ECDSA签名产生或者验证等的阶段1的情况中时，计算[1/2i]D并且实现将关于k1、k1′(k0，k0′)中的哪一个正确的信息记录在表中。例如，准备与基点的阶数相同位大小的两个表T1、T0，并且将这些表的二进制表示定义为T1＝(t1，r-1，...，t1，0)，和T0＝(t0，r-1，...，t0，0)。在寻找[1/2i]D时，如果将这样的信息存储在表中如果k1是正确的则t1，i＝0否则如果k1′是正确的则t1，i＝1；并且如果k1是正确的则t1，i＝0，否则如果k0′是正确的则t0，i＝1，则仅仅大约是基点的阶数的大小两倍的位串作为表大小就足够了。通过查询这些表，可以减小二等分的复杂度。将如应用到算法8a[Algorithm8a]HEC_HLV(h2＝1，f4＝0)的上述方法表示为算法9a[Algorithm9a]HEC_HLV(h2＝1，f4＝0，withtable-lookup)。该算法的复杂度为18M+2SR+1I+2SR+2H。Algorithm9aHEC_HLV(h2＝1，f4＝0，table-lookup)inputD2＝(U2，V2)，1/h12，t0，t1OutputD1＝(U1，V1)＝[1/2]D2Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，21.Solvek1+k12u21+1＝0α←1/u21ift1＝0thenk1←H(u21)αelsek1←(H(u21)+1)α2.Solvek1h0+k0h1+k02u21+c1＝0c1←f3+v21+u20+u212c0←f2+v20+v21(h1+v21)+u21(u20+c1)w0←u21/h12，α←h1α，γ←(c1+k1h0)w0ift0＝0thenk0←H(γ)αelsek0←(H(γ)+1)α3.ComputeU1w0←k12，w1←w0u20+k1h1+u21，w2←k0+w1+k0]]>w4←k1u21+1，u11←w2w4w1←k0u20，w5←w4+1，w6←(k0+k1)(u20+u21)u10←w4k0(w1+h0)+c0]]>4.ComputeV1＝V2+h+kU2modU1w4←w5+k0+1，w5←w1+w5+w6+v21+h1w6←w1+v20+h0，w7←w2+w4w1←w7u10，w3←(k1+w7)(u10+u11)v11←w1+w2+w3+w5v10←w1+w66.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)具体地说，将如应用到上述算法10a[Algorithm10aHEC_HLV(h2＝h1＝1，f4＝0，withtable-lookup)]的上述方法表示为下面的算法11a[Algorithm11aHEC_HLV(h2＝h1＝1，f4＝0，withtable-lookup)。Algorithm11aHEC_HLV(h2＝h1＝1，f4＝0，withtable-lookup)InputD2＝(U2，V2)，t0，t1OutputD1＝(U1，V1)＝[1/2]D2Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，U1)＝11.Solvek1+k12u21+1＝0andselectcorrectk1viat1α←1/u21ift1＝0thenk1←H(u21)αelsek1←(H(u21)+1)α2.Solvek1h0+k0+k02u21+c1＝0andselectcorrectk0viat0c1←f3+v21+u20+u212c0←f2+v20+v21+v212+u21(u20+c1)γ←(c1+k1h0)u21k0←H(γ)αift0＝0thenk0←H(γ)αelsek0←(H(γ)+1)α3.ComputeU1w0←k12，w1←w0u20+k1+u21w2←k0+w1+k0]]>w4←k1u21+1，u11←w2w4w1←k0u20，w5←w4+1，w6←(k0+k1)(u20+u21)u10←w4k0(w1+h0)+c0]]>5.ComputV1＝V2+h+kU2modU1w4←w5+k0+1，w5←w1+w5+w6+v21+1w6←w1+v20+h0，w7←w2+w4w1←w7u10，w3←(k0+w7)(u10+u11)v11←w1+w2+w3+w5v10←w1+w66.U1(x)←x2+u11x+u10，V1(x)←v11x+v107.returnD1＝(U1，V1)算法11a[Algorithm11aHEC_HLV(h2＝h1＝1，f4＝0，withtable-lookup)的复杂度为14M+3S+1I+2SR+2H，而且进一步，通过设定为h0＝1，可以以1M将该复杂度减小。在这种情况下的复杂度变为13M+3S+1I+2SR+2H。处理示例11(提出的方法D2)涉及目的是进一步增加上述的处理示例(处理示例2提出的方法D1)的运算速度的技术，其包括使用在处理示例7到10的每一个中所述的计算产生的二等分的方法来计算除数的标量乘法。在下面的每个文献中公开了使用椭圆曲线上的有理点的二等分来计算标量乘法的方法[E.Knudsen.EllipticScalarMultiplicationUsingPointHalving.ASIACRYPTO′99，LNCS1716，pp.135-149，Springer-Verlag，1999.]和[K.Fong，D.Hankerson，J.Lopez，andA.Menezes.Fieldinversionoperationandpointhalvingrevised.TechnicalReportCORR2003-18，http//www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf]。基于在这些文献中所公开的标量乘法来执行使用在超椭圆曲线上的除数的二等分来计算标量乘法的方法。这里，假设经历标量乘法的除数D是大阶数的素数。进一步，假设标量值d是整数0＜d＜r。为了使用二等分来执行标量乘法，首先，需要以半表示(halfrepresentation)来表达以二进制表示所表达的标量值d。这里，假设[公式32]进一步，求当将d乘以2m然后除以r时的余数，也就是，Σi=0md^i2i←2md(modr).]]>随后，将其除以2m以得出[公式34]Σi=0mdi/2i←Σi=0md^i2i-m]]>将在上述表达式中由[公式35]Σi=0mdi/2i]]>所表达的标量值用于使用二等分的标量乘法[二等分-并-二进制加法(halve-and-addbinary)]方法。这里[公式36]di,d^i∈{0,1}.]]>将二等分-并-二进制加法方法(右到左)和二等分-并-二进制加法方法(左到右)分别在下面表示为算法12a[Algorithm12a]和算法13a[Algorithm13a]。Algorithm12aHalve-and-addbinaryMethod(right-to-left)InputD∈J(F2n)suchthat2D≠O,]]>d∈Z，rorderofD，OutputscalarmultiplicationdD1.Σi=0md^i2i←2mdmodr,d^i∈{0,1}]]>2.Σi=0mdi/2i←Σi=0md^i2i-m,di∈{0,1}]]>3.Q←O，R←D4.forifrom0tomdoifdi＝1thenQ←Q+RR←HEC_HLV(R)5.returnQ[公式38]Algorithm13aHalve-and-addbinaryMethod(left-fo-right)InputD∈J(F2n)suchthat2D≠O,]]>d∈Z，rorderofD，OutputscalarmultiplicationdD1.Σi=0md^i2i←2mdmodr,d^i∈{0,1}]]>2.Σi=0mdi/2i←Σi=0md^i2i-m,di∈{0,1}]]>3.Q←O4.forifrommdownto0doQ←HEC_HLV(Q)ifdi＝1thenQ←Q+D5.returnQ在上述算法12a[Algorithm12a]和算法13a[Algorithm13a]的每一个的步骤4中所出现的HEC_HLV可以是使用随机曲线的上述算法5a[Algorithm5a]的HEC_HLV、带有提供给算法8a[Algorithm8a]的曲线参数的约束h2＝1、f4＝0的HEC_HLV、带有提供给算法10a[Algorithm10a]的曲线参数的约束h2＝h1＝1、f4＝0的HEC_HLV、或者带有提供给算法10a[Algorithm10a]的曲线参数的约束h2＝h1＝h0＝1、f4＝0的HEC_HLV。在参照上面处理示例1到6描述的二等分运算的情况中，例如，在上述[处理示例3(提出的方法B1)]中示出的算法10或者在[处理示例5(提出的方法C1)]中示出的算法11中，输入和输出分别需要1/u21和1/u11因此，基点D的1/2i倍乘积，也就是(1/2)D，(1/22)D，(1/23)D，(1/2i)D...可以用被取作下一个二等分运算的输入的之前二等分运算的输出1/u11来给出，因此使得有效计算成为可能。因此，当通过二等分-并-二进制加法方法(右到左)来计算标量乘积时，这可以通过适当地加法基点D的1/2i乘积来完成。因此在右到左方法的情况中可以用有效的方式来执行标量乘法。在另一方面，在左到右方法的情况中，存在不能将之前二等分运算的输出取作下一个二等分运算的输入的情况。在上述算法13a[Algorithm13a]的步骤4中，首先，将通过该算法中途获得的中间结果Q乘以1/2(Q←HEC_HLV(Q))，而且如果标量值的一位是1，则将基点加入到该中间结果(如果di＝1则Q←Q+D)。因此，如果位是1，则对于下一位，并且将之前二等分运算的输出1/u11作为下一个二等分运算的输出给出，所以需要重新计算输入值1/u21。有限域的倒数比乘法复杂得多。因此，在上面处理示例1到6中所描述的二等分方法的情况中，当应用左到右时，需要执行用于产生二等分的输入值的额外倒数运算，其降低了计算的效率。然而，根据参照从处理示例7向前的处理示例所描述的提出的方法，输入不需要1/u21，所以可以与使用左到右或者右到左方法无关地以相同的复杂度执行计算。进一步，上述算法12a[Algorithm12a]的二等分-并-二进制加法方法(右到左)的步骤4中的HEC_HLV可以是带有应用到使用随机曲线的5a[Algorithm5a]的表查询方法的HEC_HLV、带有对算法8a[Algorithm8a]的曲线参数提供约束h2＝1、f4＝0并且应用表查询方法的HEC_HLV、带有对算法10a[Algorithm10a]的曲线参数提供约束h2＝h1＝1、f4＝0并且应用表查询方法的HEC_HLV、或者带有对算法10a[Algorithm10a]的曲线参数提供约束h2＝h1＝h0＝1、f4＝0并且应用表查询方法的HEC_HLV。进一步，除了二进制方法以外还可以应用窗口方法。使得D表示输入除数而w表示窗口宽度。将针对其代替中间结果的除数表示为Q←O。关于整数i＝(iw-1，iw-2...i0)2∈{0，1，...，2w-1}，执行下面初步计算[公式39]Dj←Σj=0w-1ij2jD]]>以事先计算由2w个除数组成的表。进一步，以下面的1/2w进制表示来扩展标量值d。Σi=0lci/(2w)i←Σi=0mdi/2i]]>首先，将二等分w次地应用到Q以给出Q←(1/2w)Q。之后，以窗口宽度w从d的最高有效位中扫描标量值c1，并且查询在表中的对应除数，并且将此加入到结果如下。Q←Q+Dc1将此重复到c0。将这种计算方法[二等分-并-窗口加法方法]表示为下面算法14a[Algorithm14a]。Algorithm14aHalve-and-addWindowMethodInputD∈J(F2n)suchthat2D≠O,]]>d∈Z，rorderofD，OutputscalarmultiplicationdD1.Σi=0md^i2i←2mdmodr,d^i∈{0,1}]]>2.Σi=0mdi/2i←Σi=0md^i2i-m,di∈{0,1}]]>3.Σi=0lci/(2w)i←Σi=0mdi/2i,ci∈{0,1,···,2w-1}]]>4.Di←iw-12w-1D+···+i020D,fori=(iw-1···i0)2∈{0,1,···,2w-1}]]>5.Q←O6.forifromldownto0doforjfrom1towdoQ←HEC_HLV(Q)Q←Q+Dc17.returnQ进一步，可以将除数D＝(U，V)，U＝x2+u1x+u0，和V＝v1xandv0，的倒数表示如下-D＝(U，V+hmodU)＝(U，(v1+h2u1+h1)x+(v0+h2u0+h0))。具体地说，如果h2＝1，则不需要有限域乘法，并且四个有限域乘法运算就足以从D中找到-D。可以通过除数-D的加法来计算除数D的相减。也就是，能够以相同的复杂度得出除数的加法和相减。因此，可能通过也使用负值来表示标量值，并且使用负值来执行标量乘法。首先，使用NAF(非相邻形式，Non-AdjacentForm)，通过{-1，0，1}来表示给定整数s。在NAF中，从最低有效位中扫描以二进制表示所表达的整数s的标量值。如果存在数字1彼此相邻的点，则将其表达如下，例如在(11)的情况中，将此表达位(10-1)，也就是，3＝22-1；和在(111)的情况中，将此表达位(100-1)，也就是，7＝23-1。将用于NAF的计算方法表示为下面算法15a[Algorithm15a]。Algorithm15aConversiontoNAFInput:s=Σj=0l-1sj2j∈Z,sj∈{0,1}]]>Output:NAF(s)=Σj=0lsj′2j,sj′∈{-1,0,1}]]>1.c0←0，sl←02.Forj＝0toldosj′←sj+cj-2cj+13.returnNAF(S)＝(sl′sl-1′…s0′)NAF表示带有最少数量的非零位的表达式。由于在非零位的部分中执行除数加法或者相减，所以因为非零位的数量变得较小导致可以更快地计算标量乘法。可以将使用NAF的标量值表达式应用于二等分-并-二进制加法方法和二等分-并-窗口加法方法。二等分-并-二进制加法方法和二等分-并-窗口加法方法的每一个中所使用的HEC_HLV可以是使用随机曲线的上述算法5a[Algorithm5a]的HEC_HLV、带有提供给算法8a[Algorithm8a]的曲线参数的约束h2＝1、f4＝0的HEC_HLV、带有提供给算法10a[Algorithm10a]的曲线参数的约束h2＝h1＝1、f4＝0的HEC_HLV、或者带有提供给算法10a[Algorithm10a]的曲线参数的约束h2＝h1＝h0＝1、f4＝0的HEC_HLV。将使用NAF的二等分-并-二进制加法方法表示为下面算法16a[Algorithm16a]。Algorithm16aHalve-and-addNAFBinaryMethodInputD∈J(F2n)suchthat2D≠O,]]>d∈Z，rorderofD，OutputscalarmultiplicationdD1.Σi=0md^i2i←NAF(2mdmodr),d^i∈{-1,0,1}]]>2.Σi=0mdi/2i←Σi=0md^i2i-m,di∈{-1,0,1}]]>3.Q←O4.forifrommdownto0doQ←HEC_HLV(Q)ifdi＞0thenQ←Q+Difdi＜0thenQ←Q-D5.returnQ[增加的计算速度的验证]下面，找到应用于上述处理示例7到11的每一个的计算的复杂度，并且进行针对计算速度的增加的验证。在HEC_HLV(h2＝1，f4＝0)的情况中，所需要的复杂度平均为19.5M+2S+1I+3SR+2H+2T。首先，考虑以正规基定义有限域的情况。如上所述，当使用正规基时，仅仅考虑M和I的复杂度。根据文献[A.Menezes.EllipticCurvePublicKeyCryptosystems.KluwerAcademicPublishers，1993.]，假设有限域为Fq、q＝2n，一个倒数运算等效于通过下面表达式计算的乘法运算的数量，也就是[公式44]在这种情况下，w(n-1)表示在n-1的二进制表达式中1的数量。例如，如果n＝83、89、113，则I＝8M，而如果n＝103，则I＝9M。这里，假设I＝8M，则HEC_HLV(h2＝1，f4＝0)在复杂度表示为19.5M+1I＝27.5M。在另一方面，在HarleyDBL的情况中，其复杂度表示为21M+1I＝29M，所以HEC_HLV比HarleyDBL快大约5％。进一步，当使用表查询方法时，复杂度变为18M+1I＝26M，所以HEC_HLV比HarleyDBL快大约10％。进一步，在HEC_HLV(h2＝h1＝1，f4＝0)的情况中，复杂度平均为14.5M+3S+1I+2.5SR+2H+2T。在这种情况下，14.5M+1I＝22.5M。在另一方面，在HarleyDBL的情况中，复杂度表示为18M+1I＝26M，所以HEC_HLV比HarleyDBL快大约13％。进一步，当使用表查询方法时，复杂度变为14M+1I＝22M，所以HEC_HLV比HarleyDBL快大约15％。进一步，HEC_HLV(h2＝h1＝h0＝1，f4＝0)的复杂度平均为13.5M+3S+1I+2.5SR+2H+2T。在这种情况中，13.5M+1I＝21.5M。在另一方面，在HarleyDBL的情况中，其复杂度为15M+1I＝23M，所以HEC_HLV比HarleyDBL快大约6％。进一步，当使用表查询方法时，复杂度变为17M+1I＝25M，所以HEC_HLV比HarleyDBL快大约14％。下面，评估多项式基的情况中的复杂度。假设S、I、SR、H、T的复杂度如下S＝0.1M，I＝8M，SR＝0.5M，H＝0.5M，T＝0.5M。在HEC_HLV(h2＝1，f4＝0)的情况中，复杂度平均为19.5M+2S+1I+2.5SR+2H+2T＝29.95M。在另一方面，在HarleyDBL的情况中，复杂度为21M+5S+1I＝29.5M，所以HarleyDBL比HEC_HLV快大约1％。进一步，当使用表查询方法时，复杂度变为18M+2S+1I+2SR+2H＝28.2M，所以HEC_HLV比HarleyDBL快大约4％。进一步，在HEC_HLV(h2＝h1＝1，f4＝0)的情况中，复杂度平均为14.5M+3S+1I+2.5SR+2H+2T＝25.05M。在另一方面，在HarleyDBL的情况中，复杂度为18M+7S+1I＝26.7M，所以HEC_HLV比HarleyDBL快大约6％。进一步，当使用表查询方法时，复杂度变为14M+3S+1I+2SR+2H＝24.3M，所以HEC_HLV比HarleyDBL快大约9％。进一步，在HEC_HLV(h2＝h1＝h0＝1，f4＝0)的情况中，复杂度平均为13.5M+3S+1I+2.5SR+2H+2T＝24.05M。在另一方面，在HarleyDBL的情况中，复杂度为15M+7S+1I＝23.7M，所以HarleyDBL比HEC_HLV快大约1％。进一步，当使用表查询方法时，复杂度变为13M+3S+1I+2SR+2H＝23.3M，所以HEC_HLV比HarleyDBL快大约2％。进一步，通过软件实施针对多项式基的情况执行速度比较。在如下指示的环境中执行软件实施CPUPentiumII300MHxOSRedHat7.3编译程序gcc2.96。分别以下面文档中所公开的方式执行M(乘法)和S(平方)、I(倒数)、SR(平方根运算)和T(迹(确定对于二次等式是否存在根))、和H(半迹)(用于找到二次等式的根的运算)的运算[D.Hankerson，J.Hernandez，andA.Menezes.SoftwareImplementationofEllipticCurveCryptographyoverBinaryFields.CHES2000，LNCS1965，pp.1-24，2000.Algorithm4.6，4.7]；[S.Shantz.FromEuclid′sGCDtoMontgomeryMultiplicationtotheGreatDivide.TR-2001-95，SunMicrosystems，Inc.，2001.]；[K.Fong，D.Hankerson，J.Lopez，andA.Menezes.Fieldinversionoperationandpointhalvingrevised.TechnicalReportCORR2003-18，http//www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf]；and[K.Fong，D.Hankerson，J.Lopez，andA.Menezes.Fieldinversionoperationandpointhalvingrevised.TechnicalReportCORR2003-18，http//www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdfAlgorithm4.7]。关于n＝83、89、113的三个有限域来实施M、S、I、SR、H、T，并且找到对M的比率。在这种情况下，使用下面不可约多项式在n＝83的情况中，z83+z7+z4+z2+1＝0；在n＝89的情况中，z89+z38+1＝0；和在n＝113的情况中，z113+z9+1＝0。在相应情况中的复杂度如下。n＝83S/M＝0.12，I/M＝7.96，SR/M＝0.57，H/M＝0.58n＝89S/M＝0.05，I/M＝8.74，SR/M＝0.14，H/M＝0.61n＝113S/M＝0.06，I/M＝8.56，SR/M＝0.10，H/M＝0.50将这些应用到HarleyDBL的复杂度，21M+5S+1I，得出如下。n＝83HarleyDBL29.56Mn＝89HarleyDBL29.99Mn＝113HarleyDBL29.86M将这些应用到HEC_HLV(h2＝1，f4＝0)的复杂度，19.5M+2.5SR+2H+2T，得出如下。n＝83HEC_HLV(h2＝1，f4＝0)30.285Mn＝89HEC_HLV(h2＝1，f4＝0)29.91Mn＝113HEC_HLV(h2＝1，f4＝0)29.43M在这种情况下，当n＝83时，HarleyDBL比HEC_HLV快2％。进一步，当n＝89、113时，HEC_HLV比HarleyDBL分别快0.3％和1.5％。进一步，将这些应用到应用了表查询方法的HEC_HLV(h2＝1，f4＝0)的复杂度，18M+2S+1I+2SR+2H，得出如下。n＝83HEC_HLV(h2＝1，f4＝0，withtable-lookup)28.5Mn＝89HEC_HLV(h2＝1，f4＝0，withtable-lookup)28.34Mn＝113HEC_LV(h2＝1，f4＝0，withtable-lookup)27.88M在这种情况下，当n＝83、89、113时，HEC_HLV比HarleyDBL分别快4％、5％、6％。进一步，在h2＝h1＝1、f4＝0的情况中，将这些应用到HarleyDBL的复杂度，18M+7S+1I，得出下面。n＝83HarleyDBL27.4Mn＝89HarleyDBL27.09Mn＝113HarleyDBL26.98M下面，将这些应用于HEC_HLV(h2＝h1＝1，f4＝0)的复杂度，14.5M+3S+1I+2.5SR+2H+2T，得出下面。n＝83HEC_HLV(h2＝1，f4＝0)25.405Mn＝89HEC_HLV(h2＝1，f4＝0)24.96Mn＝113HEC_HLV(h2＝1，f4＝0)24.49M在这种情况下，当n＝83、89、113时，HEC_HLV比HarleyDBL分别快7％、8％、10％。进一步，将这些应用到应用了表查询方法的HEC_HLV(h2＝h1＝1，f4＝0)的复杂度，14M+3S+1I+2SR+2H，得出下面。n＝83HEC_HLV(h2＝h1＝1，f4＝0，withtable-lookup)24.62Mn＝89HEC_HLV(h2＝h1＝1，f4＝0，withtable-lookup)24.39Mn＝113HEC_HLV(h2＝h1＝1，f4＝0，withtable-lookup)23.94M在这种情况下，当n＝83、89、113时，HEC_HLV比HarleyDBL分别快10％、8％、11％。进一步，在h2＝h1＝h0＝1，f4＝0的情况中，应用这些到HarleyDBL的复杂度，15M+7S+1I，得出下面。n＝83HarleyDBL23.8Mn＝89HarleyDBL24.09Mn＝113HarleyDBL23.98M下面，将这些应用于HEC_HLV(h2＝h1h0＝1，f4＝0)的复杂度，13.5M+3S+1I+2.5SR+2H+2T，得出下面。n＝83HEC_HLV(h2＝h1＝h0＝1，f4＝0)24.405Mn＝89HEC_HLV(h2＝h1＝h0＝1，f4＝0)23.96Mn＝113HEC_HLV(h2＝h1＝h0＝1，f4＝0)23.49M在这种情况下，当n＝83时HarleyDBL比，HEC_HLV快2％。当n＝89、113时，HEC_HLV比HarleyDBL分别快0.5％、2％。进一步，将这些应用于应用了表查询方法的HEC_HLV(h2＝h1＝h0＝1，f4＝0)的复杂度，13M+3S+1I+2SR+2H，得出下面。n＝83HEC_HLV(h2＝h1＝h0＝1，f4＝0withtable-lookup)23.62Mn＝89HEC_HLV(h2＝h1＝h0＝1，f4＝0withtable-lookup)23.39Mn＝113HEC_HLV(h2＝h1＝h0＝1，f4＝0withtable-lookup)22.94M在这种情况下，当n＝83、89、113时，HEC_HLV比HarleyDBL分别快1％、3％、4％。根据上面的描述，可以说HEC_HLV在大多数情况中比HarleyDBL快。特别是，当参数曲线是h2＝h1＝1、f4＝0时，HEC_HLV在所有情况中都比HarleyDBL快。下面，考虑标量乘法的复杂度。关于上述例子，在HEC_HLV比HarleyDBL快的情况中，使用加法和二等分的组合的标量乘法比使用加法和加倍的组合的标量乘法快。现在，将对每个独立情况中的标量乘法的具体复杂度进行比较。对于曲线参数，使用h2＝h1＝1、f4＝0。进一步，作为标量乘法算法，使用上述NAF+二进制方法(算法16a[Algorithm16a])。由于在该算法中步骤1、2对于整个标量乘法处理的比例非常小，所以可以忽略其复杂度。这里，针对正规基和多项式基两者对于n＝83、89、113的情况考虑复杂度。进一步，假设基点的阶数对于n＝83、89、113分别为165位、177位和225位。进一步，在步骤4的重复部分中，针对基点的阶数的位的数量进行重复。以文献[T.Lange，Efficientarithmeticongenus2hyperellipticcurvesoverfinitefieldsviaexplicitformulae.CryptologyePrintArchive，2002/121，IACR，2002]中所公开的方式来执行除数加法。应该注意，曲线参数是h2＝h1＝1、f4＝0。在这种情况中除数加法所需要的复杂度为21M+3S+1I。使用NAF由{-1，0，1}来表示标量值。如果将标量值定义为m，则存在大约m/3个非零位。因此，将NAF+二进制方法的复杂度计算如下((乘法·相减的复杂度)/3+(二等分或者加倍的复杂度))×(基点的阶数的位的数量)。首先，将考虑正规基的情况。假设I＝8M。在h2＝h1＝1、f4＝0的情况中，n＝83加法·加倍5885Mn＝89加法·加倍6313Mn＝113加法·加倍8025M在h2＝h1＝1、f4＝0的情况中，n＝83加法·二等分5307.5Mn＝89加法·二等分5693.5Mn＝113加法·二等分7237.5M在h2＝h1＝1、f4＝0+表查询方法的情况中，n＝83加法·二等分5225Mn＝89加法·二等分5605Mn＝113加法·二等分7125M下面，考虑多项式基的情况。在h2＝h1＝1、f4＝0的情况中，n＝83加法·加倍6116Mn＝89加法·加倍6505.93Mn＝113加法·加倍8245.5M在h2＝h1＝1、f4＝0的情况中，n＝83加法·二等分5786.82Mn＝89加法·二等分6128.92Mn＝113加法·二等分7685.25M在h2＝h1＝1、f4＝0+表查询方法的情况中，n＝83加法·二等分5657.3Mn＝89加法·二等分6028.03Mn＝113加法·二等分7561.5M可以说(加法·加倍的标量乘积)比(加法·二等分的标量乘积)在正规基的情况中快大约10到11％，而在多项式基的情况中快大约5到8％。如上所述，根据本发明的处理，将椭圆曲线加密术的二等分扩展到超椭圆曲线加密术从而实现快速计算。在使用在超椭圆曲线上对除数的计算的加密术计算的情况中，对处理施加较大负荷的算术计算是除数的标量乘法。从这方面来说，根据上述本发明的处理使得更快的标量乘法成为可能，从而在以超椭圆曲线加密术中进行处理时实现显著的改进。如上所述，HECC(超椭圆曲线加密术)是ECC(椭圆曲线加密术)的概括概念。因此，可以将本发明应用于使用在各种应用程序中所使用的ECC(椭圆曲线加密术)的加密处理，具体包括签名处理、加密数据的产生、解密、密钥预先分发系统和验证处理。可以通过用上述标量乘法代替ECC(椭圆曲线加密术)的计算处理中的标量乘法部分来实现更快的计算。图7是示出根据本发明的加密系统的功能配置的框图。加密系统100包括基点产生部分101，用于产生除数D作为基点；存储部分102，用于存储参照上述处理示例5所述的表，也就是，记录关于对于事先固定的除数D基于计算值[1/2iD]在k1、k1′、(k0，k0′)中哪一个正确的信息的表；以及计算执行部分103。计算执行部分103执行计算运算，包括关于超椭圆曲线上的除数计算标量乘法的计算处理。具体地说，计算执行部分执行计算运算，包括关于在带有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数的标量乘法。例如，计算执行部分103执行计算运算，包括关于在带有参数h(x)＝x2+x+h0、f4＝0的特征为2下、亏格为2的超椭圆曲线上的除数D的标量乘法、或者在带有参数h(x)＝x的特征为2中在亏格为2的超椭圆曲线上的除数D的标量乘法。下面说明解释将根据本发明的技术应用于ECDSA(EC数字签名算法)的标量乘法中的情况，作为可以将本发明的处理应用到的具体加密算法的例子，其中ESDSA是用于数字签名的产生和验证的并且椭圆曲线加密术所应用到的算法。根据IEEE1363，通过执行下面序列来产生和验证数字签名。(1)输入(1-1)输入椭圆曲线的域参数和基点G(阶数r)(1-2)输入签名人的秘密密钥。(1-3)输入明文M。(2)密钥的产生(2-1)使用W＝sG作为用于秘密密钥s的公共密钥。(3)签名的产生(3-1)产生随机整数u，其中0＜u＜r。(3-2)计算V＝uG＝(xv，yv)。(3-3)将xv转换为整数i。(3-4)计算c＝imodr。如果c＝0，则转到步骤3-1。(3-5)f＝h(M)，其h是散列函数。(3-6)计算d＝u-1(f+sc)modr。如果d＝0，转到3-1。(3-7)使用(c，d)作为用于明文M的签名。(4)签名的验证(4-1)检查关系0＜c＜r和0＜d＜r是否为真。如果它们不为真，输出“无效”。(4-2)计算h＝d-1modr，h1＝fhmodr，和h2＝chmodr。(4-3)计算P＝(xp，yp)＝h1G+h2W。如果P＝0，则输出“无效”。(4-4)将xp转换为整数i。(4-5)计算c′＝imodr。(4-6)如果c′＝c，则输出“有效”。否则，输出“无效”。可以将所提出的使用超椭圆曲线的技术应用于上面算法的下面步骤中(2-1)使用W＝sG作为用于秘密密钥s的公共密钥；(3-2)计算V＝uG＝(xv，yv)；和(4-3)计算P＝(xp，yp)＝h1G+h2W。如果P＝0，则输出“无效”。在各个步骤(2-1)、(3-2)和(4-3)的每一个中的计算处理W＝sG、V＝uG和P＝(xp，yp)＝h1G+h2W表示对除数的标量乘法处理，并且可以通过本发明的应用更加快速的执行。进一步，技术处理sG、uG、和h1G表示对固定除数的标量乘法处理，并且可以通过根据本发明的表查询方法的应用更快地执行。最后，将参照图8描述作为执行上述加密处理的装置进行工作的IC模块200的示例配置。可以通过诸如PC、IC卡和读/写器之类的各种信息处理设备来执行上述处理。可以将图8中所示的IC模块200合并在这些信息处理设备中。在图8中所示的CPU(中央处理单元)201是用于执行各种程序以开始和结束加密处理、扩展数据的传送和接收、并且控制各个组成部件之间的数据传输的处理器。存储器202包括ROM(只读存储器)和RAM(随机存储器)。ROM存储用于由CPU201执行的程序或者作为计算参数的固定数据。RAM用作存储区域/工作区域以存储由CPU201执行以进行处理的程序、以及随着程序处理进行而改变的计算参数。应该注意，将存储器202中所存储的计算执行程序定义为包括加法和加倍的执行序列的程序，作为上述基点设定处理和标量乘法处理对其进行执行。此外，存储器202还作为用于加密处理所需要的密钥数据等的存储区域工作。最好将用于数据等的存储区域设计为具有防篡改(tamper-proof)结构的存储器区域。加密部分203执行诸如加密处理之类的处理，并且上述标量乘法和解密处理。应该注意，虽然将加密部分203作为独立模块示出，但是可以不提供这种独立的加密处理模块。也就是说，可以采用这样的配置例如，将加密程序存储在ROM中，而CPU201从ROM中读出加密程序并且执行该程序。随机数产生器204执行产生加密处理所必须的密钥等的产生所需要的随机数的处理。传送/接收部分205是数据通信处理单元，用于执行与外部设备的数据通信。传送/接收部分205执行与诸如读/写器之类的IC模块的数据通信，并且执行诸如输出IC模块中所产生的加密的文字或者从读/写器之类的外部设备输入数据之类的处理。至此已经参照其具体实施方式详细描述了本发明。但是，对于本领域的普通技术人员非常明显，在不偏离本发明的范围的情况下可以对这些实施方式进行变型和替换。也就是说，仅仅是示例地进行了对本发明的上述公开，而不应该对其进行限制性的理解。应该参照所附权利要求来确定本发明的范围。可以通过硬件、软件或者两者的组合结构来执行在本说明书中所描述的处理序列。如果通过软件来执行处理序列，则可以通过将记录处理序列的程序安装到在专用硬件中安置的计算机的存储器中，或者通过将程序安装到能够执行各种处理的通用计算机中，来执行处理序列。例如，可以事先将程序存储在作为记录介质的硬盘或者ROM(只读存储器)中。替代地，可以临时或者永久地将程序存储(记录)在诸如软盘、CD-ROM(致密盘只读存储器)、MO(磁光)盘、DVD(数字多功能盘)、磁盘和半导体存储器之类的可拆卸记录介质中。可以用所谓打包软件的形式提供这种可拆卸记录介质。除了从上述可拆卸记录介质中被安装到计算机中之外，可以将程序从下载站点无线地、或者经由诸如LAN(局域网)或者因特网之类的网络有线地传输到计算机。计算机接收这样传输的程序并且将该程序安装到诸如硬盘之类的内置记录介质中。在本说明书中所描述的各种处理不仅可以以它们在说明书出现的顺序在时间上顺序执行，而且可以依赖于执行处理的装置的吞吐量并行或者独立地进行执行。进一步，在本说明书中所使用的术语系统指的是多个装置的逻辑组合，并且不限于各个配置的装置都位于相同的机箱内的一种情况。产业的可利用性根据本发明的配置，将椭圆曲线加密术上的二等分扩展到超椭圆曲线加密术从而实现快速计算。在使用对超椭圆曲线上的分数的计算的加密计算的情况中，对处理产生较大负荷的计算运算是除数的标量乘法。因此，通过根据上述本发明的处理来实现较快的标量乘法，从超椭圆曲线加密术的处理角度来说可以实现显著的改进。因此可以将本发明应用于诸如IC卡之类的、需要执行快速和安全的加密计算的设备、装置等。根据本发明的配置，在关于在超椭圆曲线加密术中的除数D的标量乘法中，可以通过执行包括二等分作为计算处理的计算运算来实现较快的标量乘法。例如，通过执行计算运算来实现快速计算，该计算运算包括关于在具有h(x)＝x2+x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上、在具有h(x)＝x2+h1x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上、或者在具有h(x)＝x作为参数的特征为2中在亏格为2的超椭圆曲线上的除数在标量乘法中的二等分。因此可以将本发明应用于诸如IC卡之类的、需要执行快速和安全的加密计算的设备、装置等。根据本发明的配置，可以通过应用表来实现除数的标量乘法的复杂性的进一步降低以及因此带来的更快的计算，所述表根据关于事先固定的除数D的[1/2iD]的所计算的值记录k1、k1′、(k0，k0′)中的哪个是正确的。因此可以将本发明应用于诸如IC卡之类的、需要执行快速和安全的加密计算的设备、装置等。根据本发明的配置，在关于超椭圆曲线加密术中的除数D的标量乘法中，执行包括二等分的计算运算作为计算处理，并且应用用于减少在二等分计算处理中所执行的倒数运算的数量的算法，从而使得能够进一步降低除数的标量乘法的复杂度因此产生更快的计算。权利要求1.一种用于基于超椭圆曲线加密术执行加密计算的加密计算方法，该方法包括关于在超椭圆曲线上除数D的标量乘法的计算中，执行包括二等分作为计算处理的计算运算的计算步骤。2.根据权利要求1所述的加密计算方法，其中所述计算步骤是执行这样的计算运算的步骤，该计算运算包括关于在具有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数D的标量乘法中的二等分。3.根据权利要求1所述的加密计算方法，其中所述计算步骤是执行这样的计算运算的步骤，该计算运算包括关于在具有h(x)＝x2+x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。4.根据权利要求1所述的加密计算方法，其中所述计算步骤是执行这样的计算运算的步骤，该计算运算包括关于在具有h(x)＝x2+h1x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。5.根据权利要求1所述的加密计算方法，其中所述计算步骤是执行这样的计算运算的步骤，该计算运算包括关于在具有h(x)＝x作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。6.根据权利要求1所述的加密计算方法，其中该加密计算方法还包括查询表的表查询步骤，该表根据关于事先固定的除数D所计算的[1/2iD]的值记录k1、k1′、(k0，k0′)中的哪个是正确的；以及所述计算步骤通过基于表的查询的确定处理，来执行降低二等分的复杂度的计算处理。7.根据权利要求1所述的加密计算方法，其中所述计算步骤包括通过应用下面关系表达式，通过乘法和加法处理而不执行倒数运算来计算倒数1/k1的值的步骤1/k1＝h2+k1u21，该公式从二等分计算算法中得出，在该二等分计算算法中，InputD2＝(U2，V2)，和OutputD1＝(U1，V1)＝[1/2]D2，其中Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，2。8.根据权利要求1所述的加密计算方法，其中在二等分计算算法中，所述加密计算方法执行根据具有不应用1/u21作为输入值的设定的算法的计算，其中InputD2＝(U2，V2)；和OutputD1＝(U1，V1)＝[1/2]D2，其中Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，2。9.根据权利要求1所述的加密计算方法，其中所述加密计算方法是用于执行关于在具有h(x)＝x2+h1x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D的标量乘法的计算方法；以及所述计算步骤包括步骤将作为之前所计算的值的1/h12设定为输入值；以及应用之前所计算的输入值1/h12而不执行计算倒数1/h12的处理。10.一种基于超椭圆曲线加密术执行加密计算的加密系统，包括在关于在超椭圆曲线上的除数D计算标量乘法中执行包括二等分作为计算处理的计算运算的计算执行部分。11.根据权利要求10所述的加密系统，其中将所述计算执行部分配置为执行这样的计算运算，该计算运算包括关于在具有随机参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。12.根据权利要求10所述的加密系统，其中将所述计算执行部分配置为执行这样的计算运算，该计算运算包括关于在具有h(x)＝x2+x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。13.根据权利要求10所述的加密系统，其中将所述计算执行部分配置为执行这样的计算运算，该计算运算包括关于在具有h(x)＝x2+h1x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分。14.根据权利要求10所述的加密系统，其中将所述计算执行部分配置为执行这样的计算运算，该计算运算包括关于在具有h(x)＝x作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D在标量乘法中的二等分15.根据权利要求10所述的加密系统，其中所述加密系统进一步包括存储部分，其存储根据关于事先固定的除数D所计算的[1/2iD]的值记录k1、k1′、(k0，k0′)中的哪个是正确的表；以及所述计算执行部分被配置为通过基于表的查询的确定处理来执行降低二等分的复杂度的计算处理。16.根据权利要求10所述的加密系统，其中将所述计算执行部分配置为通过应用下面关系表达式，通过乘法和加法处理而不执行倒数运算来计算倒数1/k1的值1/k1＝h2+k1u21该表达式从二等分计算算法中得出，在该二等分计算算法中InputD2＝(U2，V2)，和OutputD1＝(U1，V1)＝[1/2]D2，其中Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，2。17.根据权利要求10所述的加密系统，其中将所述计算执行部分配置为执行二等分计算算法，在该二等分计算算法中InputD2＝(U2，V2)；和OutputD1＝(U1，V1)＝[1/2]D2，其中Ui(x)＝x2+ui1x+ui0，Vi(x)＝vi1x+vi0，gcd(h，Ui)＝1，i＝1，2，并且执行根据具有不应用1/u21作为输入值的设定的算法的计算。18.根据权利要求10所述的加密系统，其中，将所述计算执行部分配置为执行关于在具有h(x)＝x2+h1x+h0、f4＝0作为参数的特征为2下、亏格为2的超椭圆曲线上的除数D的标量乘法的计算方法；和执行这样的计算将作为之前所计算的值的1/h12设定为输入值，应用之前所计算的输入值1/h12而不执行计算倒数1/h12的处理。19.一种用于使得根据超椭圆曲线加密术的加密计算在计算机上被执行的计算机程序，包括在关于在超椭圆曲线上的除数D的标量乘法的计算中，执行包括二等分作为计算处理的计算运算的计算步骤。全文摘要实现超椭圆加密的安全、高速计算的装置和方法。通过执行包括1/2乘法的计算来增加超椭圆曲线加密的因数D的标量乘法的速度。例如，执行具有带有亏格为2和特征为2的参数h(x)＝x文档编号G09C1/00GK101031944SQ20058003317公开日2007年9月5日申请日期2005年9月26日优先权日2004年9月30日发明者北村出,坚木雅宣,高木刚申请人:索尼株式会社