CN1841443A

CN1841443A - 计算方法、计算设备以及计算机程序

Info

Publication number: CN1841443A
Application number: CNA2005100890451A
Authority: CN
Inventors: 伊藤孝一; 向田健二
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2005-03-30
Filing date: 2005-08-03
Publication date: 2006-10-04
Anticipated expiration: 2025-08-03
Also published as: DE602005018442D1; EP1708081B1; JP2006276786A; KR100723996B1; US20060222175A1; JP4662802B2; US8085931B2; CN1841443B; KR20060106565A; EP1708081A1

Abstract

计算方法、计算设备以及计算机程序。计算设备计算2^m*k+1关于除数n的等价值H₀≡2^m*k+1(mod n)(步骤A)，通过REDC运算根据H₀计算2^m*k+1(mod n)的等价值H≡2^E（p,m,k)(mod n)(步骤B)，以及当2^p＞m×k时通过H＝REDC(H，G)_n对于g＝2^k*G(p,m,k)(mod n)进行校正运算(步骤C)。

Description

计算方法、计算设备以及计算机程序

技术领域

本发明涉及一种用于计算与蒙哥马利乘法求余运算(Montgomerymultiplication remainder operation)中要用的蒙哥马利变换参数相关的值的计算方法、一种采用了该计算方法的计算设备以及一种用于实现该计算设备的计算机程序，具体来说，涉及一种用于提高计算速度的计算方法、计算设备以及计算机程序。

背景技术

可以预计，随着信息社会将来的发展，使用电子货币或诸如基本居民登记网络的信息网络的业务将得到广泛应用。信息安全技术对于安全地管理这些业务而言是不可缺少的，并且密码技术被用作信息安全的基本技术。通过使用密码技术，可以实现诸如加密、数字签名以及认证的功能，并且可以保护个人信息不受第三方的未授权访问。

迄今为止，公知的有各种系统作为用于实现密码技术的密码系统，这些系统可以被大致分为共钥密码系统和公钥密码系统两种类型。被称为共钥密码系统的系统是这样的系统，其在加密和解密时使用相同的密钥(共钥)，并通过将对于除发送方和接收方以外的第三方而言未知的信息设为该共钥来保持安全性。公钥密码系统是这样的系统，其在加密和解密时使用不同的密钥，并通过将仅由接收方拥有的保密信息设为用于对密文进行解密的密钥(秘密密钥)来保持安全性，而不是像用于加密的密钥(公钥)那样公众均能获得。当使用共钥密码系统时，必须以除发送方和接收方以外的第三方未知的安全方式共享上述共钥。另一方面，公钥密码系统的优点是无需在发送方与接收方之间共享保密信息，但是缺点是与共钥密码系统相比，用于进行处理的计算量非常大。因此，在公钥密码系统中，提高计算处理的速度是主要问题。

公知的公钥密码系统的代表系统是RSA密码技术和椭圆曲线密码技术。在RSA密码技术中进行利用取幂求余运算的处理，而在椭圆曲线密码技术中进行利用被称为点标量乘法(point scalar multiplication)的运算的处理。这两种运算都使用由表达式y＝a×b(mod n)表示的乘法求余运算作为基本运算，该表达式使用了对求余的除数进行表示的整数n以及满足0≤a，b＜n的整数a和b。

然而，当直接在硬件或软件中实现乘法求余运算时，处理时间变得很长并且处理效率变得很低。因此，广泛采用的是利用被称为蒙哥马利乘法求余的运算方法来进行计算，该蒙哥马利乘法求余使用由以下表达式而非乘法求余运算所表示的整数a、b和n。通过使用由以下表达式表示的蒙哥马利乘法求余运算，可以实现比常规乘法求余运算更快的处理。应当注意，以下表达式和以下说明中的符号“*”表示乘法符号“×”。

y＝a×b×R^-1(mod n)

其中，n：对求余的除数进行表示的整数

a，b：满足0≤a，b＜n的整数

R：由2^m*k表示的常数

k：每1个字的位长

m：对n进行表示所需的最少字数

图1是示出蒙哥马利乘法求余运算的算法的说明图。应当注意，图1所示算法中的x＝(x_m-1，...，x₁，x₀)表示用于将整数x表示成m个字值x_i(i＝m-1，...，1，0，0≤x_i＜2^k)的格式。根据如图1所示的由m个字值分别表示的a、b和n，在以下说明中，将计算由m个字表示的值y的情况下的蒙哥马利乘法求余运算y＝a×b×R^-1(mod n)表达成y＝REDC(a，b)_n或仅仅写成REDC。此外，在包括图1的附图和以下说明中，符号“：＝”表示将右手侧的数值或表达式赋予左手侧。

如上所述，蒙哥马利乘法求余运算是a×b×R^-1(mod n)并进行与常规乘法求余运算a×b(mod n)不同的运算。因此，为了正确地执行取幂求余运算，必须把要代入蒙哥马利乘法求余的输入数据变换成被称为蒙哥马利系统的数据。当把要带入常规乘法求余运算的任意输入数据表示成x时，将通过把x变换成蒙哥马利系统而获得的数据表示成x’，将从x变换成x’的变换(蒙哥马利变换)表示成x’＝Mont(x)，而将从x’变换成x的变换(蒙哥马利反变换)表示成x＝Mont^-1(x’)，以下表达式给出了这些变换：

蒙哥马利变换：x’＝Mont(x)＝x×R(mod n)

蒙哥马利反变换：x＝Mont^-1(x’)＝x’×R^-1(mod n)

可以由使用REDC的以下表达式表示由以上表达式所表示的蒙哥马利变换和蒙哥马利反变换。其中，H是被称为蒙哥马利变换参数的值，其被表示成H＝R²(mod n)，并通过预先计算而获得。

蒙哥马利变换：x’＝REDC(x，H)_n＝x×R²×R^-1＝x×R(mod n)

其中，H＝R²(mod n)

蒙哥马利反变换：x＝REDC(x’，1)_n＝x’×1×R^-1＝x’×R^-1(mod n)

以下说明将对利用根据上述表达式的蒙哥马利乘法求余的取幂求余运算的算法进行阐述。图2是示出使用蒙哥马利乘法求余运算的取幂求余运算的算法的说明图。图2示出了基于被称为二进制方法的取幂求余运算的蒙哥马利乘法求余运算的算法，并且根据输入值a、d和n计算出取幂求余运算结果y＝a^d(mod n)。图2中第一行中的处理表示将1赋作y的初始值。第二行中的处理表示计算蒙哥马利变换参数H＝R²(mod n)。第三行中的处理表示对y和a进行蒙哥马利变换以获得y’和a’。第四行到第七行中的循环表示从d的最低有效位到最高有效位，根据d的位值重复进行一次或两次蒙哥马利乘法求余的处理。第八行中的处理表示对在第四行到第七行的循环中计算出的y’进行蒙哥马利变换以获得最终运算结果y。

以下说明将阐述要在图2所示的算法的第二行中进行的蒙哥马利变换参数H＝R²(mod n)的计算方法。图3是示出蒙哥马利变换参数的计算方法的算法的说明图。图3所示的蒙哥马利变换参数的计算方法是通过重复加法、比较以及减法来计算与R＝2^x的情况对应的H＝R²(mod n)的方法。第一行中的处理表示计算H＝R(mod n)。尽管存在各种计算H＝R(mod n)的方法，但是例如当对于R＝2^x，n的有效位长是x时，可以简单地通过R(mod n)＝0-n进行计算。第二行到第五行中的循环对于H＝R(mod n)计算H+H，然后当该结果大于或等于n时减去n，以执行H+H(modn)的加法求余(2倍求余)。应当注意，也可以通过左移一位运算实现H+H的计算。图3所示的算法通过将以上加法求余运算重复x次来计算R×2^x(mod n)＝R²(mod n)。

然而，图3所示的蒙哥马利变换参数的计算方法的算法具有这样的缺点，即，由于在第二行到第五行中将加法求余重复x次，所以处理速度较慢。例如，在n为1024位的RSA运算的情况下，R＝2¹⁰²⁴，这意味着必须进行1024次加法求余运算，并且计算量变得极大，这使得处理速度降低。

因此，通过对REDC运算、移位运算以及减法进行组合，已提出了一些方法来提高蒙哥马利变换参数H＝R²(mod n)的计算速度。以下说明将这些方法作为常规方法1到3进行阐述。应当注意，在以下对常规方法1到常规方法3的说明中，将每1个字的位长表示成k，将由m个字值表示的值表示成n，并将从n的最高有效数字起连续“0”的个数表示成q。例如，在k＝8的情况下，当n的位串是“00101011 11001111”时，m＝2且q＝2，而当n的位串是“10001001 11100110 11100101”时，m＝3且q＝0。

常规方法1

图4是示出常规方法1中的蒙哥马利变换参数的计算方法的流程图。在图4所示的常规方法1中，输入求余的除数n并输出R²(mod n)。其中，R＝2^m*k(mod n)。常规方法1主要由步骤A1和步骤B1组成。步骤A1是利用移位运算和减法来计算H₀＝2^v×R(mod n)的步骤。其中，v是自然数。步骤B1是利用REDC运算根据H₀计算H＝R²(mod n)的步骤。

在步骤A1的步骤S101中，将“n”和“0”作为初始值分别赋予第一寄存器REG1和第二寄存器REG2。应当注意，n的有效字长是m，将从按右对齐方式存储在第一寄存器REG1中的初始值n的最高有效数字起连续“0”的个数表示成q。应当注意，在以下说明中，将存储在第一寄存器REG1中的值表示成REG1，将存储在第二寄存器REG2中的值表示成REG2。

在步骤A1的步骤S102中，对于第一寄存器REG1重复执行q次左移一位运算以计算REG1＝n’＝n×2^q。

在步骤A1的步骤S103中，将通过REG2-REG1计算出的值存储在第二寄存器REG2中以使REG2＝n’＝n×2^q。

在步骤A1的步骤S104中，重复v+q次以下运算以使REG2＝2^m*k+v+q：对于第二寄存器REG2进行左移一位运算、对REG2≥REG1进行真/假判断、以及当REG2≥REG1为真时将REG2-REG1的运算结果存储在第二寄存器REG2中的处理。其中，v是满足v≥1、并使得对于m和k而言(m×k)/v是2的幂的整数。

在步骤A1的步骤S105中，对于第一寄存器REG1和第二寄存器REG2重复q次右移一位运算，以计算出REG1＝n和REG2＝H₀＝2^m*k+v(mod n)。

在步骤B1的步骤S106中，将被表示成REDC(REG2，REG2)_n的REDC运算的结果存储在第二寄存器REG2中的处理重复p次，以计算REG2＝H＝2^2*m*k(mod n)＝R²(mod n)。其中，p是满足p＝log₂((m×k)/v)的整数，REDC(REG2，REG2)_n表示蒙哥马利乘法求余运算REDC(A，B)_n＝2^-m*k×A×B(mod n)。

在步骤S107中，输出计算结果REG2＝R²(mod n)并且处理结束。

图5是示出常规方法1中的蒙哥马利变换参数的计算方法所需运算次数的图表。图5按运算的类型和步骤示出了利用图4所示的常规方法1的计算方法所需的运算次数。应当注意，图5中，SFT表示进行一位移位的移位运算，SUB表示减法，CMP表示比较运算，REDC表示蒙哥马利乘法求余运算。

为了满足步骤S106中的条件，即，p必须是满足p＝log₂((m×k)/v)的整数，存在这样的限制：(m×k)/v的值必须由(m×k)/v＝2^x(使用整数x)表示，即，其值为2的幂。由于常规方法1中的v值的选择因该限制而受限，所以v的值需要随着n的有效位长而增加。如从图5所示的图表看到的，由于SFT、SUB和CMP的计算次数取决于v，所以总计算量随着v的增加而增加。

接下来，参照图5所示的图表对常规方法1中的计算方法的运算次数的示例进行描述。

示例1-1.应用于1024位的RSA密码技术的计算

根据以上条件，n是1024位。假设1个字＝32位，则k＝32并且n的有效字长：m＝32。由于每1个字的位长k与n的有效字长m的乘积k×m等于n的总位数，所以n的最高有效位＝1并且q＝0。此外，由于m×k＝1024，所以可以选择v＝1，2，4，...，1024。当v＝1时，SFT是4×0+1＝1次，SUB是0.5×(0+1)+1＝1.5次，CMP是0+1＝1次，REDC是p＝log₂((32×32)/1)＝10次。

示例1-2.应用于163位的椭圆曲线密码技术的计算

根据以上条件，n是163位。假设1个字＝8位，则k＝8并且n的有效字长：m＝21。假设n的位长＝8并且有效字长m＝21，则最高有效m×k-163＝21×8-163＝5位是0并且q＝5。此外，由于m×k＝168，所以可以选择v＝21，42，84，168。当v＝21时，SFT是4×5+21＝41次，SUB是0.5×(5+21)+1＝14次，CMP是5+21＝26次，REDC是p＝log₂((21×8)/21)＝3次。

例如在日本特开平8-263316(1996)号公报、日本特开平8-339310(1996)号公报以及日本特开平11-305995(1999)号公报中公开了常规方法1中所描述的这种计算方法。

常规方法2

图6是示出了常规方法2中的蒙哥马利变换参数的计算方法的流程图。在图6所示的常规方法2中，输入求余的除数n并输出R²(mod n)。其中，R＝2^m*k(mod n)。常规方法2主要由步骤A2和步骤B2组成。步骤A2是使用例如与常规方法1中所描述的处理相同的处理中的移位运算和减法来计算H₀＝2^v×R(mod n)的步骤。其中，v是自然数。步骤B2是利用REDC运算从H₀计算出H＝R²(mod n)的步骤。

在步骤A2的步骤S201中，将“n”和“0”作为初始值分别赋予第一寄存器REG1和第二寄存器REG2。应当注意，n的有效字长是m，将从按右对齐方式存储在第一寄存器REG1中的初始值n的最高有效数字起连续“0”的个数表示成q。

在步骤A2的步骤S202中，对于第一寄存器REG1重复执行q次左移一位运算，以计算REG1＝n’＝n×2^q。

在步骤A2的步骤S203中，将通过REG2-REG1计算出的值存储在第二寄存器REG2中，以使得REG2＝n’＝n×2^q。

在步骤A2的步骤S204中，重复v+q次2倍求余运算以使得REG2＝2^m*k+v+q，该2倍求余运算由以下运算组成：对于第二寄存器REG2进行左移一位运算、对REG2≥REG1进行真/假判断、以及当REG2≥REG1为真时将REG2-REG1的运算结果存储在第二寄存器REG2中的处理。其中，v是满足v≥1、并使得对于m和k而言(m×k)/v是自然数。

在步骤A2的步骤S205中，对第一寄存器REG1和第二寄存器REG2重复q次右移一位运算，以计算REG1＝n和REG2＝H₀＝2^m*k+v(mod n)。然后，将存储在第二寄存器REG2中的值存储到辅助寄存器REG0中。

在步骤B2的步骤S206中，将被表示成REDC(REG2，REG2)_n的REDC运算的结果存储在第二寄存器REG2中，此外，当(m×k)的第i位值＝1时，对i＝p’-2，...，1，0，重复p’-1次将被表示成REDC(REG2，REG2)_n的REDC运算的结果存储在第二寄存器REG2中的处理，以计算REG2＝H＝2^2*m*k(mod n)＝R²(mod n)。其中，p’是表示位长为(m×k)/v的整数，REDC(A，B)_n表示蒙哥马利乘法求余运算REDC(A，B)_n＝2^-m*k×A×B(mod n)。

在步骤S207中，输出计算结果REG2＝R²(mod n)并且处理结束。

图7是示出了常规方法2中的蒙哥马利变换参数的计算方法所需的运算次数的图表。图7按运算的类型和步骤示出了利用图6而示出的常规方法2的计算方法所需的运算次数。应当注意，图7中，SFT表示进行一位移位的移位运算，SUB表示减法，CMP表示比较运算，REDC表示蒙哥马利乘法求余运算。此外，W(x)是x的除最高有效位以外的1的个数，并且在步骤S206中在(m×k)/v的位值是1的情况下是REDC运算的次数。例如，W((10000)₂)＝0并且W((1000101)₂)＝2。其中，符号(...)₂表示二进制数，例如(1101)₂＝13，(11100)₂＝28。

由于p’是由步骤S206所示的(m×k)/v表示的整数，并且在常规方法2中可以按比常规方法1更宽的条件设置v的值，所以可以通过设置v的最佳值，使得以比常规方法1小的计算量计算出蒙哥马利变换参数H。

接下来，参照图7所示的图表对常规方法2中的计算次数的示例进行说明。

示例2-1.应用于1024位的RSA密码技术的计算

根据以上条件，n是1024位。假设1个字＝32位，则k＝32并且n的有效字长：m＝32。由于每1个字的位长k与n的有效字长m的乘积k×m等于n的总位数，所以n的最高有效位＝1并且q＝0。此外，由于m×k＝1024，所以可以从1024个任意因数(factor)中选择v。当v＝1时，SFT是1次，SUB是0.5×(1)+1＝1.5次，CMP是1次，REDC是p＝log₂((32×32)/1)＝10次。

示例2-2.应用于163位的椭圆曲线密码技术的计算

根据以上条件，n是163位。假设1个字＝8位，则k＝8并且n的有效字长：m＝21。假设n的位长＝8并且有效字长m＝21，则最高有效m×k-163＝21×8-163＝5位是0并且q＝5。此外，由于m×k＝168，所以可以从168个任意因数中选择v。当v＝21时，SFT是4×5+21＝41次，SUB是0.5×(5+21)+1＝14次，CMP是5+21＝26次，并且根据(m×k)/v＝(1000)₂，REDC是p’-1+W((m×k)/v)＝4-1+0＝3次。

例如在美国专利No.5777916中公开了在常规方法2中描述的这种计算方法。

常规方法3

图8是示出常规方法3中的蒙哥马利变换参数的计算方法的流程图。在图8所示的常规方法3中，输入求余的除数n并输出R²(mod n)。其中，R＝2^m*k(mod n)。常规方法3主要由步骤A3、步骤B3以及步骤C3组成。步骤A3是利用移位运算和减法来计算满足H₀＝2^m*k+v的H₀的步骤。其中，v是自然数并且满足：(m×k)/v是自然数。步骤B3是利用REDC运算根据H₀计算H＝2^{E(p”，m，k)}(mod n)的步骤。其中，p”是整数，其满足：2^p”-1＜(m×k)/v≤2^p”，并且E(p”，m，k)＝m×k+v×2^p”。步骤C3是当2^p”＞(m×k)/v时对于g＝2^{k*G(p”，m，k)}通过H＝REDC(H，G)_n进行校正运算的步骤。其中，G由G(p”，m，k)＝2×m-(v×2^p”)/k表示并且是满足1≤G(p”，m，k)≤m-1的范围的整数。

在步骤A3的步骤S301中，将“n”和“2^(m-1)*k”作为初始值分别赋给第一寄存器REG1和第二寄存器REG2。应当注意，n的有效字长是m。

在步骤A3的步骤S302中，重复k+v次2倍求余运算以使得REG2＝H₀＝2^m*k+v(mod n)，该2倍求余运算由以下运算组成：对于第二寄存器REG2进行左移一位处理、对REG2≥REG1进行真/假判断、以及当REG2≥REG1为真时将REG2-REG1的运算结果存储在第二寄存器REG2中的处理。其中，v是自然数并且(m×k)/v是整数。

在步骤B3的步骤S303中，对于i＝1，2，...，p”，重复p”次将被表示成REDC(REG2，REG2)_n的REDC运算的结果存储在第二寄存器REG2中的处理，以计算REG2＝2^{E(p”，m，k)}(mod n)。其中，p”是满足2^p”-1＜(m×k)/v≤2^p”的整数，E(p”，m，k)＝m×k+v×2^p”，并且REDC(A，B)_n表示蒙哥马利乘法求余运算REDC(A，B)_n＝2^-m*k×A×B(mod n)。

在步骤C3的步骤S304中，当2^p”＞(m×k)/v时将被表示成REDC(REG2，g)_n的REDC运算的结果存储在第二寄存器REG2中。其中，g＝2^{k*G(p”，m，k)}并且G(p”，m，k)＝2×m-(v×2^p”)/k。

在步骤S305中，输出计算结果REG2＝R²(mod n)并且处理结束。

图9是示出常规方法3中的蒙哥马利变换参数的计算方法所需的运算次数的图表。图9按运算的类型和步骤示出了利用图8而示出的常规方法3的计算方法所需的运算次数。应当注意，图9中，SFT表示进行一位移位的移位运算，SUB表示减法，CMP表示比较运算，REDC表示蒙哥马利乘法求余运算。

如步骤A3所示，在常规方法3中不使用q值来计算H₀。此外，通过将步骤S304中所示的校正运算处理添加到步骤S303中，不再存在(m×k)/v的值必须是2的幂的限制，并且v只要满足步骤S302中所示的条件即可。此外，无需检测(m×k)/v的各个位值。

接下来，参照图9所示的图表对常规方法3中的计算次数的示例进行说明。

示例3-1.应用于1024位的RSA密码技术的计算

根据以上条件，n是1024位。假设1个字＝32位，则k＝32并且n的有效字长：m＝32。由于m×k＝1024，所以可以从1024个任意因数中选择v。当v＝1时，SFT是32+1＝33次，SUB是0.5×(32+1)＝16.5次，CMP是32+1＝33次，REDC是p＝log₂((32×32)/1)＝10次。

示例3-2.应用于163位的椭圆曲线密码技术的计算

根据以上条件，n是163位。假设1个字＝8位，则k＝8并且n的有效字长：m＝21。由于m×k＝168，所以可以从168个任意因数中选择v。当v＝21时，SFT是8+21＝29次，SUB是0.5×(8+21)＝14.5次，CMP是8+21＝29次，并且根据(m×k)/v＝(1000)₂，REDC是p’-1+W((m×k)/v)＝4-1+0＝3次。

例如在PCT国际公开No.2005/013243中公开了常规方法3中描述的这种计算方法。

然而，以上常规方法1到常规方法3存在如下所述地要解决的问题。

问题1

由于常规方法1所描述的计算方法中的步骤A1的处理使用从存储在第一寄存器REG1中的“n”的位串中的较高位起连续“0”的个数作为后续计算所需的参数q，所以必需计算数据值的最高有效位(以下称为MSB)。这存在如下问题：为了计算MSB，必需进行按位(bit-oriented)运算处理，而该按位运算处理在软件实现中的处理效率较低。此外，由于从图5所示的图表显见，移位运算次数、减法次数以及比较运算次数取决于q的值，所以存在处理负荷随着q变大而增加的问题。如上所述，存在与q相关的处理负荷增加的问题。

问题2

此外，常规方法1所描述的计算方法被设计成在步骤B1的处理中重复p次REDC运算以计算H＝2^2*m*k(mod n)＝R²(mod n)。其中，p限于满足p＝log₂((m×k)/v)的整数，即，该值使得(m×k)/v的值是2的幂。为了满足该限制，按以下过程确定m、k以及v：根据n的位长和每1个字的位长确定m和k，并对于确定的m和k将v的值设置为使得(m×k)/v的值为2的幂。即，由于必须将v的值设成使得(m×k)/v的值为2的幂的限制，v的值可能很大。如从图5中所示的图表显见，移位运算次数、减法次数以及比较运算次数取决于v的值，因而存在处理负荷随着v变大而增加的问题。如上所述，存在如下问题：与(m×k)/v的值必须是2的幂的限制相关的处理负荷增加。

问题3

常规方法2所描述的计算方法(包括与常规方法1的步骤A1的处理相同的步骤A2的处理)具有与常规方法1类似的与q相关的处理负荷增加的问题。

问题4

此外，由于在步骤B2的处理中重复p’-1次REDC运算，并且常规方法2所描述的计算方法检测(m×k)的第i个位值，所以存在这样的问题：必需进行在软件实现中处理效率很低的按位运算处理。如上所述，由于重复进行REDC运算而存在与对(m×k)/v的各个位值进行检测相关的问题。

问题5

常规方法3所描述的计算方法的优势在于：没有常规方法1和常规方法2中所描述的取决于q值以及MSB的计算的处理。然而，由于在步骤A3的处理中重复k+v次2倍求余运算，所以从图9所示的图表显见，移位运算次数、减法次数以及比较运算次数取决于k的值，并且处理负荷随着k变大而增加。

图10是示出常规方法中的蒙哥马利变换参数的计算方法所需的运算次数的图表。图10示出了图5所示的常规方法1中的步骤A1的计算量、图7所示的常规方法2中的步骤A2的计算量以及图8所示的常规方法3中的步骤A3的计算量。应当注意，移位运算SFT、减法SUB以及比较运算CMP的运算所需的处理负荷被视为是相同的，从而便于对各计算方法中的处理负荷进行比较，并且以常数LC代替该运算所需的处理负荷。

图10的图表表明：当满足(2.5×k+2.5×v)×LC＜(5.5×q+2.5×v+1)×LC时，即，当满足(5×k-2)/11＜q时，常规方法3中所描述的计算方法的计算量比常规方法1和常规方法2的计算量小，并且是高效的方法。然而，当q的值较小并且满足(5×k-2)/11＞q，即，当q较小时，常规方法3中所描述的计算方法的计算量比常规方法1和常规方法2的计算量大，并且变得低效。

在RSA密码技术中，实际上通常使用为2的幂的n的位长(如2048、1024或512)作为q的值，在这种情况下q＝0。尽管在使用椭圆曲线密码技术时n的位长取任意值，但是在SECG(Standards for EfficientCryptography Group)中的SEC1所指定的标准中，推荐使用32的倍数的位长，如160、192或224，在使用这些参数中任一个的情况下q＝0。

因此，从实际观点来看，常规方法3中所描述的计算方法并不总是优于常规方法1和常规方法2，并且在q的值较小时存在步骤A3处理的处理负荷比步骤A1和A2处理的处理负荷大的问题。

发明内容

为解决以上问题而提出了本发明，本发明的目的是提供一种计算方法、采用了该计算方法的计算设备以及用于实现该计算设备的计算机程序，其能够通过以下步骤解决常规方法1到常规方法3中的问题：获得n的负数作为2^m*k关于除数n的等价值，并将该负数存储在寄存器中；重复对存储在该寄存器中的值在进位方向上进行一位移位、并舍去溢出该寄存器的最高有效位的处理，直到要舍去的最高有效位变成0，以获得2^m*k+1关于除数n的等价值并将该等价值存储在寄存器中；以及根据存储在该寄存器中的值，通过蒙哥马利乘法求余运算计算出使得关于除数n的余数值与蒙哥马利变换参数关于除数n的余数值相同的等价值。

根据第一方面的计算方法是一种用于使用寄存器计算与蒙哥马利变换参数相关的值的计算方法，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该寄存器具有至少m个字，每个字的位长是k，该计算方法的特征在于包括以下步骤：获得n的负数作为2^m*k关于除数n的等价值，并将该负数存储在寄存器中；重复对存储在该寄存器中的值在进位方向上进行一位移位、并舍去溢出该寄存器的最高有效位的处理，直到要舍去的最高有效位变成0，以获得2^m*k+1关于除数n的等价值并将该等价值存储在寄存器中；以及根据存储在该寄存器中的值通过蒙哥马利乘法求余运算计算出使得关于除数n的余数值与蒙哥马利变换参数关于除数n的余数值相同的等价值。

根据第二方面的计算方法是根据第一方面的计算方法，其特征在于利用所计算出的等价值执行取幂求余运算。

根据第三方面的计算设备是一种用于计算与蒙哥马利变换参数相关的值的计算设备，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该计算设备的特征在于包括：寄存器；用于在该寄存器中存储求余的除数n的负数的装置；用于重复对存储在该寄存器中的值在进位方向上进行一位移位的处理直到溢出该寄存器的最高有效位变成0的装置；以及用于根据存储在该寄存器中的值通过蒙哥马利乘法求余运算计算出使得关于除数n的余数值与蒙哥马利变换参数关于除数n的余数值相同的等价值。

根据第四方面的计算设备是一种用于计算与蒙哥马利变换参数相关的值的计算设备，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该计算设备的特征在于包括：寄存器，至少具有m个字，每个字的位长是k；运算装置，用于对值A和B以及有效字长为m的求余的除数n执行被定义为2^-m*k×A×B(mod n)的蒙哥马利乘法求余运算REDC(A，B)_n；用于在该寄存器中存储求余的除数n的负数的装置；用于重复对存储在该寄存器中的值在进位方向上进行一位移位的移位处理直到溢出该寄存器的最高有效位变成0的装置；用于重复p次通过运算装置对存储在寄存器中的值REG执行蒙哥马利乘法求余运算REDC(REG，REG)_n并将其结果存储在该寄存器中的处理的装置，p是满足2^p-1＜m×k≤2^p的整数；用于在2^p＞m×k(其中，g＝2^{k*G(p，m，k)}并且G(p，m，k)＝2×m-2^p/k)时通过运算装置对存储在寄存器中的值REG执行蒙哥马利乘法求余运算REDC(REG，g)_n并将其结果存储在该寄存器中的装置；以及用于输出存储在该寄存器中的值REG作为使得关于除数n的余数值与蒙哥马利变换参数关于除数n的余数值相同的等价值的装置。

根据第五方面的计算设备是根据第四方面的计算设备，其特征在于还包括：多个寄存器；用于在具有m个字的第一寄存器中存储n并在具有m个或更多个字的第二寄存器中存储0的装置；以及用于从存储在第二寄存器中的值中减去存储在第一寄存器中的值以计算出求余的除数n的负数的装置。

根据第六方面的计算设备是根据第四方面的计算设备，其特征在于还包括：用于在所述寄存器中存储求余的除数n的装置；以及用于计算存储在所述寄存器中的值的补数作为求余的除数n的负数的装置。

根据第七方面的计算设备是根据第四方面的计算设备，其特征在于还包括：用于将除数n存储在所述寄存器中的装置；用于使存储在所述寄存器中的值取反的装置；以及用于在存储在所述寄存器中的值的最低有效位是1的情况下计算求余的除数n的负数的装置。

根据第八方面的计算设备是根据第四方面到第七方面中的任一方面的计算设备，其特征在于：所述移位处理是将存储在寄存器中的值加到所述值的加法处理，并且在该移位处理中溢出所述寄存器的最高有效位被检测为由该加法处理产生的进位值。

根据第九方面的计算机程序是一种用于使计算机计算与蒙哥马利变换参数相关的值的计算机程序，该计算机包括具有至少m个字的寄存器，每1个字的位长是k，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该计算机程序的特征在于使得该计算机执行以下过程：获得n的负数作为2^m*k关于除数n的等价值，并将该负数存储在寄存器中；重复对存储在该寄存器中的值在进位方向上进行一位移位并舍去溢出该寄存器的最高有效位的处理，直到要舍去的最高有效位变成0，以获得2^m*k+1关于除数n的等价值并将该等价值存储在寄存器中；以及根据存储在该寄存器中的值通过蒙哥马利乘法求余运算计算出使得关于除数n的余数值与蒙哥马利变换参数关于除数n的余数值相同的等价值。

在第一方面、第三方面、第四方面以及第九方面中，计算出得到关于除数n的相同余数值的等价值作为与蒙哥马利变换参数相关的值，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值。尽管存在该余数值必须大于或等于0并且小于除数n的限制，但是对该等价值不存在限制。因此，通过计算等价值而非余数，放松了该限制并且基于该限制的各种处理都变得不必要了，从而可以提高计算处理的速度。此外，通过把等价值作为计算结果，除针对严格限制的余数值以外，还可以针对在计算处理中产生的中间数据使用放松限制的等价值，从而可以提高计算处理的速度。

例如，在进行计算的同时调整REG2的值以使其保持小于n’的以上常规方法1的步骤A1和常规方法2的步骤A2中，由于必须执行取决于q的次数的移位运算，所以存在问题1和问题3所指出的问题。此外，在进行计算的同时调节REG2的值以使其保持小于n的以上常规方法3的步骤A3中，存在问题5所指出的问题。问题1、问题3以及问题5所述的这些问题是由于要计算余数值大于或等于0并且小于除数n的值而产生的，本发明通过计算余数值的等价值而非该余数值，可以解决这些问题并提高计算处理的速度。

应当注意，在本发明中进行这样的处理：重复对存储在寄存器中的值在进位方向上进行一位移位并舍去溢出该寄存器的最高有效位的处理，直到要舍去的最高有效位变成0。重复移位运算的处理和判断要舍去的1位的值的处理比常规方法1的步骤S104、常规方法2的步骤S204以及常规方法3的步骤S302中进行的重复移位运算和比较运算的方法具有更高的运算效率。这是因为对1位的值的进行判断(仅包括1位的运算)可以比多位运算要快，而对于通过公钥密码系统进行的运算中使用具有160-2048位的极长的位长的数据，移位运算和比较运算执行了多位运算。由于本发明通过不把计算目标限制于余数值而是将余数值扩展到等价值，打破了各种限制，所以能够实现只使用1位判断的高效处理。

此外，在本发明中，由于不存在(m×k)/v必须是2的幂值的限制，所以可以解决常规方法1的问题2所指出的问题。

此外，在本发明中，由于重复了p’-1次REDC运算并且不进行检测(m×k)的第i位值的处理，所以可以解决常规方法2的问题4所指出的问题。

在第二方面中，由于还可以利用等价值执行取幂求余运算，所以通过执行使用等价值的处理(如上所述，其得到高处理效率)可以提高总处理速度。

在第五到第八方面中，由于可以使用现有算法，所以很容易实现。

一种用于使用寄存器计算与蒙哥马利变换参数相关的值的计算方法、计算设备以及计算机程序，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该寄存器至少具有m个字，每1个字的位长是k，该计算方法、计算设备以及计算机程序执行以下处理：获得n的负数作为2^m*k关于除数n的等价值，并将该负数存储在寄存器中；重复对存储在该寄存器中的值在进位方向上进行一位移位并舍去溢出该寄存器的最高有效位的处理，直到要舍去的最高有效位变成0，以获得2^m*k+1关于除数n的等价值并将该等价值存储在寄存器中；以及根据存储在该寄存器中的值通过蒙哥马利乘法求余运算计算出使得关于除数n的余数值与蒙哥马利变换参数关于除数n的余数值相同的等价值。

尽管常规方法中使用的余数值存在必须大于或等于0并且小于除数n的限制，但是本发明中使用的等价值不存在限制。因此，由于通过计算等价值而非余数值放松了限制，所以变得不必执行基于该限制的各种处理，并可以提供更优良的效果，如提高了计算处理的速度。此外，通过把等价值作为计算结果，由于除针对严格限制的余数值以外，还可以针对在计算处理中产生的中间数据使用宽松限制的等价值，所以可以提供更优良的效果，如提高了计算处理的速度。

此外，在本发明中，由于可以使用如上所述的具有高处理效率的等价值来执行取幂求余运算，所以可以提供更优良的效果，如提高了总处理速度。此外，由于本发明可以应用于使用诸如RSA密码技术或椭圆曲线密码技术的公钥密码系统，所以可以提供更优良的效果，如提供用于实现快速和高度保密通信的信息安全技术。

根据参照附图进行的以下详细描述，本发明的以上和其它目的和特征将更加全面地显见。

附图说明

图1是示出蒙哥马利乘法求余运算的算法的说明图；

图2是示出利用蒙哥马利乘法求余运算的取幂求余运算的算法的说明图；

图3是示出蒙哥马利变换参数的计算方法的算法的说明图；

图4是示出常规方法1中的蒙哥马利变换参数的计算方法的流程图；

图5是示出常规方法1中的蒙哥马利变换参数的计算方法所需的运算次数的图表；

图6是示出常规方法2中的蒙哥马利变换参数的计算方法的流程图；

图7是示出常规方法2中的蒙哥马利变换参数的计算方法所需的运算次数的图表；

图8是示出常规方法3中的蒙哥马利变换参数的计算方法的流程图；

图9是示出常规方法3中的蒙哥马利变换参数的计算方法所需的运算次数的图表；

图10是示出常规方法中的蒙哥马利变换参数的计算方法所需的运算次数的图表；

图11是示出本发明的计算设备的结构示例的框图；

图12是示出与本发明的计算方法相关的蒙哥马利乘法求余运算的算法的说明图；

图13是示出使用与本发明的计算方法相关的蒙哥马利乘法求余运算的取幂求余运算的算法的说明图；

图14是示出本发明的计算设备的处理流程图；

图15是示意性地示出要存储于包括在本发明的计算设备中的第一寄存器和第二寄存器中的值的说明图；

图16是示意性地示出要存储于包括在本发明的计算设备中的第一寄存器和第二寄存器中的值的说明图；

图17A到17D是示意性地示出要存储于包括在本发明的计算设备中的第二寄存器中的值的说明图；

图18A和18B是示意性地示出要存储于包括在本发明的计算设备中的第二寄存器中的值的说明图；

图19A和19B是示意性地示出要存储于包括在本发明的计算设备中的第二寄存器中的值的说明图；

图20是示出本发明的蒙哥马利变换参数的计算方法所需的运算次数的图表；

图21是示出本发明的计算方法和常规方法中的蒙哥马利变换参数的计算方法所需的运算次数的图表；以及

图22是示出本发明的计算方法和常规方法中的蒙哥马利变换参数的计算方法所需的运算次数的图表。

具体实施方式

以下说明将参照例示了本发明实施例的附图对本发明进行详细阐述。图11是示出本发明的计算设备的结构示例的框图。图11的1处表示本发明的计算设备，如用作微计算机的运算卡等，并且计算设备1被并入诸如个人计算机或服务器计算机的通信设备2中。计算设备1包括：控制装置11，如用于控制整个设备的MPU；记录装置12，如记录诸如本发明的计算机程序3等的各种计算机程序和数据的ROM或RAM；用于进行计算的第一寄存器13a和第二寄存器13b；运算装置14，如用于进行REDC运算的协处理器；以及连接装置15，用作与通信设备2的接口。通过由控制装置11执行记录装置12中所记录的本发明的计算机程序3，用作微计算机的运算卡执行作为本发明的计算设备的各种过程。应当注意，第一寄存器13a是能够存储m位二进制数据并具有m个字的寄存器，第二寄存器13b是具有m个或更多个字的寄存器。

本发明的计算设备1在如通信等的使用诸如公钥密码系统等的密码技术的处理中执行各种处理。具体来说，本发明的计算设备1利用预先记录的公钥对经由连接装置15从通信设备2接受的明文(plain text)信息进行加密以生成密文，并将所生成的密文经由连接装置15输出到通信设备2。此外，当通信设备2从另一设备接收到以公钥进行了加密的密文时，本发明的计算设备1接受经由连接装置15从通信设备2接收到的密文，利用预先记录的秘钥对该密文进行解密以生成明文，并将所生成的明文经由连接装置15输出到通信设备2。应当注意，本发明的计算设备1可以利用相同的技术通过秘钥对明文进行加密，并且可以执行数字签名所涉及的处理以利用公钥对密文进行解密。

对于公钥密码系统的密码技术，使用诸如RSA密码技术或椭圆曲线密码技术的密码系统。例如，在RSA密码技术中，使用求余的除数n，将利用公钥e对明文m进行加密而获得的密文c表示成c＝m^e(mod n)。此外，使用求余的除数n，将利用秘钥d对密文c进行解密而获得的明文m表示成m＝c^d(mod n)。如上所述，在RSA密码技术中进行被表示成y＝a^x(mod n)的取幂求余运算。此外，在椭圆曲线密码技术中也使用乘法求余运算处理。

本发明的计算设备1利用如下运算方法代替乘法求余运算处理来进行加密处理和解密处理，该方法称为蒙哥马利乘法求余、使用整数a、b和n并且由以下表达式表示：

Y＝a×b×R^-1(mod n)

其中n：对求余的除数进行表示的整数

a，b：满足0≤a，b＜n的整数

R：由2^m*k表示的常数

k：每1个字的位长

m：表示n所需的最少字数

图12是示出与本发明的计算方法相关的蒙哥马利乘法求余运算的算法的说明图。应当注意，图12所示的算法中的x＝(x_m-1，...，x₁，x₀)表示用于把整数x表示成m个字值x_i(i＝m-1，...，1，0，0≤x_i＜2^k)的格式。此外，在包括图12的以下附图和以下说明中，符号“：＝”表示将右手侧的数值或表达式赋予左手侧。根据如图12所示的由m个字值分别表示的a、b以及n，在以下说明中，将计算由m个字表示的值y的情况下的蒙哥马利乘法求余运算y＝a×b×R^-1(mod n)表达成y＝REDC(a，b)_n或仅仅写成REDC。如上所述定义的REDC包括下述三个性质：

(性质1)将除数n限定为奇数。

(性质2)当a和b的值都可以由m个字值表示并且满足a×b≤R×n的条件时，进行y＝a×b×R^-1(mod n)的计算。其中，满足0≤y＜n。

(性质3)当a和b的值都可以由m个字值表示并且不满足a×b≤R×n的条件时，进行y≡a×b×R^-1(mod n)的计算。其中，并不总是满足0≤y＜n 。

以下说明将对性质2中所述的计算y＝a×b×R^-1(mod n)与性质3中所述的计算y≡a×b×R^-1(mod n)之间的差别进行阐述。性质2中所述的计算与性质3中所述的计算之间的差别在于以下事实：性质2中所述的计算获得了关于除数n的“余数值”，而性质3中所述的计算获得了关于除数n的“等价值(equivalence)”。

将整数x关于除数n(其为自然数)的除法中计算出的余数y称为“余数(关于除数n)”，并表示为y＝x(mod n)。由于在余数值计算中余数y取大于或等于0并小于n的值，所以在上述性质2的计算中满足0≤y＜n。

另一方面，将并不总是大于等于0并且并不总是小于n、得到相同余数值的多个值x和x’称为“等价值(关于除数n)”，并表示为x’≡x(modn)。即，当x的余数值y、除数n以及整数s具有x’＝y+s×n的关系时，每个x’都成为x的等价值。例如，在n＝5并且x＝13的情况下，x关于除数n的余数值y成为y＝3。此外，在同样的条件下，一系列值x’＝3、8、13、18、23、……都是关于除数n的等价值并且其余数值为3。如上所述，等价值是这样的一系列数：其得到相同的关于除数n的余数，并且不限于大于或等于0并且小于n的值。因此，在以上性质3的计算中并不总是满足0≤y＜n。

如上所述，蒙哥马利乘法求余运算是a×b×R^-1(mod n)并且进行与常规乘法求余运算a×b(mod n)不同的运算。因此，为了正确地执行取幂求余运算，必须把要赋给蒙哥马利乘法求余的输入数据变换成称为蒙哥马利系统的数据。当将要赋给常规乘法求余运算的任意输入数据表示成x时，将通过把x变换成蒙哥马利系统而获得的数据表示成x’，将从x到x’的变换(蒙哥马利变换)表示成x’＝Mont(x)，而把从x’到x的变换(蒙哥马利反变换)表示成x＝Mont^-1(x’)，以下表达式给出了这些变换：

蒙哥马利变换：x’＝Mont(x)＝x×R(mod n)

蒙哥马利反变换：x＝Mont^-1(x’)＝x’×R^-1(mod n)

可以由使用REDC的以下表达式表示由上述表达式表示的蒙哥马利变换和蒙哥马利反变换。其中，H是表示成H＝R²(mod n)的、称为蒙哥马利变换参数的值，并通过预先计算而获得。

蒙哥马利变换：x’＝REDC(x，H)_n＝x×R²×R^-1＝x×R(mod n)

其中，H≡R²(mod n)

以下说明将根据以上表达式对使用蒙哥马利乘法求余的取幂求余运算的算法进行阐述。图13是示出使用与本发明的计算方法相关的蒙哥马利乘法求余运算的取幂求余运算的算法的说明图。图13示出了基于被称为二进制方法的取幂求余运算的蒙哥马利乘法求余运算的算法，并根据输入值a、d和n计算出取幂求余运算结果y＝a^d(mod n)的算法。图13的第一行中的处理表示将1赋为y的初始值。第二行中的处理表示计算蒙哥马利变换参数H’≡R²(mod n)。第三行中的处理表示对y和a进行蒙哥马利变换以获得y’和a’。第四行到第七行中的循环表示从d的最低有效位到最高有效位，根据d的位值将进行蒙哥马利乘法求余的处理重复一次或两次。第八行中的处理表示对在第四行到第七行的循环中计算出的y’进行蒙哥马利反变换以获得最终运算结果y。

以下说明将对图13所示的算法的第二行中进行的蒙哥马利变换参数H≡R²(mod n)的计算处理进行阐述。图14是示出本发明的计算设备1的处理的流程图。图14示出了由本发明的计算设备1进行的以下处理：接受求余的除数n的输入、执行本发明的计算处理并输出H≡R²(mod n)(其为R²(mod n)的等价值)。应当注意，在以下阐述中k表示每1个字的位长，n是由m个字值表示的值。此外，R＝2^m*k。应当注意，在以下附图和以下阐述中的符号“*”表示乘法符号“×”。

本发明的蒙哥马利变换参数的变换方法主要由步骤A、步骤B以及步骤C组成。步骤A是计算2^m*k+1关于除数n的等价值H₀≡2^m*k+1(mod n)的步骤。步骤B是通过REDC运算根据H₀计算2^E(p，m，k)(mod n)的等价值H≡2^E(p，m，k)(mod n)的步骤。其中，p是整数，其满足：2^p-1＜m×k≤2^p，并且E(p，m，k)＝m×k+2^p。步骤C是当2^p＞m×k时，对于g＝2^{k*G(p，m，k)}通过H＝REDC(H，G)_n进行校正运算的步骤。其中，G被表示成G(p，m，k)＝2×m-2^p/k并且是满足1≤G(p，m，k)≤m-1的范围的整数。

作为步骤A中的步骤S1的处理，本发明的计算设备1进行将“n”和“0”作为初始值分别赋予第一寄存器13a和第二寄存器13b的初始化。其中，n的有效字长是m。

图15是示意性地示出要存储于包括在本发明的计算设备1中的第一寄存器13a和第二寄存器13b中的值的说明图。图15中，REG1表示存储在第一寄存器13a中的值，REG2表示存储在第二寄存器13b中的值。在示出已执行了步骤A中的步骤S1的处理的状态的图15中，将n作为初始值存储在第一寄存器13a中，将0作为初始值存储在第二寄存器13b中。

回到图14的流程图，作为步骤A中的步骤S2的处理，本发明的计算设备1计算与2^m*k和除数n相关的等价值REG2≡2^m*k(mod n)。通过以下处理进行步骤A中的步骤S2的处理：从存储在第二寄存器13b中的值中减去存储在第一寄存器13a中的值，并将得到的结果，即除数n的负数存储在第二寄存器13b中。

通过从存储在第二寄存器13b中的值中减去存储在第一寄存器13a中的值而得到的结果(即，REG2-REG1＝0-n)(可以使用整数s将其表示成2^m*k+s×n的形式)是与2^m*k和除数n相关的等价值，并且是可由m个字表示的值。

应当注意，可以通过获得与存储在第一寄存器13a中的值n相关的2的补数值、并把获得的2的补数值存储在第二寄存器13b中，来进行步骤A中的步骤S2的处理，而不是进行所述运算处理(REG2：＝REG2-REG1)。可以通过对存储在第一寄存器13a中的n的所有位取反然后将1设置给其最低有效位，来获得与值n相关的2的补数值。

图16是示意性地示出要存储于包括在本发明的计算设备1中的第一寄存器13a和第二寄存器13b中的值的说明图。在示出已执行了步骤A中的步骤S2的处理的状态的图16中，将n作为初始值存储在第一寄存器13a中，并且将2^m*k关于除数n的等价值(已被计算为0-n)存储在第二寄存器13b中。

回到图14所示的流程图，作为步骤A中的步骤S3的处理，本发明的计算设备1计算出与2^m*k+1和除数n相关的等价值REG2＝2^m*k+1(modn)。具体来说，步骤A中的步骤S3的处理包括：对存储在第二寄存器13b中的值进行左移一位运算的处理(步骤S3-1)；和对由于左移一位运算而溢出的值(即，运算前的最高有效位值)进行判断的处理(步骤S3-2)。步骤S3-1的进行左移一位运算的处理是使第二寄存器13b的各数位中的值进位的处理，即，使存储在第二寄存器13b中的值2倍的处理、并舍去作为溢出的值的最高有效数位的位值。然后，在步骤S3-2中，当判定溢出的值为“1”时，判定存储在第二寄存器13b中的值是与除数n和2^m*k相关的等价值，并且处理返回到步骤S3-1以重复下面的处理。另一方面，当判定溢出的值为“0”时，判定存储在第二寄存器13b中的值是与除数n和2^m*k+1相关的等价值，并且步骤S3的处理结束。

应当注意，步骤A中的步骤S3的步骤S3-1的处理可以由以下处理代替：将存储在第二寄存器13b中的值加到存储在第二寄存器13b中的值，即，进行运算处理(REG2：＝REG2+REG2)的处理。此外，步骤S3-2的处理可以由以下处理代替：判断是否存在由于步骤S3-1的处理而产生的进位值。在此情况下，当判定已产生进位值时处理返回到步骤S3-1，而当判定未产生进位值时步骤S3的处理结束。

图17A到17D是示意性地示出要存储于包括在本发明的计算设备1中的第二寄存器13b中的值的说明图。应当注意，图17B到17D中的虚线所示的四边形中示出的数值表示由于左移一位运算而溢出的值。图17A示出了在执行步骤A中的步骤S3的处理之前的状态，并且REG2≡2^m*k(mod n)。图17B示出了在图17A的状态之后在步骤S3-1中执行了一次左移一位运算处理的状态，并且REG2≡2^m*k(mod n)。如图17B所示，溢出的值为“1”，处理返回到步骤S3-1并再次执行左移一位运算。图17C示出了执行了第二次左移一位运算的状态，并且REG2≡2^m*k(mod n)。如图17C所示，由于溢出的值为“1”，所以处理返回到步骤S3-1并再次执行左移一位运算。图17D示出了执行了第三次左移一位运算的状态。如图17D所示，由于溢出的值为“0”，所以判定REG2≡2^m*k+1(mod n)并且步骤S3的处理结束。如上所述，在步骤A的步骤S3中，通过重复左移一位运算同时舍去溢出的位值，可以在步骤S3结束时计算出2^m*k+1的等价值同时将结果保持在m个字的范围内。

以下说明将对通过步骤A中的步骤S3的处理可以计算出2^m*k+1的等价值的原因进行阐述。图18A、18B、19A以及19B是示意性地示出要存储于包括在本发明的计算设备1中的第二寄存器13b中的值的说明图。图18A和18B示出了由于执行步骤A的步骤S3的处理而溢出的值为“0”的情况，图18A示出了在执行左移一位运算处理之前的状态，而图18B示出了在执行左移一位运算处理之后的状态。图19A和19B示出了由于执行步骤A中的步骤S3的处理而溢出的值为“1”的情况，图19A示出了在执行左移一位运算处理之前的状态，而图19B示出了在执行左移一位运算处理之后的状态。

如图18B和19B所示，包括执行左移一位运算处理之后即溢出的那1位的m×k+1位的值(其为通过对图18A和19A所示的、为2^m*k(mod n)的等价值的值取2倍而获得的值)是2^m*k+1(mod n)的等价值。当如图18B所示，溢出的最高有效位的值为“0”时，由于没有因舍去溢出的最高有效位而改变实际数，所以存储在第二寄存器13b中的值是通过对2^m*k(mod n)取2倍而获得的2^m*k+1(mod n)的等价值。当如图19B所示，溢出的最高有效位的值为“1”时，舍去最高有效位就是从通过对2^m*k(mod n)取2倍而获得的2^m*k+1(mod n)中减去2^m*k，并且其结果是2^m*k(mod n)的等价值。即，REG2≡2×2^m*k(mod n)-2^m*k(mod n)≡2^m*k(mod n)。

如上所述，在本发明的计算设备1的步骤A中，可以在步骤S3中通过重复左移一位运算处理和对溢出的位值进行判断的处理，计算出H₀≡2^m*k+1(mod n)的值，其为与除数n和2^m*k+1相关的等价值。

回到图14所示的流程图，作为步骤B中的步骤S4的处理，本发明的计算设备1对于i＝1，2，...，p重复p次如下处理：由运算装置14执行REDC运算(由REDC(REG2，REG2)_n表示)并将其结果存储在第二寄存器13b中，以计算REG2＝2^E(p，m，k)(mod n)。其中，p是满足2^p-1＜m×k≤2^p的整数，E(p，m，k)＝m×k+2^p，并且REDC(A，B)_n表示蒙哥马利乘法求余运算REDC(A，B)_n＝2^-m*k×A×B(mod n)。

作为步骤C中的步骤S5的处理，本发明的计算设备1判断2^p＞m×k的真/假；进行校正运算，即由运算装置14执行被表示成REDC(REG2，g)_n的REDC运算；并且在判定2^p＞m×k为真时将其结果存储在第二寄存器13b中。应当注意，当判定2^p＞m×k为假时不执行由运算装置14执行REDC运算的校正运算。其中，g＝2^{k*G(p，m，k)}并且G(p，m，k)＝2×m-2^p/k。

作为步骤S6的处理，本发明的计算设备1输出存储在第二寄存器13b中的计算结果，即，REG2＝R²(mod n)，并结束处理。随后，本发明的计算设备1使用作为输出结果的R²(mod n)执行取幂求余运算，进而进行加密和/或解密。

图20是示出本发明的蒙哥马利变换参数的计算方法所需的运算次数的图表。图20按运算的类型和步骤示出了利用图14而示出的本发明的蒙哥马利变换参数的计算方法所需的运算次数。应当注意，图20中，SFT表示进行一位移位的移位运算，SUB表示减法，CPL表示2的补数计算，BITCHK表示对一个位值的计算的检测，REDC表示蒙哥马利乘法求余运算。此外，图20中，q表示从n的最高有效数字起连续的“0”的个数。

以下说明将参照图20所示的图表对本发明的计算方法的运算次数示例进行阐述。

[示例1]

应用于1024位的RSA密码技术(1个字是32位：k＝32)的计算

以下说明将阐述将n＝2¹⁰²³+1作为1024位的除数n的情况的示例。用于RSA密码技术的值受到n必须是两个质数p与q的积的条件的限制，而示例1中的n不满足该条件。然而，在本发明的计算方法(其为当除数n是任意奇数值时计算2^2*m*k关于除数n的等价值H≡2^2*m*k(mod n)的方法)中，n不限于质数的积。因此，即使该示例中的n不满足RSA密码技术的条件，也认为容易理解本发明的示例1，因为n的值满足根据本发明的计算方法的条件、并可由极简单的形式表示。根据以上说明，以下说明将阐述将n＝2¹⁰²³+1作为1024位的n的情况的示例。

由于如标题中的条件所述，1个字是32位，所以由32个字表示1024位，因此m＝32。从图20可见，计算H₀≡2^2*m*k(mod n)≡2²⁰⁴⁸(mod n)所需的计算量是：1次SFT、1次SUB(CPL)、1次BITCHK以及10次REDC。以下将描述该具体计算。

步骤A中的步骤S1

REG1：＝n＝(100...01)_2，1024

REG2：＝0

对第一寄存器13a和第二寄存器13b进行初始化。其中，a＝(b)_2，c表示按c位二进制数表示值a的结果是b。

步骤A中的步骤S2

REG2：＝0-n＝(0111...11)_2，1024

应当注意，对于REG2：＝(REG1的2的补数)也可以获得相同的结果。此外，可以对REG1的所有位取反，进而可以将1设置在其最低有效位中。

步骤A中的步骤S3

对于REG2＝(0111...11)_2，1024进行左移一位运算处理以使得REG2＝(111...110)_2，1024。然后，判定溢出的值是“0”，处理进行到步骤S4。应当注意，此处通过REG2(mod n)＝(111...110)_2，1024(mod n)＝(011...1100)_{2， 1024}和2¹⁰²⁵(mod n)＝(011...1100)_2，1024证实运算结果的正确性。

步骤B中的步骤S4

REG2：＝REDC(REG2，REG2)

重复p＝10次以上处理，该次数是根据2⁹＜m×k＝1024≤2¹⁰确定的。

第一次REG2：＝REDC(REG2，REG2)

≡2¹⁰²⁴⁺¹×2¹⁰²⁴⁺¹×2^-1024≡2¹⁰²⁴⁺²(mod n)

第二次REG2：＝REDC(REG2，REG2)

≡2¹⁰²⁴⁺²×2¹⁰²⁴⁺²×2^-1024≡2¹⁰²⁴⁺⁴(mod n)

第三次REG2：＝REDC(REG2，REG2)

≡2¹⁰²⁴⁺⁴×2¹⁰²⁴⁺⁴×2^-1024≡2¹⁰²⁴⁺⁸(mod n)

：

第九次REG2：＝REDC(REG2，REG2)

≡2^1024+256×2^1024+256×2^-1024≡2^1024+512(mod n)

第十次REG2：＝REDC(REG2，REG2)

≡2^1024+512×2^1024+512×2^-1024≡2^1024+1024(mod n)

根据以上计算得到REG2≡2²⁰⁴⁸(mod n)。

步骤C中的步骤S5

由于2^p(＝2¹⁰)＞m×k(＝1024)为假，所以不执行校正运算。

步骤S6

输出REG2≡H₀≡2²⁰⁴⁸(mod n)并且处理结束。

[示例2]

应用于163位的椭圆曲线密码技术(1个字是8位：k＝8)的计算

以下说明将阐述将n＝0x7、0263d95a、880adfbc、e3c1648d、44ce22fa、813980fb作为163位的除数n的情况的示例。其中，以上0x...表示由16进制数表示的数值。由于1个字是8位，由21个字表示163位，因此m＝21。从图20可见，计算H₀≡2^2*m*k(mod n)≡2³²⁶(mod n)所需的计算量是：6次SFT、1次SUB(CPL)、6次BITCHK以及8次REDC。下面将描述该具体计算。

步骤A中的步骤S1

REG1：＝n＝0x7、0263d95a、880adfbc、e3c1648d、44ce22fa、813980fb

REG2：＝0

步骤A中的步骤S2

REG2：＝0-n＝0xf8、fd9c26a5、77f52043、1c3e9b72、bb31dd05、7ec67f05

应当注意，对于REG2：＝(REG1的2的补数)也可以获得相同的结果。

步骤A中的步骤S3

对于REG2＝0xf8、fd9c26a5、77f52043、1c3e9b72、bb31dd05、7ec67f05进行左移一位运算，使得REG2＝0xf1、fb384d4a、efea4086、387d36e5、7663ba0a、fd8cfe0a。此处，应当注意，判定溢出的值是“1”并重复相同的处理。即，对于第二个处理：

对于REG2＝0xf1、fb384d4a、efea4086、387d36e5、7663ba0a、fd8cfe0a进行左移一位运算，以使得REG2＝0xe3、f6709a95、dfd4810c、70fa6dca、ecc77415、fb19fc14。此处，判定溢出的值是“1”并重复相同的处理。即，对于第三个处理：

对于REG2＝0xe3、f6709a95、dfd4810c、70fa6dca、ecc77415、fb19fc14进行左移一位运算，以使得REG2＝0xc7、ece1352b、bfa90218、e1f4db95、d98ee82b、f633f828。此处，判定溢出的值是“1”并重复相同的处理。即，对于第四个处理：

对于REG2＝0xc7、ece1352b、bfa90218、e1f4db95、d98ee82b、f633f828进行左移一位运算，以使得REG2＝0x8f、d9c26a57、7f520431、c3e9b72b、b31dd057、ec67f050。此处，判定溢出的值是“1”并重复相同的处理。即，对于第五个处理：

对于REG2＝0x8f、d9c26a57、7f520431、c3e9b72b、b31dd057、ec67f050进行左移一位运算，以使得REG2＝0x1f、b384d4ae、fea40863、87d36e57、663ba0af、d8cfe0a0。此处，判定溢出的值是“1”并重复相同的处理。即，对于第六个处理：

对于REG2＝0x1f、b384d4ae、fea40863、87d36e57、663ba0af、d8cfe0a0进行左移一位运算，以使得REG2＝0x3f、6709a95d、fd4810c7、0fa6dcae、cc77415f、b19fc140。此处，判定溢出的值是“0”并且处理进行到S4。应当注意，此处通过REG2(mod n)＝2¹⁶⁹(mod n)＝0x5187052f、34e63323、0dda53b7、61380691、269a386d证实该运算结果的正确性。

步骤B中的步骤S4

REG2：＝REDC(REG2，REG2)

重复p＝8次以上处理，该次数是由2⁷＜m×k＝1024≤2⁸确定的。

第一次REG2：＝REDC(REG2，REG2)

≡2¹⁶⁸⁺¹×2¹⁶⁸⁺¹×2^-168≡2¹⁶⁸⁺²(mod n)

第二次REG2：＝REDC(REG2，REG2)

≡2¹⁶⁸⁺²×2¹⁶⁸⁺²×2^-168≡2¹⁶⁸⁺⁴(mod n)

第三次REG2：＝REDC(REG2，REG2)

≡2¹⁶⁸⁺⁴×2¹⁶⁸⁺⁴×2^-168≡2¹⁶⁸⁺⁸(mod n)

：

第七次REG2：＝REDC(REG2，REG2)

≡2¹⁶⁸⁺⁶⁴×2¹⁶⁸⁺⁶⁴×2^-168≡2^168+128(mod n)

第八次REG2：＝REDC(REG2，REG2)

≡2^168+128×2^168+128×2^-168≡2^168+256(mod n)

根据以上计算得到REG2≡2⁴²⁴(mod n)。

步骤C中的步骤S5

由于2^p(＝2⁸)＞m×k(＝168)为真，所以执行校正运算。

校正运算

REG2：＝REDC(REG2，g)≡2⁴²⁴×2⁸⁰×2^-168≡2³³⁶

应当注意，在以上计算中：

G(p，m，k)＝2×m-(2^p/k)

G(8，21，8)＝2×21-(2⁸/8)＝10

此外，

g＝2^{k*G(p，m，k)}＝2^8*10＝2⁸⁰

利用如上所述而确定的g＝2⁸⁰进行校正运算。

步骤S6

输出REG2≡H≡2³³⁶(mod n)并且处理结束。

[示例3]

应用于160位的椭圆曲线密码技术(1个字是32位：k＝32)的计算

以下说明将阐述将n＝0x89381a5a、0ff02e5e、42d13b94、b6e022e6、96f53721作为160位的除数n的情况的示例。此处，以上0x...表示由16进制数表示的数值。由于1个字是32位，由5个字表示160位，因此m＝5。如从图20看到的，计算H≡2^2*m*k(mod n)≡2³²⁰(mod n)所需的计算量是：1次SFT、1次SUB(CPL)以及8次REDC。以下将描述具体计算。

步骤A中的步骤S1

REG1：＝n＝0x89381a5a、0ff02e5e、42d13b94、b6e022e6、96f53721

REG2：＝0

步骤A中的步骤S2

REG2：＝0-n＝0x76c7e5a5、f00fd1a1、bd2ec46b、491fdd19、690ac8df

步骤A中的步骤S3

对于REG2＝0x76c7e5a5、f00fd1a1、bd2ec46b、491fdd19、690ac8df进行左移一位运算，以使得REG2＝0xed8fcb4b、e01fa343、7a5d88d6、923fba32、d21591be。此处，判定溢出的值是“0”并且处理进行到步骤S4。应当注意，此处通过REG2(mod n)＝2¹⁶¹(mod n)＝0x6457b0f1、d02f74e5、378c4d41、db5f974c、3b205a9d证实运算结果的正确性。

步骤B中的步骤S4

REG2：＝REDC(REG2，REG2)

第一次REG2：＝REDC(REG2，REG2)

≡2¹⁶⁰⁺¹×2¹⁶⁰⁺¹×2^-160≡2¹⁶⁰⁺²(mod n)

第二次REG2：＝REDC(REG2，REG2)

≡2¹⁶⁰⁺²×2¹⁶⁰⁺²×2^-160≡2¹⁶⁰⁺⁴(mod n)

第三次REG2：＝REDC(REG2，REG2)

≡2¹⁶⁰⁺⁴×2¹⁶⁰⁺⁴×2^-160≡2¹⁶⁰⁺⁸(mod n)

：

第七次REG2：＝REDC(REG2，REG2)

≡2¹⁶⁰⁺⁶⁴×2¹⁶⁰⁺⁶⁴×2^-160≡2^160+128(mod n)

第八次REG2：＝REDC(REG2，REG2)

≡2^160+128×2^160+128×2^-160≡2^160+256(mod n)

根据以上计算得到REG2≡2⁴¹⁶(mod n)。

步骤C中的步骤S5

由于2^p(＝2⁸)＞m×k(＝160)为真，所以执行校正运算。

校正运算

REG2：＝REDC(REG2，g)≡2⁴¹⁶×2⁶⁴×2^-160≡2³²⁰

应当注意，在以上计算中：

G(p，m，k)＝2×m-(2^p/k)

G(8，5，32)＝2×5-(2⁸/32)＝2

此外，

g＝2^{k*G(p，m，k)}＝2^32*2＝2⁶⁴

使用如上所述确定的g＝2⁶⁴执行校正运算。

步骤S6

输出REG2≡H≡2³²⁰(mod n)并且处理结束。

接下来，对本发明的计算方法与上述常规方法1到常规方法3的运算次数进行比较。图21是示出本发明的计算方法以及常规方法中的蒙哥马利变换参数的计算方法所需的运算次数的图表。图21示出了图20所示的本发明的计算方法的步骤A、步骤B和步骤C的计算量、图5所示的常规方法1的步骤A1和步骤B1的计算量、图7所示的常规方法2的步骤A2和步骤B2的计算量，以及图9所示的常规方法3的步骤A3、步骤B3和步骤C3的计算量。应当注意，认为移位运算SFT、减法SUB、2的补数计算CPL以及比较运算CMP的运算(它们是多位运算)所需的处理负荷是相同的，以便于对各计算方法中的处理负荷进行比较，以常数LC代替来表示这些运算所需的处理负荷。此外，将一位值的检测计算BITCHK的计算量表示成常数SC，将蒙哥马利乘法求余运算REDC的计算量表示成常数REDC。应当注意，由于一位运算BITCHK比多位运算的计算量要小，所以认为满足BITCHK＜LC、REDC。图21中的LC和SC所示的列示出了常规方法1的步骤A1、常规方法2的步骤A2、常规方法3的步骤A3以及本发明的计算方法中的步骤A中所涉及的计算量。此外，REDC所示的列示出了常规方法1的步骤B1、常规方法2的步骤B2、常规方法3的步骤B3和C3以及本发明的计算方法的步骤B和步骤C中所涉及的计算量。

首先，对常规方法1的步骤A1、常规方法2的步骤A2以及常规方法3的步骤A3中所涉及的计算量与本发明的计算方法的步骤A中所涉及的计算量进行比较。下面计算常规方法1中的步骤A1或常规方法2中的步骤A2的计算量与本发明的计算方法中的步骤A的计算量之差。

(常规方法1或常规方法2的计算量)-(本发明的计算方法中的计算量)＝(5.5q+2.5v+1)×LC-((q+2)×LC+(q+1)×SC)＝(4.5q+2.5v-1)×LC-(q+1)×SC＝(3.5q+2.5v-2)×LC+(q+1)×(LC-SC)

在以上计算中，由于q≥0、v≥1并且LC＞SC，所以计算结果是正值。因此，这证明本发明的计算方法中的计算量比常规方法1或常规方法2的计算量要小。

下面计算常规方法3的步骤A3的计算量与本发明的计算方法中的步骤A的计算量之差。

(常规方法3的计算量)-(本发明的计算方法中的计算量)＝(2.5k+2.5v)×LC-((q+2)×LC+(q+1)×SC)＝(2.5k+2.5v-q-2)×LC-(q+1)×SC＝(2.5k+2.5v-2q-3)×LC+(q+1)×(LC-SC)

在以上计算结果中，由于q≥0并且LC＞SC，所以第二项取正值。此外，由于v≥1，所以可以如下来表示以上计算结果中的第一项的LC的系数：

2.5k+2.5v-2q-3≥2.5×(k-q)+0.5q-0.5

在以上不等式中，显然从最高有效数字起连续“0”的个数比每1个字的位长要小，所以满足q≥0和q＜k。因此，可以如下表示以上不等式并且该第一项取正值：

2.5k+2.5v-2q-3≥2.5×(k-q)+0.5q-0.5＞0

根据以上计算结果证明了本发明的计算方法中的计算量小于常规方法3的计算量。因此，当对常规方法1的步骤A1、常规方法2的步骤A2以及常规方法3的步骤A3与本发明的计算方法中的步骤A中所涉及的计算量进行比较时，证明出本发明的计算方法中的步骤A所涉及的计算量具有最小值，并且本发明的计算方法更具优势。

接下来，考虑常规方法1的步骤B1、常规方法2的步骤B2以及常规方法3的步骤B3和C3与本发明的计算方法中的步骤B和步骤C所涉及的计算量，利用示例对总计算量进行比较。REDC的计算量根据情况而以各种方式变化。如上所述，本发明的计算设备1通过由协处理器构成的运算装置14进行REDC运算，其实现了快速计算。因此，此处基于REDC的计算量等于LC的计算量的假设对计算量进行比较。此外，假设在各示例和计算方法中选择尽可能小的值作为v的值。对于v选择最小值的原因是LC的次数和SC的次数与v成比例地增加，而REDC的次数与log₂(1/v)成比例地降低。例如，当v的值加倍时，LC的次数和SC的次数也加倍，而REDC只减少一次。此外，在LC＝REDC的情况下，还考虑到LC次数、SC次数以及REDC次数的总和直接给出了总计算量，所以认为当选择v的最小值时总计算量具有最小值。应当注意，对于下述示例，示例4对应于以上示例1，示例5对应于以上示例2，示例6对应于以上示例3。

[示例4]

应用于1024位的RSA密码技术(1个字是32位：k＝32)的计算

当1个字是32位时，由32个字表示1024位。因此，k＝32并且m＝32。此外，从最高有效数字起连续“0”的个数q＝0。

常规方法1

由于m×k＝1024，并且使(m×k)/v具有2的幂值的v的最小值是1，所以选择v＝1。

步骤A1

(5.5q+2.5v+1)×LC＝3.5×LC

步骤B1

p×REDC＝log₂((m×k)/v)×REDC＝10×REDC

总和

3.5×LC+10×REDC＝13.5×LC

常规方法2

由于(m×k)/v不必是2的幂值，所以选择v＝1。

步骤A2

(5.5q+2.5v+1)×LC＝3.5×LC

步骤B2

p’-1+W((m×k)/v)×REDC＝(11-1+W((10000000000)_2，11))×REDC＝10×REDC

总和

3.5×LC+10×REDC＝13.5×LC

常规方法3

由于(m×k)/v不必是2的幂值，所以选择v＝1。

步骤A3

(2.5k+2.5v)×LC＝82.5×LC

步骤B3和步骤C3

p”×REDC＝log₂((m×k)/v)×REDC＝10×REDC

应当注意，由于(m×k)/v取2的幂值，所以不进行校正运算。

总和

82.5×LC+10×REDC＝92.5×LC

本发明的计算方法

步骤A

(q+1)×LC+(q+1)×SC＝LC+SC

步骤B和步骤C

p×REDC＝log₂(m×k)×REDC＝10×REDC

应当注意，由于(m×k)/v取2的幂值，所以不进行校正运算。

总和

LC+SC+10×REDC＝11×LC+SC

[示例5]

应用于163位的椭圆曲线密码技术(1个字是8位：k＝8)的计算

当1个字是8位时，由21个字表示163位。因此，k＝8并且m＝21。此外，从最高有效数字起连续的“0”的个数q＝5。

常规方法1

由于m×k＝168，并且使(m×k)/v具有2的幂值的v的最小值是21，所以选择v＝21。

步骤A1

(5.5q+2.5v+1)×LC＝(27.5+52.5+1)×LC＝81×LC

步骤B1

p×REDC＝log₂((m×k)/v)×REDC＝3×REDC

总和

81×LC+3×REDC＝84×LC

常规方法2

由于(m×k)/v不必是2的幂值，所以选择v＝1。

步骤A2

(5.5q+2.5v+1)×LC＝(27.5+2.5+1)×LC＝31×LC

步骤B2

p’-1+W((m×k)/v)×REDC＝(8-1+W((10101000)_2，8))×REDC＝9×REDC

总和

31×LC+9×REDC＝40×LC

常规方法3

由于(m×k)/v不必是2的幂值，所以选择v＝1。

步骤A3

(2.5k+2.5v)×LC＝22.5×LC

步骤B3和步骤C3

(p”+1)×REDC＝(log₂((m×k)/v)+1)×REDC＝(8+1)×REDC＝9×REDC

应当注意，由于(m×k)/v不是2的幂值，所以进行校正运算。

总和

23.5×LC+9×REDC＝32.5×LC

本发明的计算方法

步骤A

(q+1)×LC+(q+1)×SC＝6×LC+6×SC

步骤B和步骤C

(p+1)×REDC＝(log₂(m×k)+1)×REDC＝(8+1)×REDC＝9×REDC

应当注意，由于(m×k)/v不是2的幂值，所以进行校正运算。

总和

6×LC+6×SC+9×REDC＝15×LC+6×SC

[示例6]

应用于160位的椭圆曲线密码技术(1个字是32位：k＝32)的计算

当1个字是32位时，由5个字表示160位。因此，k＝32并且m＝5。此外，从最高有效数字起连续“0”的个数q＝0。

常规方法1

由于m×k＝160，并且使(m×k)/v具有2的幂值的v的最小值是5，所以选择v＝5。

步骤A1

(5.5q+2.5v+1)×LC＝(12.5+1)×LC＝13.5×LC

步骤B1

p×REDC＝log₂((m×k)/v)×REDC＝5×REDC

总和

13.5×LC+5×REDC＝18.5×LC

常规方法2

由于(m×k)/v不必是2的幂值，所以选择v＝1。

步骤A2

(5.5q+2.5v+1)×LC＝(2.5+1)×LC＝3.5×LC

步骤B2

p’-1+W((m×k)/v)×REDC＝(8-1+W((10100000)_2，8))×REDC＝8×REDC

总和

3.5×LC+8×REDC＝11.5×LC

常规方法3

由于(m×k)/v不必是2的幂值，所以选择v＝1。

步骤A3

(2.5k+2.5v)×LC＝82.5×LC

步骤B3和步骤C3

(p”+1)×REDC＝(log₂((m×k)/v)+1)×REDC＝(8+1)×REDC＝9×REDC

应当注意，由于(m×k)/v不是2的幂值，所以进行校正运算。

总和

82.5×LC+9×REDC＝91.5×LC

本发明的计算方法

步骤A

(q+1)×LC+(q+1)×SC＝LC+SC

步骤B和步骤C

(p+1)×REDC＝(log₂(m×k)+1)×REDC＝(8+1)×REDC＝9×REDC

应当注意，由于(m×k)/v不是2的幂值，所以进行校正运算。

总和

LC+SC+9×REDC＝10×LC+SC

图22是示出本发明的计算方法以及常规方法中的蒙哥马利变换参数的计算方法所需的运算次数的图表。图22是一起示出了示例4到示例6所示的结果的图表。从图22显见，在示例4到示例6所示的任何条件下，本发明的计算方法都比常规方法1到常规方法3更具优势。

尽管在以上实施例中阐述了将计算设备应用于运算卡的形式，但是本发明并不限于此，而是可以应用于各种形式，如将计算设备应用于诸如个人计算机或服务器计算机的计算本体的形式。

此外，尽管在以上实施例中对实现用于执行REDC运算的协处理器的形式进行了描述，但是本发明并限于此，而是可以应用于各种形式，如通过软件处理执行REDC运算。

Claims

1、一种用于使用寄存器计算与蒙哥马利变换参数相关的值的计算方法，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该寄存器具有至少m个字，每1个字的位长是k，该计算方法包括以下步骤：

获得n的负数作为2^m*k关于除数n的等价值，并将该负数存储在该寄存器中；

重复对存储在该寄存器中的值在进位方向上进行一位移位、并舍去溢出该寄存器的最高有效位的处理，直到要舍去的最高有效位变成0，以获得2^m*k+1关于除数n的等价值并将该等价值存储在该寄存器中；以及

根据存储在该寄存器中的值，通过蒙哥马利乘法求余运算计算出使得关于除数n的余数值与蒙哥马利变换参数关于除数n的余数值相同的等价值。

2、根据权利要求1所述的计算方法，其中使用所计算出的等价值执行取幂求余运算。

3、一种用于使用寄存器和运算单元计算与蒙哥马利变换参数相关的值的计算方法，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该寄存器具有至少m个字，每1个字的位长是k，该运算单元用于对于值A和B以及有效字长为m的求余的除数n执行定义为2^-m*k×A×B(mod n)的蒙哥马利乘法求余运算REDC(A，B)_n，该计算方法包括以下步骤：

将求余的除数n的负数存储在寄存器中；

重复对存储在该寄存器中的值在进位方向上进行一位移位的移位处理，直到溢出该寄存器的最高有效位变成0；

重复p次以下处理：通过运算单元对存储在该寄存器中的值REG执行蒙哥马利乘法求余运算REDC(REG，REG)_n并将其结果存储在该寄存器中，其中p是满足2^p-1＜m×k≤2^p的整数；

当2^p＞m×k时，通过运算单元对存储在该寄存器中的值REG执行蒙哥马利乘法求余运算REDC(REG，g)_n并将其结果存储在该寄存器中，其中，g＝2^{k*G(p，m，k)}并且G(p，m，k)＝2×m-2^p/k；以及

输出存储在该寄存器中的值，作为使得关于除数n的余数值与蒙哥马利变换参数关于除数n的余数值相同的等价值。

4、一种用于计算与蒙哥马利变换参数相关的值的计算设备，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该计算设备包括：

寄存器；以及

控制器，其能够进行以下操作：

将求余的除数n的负数存储在该寄存器中；

重复对存储在该寄存器中的值在进位方向上进行一位移位的处理，直到溢出该寄存器的最高有效位变成0；以及

5、一种用于计算与蒙哥马利变换参数相关的值的计算设备，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该计算设备包括：

寄存器，具有至少m个字，每个字的位长是k；

运算单元，用于对值A和B以及有效字长为m的求余的除数n执行定义为2^-m*k×A×B(mod n)的蒙哥马利乘法求余运算REDC(A，B)_n；以及

控制器，其能够进行以下操作：

将求余的除数n的负数存储在该寄存器中；

重复对存储在该寄存器中存储的值在进位方向上进行一位移位的移位处理，直到溢出该寄存器的最高有效位变成0；

重复p次以下处理：通过运算单元对存储在寄存器中的值REG执行蒙哥马利乘法求余运算REDC(REG，REG)_n并将其结果存储在该寄存器中，其中p是满足2^p-1＜m×k≤2^p的整数；

当2^p＞m×k时，通过运算单元对存储在寄存器中的值REG执行蒙哥马利乘法求余运算REDC(REG，g)_n并将其结果存储在该寄存器中，其中，g＝2^{k*G(p，m，k)}并且G(p，m，k)＝2×m-2^p/k；以及

6、根据权利要求5所述的计算设备，其中

设有另一寄存器，并且

控制器还能够进行以下操作：

在具有m个字的第一寄存器中存储n并在具有m个或更多个字的第二寄存器中存储0；以及

从存储在第二寄存器中的值中减去存储在第一寄存器中的值以计算求余的除数n的负数。

7、根据权利要求5所述的计算设备，其中控制器还能够进行以下操作：

将求余的除数n存储在寄存器中；以及

计算出存储在寄存器中的值的补数作为求余的除数n的负数。

8、根据权利要求5所述的计算设备，其中所述控制器还能够进行以下操作：

将求余的除数n存储在寄存器中；

对存储在寄存器中的值取反；以及

在存储在寄存器中的值的最低有效位是1的情况下计算求余的除数n的负数。

9、根据权利要求5到8中的任何一项所述的计算设备，其中所述移位处理是将存储在寄存器中的值加到所述值中的加法处理，并且

检测出在该移位处理中溢出寄存器的最高有效位，作为由该加法处理产生的进位值。

10、一种用于使计算机计算与蒙哥马利变换参数相关的值的计算机程序，该计算机包括寄存器，该寄存器具有至少m个字，每1个字的位长是k，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该计算机程序包括以下步骤：

使该计算机获得n的负数作为2^m*k关于除数n的等价值并将该负数存储在寄存器中；

使该计算机重复对存储在该寄存器中的值在进位方向上进行一位移位并舍去溢出该寄存器的最高有效位的处理，直到要舍去的最高有效位变成0，以获得2^m*k+1关于除数n的等价值并在寄存器中存储该等价值；以及

使该计算机根据存储在该寄存器中的值，通过蒙哥马利乘法求余运算计算出使得关于除数n的余数值与蒙哥马利变换参数关于除数n的余数值相同的等价值。

11、一种用于使计算机计算与蒙哥马利变换参数相关的值的计算机程序，该蒙哥马利变换参数用于蒙哥马利乘法求余运算并且是与求余的除数n相关的余数值，该计算机包括寄存器和运算单元，该寄存器具有至少m个字，每1个字的位长是k，该运算单元用于对于值A和B以及有效字长为m的求余的除数n执行定义为2^-m*k×A×B(mod n)的蒙哥马利乘法求余运算REDC(A，B)_n，所述计算机程序包括以下步骤：

使该计算机将求余的除数n的负数存储在该寄存器中；

使该计算机重复对存储在该寄存器中的值在进位方向上执行一位移位的移位处理，直到溢出该寄存器的最高有效位变成0；

使该计算机重复p次以下处理：通过所述运算单元对存储在该寄存器中的值REG执行蒙哥马利乘法求余运算REDC(REG，REG)_n并将其结果存储在该寄存器中，其中p是满足2^p-1＜m×k≤2^p的整数；

当2^p＞m×k时，使该计算机通过运算单元对存储在寄存器中的值REG执行蒙哥马利乘法求余运算REDC(REG，g)_n并将其结果存储在该寄存器中，其中，g＝2^k*G(p，m，k)并且G(p，m，k)＝2×m-2^p/k；以及使该计算机输出存储在该寄存器中的值，作为使得关于除数n的余数值与蒙哥马利变换参数关于除数n的余数值相同的等价值。