标量乘法的运算方法、幂运算的运算方法、记录有标量乘法的运算程序的记录介质及记录...的制作方法
专利名称：标量乘法的运算方法、幂运算的运算方法、记录有标量乘法的运算程序的记录介质及记录 ...的制作方法
技术领域：
本发明涉及一种标量乘法的运算方法和记录有其运算程序的记录介质，通过将有 理点Q的标量η乘法的η基于t-Ι进制展开来提高标量乘法的运算速度，并涉及一种幂运 算的运算方法和记录有其运算程序的记录介质，通过对A的η次幂的η基于q-r进制展开 来提高幂运算的运算速度。
背景技术：
目前，利用因特网等电气通信线路的信息网络技术高度发展，不仅能利用网络取 得各种各样的信息，而且还能够提供如网络银行或向行政机关提交电子申请等各种服务。在使用上述服务时，需要进行认证处理，以确认服务的用户并不是冒充或虚构的， 而是恰当的用户，作为高可靠性的认证方法，多采用如下电子认证技术，即基于使用公钥和 私钥的公钥加密的电子认证技术。然而，在公钥加密方式的电子认证中，当公钥或私钥泄露时，需要立即变更公钥和 私钥，必须谨慎保管公钥和私钥，并且根据需要还需进行新公钥和私钥设定登记操作，使用 复杂，因此，如用户的名字或邮件地址那样，最近多使用以用户特有ID进行电子认证的基 于ID加密。另外，利用进行电子认证的认证装置对用户进行个人认证时，在认证装置中保存 了每个用户的简历，该简历信息本身为用户的个人信息，最近被指出存在会因该简历信息 泄露导致个人信息泄露的问题。因而，提出如下所述的群签名技术，S卩，在认证装置中，不是使用用户的个人信息 来进行认证，而是以多个用户为整体的群，通过使用表示属于该群的信息的群签名，不特别 指定用户而进行认证，由此，在认证装置中不保存个人信息并能够进行认证。在上述基于ID加密和群签名中所使用的运算，采用被称为配对的方法，其利用椭 圆曲线上的有理点的双线性对映射。所谓配对，其运算为，例如以P为素域Fq上的有理点， WQSk扩域F^k上的有理点输入P和Q，输出扩域F+qk的元素z，此时，若输入a倍的P和
b倍的Q，则输出ζ的ab次幂。而且，在此“k”称为嵌入次数，对于"F*qk，’，其正确的表示方
式如下式，但因文本限制在行文中记为"FVc ’’。[式1]
ΦP k
Vl在基于ID加密时的加密或解码处理，或群签名时的认证处理中，需要在尽可能短 的时间执行。尤其是在基于配对的加密方式等中，执行很多标量乘法和幂运算，因而期望能 够高速执行上述运算。
为此，以往使用二进制法或窗口法提高标量乘法和幂运算的速度。另外，在运算扩域的元素AeFqk的幂An时，通过使用弗罗贝尼乌斯映射φ : A-Atl消减运算次数提高运算速度。另外，提出了在标量乘法中也利用映射消减运算次数提高运算速度的方案(例如 参照专利文献1、专利文献2)。专利文献1 日本专利公开2004-271792号公报专利文献2 日本专利公开2007-41461号公报
发明内容
但是，公知的通过映射提高运算速度的方法，在当标量乘法中的标量η或幂运算 中的指数η远大于阶数q的情况下(n>>q)非常有效，然而，当标量η和指数η不是远大 于有限域Fq的阶数q时，与不使用提高运算速度的方法而直接执行标量乘法和幂运算的情 况相比，并没有显著的效果。尤其是在基于ID的加密中的加密或解码处理，及群签名中的认证处理中，当必须 使用带有标量η的标量乘法或带有指数η幂运算时，多数情况下标量η或指数η不是远大 于有限域Fq的阶数q，即使使用公知的提高运算速度的方法也不能得到很好的效果。本发明人有鉴于上述现状，对即使当标量η或指数η不是远大于有限域Fq阶数q 时，也能够高速地执行标量乘法或幂运算的运算方法展开研究，并得到本发明。本发明的标量乘法的运算方法中，设椭圆曲线为E/F, = x3+ax+b-y2 = 0，其中 a e Fq，b e Fq令，E(Fq)为由有限域Fq定义的椭圆曲线的有理点构成的加法群；E(F^k)为由有限域Fq的扩域F^k定义的椭圆曲线的有理点构成的加法群；为关于有限域Fq的有理点的弗罗贝尼乌斯自同态映射；t为弗罗贝尼乌斯自同态映射的迹；r为整除E (Fq)的阶数#E (Fq) = q+1-t的素数阶数；E[r]为阶数为素数r的有理点集合；[j]为j倍的有理点的映射；G为包含于满足G = E[r] Π Ker(Φq-[q])
的E (Fqk)中的有理点集合，利用具有CPU和存储模块的电子计算机来运算关于非负整数η的G的有理点Q的 标量η乘法，本发明的标量乘法的运算方法包括输入步骤，CPU输入所述非负整数η的值、所述迹t的值、和由QGGcE(Fqk)表示 的有理点Q的值，并存储在所述存储模块中；初始化步骤，CPU将存储运算结果Z的所述存储模块初始化；展开步骤，对于G的有理点Q，
Φ,(Q) = [q]Q = [t_l]Q 成立，由此 CPU设s = t-1，根据将所述η以s进制展开的下式，[式2]N = ^cMsi, 0 < c[i] < S从i = 0开始重复进行规定次数的由C[i] — s和η — (n-c[i])/s表示的代 入运算，将各系数c [i]和非负整数η的值存储在所述存储模块中；运算步骤，CPU从所述存储模块读出所述有理点Q和所述系数c [i]，从i = 0开始 重复进行规定次数的由Q[i] =c[i]Q表示的运算，将各Q[i]的值存储在所述存储模块中； 禾口合成步骤，CPU替代为t-Ι，根据由关于有理点的弗罗贝尼乌斯自同态映射表 示下式的标量乘法nQ[式3]nQ =》 ·])
i从所述存储模块读出Q[i]和运算结果Z，从i = 0开始重复规定次数的由 Ζ-Ζ+Φ； (Q[i])表示的代入运算，将标量乘法的运算结果Z存储在存储模块中。进而，在本发明的标量乘法的运算方法中，在利用整数变量X分别由q(>c)、r(>c)、t(>c)给出所述椭圆曲线的有限域Fq的 阶数q、整除#E(Fq)的素数阶数r、弗罗贝尼乌斯自同态映射的迹t时，包括辅助输入步骤，CPU输入所述q(>c)、r(>c)、t(>c)各值，存储在所述存储模块中；辅助展开步骤，CPU从所述存储模块读出Hx)和t(x)的值，令所述s(x)= t(x)_l，根据将r(x)以S(X)进制展开的下式[式4]
fdeg r(%)/degs (%)]
r(x)= Yj DiOOsOOi, 0 < degCDiCx)) < deg(s(x))
i=0从i = o 到 i<[deg r(x)/deg s(x)]重复进行由 Di(X) - r(x) %s(x)和 r(x) — (r(x)-Di(x))/s(x)表示的代入运算，将各系数Di ( χ )和r ( χ )的值记录在所 述存储模块中；辅助抽出步骤，CPU抽出所述被存储的系数03>0中，deg(Di(x))为最大的 Ddfflax(x),存储在所述存储模块中；辅助确定步骤，CPU从所述存储模块读出Ddmax ( χ )、Di ( χ )、Q的值，使用满足Φ/max ([Ddfflax ( χ )]Q) =Σ Φ ([ (χ)]0)-Φ(1<1ω3χ(
0) = ^(Φ,, x)]Q的多项式f ( Φ q，x )，根据Φ qkQ = Q，确定满足[Ddmax(X)JQ = ^(Φ,, x)=x)]Q的多项式h ( Φ ,，χ )，将所述多项式h ( Φ q，X )的值存储在所述存储模块中；和
CPU令χ = a将所述s进制展开替换为由s = Ddfflax (a)构成的Ddfflax (a)进制展开， 替换为Ddmax(a)并使用所述多项式h(c^，a)的步骤。而且，在本发明的标量乘法的运算方法中，
当所述系数Di ( χ )中存在多个为最高次数dmax的系数Di ( χ )时，所述辅助输入步骤还包括，CPU输入满足r(X) Im(X)的m(X)的值，并存储在所 述存储模块中的步骤，并具有第二辅助确定步骤，CPU令deg^J χ ))的最高次数dmax项，即，χ “的系数为 ^ ($(1)，从所述存储模块读出系数01(>0，在所述存储模块中对11((^，χ)和υ(Φ,，χ) 分配初始值“0”，从i = 0到i <「degr(>c)/degS(>c)」为止重复进行代入运算，该代入运 算中，当 deg^Jx)) = dmax 时，表示为 Τ(Φ,，χ) — Τ(Φ,，x )+Di ( χ ) Φ J，其他情况下， 表示为υ(Φ,，χ)χ HDi(X) Φ ，将Τ(Φ,，χ)和υ(Φ,，χ)的值存储在存储模 块中，确定最高次数系数Tdmax(CK)；第三辅助确定步骤，CPU从存储模块读出m(X)和R(X)的值，使用满足 H χ ) Im(X)的最小次数的多项式m(X)，进行由W(Cj5q) 一 gccKTjc^)，m(c^))和 ν(Φ,) -ΚΦ,)表示的代入运算，确定满足ν(Φ,) |πι(Φ(1),δο(1(Τ(1ω3Χ(Φ(1),ν(Φ(1)) =1的V ( Φ ，将所述V ( Φ 的值存储在存储模块中；第四辅助确定步骤，CPU从所述存储模块读出V(Cj5q)和m(c^)的值，利用扩展欧 几里得互除法确定满足δ(φ )ν(φ ) = v(mod !!!(Φ,))的整数标量ν和g( Φ)的值，将所述标量ν和g( Φ)存储在所述存储模块中；第五辅助确定步骤，替代所述辅助确定步骤，CPU从所述存储模块读出Tdmax ( Φ 、 x dmaxJi(X)、Q各值，使用满足[Tdfflax ( Φ q) XdmaxJQ=E Φ ([Ο (χ)]0)-[Τ,ω3Χ(Φ ) XdmaxJQ= [ ΧΦ,，x)]Q的多项式f (Φ q，χ )和所述g (Φ ，根据Φ qkQ = Q确定满足[VXdmaxJQ = [g(c^)f(cK，x)]Q = ^(Φ,, x)]Q的多项式h ( Φ ,，χ )，将所述多项式h ( Φ q，X )的值存储在所述存储模块中；和CPU从所述存储模块读出所述h ( Φ q，X )的值，使该h ( Φ q，X )的关于Φ q的常数项h (0，X )满足[vx^-h (0, x)]Q = [h((^，x)-h (0, x)]Q，由此令χ = a，进行由 s，= vadmax-h (0，a)和 h，( Φ = h ( Φ q，a) _h (0，a)表示的运 算，将s’和h’ (Φ,)的值存储在所述存储模块中，代替以D-Ja)进制展开，对t-1进制展开后的所述n，以VadmaM1(OA)进制展开， 并用 h ( Φ q，a) -h (0，a)代替 vadmax-h (0，a)的步骤。另外，在本发明的幂运算的运算方法中，令Fqk为阶数q的有限域Fq的k次扩域，H为F^k的素数阶数r的乘法子群，Φ q为关于有限域Fq的元素的弗罗贝尼乌斯自同态映射，
利用具有CPU和存储模块的电子计算机运算关于非负整数η的H的元素A的η次 幂的幂运算，本发明的幂运算的运算方法包括 输入步骤，CPU输入所述非负整数η的值、所述阶数q的值、所述F^k的素数阶数r 的值、由AeHcFqk表示的元素A的值，并存储在所述存储模块中；初始化步骤，CPU对存储运算结果Z的所述存储模块进行初始化；第一运算步骤，CPU从所述存储模块读出所述阶数q、所述元素A的值，令所述q与 r的差为s = q-r，从j = 0到j <「lo&s」重复由T[j] 一 A和A — A*A表示的代入运算， 将所述T[j]和所述A的值存储在所述存储模块中；展开步骤，CPU从所述存储模块读出所述η和差s的值，根据由差s展开的下式[式5]n = ^c[i]si, ο < c[i] < s
i从i = 0开始重复规定次数的由c[i] — s和η — (n-c[i])/s表示的代入运 算，将各系数c [i]和非负整数η的值存储在存储模块中；第二运算步骤，CPU从存储模块读出c[i]和所述η的值，根据A[i] = Ac[i], 初始化A[i] = 1，在c[i]&l时，从i = 0开始重复规定次数的由A[i] — A[i]*T[j]和 c[i] — c[iV2表示的代入运算，将A[i]和c[i]的值存储在存储模块中；和合成步骤，CPU从存储模块读出各A[i]，根据下式[式6]An=P] φ (A[i])从i = 0开始重复规定次数的由Ζ —Ζ* Φ ^(Ati])表示的幂运算，将计算的结果 Z存储在存储模块中。进而，本发明的幂运算的运算方法中，设Χ~{Υ}表示 χγ，在用整数变量X分别由q(X)、r(>c)、S(>c)给出所述阶数q、所述素数阶数r、所 述s时，包括辅助输入步骤，CPU输入所述q(>c)、r(>c)、S(>c)各值，存储在所述存储模块中；辅助展开步骤，CPU从所述存储模块读出r(X)和s(x)，用所述S(X)根据将 r(x)以s(x)进制展开的下式[式7]
r(x)= Yi DiOOsOrf, 0<deg(Di(x))<deg(s(x))
i=0从 i = 0 至Ij i <「degr(x)/degs(x)」重复由 Di(X) —r(x) %s(x)禾口 r(x) — (r(x)-Di(x))/s(x)表示的代入运算，将所述系数Di ( χ )和r ( χ )存储在所述存储模块中； 辅助抽出步骤，CPU抽出被存储的系数Di (X) ^,deg(Di(x))为最大的Ddfflax ( χ )， 存储在所述存储模块中；辅助确定步骤，CPU从所述存储模块读出所述Ddmax ( X )、Di ( X )、q的值，使用满足(A"{Ddfflax(x)})"{qdfflax} =Α"{ Σ ^dmax-Di(X)qiI =A"{f(q, x)}的多项式f(q，X)，根据C^k(A) =A，确定满足A" (Ddfflax (x)} =Α"{ Σ ^ ^ax-Di ( χ ) Qi-QdmaxI =A"{h(q, χ)}的多项式h(q，X)，将所述多项式h(q，x)的值存储在所述存储模块中；和CPU令χ = a将所述s进制展开的所述η替换为由s = Ddmax(a)构成的Ddmax(a) 进制展开，用所述多项式h(q，a)替换D-Ja)的步骤。而且，在本发明的幂运算的运算方法中，当所述系数Di(X)中存在多个为最高次数dmax的系数Di (X)时，所述辅助存储步骤还包括，CPU输入满足r(x) Im(X)的m(x)的值，存储在所述 存储模块中的步骤，并具有第二辅助确定步骤，CPU令deg (Di (X))的最高次数dmax的项，即x dmax的系数为 Tdfflax (q)，从所述存储模块读出系数Di (X)，在所述存储模块中对T (q，x)和U(q，x )的分 配初始值“0”，从i = 0到i <「degr(>c)/degS(>c)」重复进行代入运算，该代入运算中， 当 deg^Jx)) = dmax 时，表示为 T (q，x) — T(q，x )+Di ( x ) q、其他情况下，表示为 U (q， x) —U(q，XHDi(X)qS将T(q，x)和U(q，x)的值存储在所述存储模块中，确定最高次 数系数Tdmax (q)；第三辅助确定步骤，CPU从所述存储模块读出m(X)和R(X)的值，使用满 足r(X)lm(X)的最小次数的多项式m(X)，进行由W(q) - gcd (Tdfflax (q), m(q))和 V(q) — W(q)表示的运算，确定满足 V (q) I m (q)，gcd (Tdmax (q)，V (q)) =1的V(q)，将所述V(q)的值存储在所述存储模块中；第四辅助确定步骤，CPU从所述存储模块读出V(q)和m(q)的值，利用扩展欧几里 得互除法确定满足g(q)V(q) = ν (mod m(q))的整数标量ν和g(q)，将所述标量ν和g(q)的值存储在所述存储模块中；第五辅助确定步骤，替代所述辅助确定步骤，CPU从所述存储模块读出Tdmax(q)、 X dmax^ Di ( χ )、Q 各值，利用满足 A" ITdmax (q) χ dmaxI = Α"{ Σ Di(X) Qi-Tdmax (q) χ “)= A"{f(q, x)}的多项式f(q，x)和所述g(q)，根据(^k(A) =A，确定满足Α" {ν χ dmaxI = A"{g(q)f(q, x)} = A"{h(q, x)}的多项式h(q，X )，将所述多项式h(q，X )的值存储在所述存储模块中；和CPU从所述存储模块读出所述h(q，X)的值，使该h(q，X)的关于q的常数项h(0，x)满足A'lvx^-h (0, x)} = A"{h(q, x)_h(0，x)}，
令χ = a，进行由 s’ = vadmax-h(0, a)和 h，(q) = h(q，a)_h(0，a)表示的运算， 将S’和h’ (q)的值存储在所述存储模块中，代替以Ddmax(a)进制展开，对以s进行展开后 的所述η以vadmax_h (0，a)进制展开，并用h (q, a) _h (0，a)代替VadmaM1 (0，a)的步骤。另外，本发明的记录有标量乘法的运算程序且能够被电子计算机读取的记录介质 中，记录有如下所述标量乘法的运算程序，设椭圆曲线为E/F, = x3+ax+b-y2 = 0，其中 a G Fq，b e Fq
令，E(Fq)为由有限域Fq定义的椭圆曲线的有理点构成的加法群；E(F^k)为由有限域Fq的扩域F^k定义的椭圆曲线的有理点构成的加法群；为关于有限域Fq的有理点的弗罗贝尼乌斯自同态映射；t为弗罗贝尼乌斯自同态映射的迹；r为整除E (Fq)的阶数#E (Fq) = q+1-t的素数阶数；EM为阶数为素数r的有理点集合；[j]为j倍的有理点的映射；G为包含于满足G = E[r] Π Ker(<j5r[q])的E(F^k)中的有理点集合，利用具有CPU和存储模块的电子计算机执行关于非负整数η的G的有理点Q的标 量η乘法，该运算程序在电子计算机中执行输入步骤，输入所述非负整数η的值、所述迹t的值、和由Q EGc=E(Fqk)表示的有 理点Q的值，并存储在所述存储模块中；初始化步骤，将存储运算结果Z的所述存储模块初始化；展开步骤，令对于G的有理点Q，(^(Q) = [q]Q = [t_l]Q 成立，由此设s = t-Ι，根据将所述η以s进制展开的下式，[式8]N = ^ Cplsi, 0 < C[l] < S从i =0开始重复进行规定次数的由C[i] — 和η — (n_C[i])/s表示的代 入运算，将各系数c [i]和非负整数η的值存储在所述存储模块中；运算步骤，从所述存储模块读出所述有理点Q，非负整数η和所述系数c[i]，从i =0开始重复规定次数的由Q[i] = c[i]Q表示的运算，将各Q[i]的值存储在所述存储模 块中；和合成步骤，替代为t-Ι，根据由关于有理点的弗罗贝尼乌斯自同态映射表示下 式的标量乘法nQ[式9]
从所述存储模块读出Q[i]和运算结果Z，从i = 0开始重复规定次数的由 Ζ-Ζ+Φ； (Q[i])表示的代入运算，将标量乘法的运算结果Z存储在存储模块中。进而，在本发明的记录有标量乘法的运算程序且能够被电子计算机读取的记录介 质中，在分别由整数变量X由q(>c)、r(>c)、t(>c)给出所述椭圆曲线的有限域Fq的阶 数q、整除#E(Fq)的素数阶数r、弗罗贝尼乌斯自同态映射Φ q的迹t时，由电子计算机执行 如下步骤辅助输入步骤，输入所述9(乂)、1~(>0 3(>0各值，存储在所述存储模块中；辅助展开步骤，从所述存储模块读出r(x )和t(x)的值，令所述S(X)= t(x)_l，根据将r(x)以S(X)进制展开的下式[式10]
τω= Yj Di(X)SOOi, 0 < deg(Di(x)) < deg(s(x)) i=0从i = 0 到 i<[deg r(%)/deg重复进行由 Di(X) - r(x) % s(x)和 r(x) — (r(x)-Di(x))/s(x)表示的代入运算，将各系数Di ( χ )和r ( χ )的值记录在所 述存储模块中；辅助抽出步骤，抽出所述被存储的系数Di(X)中，degQJx))为最大的 Ddfflax(x),存储在所述存储模块中； 辅助确定步骤，从所述存储模块读出Ddfflax ( χ )、Di ( χ )、Q的值，使用满足Φ/"χ(
0) =Σ Φ ([ (χ)]0)-Φ(1<1ω3χ(
0) = ^(Φ,, x)]Q的多项式f ( Φ q，X )，根据Φ qkQ = Q，确定满足[Ddmax(X)JQ = ^(Φ,, χ)=X)]Q的多项式!!(Φ,，乂)，将所述多项式11((^，x)的值存储在所述存储模块中；和令χ = a将所述s进制展开替换为由s = Ddmax(a)构成的D-Ja)进制展开，替 换为Ddmax(a)并使用所述多项式h(c^，a)的步骤。而且，本发明的记录有标量乘法的运算程序且能够被电子计算机读取的记录介质 中，当所述系数Di (X)中存在多个为最高次数dmax的系数Di (X)时，所述辅助输入步骤还包括，输入满足r(X) Im(X)的m(X)的值，存储在所述存储 模块中的步骤，并由所述电子计算机执行如下步骤第二辅助确定步骤，令degQJx))的最高次数dmax项，即x “的系数为 ^ ($(1)，从所述存储模块读出系数01(>0，在所述存储模块中对11((^，χ)和υ(Φ,，χ) 分配初始值“0”，从i = 0到i <「degr ( χ ) /degs ( χ )」重复进行代入运算，该代入运算中，当deg^Jx)) =dmax时，表示为Τ(Φ,，χ)x )+Di ( χ ) Φ J，其他情况下，表示为
υ(Φ,，χ) — υ(Φ,，XHDi(X) Φ/，将Τ(Φ,，χ)禾口 υ(Φ,，χ)的值存储在存储模块中，确 定最高次数系数Tdmax(Cttl)；第三辅助确定步骤，从存储模块读出m(X)和R(X)的值，使用满足r(x) Im(X) 的最小次数的多项式m( χ )，进行由W(Cj5q) —gccKUc^)，m(c^))和ν(Φ,) -ΚΦ,) 表示的代入运算，确定满足ν(Φ5) |m(c^)，gCd(Tdmax((^)，V((^)) =1
的V ( Φ ，将所述V ( Φ 的值存储在存储模块中；第四辅助确定步骤，从所述存储模块读出ν(Φ,)和m(c^)的值，利用扩展欧几里 得互除法确定满足δ(φ )ν(φ ) = v(mod !!!(Φ,))的整数标量ν和g( Φ)的值，将所述标量ν和g( Φ)存储在所述存储模块中；第五辅助确定步骤，替代所述辅助确定步骤，从所述存储模块读出Tdmax(CK)、 X dmaxJi(X)、Q各值，使用满足[Tdfflax ( Φ q) XdmaxJQ=E Φ ([Ο (χ)]0)-[Τ,ω3Χ(Φ ) XdmaxJQ= [ ΧΦ,，x)]Q的多项式 ΧΦ,，x)和所述g(c^)，根据^KkQ = Q确定满足[VXdmaxQ= [δ(Φ )Γ(Φ(1, x)]Q = ^(Φ,, x)]Q的多项式!!(Φ,，乂)，将所述多项式11((^，x)的值存储在所述存储模块中；和从所述存储模块读出所述!!(Φ,，x)的值，使该!!(Φ,，x)的关于Φ,的常数项h(0，x)满足[vx^-h (0, x)]Q = ^(Φ,, x)-h (0, x)]Q，令χ = a，进行由 s，= vadmax-h(0, a)和 h，( Φ = h ( Φ q，a)-h (0, a)表示的运 算，将s’和h’ (Φ,)的值存储在所述存储模块中，代替以D-Ja)进制展开，对t-1进制展开的所述n，以VadmaM1(OA)进制展开，并 用 h ( Φ q，a) -h (0，a)代替 vadmax-h (0，a)的步骤。另外，本发明的记录有幂运算的运算程序且能够被电子计算机读取的记录介质 中，如下所述幂乘法的运算程序，令，Fqk为阶数q的有限域Fq的k次扩域，H为F^k的素数阶数r的乘法子群，φ q为关于有限域Fq的元素的弗罗贝尼乌斯自同态映射，利用具有CPU和存储模块的电子计算机运算对于非负整数η的H的元素A的η次 幂的幂运算，该运算程序在电子计算机中执行输入步骤，输入所述非负整数η的值、所述阶数q的值、所述F^k的素数阶数r的 值、由AEHcFqk表示的元素A的值，并存储在所述存储模块中；初始化步骤，对存储运算结果Z的所述存储模块进行初始化；第一运算步骤，从所述存储模块读出所述阶数q、所述元素A的值，令所述q与r的 差为s = q_r，从j = 0到j <「lo&s」重复由T[j] 一 A和A — A*A表示的代入运算，将所述T[j]和所述A的值存储在所述存储模块中；展开步骤，从所述存储模块读出所述η和差s的值，根据由差s展开的下式[式11] i从i =0开始重复规定次数的由c[i] — 和η — (n_c[i])/s表示的代入运 算，将各系数c [i]和非负整数η的值存储在存储模块中；第二运算步骤，从存储模块读出c[i]和所述η的值，根据A[i] = f[i]，初始化A[i] =1，在c[i]&l时，从i = 0开始重复规定次数的由A[i] —A[i]*T[j]和c[i] — c[i]/2 表示的代入运算，将A [i]和c[i]的值存储在存储模块中；和合成步骤，CPU从存储模块读出各A[i]，根据下式[式12]Α^ΡΙΦ^ΑΜ)从i = 0开始重复规定次数的由Ζ —Ζ* Φ ^(Ati])表示的幂运算，将计算的结果 Z存储在存储模块中。进而，本发明的记录有幂运算的运算程序的记录介质中，设Χ~{Υ}表示 ΧΥ，在用整数变量X分别由q(>c)、r(>c)、S(>c)给出所述阶数q、所述素数阶数r、所 述s时，由电子计算机中执行如下步骤辅助输入步骤，输入所述9(>0、1~(>0、8(>0各值，存储在所述存储模块中；辅助展开步骤，从所述存储模块读出r ( X )和s ( X )，用所述s ( X )根据将Hx) 以S(X)进制展开的下式[式13]
fdeg r(x)/deg s(%)l
r(x) = Yj DiOOsOOi, 0 < Cleg(DiOO) < deg (s(x)) i=0从i = 0 至Ij i <「degr ( χ ) /degs (x)」重复由 Di(X)^r(X) %s(x)禾口 r(x) — (r(x)-Di(x))/s(x)表示的代入运算，将所述系数Di ( χ )和r ( χ )存储在所述 存储模块中；辅助抽出步骤，抽出被存储的系数Di(X)中，deg(Di(x))为最大的Ddmax ( χ )，存 储在所述存储模块中；辅助确定步骤，从所述存储模块读出所述Ddfflax ( X )、Di ( X )、q的值，使用满足(A" (Ddfflax (X)})" {qdmax} = Α" { Σ ^ ^ax-Di ( x ) q1} =A" {f (q, x)}的多项式f(q，X)，根据C^k(A) =A，确定满足A" (Ddfflax (x)} =A"{ Σ ^ ^ax-Di ( x ) Qi-QdmaxI = A" {h (q, x)}的多项式h (q，Χ )，将所述多项式h (q，X )的值存储在所述存储模块中；和
令χ = a将所述s进制展开的所述η替换为由s = Ddmax(a)构成的Ddfflax (a)进制 展开，替换为Ddmax (a)并使用所述多项式h(q，a)的步骤。而且，在本发明的记录有幂运算的运算程序的记录介质中，当所述系数Di ( χ )中存在多个为最高次数dmax的系数Di ( χ )时，所述辅助存储步骤还包括，输入满足r(X) Im(X)的m(X)的值，存储在所述存储 模块中的步骤，在电子计算机中执行如下步骤 第二辅助确定步骤，令degQJx))的最高次数dmax的项，S卩Xdmax的系数为 Tdfflax (q)，从所述存储模块读出系数Di (X)，在所述存储模块中对T (q，x)和U(q，x )的分 配初始值“0”，从i = 0到i <「degr(>c)/degS(>c)」重复进行代入运算，该代入运算中， ^deg(Di(x)) = dmax 时，表示为 T (q，x) — T(q，x )+Di ( x ) q、其他情况下，表示为 U (q， x) —U(q，XHDi(X)qS将T(q，x)和U(q，x)的值存储在所述存储模块中，确定最高次 数系数Tdmax (q)；第三辅助确定步骤，从所述存储模块读出m(x)和R(x)的值，使用满 Mr(X)Im(X)的最小次数的多项式m(X)，进行由W(q) - gcd (Tdfflax (q), m(q))和 V(q) — W(q)表示的运算，确定满足V (q) I m (q)，gcd (Tdmax (q)，V (q)) =1的V (q)，将所述V (q)的值存储在所述存储模块中；第四辅助确定步骤，从所述存储模块读出V(q)和m(q)的值，利用扩展欧几里得互 除法确定满足g(q)V(q) = ν (mod m(q))的整数标量ν和g (q)，将所述标量ν和g (q)的值存储在所述存储模块中；第五辅助确定步骤，替代所述辅助确定步骤，从所述存储模块读出Tdfflax (q)、X dma\ Di(X)、Q各值，利用满足A" (Tdfflax (q) x dmax} = A" { Σ Di(X) Qi-Tdmax (q) x dmax) = A" {f (q, x)}的多项式f(q，x)和所述g(q)，根据(^k(A) =A,确定满足Α" {ν χ dmaxI = A" {g (q) f(q, x)} = A"{h(q, x)}的多项式h (q，Χ )，将所述多项式h (q，X )的值存储在所述存储模块中；和CPU从所述存储模块读出所述h (q，X )的值，使该h (q，X )的关于q的常数项h (0，X )满足Α" {ν X —-h (0，x)} = A" {h (q，x ) _h (0，x )}，令x = a，进行由 s’ = vadmax-h(0, a)和 h，(q) = h(q，a)_h(0，a)表示的运算， 将S’和h’ (q)的值存储在所述存储模块中，代替以Ddmax(a)进制展开，对以s进行展开后 的所述η以vadmax_h (0，a)进制展开，并用h (q, a) _h (0，a)代替VadmaM1 (0，a)的步骤。发明效果本发明利用弗罗贝尼乌斯自同态映射Φ q消减运算次数，尤其是在标量乘法中，对 于G的有理点Q，使= [q]Q = [t-l]Q成立，或者是在幂运算时，令q与r的差为s = q-r,对于H的非零元素A，使
Φ^Α) = Aq = As成立，由此，对标量η以t-1进制展开，或对指数(Χ t数)η以s进制展开，通过替 换为t-Ι并使用有理点的弗罗贝尼乌斯映射，或替换为s并使用元素的弗罗贝尼乌斯自 同态映射Φ q，使得即使在标量乘法中的标量n，或幂运算中的指数η不是远大于阶数q时， 也能够减少运算次数，提高运算速度。尤其是在以配对为基础的基于ID加密或群签名等中使用椭圆曲线作为双线性对 曲线的配对，在使用该双线性对曲线时，使用整数变量X预先给出阶数q(x)、整除#E(Fq) 的素数阶数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)，在标量乘法中，将Hx)以 t ( X ) -1进制展开，并设在该Wt(X)-I进制展开时导入的系数Di ( χ )中最高次数的系数 Di(X) SDdmax(X),将该Ddmax(X)置换为多项式h(c^，χ )，由此进一步消减运算次数，另 夕卜，在幂运算中，将r(x)以S(X) = q(x)-r(x)进制展开，并设在该以s(x)进制展开 时导入的系数Di(X)中最高次数的系数Di(X)为Ddmax(X),将该Ddmax (χ)置换为多项式 h (Φ ,，χ )，由此能够进一步消减运算次数，提高运算速度。而且，当存在多个为最高次数的dmax WDi (X)时，使用满足r ( χ ) |m( χ )的最小 次数的多项式m (χ)，确定满足V (q) I m (q)，gcd (Tdmax (q)，V (q)) =1的V (q)，并使用满足g(q)V(q)三ν (mod m(q))的整数标量V，在标量乘法中，替代以Ddfflax ( x )进制展 开，对以t-Ι进制展开后的标量η以VXdmaM1 (0，X)进制展开，通过用h(q，x)-h(0, χ) 代替vXd X_h(0，χ )，进一步消减运算次数，另外，在幂运算中，代替Ddmax(X)进制展开， 对以s进制展开后的指数η以vxdmax-h(0，X)进制展开，通过用h(q，x)-h(0, x )代替 ν χ dmaMi(C), χ )，进一步消减运算次数，提高运算速度。
图1具有标量乘法的运算程序和幂运算的运算程序的电子计算机。图2是标量乘法的运算程序的流程图。图3是标量乘法的运算程序的流程图。图4是用于求取Ddmax (X)和多项式!!(Φ,，x)的辅助程序的流程图。图5是标量乘法的运算程序的流程图。图6是用于求取!!(Φ,，X )禾Π ν X dmax-h(0, χ )的辅助程序的流程图。图7是幂运算的运算程序的流程图。图8是幂运算的运算程序的流程图。图9是用于求取Ddmax (X)和多项式h(q，x)的辅助程序的流程图。图10是幂运算的运算程序的流程图。图11是用于求取多项式h(q，X )禾Π ν X dmaM1 (0，x )的辅助程序的流程图。符号说明10电子计算机
IlCPU12存储装置
13存储器14 总线15输入输出控制部20电气通信线路30客户端
具体实施例方式本发明的目的是提高标量乘法和幂运算的运算速度，虽然标量乘法和幂运算的运 算本身不同，但使用相同方法提高运算速度，能够消减他们的运算次数，从而能够提高运算 速度。首先对标量乘法进行说明，然后再对幂运算进行说明。首先，设椭圆曲线为E/F, = x3+ax+b-y2 = 0，其中 a G Fq，b e Fq定义E(Fq)由有限域Fq定义的椭圆曲线的有理点构成的加法群；E (Fqk)由有限域Fq的扩域E (Fqk)定义的椭圆曲线的有理点构成的加法群；关于有限域Fq的有理点的弗罗贝尼乌斯自同态映射；t:弗罗贝尼乌斯自同态映射的迹；r 整除E (Fq)的阶数#E (Fq) = q+1-t的素数阶数；EM 阶数为素数r的有理点集合；[j] :j倍的有理点的映射；G 包含于满足G = E[r] Π Ker ( Φ「[q])的E(F^k)中的有理点集合。然后，运算关于非负整数η的G的有理点Q的标量η乘法，即nQ。而且，在本实施 方式中，所设定的标量乘法是在配对运算时进行的，一般标量η不远大于阶数r。另夕卜，由于 r = q+1-t,因此 0 三 q+r-t (mod r)。再次，对标量η以t-1进制展开，则标量η不远大于阶数r，因此为η = Cjt-1)+C。，或η = (t-1)'+C1U-I)+C00由于(^(Q)= [q]Q = [t_l]Q，因此在 η = C1 (t_l)+C。，nQ 时，nQ 如下所示，nQ = [C1U-I)+C0] Q= [Ciq]Q+[C0]Q= cji(1([C1]Q) + [C(1]Q。另夕卜，当n = (t-lV+Qa-D+Co时，nQ如下所示nQ = [ (t-1) '+C1 (t_l) +C0] Q= [q] [q]Q+[Ciq]Q+[C0]Q= (^((^(QD + c^aCjQHECjQ。在此，C1和Ctl与t-1同等或略小，而且能够使用有理点的弗罗贝尼乌斯自同态映 射，由此能够减少运算次数。因而，能够提高标量乘法的运算速度。另外，通常进行配对运算时，多是使用已知的双线性对曲线，预先由整数变量X 给出阶数q(x)、整除#E(Fq)的素数阶数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)。在此，考虑[r]Q= [q+l-t]Q = 0，设用t(x)_l除r(x)而未除尽。即，r(x)表示为
[r ( χ ) Q = Σ [Di(X) U(X)-DiJQ =Σ Φ ； ([Di (( χ ) ]Q),以t(x)_l进制展开，令Di(X)中最高次数者为Ddmax(X)。然后，将定义为Φ/"χ(
0) =Σ Φ (
0)-Φ^χ(
0)= [f(Φ,, x)]Q的以Φ q和x为变量的二元多项式!!(Φ,，X)导入。进而，根据Φ qkQ = Q，将定义为[Ddmax(X)JQ = ^(Φ,, χ) Φ广ax]Q= ^(Φ,, x)]Q的以Φ q和x为变量的二元多项式!!(Φ,，X)导入。即，该多项式!!(Φ,，X)，能 够将Di (χ)中最高次数的Ddmax(x)，替换为以和χ为变量的多项式!!(Φ,，>0，能够抑 制向次数小于最高次数的运算。特别是χ =a时，将以t-Ι进制展开后的标量η进一步以 Ddfflax(a)进制展开，并用h(c^，χ)替换Ddfflax(a)，由此，能够大大减少运算次数，提高标量乘 法的运算速度。另外，当在Di ( χ )中有多个最高次数者时，用dmax表示最高次数，设作为最高次 数dmax项的Xdmax的系数为Tdmax(c^)，使用满足Hx) |m(X)的最小次数的多项式m( χ ) 确定满足ν(Φ5) |m(c^)，gCd(Tdmax((^)，V((^)) =1的ν(Φ,)。在此，多项式m(X)可以使用割圆多项式等。然后，使用扩展欧几里得互除法确定满足δ(φ )ν(φ ) = v(mod !!!(Φ,))的整数标量ν和g ( Φ ，作为[Tdfflax ( Φ q) XdmaxJQ=E Φ ([Ο (χ)]0)-[Τ,ω3Χ(Φ ) XdmaxJQ= [f(c^，x)]Q导入以Φ,和X为变量的二元多项式f( Φ ,，X)。进一步，使用g ( Φ ，并根据Φ qkQ = Q，令[VXdmaxJQ =x) (Γ(Φ,, x)]Q = ^(Φ,, x)]Q，导入以φ^和χ为变量的二元多项式!!(Φ,，X)。然后，使!!(Φ,，x)的关于Φ,的常数项h(0，x)满足[vx^-h (0, x)]Q = ^(Φ,, x)-h (0, x)]Q令χ =a，s，= vadmax h(0，a)，h，(Φ,) = h ( Φ q，a) _h (0，a)，替换以 Ddmax (a)进制 展开，将以t-1进制展开后的标量η以VadmaMi (0，a)进制展开，使用h ( Φ q，a) _h (0，a)替代 va^x-hO)，a)，由此能够减少运算次数，因而能够提高标量乘法的运算速度。在此，h’ (Φ,) 表示，在二元多项式!!(Φ,，χ)中，因令χ =a而成为Φ q这一个变量。以上对标量乘法进行了说明，但在幂运算中，定义Fqk 阶数q的有限域Fq的k次扩域；H :Fqk的素数阶数r的乘法子群；Φ q 关于有限域Fq的元素的弗罗贝尼乌斯自同态映射，进行关于非负整数η的H的元素A的η次方。令q与r的差为s = q~r,该s置换 标量乘法中的t-i，只需将上述说明改为幂运算，省略详细说明。在幂运算中，最高次数部分的运算能够置换为低次数的运算，从而能够减少运算次数，提高幂运算的运算速度。下面，使用已知的双线性对曲线说明具体的例子。作为埋入次数8的双线性对曲线，已知由r(x) = x4-8x2+25，t(x) = (2x3-ll x+15)/15 给出的整除#E(Fq)的素数阶数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)。此时，对r (χ)以t( χ )_1进制展开，利用弗罗贝尼乌斯自同态映射，得到2r(x) = (15 χ ) Φ,+(-5 χ 2+50)，0 = (15 χ) Φ,+ (-5 χ 2+50) (mod r ( χ ))因此，Di(X)成为D0(X) = -5 Χ2+50,D^ χ ) = 15 χ。其中，由于Dtl(X)为最高次数，因此，除Dq (Χ)以外移动到右侧，而得到-5 χ2+50 = 15 Χ Φ,对该式整理得到X2-IO = 3 χ Φ,ο因此，在进行关于非负整数η的G的有理点Q的标量η乘法，或关于非负整数η的 H的元素A的η次幂中，对于非负整数η，将η以t_l进制展开，进而以x 2_10进制展开，用 15 χ 代替x2-10，由此能够利用弗罗贝尼乌斯自同态映射Φ q来运算G的有理点标量η 乘法或H的元素A的η次幂，减少运算次数，提高幂运算的运算速度。作为其他埋入次数8的双线性对曲线，在由r ( χ ) = x8-x 4+1,t ( χ ) = χ 5- χ +1给出整除#E(F(1)的素数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)时，将 r(x)以t( χ )-1进制展开，使用弗罗贝尼乌斯自同态映射，得到r( χ ) = χ0 三 βφ^+ Οιιο Ι r(x))。因此，Di(X)成为D0(X) = -1，D1(X) = x3。其中，由于D1 ( χ )为最高次数，因此，除D1 ( χ ) 以外移动到右侧，得到X3(J)q = -I两边同时乘以得到X3 = -(J)tJ115因此，在进行关于非负整数η的G的有理点Q的标量η乘法，或关于非负整数η的H 的元素A的η次幂中，对于非负整数η，将η以t_l进制展开，进而以x 3进制展开，用_ Φ ；1 代替χ 3，从而能够使用关于有理点的弗罗贝尼乌斯自同态映射来运算G的有理点的标 量η乘法或H的元素A的η次幂，能够减少运算次数提高幂运算的运算速度。另外，在埋入次数10的双线性对曲线中，已知由
r ( χ ) = 25 χ 4+25 χ 3+15 χ 2+5 χ +1，t ( χ ) = 10 χ 2+5 χ +3 给出整除#E(F(1)的素数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)。此时，将r (X)以t( X )_1进制展开，通过使用弗罗贝尼乌斯自同态映射，得到8r(x) = 2 Φ q2- Φ q+ (5 χ +2),0 = 2 Φ q2- Φ q+ (5 χ +2) (mod r(x))因此，Di(X)成为D0( χ ) = 5 χ +2,D^ χ ) = -1，D2(χ) =2。其中Dtl(X)为最高次数，因此，除Dq (Χ)以外移动到右侧，得到5χ+2 = ^Φ^+Φ,ο因此，在进行关于非负整数η的G的有理点Q的标量η乘法，或关于非负整数η 的H的元素A的η次幂中，对于非负整数η，将η以t_l进制展开，进而以5 χ +2进制展开， 用-2 Φ q2+ Φ q代替5 χ +2，由此能够利用弗罗贝尼乌斯自同态映射Φ q来运算G的有理点标 量η乘法或H的元素A的η次幂，减少运算次数，提高幂运算的运算速度。另外，在埋入次数12的双线性对曲线中，已知由r( χ ) = 36 χ 4_36 χ 3+18 χ 2_6 χ +1，t ( χ ) = 6 χ 2+1给出整除#E(F(1)的素数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)。此时，将r(χ)以t( χ )_1进制展开，通过使用弗罗贝尼乌斯自同态映射，得到r(x) = Φq2+ (-6 χ +3) Φq+ (_6 χ +1)，0 = Φ,2+ (-6 χ +3) Φq+ (-6 χ +1) (mod r ( χ ))。因此，Di(X)成为D0( χ ) = -6 χ +1，Di( χ ) = -6 χ +3,D2 ( χ ) = 1。其中D。(x)和01(>0为最高次数，因此，除Dtl(X)和01(>0 (^得到最高次数的 X以外项移动到右侧，得到6 χ (Φ,+1) = φ^+βφ,+ ο在此，若设g(c^) = (^4-(^2+1，则满足8(3(1((^+1，8((^)) = 1，利用扩展欧几里 得互除法得到( φq+l)-1E φ,2 (1-φq) (mod g( Φ)。因此，两边同乘以\2(1-(^)，得到6x = Φ^Ι-Φ^) ((^2+3(^+1)。因此，在进行关于非负整数η的G的有理点Q的标量η乘法，或关于非负整数η 的H的元素A的η次幂中，对于非负整数η，将η以t_l进制展开，进而以6 χ进制展开，用 Φ,2(1-Φ(1)(Φ q2+3 Φ q+l)代替6 χ，由此能够利用弗罗贝尼乌斯自同态映射Φ q来运算G的 有理点标量η乘法或H的元素A的η次幂，减少运算次数，提高幂运算的运算速度。
作为更具体的例子，设X = 825 (10位)。此时，r = 16656811746301 (44 位)t = 4083751(22 位)。此时，由于
6 χ = 4950(13bits) = Φ,2(I"Φ,) (φ,'+βφ,+ )因此，在进行G的有理点的标量η乘法或H的元素A的η次幂时，使用有关有理点 的弗罗贝尼乌斯自同态映射变换为13位左右的标量乘法或幂运算后，进行运算，能够 大幅减少运算次数。另外，在埋入次数18的双线性对曲线中，由r(x) = χ 6+37 χ 3+343，t(x) = (x 4+16 χ+7)/7给出整除#E(F(1)的素数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)。此时，将r(χ)以t( χ )_1进制展开，通过使用弗罗贝尼乌斯自同态映射，得到r(x) = (7 χ2)) Φ,+ (21 x 3+343)0 = (7 χ2) Φ J (21 χ 3+343) (mod r(x))。因此，Di(X)成为D0(X) = 21 X3_343，D1(X) = 7 X20其中Dtl(X)为最高次数，因此，除Dq(Χ)以外移动到右侧，得到21 χ 3-343 = 7 χ2Φ9,对该式整理，得到χ 3-49 = χ2Φ 0因此，在进行关于非负整数η的G的有理点Q的标量η乘法，或关于非负整数η的 H的元素A的η次幂中，对于非负整数η，将η以t_l进制展开，进而以x 3_49进制展开，用 Χ2Φ,代替χ 3_49，由此能够利用弗罗贝尼乌斯自同态映射Φ q来运算G的有理点标量η乘 法或H的元素A的η次幂，减少运算次数，提高幂运算的运算速度。最后，对标量乘法的运算程序和幂运算的运算程序进行说明。而且，在本实施方式 中，标量乘法的运算程序和幂运算的运算程序是在由电子计算机执行基于ID加密或群签 名等时，作为一个子程序来执行的。如图1所示，执行标量乘法的运算程序和幂运算的运算程序的电子计算机10具 有执行运算处理的CPUll ；和由存储所需程序或数据的硬盘等存储装置12、能够展开执行 所需程序并临时存储运算中生成的数据的RAM构成的存储器13。图1中，14为总线。在本 实施方式中，在存储装置12中存储有主程序、标量乘法的运算程序/幂运算的运算程序等 各种程序、以及这些程序所要使用的数据。电子计算机10，在用作例如群签名中的认证装置时，与因特网等电气通信线路20 连接，接收从连接在该电气通信线路20上的客户端装置30发送来的群签名的签名数据，临 时存储于存储器13中，根据群签名用的程序判断签名数据的合法性而进行认证处理。图1 中，15为电子计算机10的输入输出控制部。在判断签名数据的合法性的处理中，多是执行标量乘法的运算程序和幂运算的运算程序，以下，对标量乘法的运算程序和幂运算的运算程序进行说明。而且，本发明的标量 乘法的运算程序和幂运算的运算程序并限于在群签名处理中使用，其能够用于多种用途。 并且，本发明的标量乘法的运算程序和幂运算的运算程序，可以是记录在存储装置12中或 能够由电子计算机读取的记录介质中，或者从服务器下载到记录装置中的，还可以是构成 为半导体电路，即以硬件形式构成的。首先，说明基于t-Ι进制展开的标量乘法nQ。图2为用于求取标量乘法nQ( = Ζ)的流程图。执行标量乘法的运算程序，电子 计算机发挥标量乘法器的作用。如图2所示，最初，CPUll通过电气通信线路20、输入输出 控制部15从客户端装置30输入标量IuE(Fq)的弗罗贝尼乌斯自同态映射的迹t和有理点 QeGcE(Fqk)的值，存储在存储器13中(步骤S101)。此时，电子计算机用作输入装置。然后，CPUll在存储器装置13中设定要保持的运算结果Z，并对Z初始化(Z — 0) (步骤S102)。因此电子计算机用作输入装置。CPUll对输入的Q执行有2恂表示的运算 (步骤 S103)。 在步骤S103中，令T[j] = 2JQ,CPUll从存储器13读出Q、t的值，执行如下动作(l)for(j = 0 ;j <「Iog2S」；j++)(2)T[j]—Q(3)Q —Q+Q(4)End for。在此，(1)中的「log2s」准确意义上应为[式14]
卩Og2 Sl
9但因文本的原因，用「」来标记。在此，CPUll令s = t-Ι，设j为自然数，从j = 0 到j <「lo&s」反复执行由T[j] — Q和Q — Q+Q表示的代入运算，将运算结果值存储在存 储器13中。而且，以下动作用使用的「」与上同。接着，令t-l = s,CPUll从存储器11读出c[i]、s、标量η的值，用作转换装置，将 标量η，根据[式15]
Hogs.nl
η = ^ C^si, 0 < c[i] < s i=0以s进制展开(步骤S104)。在此，i为自然数，i的大小由η决定。在步骤S104中，进行s进制展开运算，CPUll执行以下动作(l)for(i = O ;i <「logsn」；i++)(2)c[i] ^ n% s(3)n — (n_c[i])/s(4) End for
在此，“ ％，，表示余数。即，CPUll从存储器13读出c [i]、s、η的值，从i = 0到i <「logsn」反复执行由c [i] — s和η — (n-c [i]) /s表示的代入运算，将各系数c [i]、 和标量η的值存储在存储器13中。
然后，在本实施方式中，电子计算机用作第二运算装置进行Q[i] =c[i]Q运算 (步骤 S105)。在步骤S105中，用二进制法，CPUll执行以下动作(l)for(i = 0 ;i <「logsn」；i++)(2)Q[i]—0(3)for(j = 0 ；c[i] ！ = 0 ；i++)(4)if(c[i]&l)(5)Q[i] — Q[i]+T[j](6) End if(7)C[i] — c[i]/2(8) End for(9) End forBP, CPUll从i = 0到i <「logsn」利用Q[i] — 0的代入运算对存储在存储器13 中的Q[i]初始化，并重复执行以下运算。CPUll从存储器13读出系数Q[i]、T[i]，从j = 0到c[i] ！ =0，重复执行如下代入运算，即，在c[i]&l时执行由Q[i] — Q[i]+T[j]表示 的代入运算，在其他情况下执行由c[i] — c[i]/2表示的代入运算，将各Q[i]和系数c[i] 存储在存储器13中。接着，电子计算机作为合成装置，使用在步骤S105中运算的Q[i]，利用[式 16]
Hogs nl
IiQ=艺
i=0对标量乘法nQ进行合成(步骤S106)。在步骤S106中，CPU执行以下动作(l)for(i = 0 ;i <「logsn」；i++)(2)Z - Ζ+Φ； (Q[i])(3) End forBP, CPUll从存储器13读出Q[i]、的值，从i = 0到1 <「logsn」重复执行由 Z — Ζ+Φ； (Q[i])表示的代入运算，将Z的值存储在存储器13中。然后，电子计算机作为输出装置，从输入输出控制部15输出Z的值作为标量乘法 的运算程序的执行结果(步骤S107)，结束标量乘法的运算程序。由此，对标量η进行IogsIi 分割，因而能够通过使用Φ q将椭圆二倍计算的运算次数较少为大致l/logsn。另外，在用整数变量X分别以q(>c)、r(>c)、t(>c)来确定椭圆曲线的有限域Fq 的阶数q、整除#E(Fq)的素数阶数r、弗罗贝尼乌斯自同态映射Φq的迹t时，将r ( χ )以 t(x)_l展开，从而令由
[r(x)]Q =Σ [Di(X) (t(x)-l)i]Q =Σ Φ ； ([Di ( χ ) ]Q)表示的Di(X)中最高次数者为Ddmax(X),并使用由Φ/"χ(
9=Σ Φ (
0)-Φ^χ(
0)
= [f(Φ,, x)]Q表示的多项式 ΧΦ,，X)，根据cj\kQ = Q，使用由[Ddmax(X)JQ = ^(Φ,, x) Φ广ax]Q= ^(Φ,, x)]Q表示的多项式h ( Φ ,，χ )禾Π Ddmax (χ),来提高标量乘法nQ的运算速度。即，在Ddmax ( χ )和多项式h ( Φ ,，χ)被确定时，设χ = a，对标量η以Ddmax (a)进 制展开，并用ΜΦ,，χ)替换Ddmax (a)，从而减少运算次数。当Ddmax ( χ )和多项式h ( Φ ,，χ )被确定时，在标量乘法nQ中执行标量乘法的运算 程序，电子计算机作为标量乘法器使用。此时，如图3所示，最初CPUll输入标量n，令χ = 8,8 = 0^(8)^' (Φ,) =h(c^，a)，并输入有理点Q EGcE(Fqk)各值，存储在存储器I3 中(步骤S201)。此时，电子计算机用作输入装置。接着，电子计算机作为初始化装置。S卩，CPUll在存储器13中设定保持运算结果 的Z，并对其初始化为Z —0 (步骤S202)。然后，电子计算机用作第一运算装置。S卩，CPUll 对输入的Q预先运算2力(步骤S203)。步骤S203的运算与步骤S103的动作相同，省却其 说明。然后，电子计算机用作第一展开装置，用[式17]
『logs nl
η = ^ c^s1, 0 < c[i] < s i=0对标量η以s进制展开(步骤S204)。步骤S204中的s进制展开与步骤S104中 的展开动作相同，省略其说明。然后，电子计算机用作第二展开装置，使用h’ (Φ,)和c [i]，并利用[式18] k-1η = ^ Ηφη1, 0 < d[i] < S
i=0对标量η以Φ q进制展开(步骤S205)。在步骤S205中，进行Φ q进制展开，CPUll执行以下动作(1)Τ(Φ ) - 1(2)for(i = 0 ;i <「logsn」；i++)(3)d[i] - c[i](4)if(d[i]彡 s)(5)for(j = 0 ;j <「logsd[i]」；j++)(6)e[j] - d[i]% s(7)d[i] - (d[i]-e[j])% s
(8) End for(9)υ(Φ ) - 1(10) for (j = 0 ;j <「logsd[i]」；j++)(11)υ(Φ ) - {U(c^)*e[j]*h，(Φ ) '}% (Φ,'-Ι)(12) End for(13)Τ(Φ ) 一 {!"(Φ^+ΜΦ,)*!!，(Φ ) }% (Φ,'-Ι)(14) End if
(15)else(16)Τ(Φ ) 一 {T(c^)+d[i]*h，(Φ ) }% (Φ,'-Ι)(17)End else(18) End forBP, CPUll对存储在存储器13中的Τ(Φ,)初始1。CPUll从存储器13读出c[i] 的值，进行d[i] —c[i]的代入运算，并将d[i]的值存储在存储器13中。然后CPU从存 储器13读出d[i]、s的值，在满足d[i]彡s时，从j = 0到j <「logs d[i]」反复执行由 e[j] -d[i]%siPd[i] 一(d[i]-e[j])%s 表示的代入运算，在进行了 υ(Φ) —1 的 初始化后，从 j = 0 到 j < riogsd[i]J 反复执行由 υ(Φ,) — {U(c^)*e[j]*h’ (Φ,)^ % (Φ,'-Ι)表示的代入运算，然后执行由 Τ(Φ,) — {T(c^)+d[i]*h，(Φ,)1} % (Φ^-Ι)表 示的代入运算，将Τ(Φ,)的值存储在存储器13中。CPU11，在不满足d[i] > s时，执行由 Τ(Φ,) 一 {Τ(Φ,)+(1[ ]^'(Φ(1) }% (Φ^-1)表示的代入运算，将Τ(Φ,)的值存储在存储 器13中。CPUll从i = 0到i <「logsn」反复执行以上运算，将各i的d[i]、Τ(Φ)的值 存储在存储器13中。而且，在将标量η以Φ q进制展开时，以进制展开的系数d[i]比s大。CPUll 将进制展开的系数d[i]与s相比较，在判断为进制展开的系数d[i]比s大时(步 骤S206 =NO)，通过相对于以Φ q展开的系数d[i]取s的余数而进行调整，以使Φ q展开的系 数d[i]比s小(步骤S207)。此时，电子计算机在步骤S206中用作比较装置，在步骤S207
中用作调整装置。在步骤S207中，电子计算机执行以下动作(1) until(Vd[i]<s)(2)for(i = 0 ;i < k-1 ；i++)(3)d[i] — the i_th coefficient of Τ(Φ)(4)if(d[i]彡 s)(5) the i_th coefficient of !"(Φ) 一 0(6)for(j = 0 ;j <「logsd[i]」；j++)(7)e[j] - d[i]% s(8)d[i] - (d[i]-e[j])% s(9) End for(10)υ(Φ ) - 1(ll)for(j = 0 ;j <「logsd[i]」；j++)(12)υ(Φ,) 一 {U(c^)*e[j]*h，(Φ,'-Ι)
(13) End for (H)T(Cj5q) — {Τ(Φ )+υ(Φ(1)*Φ(1 }% (Φ,'-Ι)(15) End if(16) End for(17)End untilS卩，CPUll从存储器13读出Τ(Φ,)的第i个系数的值，在d[i]中存储其值，将d[i] 与s的值相比较。CPU11，在满足d[i]彡s时，对Τ(Φ,)的第i个系数存储0、从j = 0到 j <「logsd[i]」重复执行由 e[j] —d[i]%s 禾口d[i] — (d[i]_e[j])% s表示的代入运算，然后，在进行了 υ(Φ,) — 1的初始化 后，从 j = o 到 j <「iogsd[i]」重复执行由 υ(Φ,) — {u(c^)*e[j]*h，(Φ,'-ι) 表示的代入运算，接着，执行由τ(φ,) — {Τ(Φ )+υ(Φ(1)*Φ(1 }% (Φ^-Ι)表示的代入运算， 将τ(φ,)的值存储在存储器13中。CPU11，在不满足d[i] > S时，不进行上述一系列的运 算。CPUll从i = 0到i < k-ι重复执行上述运算，直到满足Vd[i]<s。接着，电子计算机作为第二运算装置，进行Q[i] = d[i]Q的运算(步骤S208)。在步骤S208中，使用二进制法，CPUll执行以下动作(l)for(i = 0 ;i < k ；i++)(2)Q[i]—0(3)for(j = 0 ；d[i] ！ = 0 ；i++)(4)if(d[i]&l)(5)Q[i] — Q[i]+T[j](6) End if(7)d[i] — d[i]/2(8) End for(9) End for即，CPUll从存储器13读出d[i]和T[j]的值，令Q[i] — 0，对Q[i]初始化后， 在满足d[i]&l时，执行由Q[i] — Q[i]+T[j]表示的代入运算，在不满足d[i]&l时，执行由 d[i] — d[i]/2表示的代入运算，将Q[i]和d[i]的值存储在存储器13中。然后，电子计算机用作合成装置，使用由步骤S208运算的Q[i]，利用[式19]
k-1
i=0对标量乘法nQ进行合成(步骤S209)。在步骤S209中，CPUl 1执行以下动作(l)for(i = 0 ;i < k ；i++)(2)Z - Ζ+Φ； (Q[i])(3) End forBP, CPUll从存储器13读出Z和Q[i]的值，从i = 0到i < k重复执行由 Ζ-Ζ+φ;(0[ ])表示的代入运算，将Z的值存储在存储器13中。CPUll从输入输出控制部15输出Z的值。S卩，电子计算机用作输入装置，输入Z作为标量乘法的运算程序的执行 结果(步骤S210)，宛城标量乘法的运算程序。由此，对标量η进行IogsIi分割，因而能够通 过使用Φ q将椭圆二倍计算的运算次数较少为大致ClegDdmax ( χ ) /degr ( χ )。由于预先给出椭圆曲线的有限域Fq的阶数q ( χ )，整除#E (Fq)的素数阶数r ( χ )， 弗罗贝尼乌斯自同态映射Φ q的迹t ( χ )，因而能够预先确定Ddfflax ( χ )和多项式h (Φ ,，χ )， 所以也可以预先将Ddmax(X)和多项式!!(Φ,，χ)与q(x)、r(>c)和t(x) —同安装到标 量乘法的运算程序中，也可以用r(χ)和t( χ )根据以下辅助程序求出Ddmax(X)和多项式 h( Φ。χ )。在电子计算机启动辅助程序时，如图4所示，首先用作输入装置。S卩，CPUll输入 r(x)和t(x)的值并存储在存储器13中(步骤S221)。然后，电子计算机用作展开装置，使用输入的t ( X )，令t ( X ) -1 = s ( X )，利用[式 20]
『deg r(x)/degs (χ)1
Γω = Z Di(X)S(X)S O^deg(DiOO)(5(χ))
i=0 将r(x)以s(x)进制展开(步骤S222)。在此，i的大小由r(x)和s(x)自动 决定。在步骤S222中，作为S(X)进制展开的运算，CPUll执行以下动作(l)for(i = 0 ;i <「degr ( x )/degs ( x )」；i++)(2)Di(X) —r(x) % s(x)(3)r(x) — (r ( x ) -Di ( x )) /s ( x )(4) End forBP, CPUll 从存储器 13 读出 r(x)和 s(x)的值，从 i = 0 到 i < degr(x)/ degs(x)重复执行由 Di(X) —r(x) % S(x)和 r(x) — (HX)-Di(X)Vs(X)表示的 代入运算，将Di(X)和r( χ的值存储在存储器13中。然后，电子计算机用作抽出装置，抽出deg^Jx))为最大者，作SDdfflax (X)输出 (步骤S223)。即，CPUll从存储器13读出Di(X)的值并进行比较，将最大的Di ( x )作为 Ddfflax ( Χ )并将其值存储在存储器13中。然后，电子计算机用作运算装置。S卩，CPUll进行[式21]
fdeg r(x)/degs (χ)1
h(ctvx) =^DiOO&ifd腿)-Ddmax (χ)
i=0的运算，确定多项式!!(Φ,，x )，将其值存储在存储器13中，并输出(步骤S224)。 如上所述，在电子计算机使用辅助程序，能够求出Ddmax(X)和多项式ΜΦ,，x)。通过将 Ddfflax(X)和多项式ΜΦ,，Χ)用于图3的步骤201，能够使图3所示标量乘法中椭圆二倍计 算的运算次数较少为大致ClegDdmax ( χ ) /degr ( x )。另外，使用整数变量X并分别预先由q(>c)、r(>c)、t(>c)确定椭圆曲线的有限域Fq、整除#E (Ftl)的素数阶数r(x)、弗罗贝尼乌斯自同态映射的迹t，并且将Hx)以 t(x)_l进制展开，从而由[r(x)]Q =Σ [Di ( χ ) (t ( χ )-1) iJ Q = Σ Φ ； ([Di ( χ ) ]Q) 表示Di ( χ )，当Di ( χ )中最高次数dmax为多个时，设作为最高次数dmax的项的 Χ “的系数为Tdmax ( Φ ，使用满足r ( χ ) I m ( χ )的最小次数的多项式m ( χ )，确定满足ν(Φ5) |m(c^)，gCd(Tdmax((^)，V((^)) =1的V ( Φ ，并利用扩展欧几里得互除法确定满足Ε(Φ )ν(Φ ) = v(mod !!!(Φ,))的标量ν和g ( Φ ，使用满足[Tdfflax ( Φ q) XdmaxJQ=E Φ ([Ο (χ)]0)-[Τ,ω3Χ(Φ ) XdmaxJQ= [f(c^，x)]Q的多项式f ( Φ q，x )和g ( Φ ，根据Φ qkQ = Q，来确定满足[VXdmaxJQ = [g(c^)f(cK，x)]Q = ^(Φ,, x)]Q的多项式!!(Φ,，乂)，并使该11((^，x)的关于Φ,的常数项h(0，x)满足[vx^-h(0, x)]Q = ^(Φ,, x)-h(0, x)]Q，从而提高标量乘法nQ的运算速度。即，令χ =a，s，= vadmax-h (0，a)，h，(Φ,) = h ( Φ q，a) _h (0，a)，代替以 Ddmax (a) 进制展开，而将标量η以vadmax-h (0，a)进制展开，用h ( Φ q，a) _h (0，a)代替vadmax-h (0，a)， 由此消减运算次数。当确定了s，= VadmaMi(Oia)，h，(Φ,) = h ( Φ q, a)-h (0, a)时，在标量乘法 nQ 中， 执行标量乘法的运算程序，电子计算机用作标量乘法器。此时，如图5所示，首先CPUll输 入标量 n，令 χ =a、标量 s，= Vadmax-h(0，a)、h，(Φ,) = h ( Φ q，a) _h (0，a)，并输入有理点
QEGcE(Fqk)的值，存储在存储器13中(步骤S301)。此时，电子计算机用作输入装置。接着，电子计算机用作初始化装置，CPUll在存储器13中设定保持运算结果的Z， 并进行Z —0的初始化(步骤S302)。然后电子计算机用作第一运算装置，CPUll读出存 储在存储器13中的Q的值，预先进行2力的运算，存储在存储器13中(步骤S303)。步骤 S303的运算与步骤S103的运算动作相同，CPUll进行的处理也相同，省略其说明。然后，电子计算机用作第一展开装置，利用[式 2幻
flog s η!
η= I OScDW
i=0将标量η以s，进制展开(步骤S304)。步骤S304中的S，进制展开与步骤S204 中的s进制展开的动作相同，CPUll进行的处理也相同，省略其说明。接着，电子计算机用作第二展开装置，使用h’ (Φ,)和c [i]，并根据[式2幻 k-1η = ^ d[i]<^q[, 0 < d[i] < s'
i=0
将标量η以Φ q进制展开(步骤S305)。步骤S305中的Φ q进制展开，除了标量 s，( = vadmax-h(0, a))与步骤S205中的标量M = Ddfflax(a))不同以外，与步骤205中以s 进制展开动作相同，CPUll进行的处理也相同，省略其说明。步骤S305中的进制展开中，进制展开的系数大于s，。如上所述，在进 制展开的系数比s’大时(步骤S306 :N0)，相对Φ q进制展开的系数取S’的余数而进行调 整，以使进制展开的系数比s’小(步骤S307)。步骤S307中的运算，除标量S’ (= VadmaM1 (0，a))与步骤S207中的标量s ( = Ddmax(a))不同以外，与步骤S207的运算动作相 同，CPUll进行的处理也相同，因此省略其说明。此时，电子计算机在步骤S306中用作比较 装置，在步骤S307中用作调整装置。接着，电子计算机用作第二运算装置，进行Q[i] =d[i]Q的运算(步骤S308)。在 步骤S308中，利用二进制法，步骤S308的运算与步骤S208的运算动作相同，CPUll进行的 处理也相同，省略其说明。接着，电子计算机用作合成装置，使用在步骤S308中运算的Q[i]，利用[式24]
权利要求
一种标量乘法的运算方法，其特征在于设椭圆曲线为E/Fq＝x3+ax+b y2＝0，其中a∈Fq，b∈Fq令，E(Fq)为由有限域Fq定义的椭圆曲线的有理点构成的加法群；E(Fqk)为由有限域Fq的扩域Fqk定义的椭圆曲线的有理点构成的加法群；φq为关于有限域Fq的有理点的弗罗贝尼乌斯自同态映射；t为弗罗贝尼乌斯自同态映射φq的迹；r为整除E(Fq)的阶数#E(Fq)＝q+1 t的素数阶数；E[r]为阶数为素数r的有理点集合；[j]为j倍的有理点的映射；G为包含于满足G＝E[r]∩Ker(φq [q])的E(Fqk)中的有理点集合，利用具有CPU和存储模块的电子计算机来运算关于非负整数n的G的有理点Q的标量n乘法，所述运算方法包括输入步骤，CPU输入所述非负整数n的值、所述迹t的值、和由表示的有理点Q的值，并存储在所述存储模块中；初始化步骤，CPU将存储运算结果Z的所述存储模块初始化；展开步骤，对于G的有理点Q，φq(Q)＝[q]Q＝[t 1]Q成立，由此CPU令s＝t 1，根据将所述n以s进制展开的下式，[式39] <mrow><mi>n</mi><mo>=</mo><munder> <mi>Σ</mi> <mi>i</mi></munder><mi>c</mi><mo>[</mo><mi>i</mi><mo>]</mo><msup> <mi>s</mi> <mi>i</mi></msup><mo>,</mo><mn>0</mn><mo>≤</mo><mi>c</mi><mo>[</mo><mi>i</mi><mo>]</mo><mo>≤</mo><mi>s</mi> </mrow>从i＝0开始重复进行规定次数的由C[i]←n％s和n←(n c[i])/s表示的代入运算，将各系数c[i]和非负整数n的值存储在所述存储模块中；运算步骤，CPU从所述存储模块读出所述有理点Q和所述系数c[i]，从i＝0开始重复进行规定次数的由Q[i]＝c[i]Q表示的运算，将各Q[i]的值存储在所述存储模块中；和合成步骤，用弗罗贝尼乌斯自同态映射φq取代t 1，标量乘法nQ表示为下式[式40] <mrow><mi>nQ</mi><mo>=</mo><munder> <mi>Σ</mi> <mi>i</mi></munder><msup> <msub><mi>φ</mi><mi>q</mi> </msub> <mi>i</mi></msup><mrow> <mo>(</mo> <mi>Q</mi> <mo>[</mo> <mi>i</mi> <mo>]</mo> <mo>)</mo></mrow><mo>,</mo> </mrow>CPU根据该式，从所述存储模块读出Q[i]和运算结果Z，从i＝0开始重复规定次数的由Z←Z+φqi(Q[i])表示的代入运算，将标量乘法的运算结果Z存储在存储模块中。FPA00001208044000011.tif
2.如权利要求1所述的标量乘法的运算方法，其特征在于在利用整数变量χ分别由q(>c)、r(>c)、t(>c)给出所述椭圆曲线的有限域Fq的阶数q、整除#E(Fq)的素数阶数r、弗罗贝尼乌斯自同态映射的迹t时，包括辅助输入步骤，CPU输入所述q(>c)、r(>c)、t(>c)各值，存储在所述存储模块中； 辅助展开步骤，CPU从所述存储模块读出Hx)和t(x)的值，令所述s(x)= t(x)_l，根据将r(x)以s(x)进制展开的下式 [式 41]
3.如权利要求2所述的标量乘法的运算方法，其特征在于 当所述系数Di (χ)中存在多个为最高次数dmax的系数Di (χ)时， 所述辅助输入步骤还包括，CPU输入满足r (χ) |m(X)的m(X)的值，并存储在所述存 储模块中的步骤， 并具有第二辅助确定步骤，CPU令作为degQJx))的最高次数dmax项的Xdmax的系数为 U Φ)，从所述存储模块读出系数Di (χ)，在所述存储模块中对Τ(Φ,，χ)和υ(Φ,，χ) 分配初始值“0”，从i = 0到i <「degr(>c)/degS(>c)」重复进行如下代入运算，该代入运 算中，当deg^Jx)) = dmax时，进行由Τ(Φ,，χ)x )+Di ( χ ) Φ /表示的代入运算，其他情况下，进行由υ(Φ,，χ)XHDi(X) Φ^表示的代入运算，将Τ(Φ,，χ)和υ(Φ,，χ)的值存储在存储模块中，确定最高次数系数Tdmax(CK)；第三辅助确定步骤，CPU从所述存储模块读出m(X)和R(X)的值，用满足 H χ ) Im(X)的最小次数的多项式m(X)，进行由W(Cj5q) 一 gccKTjc^)，m(c^))和 ν(Φ,) -ΚΦ,)表示的代入运算，确定满足 ν(Φ,) ImQ^gccKUc^)，V(Cj5q)) = 1 的V ( Φ ，将所述V ( Φ 的值存储在存储模块中；第四辅助确定步骤，CPU从所述存储模块读出V( Φ 和m(c^)的值，利用扩展欧几里 得互除法确定满足三 ν (mod m((j5q))的整数标量ν和g ( Φ 的值，将所述标量ν和g ( Φ 存储在所述存储模块中； 第五辅助确定步骤，替代所述辅助确定步骤，CPU从所述存储模块读出Tdmax(CK)、 χ “、Di ( χ )、Q 各值，使用满足[Tdmax (Φ,) χ dmax] Q=E Φ / ([Di ( χ ) ] Q) - [Tdfflax (Φ q)dmax] Q = [ΜΦ,，x)]Q的多项式ΜΦ,，x)和所述β(Φ )，根据= 9确定满足 [ν X dmaxJQ= [g(c^)f(cK，x)]Q= ^(Φ,, x)]Q的多项式h(c^，\)，将所述多项式11((^，χ)的值存储在所述存储模块中；和 CPU从所述存储模块读出所述h(c^，χ)的值， 使该ΜΦ,，χ)的关于Φ,的常数项h(0，χ)满足 [vxdmax-h(0, x)]Q = ^(Φ,, x)-h(0，x)]Q，由此令 χ = a，进行由 s，= VadmaMi(Oia)和 h，(φ,) = h ( Φ q, a)-h (0, a)表示的运算，将 s’和h’ (Φ,)的值存储在所述存储模块中，代替以Ddmax(a)进制展开，对以t-1进制展开后 的所述n，以VadmaM1 (0，a)进制展开，并用h ( Φ q，a) _h (0，a)代替VadmaM1 (0，a)的步骤。
4. 一种幂运算的运算方法，其特征在于 令Fqk为阶数q的有限域Fq的k次扩域，H为Fqk的素数阶数r的乘法子群，Φ q为关于有限域Fq的元素的弗罗贝尼乌斯自同态映射，利用具有CPU和存储模块的电子计算机来运算关于非负整数η的H的元素A的η次幂 的幂运算，所述运算方法包括输入步骤，CPU输入所述非负整数η的值、所述阶数q的值、所述F^k的素数阶数r的值、 由AEHcFqk表示的元素A的值，并存储在所述存储模块中；初始化步骤，CPU对存储运算结果Z的所述存储模块进行初始化； 第一运算步骤，CPU从所述存储模块读出所述阶数q、所述元素A的值，令所述q与r的 差为s = q_r，从j = 0到j <「lo&s」重复进行由T[j] 一 A和A — A*A表示的代入运算， 将所述T[j]和所述A的值存储在所述存储模块中；展开步骤，CPU从所述存储模块读出所述η和差s的值，根据以差s展开的下式 [式 42]
5.如权利要求4所述的幂运算的运算方法，其特征在于 设X" {Y}表示Xy,在使用整数变量χ分别由q(>c)、r(>c)、S(>c)给出所述阶数q、所述素数阶数r、所述 s时，包括辅助输入步骤，CPU输入所述q(>c)、r(>c)、S(>c)各值，存储在所述存储模块中； 辅助展开步骤，CPU从所述存储模块读出Hx)和S(X)，用所述S(X)根据将r (X) 以S(X)进制展开的下式 [式 44]
6.如权利要求5所述的幂运算的运算方法，其特征在于当所述系数Di (χ)中存在多个为最高次数dmax的系数Di (χ)时， 所述辅助存储步骤还包括，CPU输入满足r (χ) |m(X)的m(X)的值，并存储在所述存 储模块中的步骤， 并具有第二辅助确定步骤，CPU令作为degQJx))的最高次数dmax项的Xdmax的系数为 Tdfflax (q)，从所述存储模块读出系数Di (X)，在所述存储模块中对T (q，x)和U(q，x )的分 配初始值“0”，从i = 0到i <「degr (χ)/degs ( χ )」重复进行代入运算，该代入运算中， ^deg(Di(x)) =dmax时，进行由T(q，χ) —T(q，x )+Di ( χ ) Qi表示的代入运算，其他情 况下，进行由U(q，x) -U(q, x )+Di (X)Cii表示的代入运算，将T (q，x)和U(q，x )的值 存储在所述存储模块中，确定最高次数系数Tdmax (q)；第三辅助确定步骤，CPU从所述存储模块读出m(X)和R(X)的值，用满足r(x) |m(x)的最小次数的多项式m(X)，进行由ff(q) — gcd (Tdfflax (q), m(q))和 V(q) — W(q)表示的运算，确定满足V(q) Im(q), gcd(Tdmax(Q), V(q)) = 1 的V (q)，将所述V (q)的值存储在所述存储模块中；第四辅助确定步骤，CPU从所述存储模块读出V(q)和m(q)的值，利用扩展欧几里得互 除法确定满足g (q) V (q) = ν (mod m(q))的整数标量ν和g (q)，将所述标量ν和g (q)的值存储在所述存储模块中； 第五辅助确定步骤，替代所述辅助确定步骤，CPU从所述存储模块读出Tdfflax (q)、X dma\ Di ( X )、Q 各值，利用满足 A" (Tdfflax (q) χ dmax} =Α"{ Σ Di ( χ ) Qi-Tdmax (q) χ dmax) =A"{fq, x)}的多项式f(q，x)和所述g(q)，根据Φ,ΥΑ) =A确定满足 Α" {ν X dmax} = A"{g(q)f(q, x)} = A"{h(q, x)}的多项式h(q，X)，将所述多项式h(q，x)的值存储在所述存储模块中；和 CPU从所述存储模块读出所述h(q，x)的值， 使该h(q，X)的关于q的常数项h(0，X)满足 A"{vxdmax-h (0, x)} = A"{h(q, x)-h (0, x)},令 x = a，进行由 s’ = vadmax-h(0, a)和 h’ (q) = h(q，a)_h(0，a)表示的运算，将 s’ 和h’ (q)的值存储在所述存储模块中，代替以Ddmax (a)进制展开，对以s进行展开后的所述 η 以 VadmaMi (0，a)进制展开，并用 h(q，a)-h(0, a)代替 vadmax-h (0，a)的步骤。
7. —种记录有标量乘法的运算程序的能够由电子计算机读取的记录介质，其特征在于所述标量乘法的运算程序用于，由具有CPU和存储模块的电子计算机来运算关于非负 整数η的G的有理点Q的标量η乘法，其中，设椭圆曲线为 E/F, = x3+ax+b-y2 = 0，其中 a G Fq，b e Fq 令，E(Fq)为由有限域Fq定义的椭圆曲线的有理点构成的加法群；E(F^k)为由有限域Fq的扩域F^k定义的椭圆曲线的有理点构成的加法群；Φ q为关于有限域Fq的有理点的弗罗贝尼乌斯自同态映射；t为弗罗贝尼乌斯自同态映射的迹；r为整除E(Fq)的阶数#E(Fq) = q+1-t的素数阶数；E[r]为阶数为素数r的有理点集合；[j]为j倍的有理点的映射；G为包含于满足G = E[r] η ΚθΓ(ΦΓ[α])的E (Fqk)中的有理点集合，并在电子计算机中执行输入步骤，输入所述非负整数η的值、所述迹t的值、和由QEGc=E(Fqk)表示的有理 点Q的值，并存储在所述存储模块中；初始化步骤，将存储运算结果Z的所述存储模块初始化； 展开步骤，对于G的有理点Q， Φ q(Q) = [q]Q = [t_l]Q 成立，由此 令s = t-Ι，根据将所述η以s进制展开的下式， [式 45]
8.如权利要求7所述的能够由电子计算机读取的记录介质，其特征在于 在利用整数变量χ分别由q(>c)、r(>c)、t(>c)给出所述椭圆曲线的有限域Fq的阶数 q、整除#E(Fq)的素数阶数r、弗罗贝尼乌斯自同态映射Φ q的迹t时，在电子计算机中执行 辅助输入步骤，输入所述q(x)、r(X)、t(X)各值，存储在所述存储模块中； 辅助展开步骤，从所述存储模块读出r ( χ )和t ( χ )的值，令所述s ( χ ) = t ( χ ) -1，根 据将r(x)以S(X)进制展开的下式 [式 47]
9.如权利要求8所述的能够由电子计算机读取的记录介质，其特征在于 当所述系数Di (χ)中存在多个为最高次数dmax的系数Di (χ)时，所述辅助输入步骤还包括，输入满足r (χ) |m(X)的m(X)的值，并存储在所述存储模 块中的步骤，在电子计算机中执行第二辅助确定步骤，令作为degQi (χ))的最高次数dmax项的Xdmax的系数为 U Φ)，从所述存储模块读出系数Di (χ)，在所述存储模块中对Τ(Φ,，χ)和υ(Φ,，χ) 分配初始值“0”，从i = 0到i <「degr(>c)/degS(>c)」重复进行如下代入运算，该代入运 算中，当deg^Jx)) = dmax时，进行由Τ(Φ,，χ)x )+Di ( χ ) Φ /表示的代入运算，其他情况下，进行由υ(Φ,，χ)x)+DiX) Φ 表示的代入运算，将Τ(Φ,，χ)和υ(Φ,，χ)的值存储在存储模块中，确定最高次数系数Tdmax(CK)；第三辅助确定步骤，从所述存储模块读出m((X)和R(x)的值，用满足r(x) |m(X) 的最小次数的多项式m( χ )，进行由W(Cj5q) —gccKUc^)，πΚΦ))和ν(Φ,) -ΚΦ,) 表示的代入运算，确定满足ν(Φ,) ImQ^gccKUc^)，V(Cj5q)) = 1 的V ( Φ ，将所述V ( Φ 的值存储在存储模块中；第四辅助确定步骤，CPU从所述存储模块读出V( Φ 和m(c^)的值，利用扩展欧几里 得互除法确定满足Ε(Φ )ν(Φ )三 ν (mod m(c^))的整数标量ν和g ( Φ 的值，将所述标量ν和g ( Φ 存储在所述存储模块中； 第五辅助确定步骤，替代所述辅助确定步骤，CPU从所述存储模块读出Tdmax(CK)、 χ dmaxJi (χ)、Q 各值，使用满足[Tdmax(Cttl) XdmaxJQ=E Φ ([ (χ)]0)-[Τ(1ω3Χ(Φ(1) xdmax]Q =[ΜΦ,，x)]Q的多项式ΜΦ,，x)和所述β(Φ )，根据= 9确定满足 [VXdmaxJQ= [g(c^)f(cK，x)]Q= ^(Φ,, x)]Q的多项式h(c^，\)，将所述多项式11((^，χ)的值存储在所述存储模块中；和 从所述存储模块读出所述h(c^，X)的值， 使该h(c^，χ)的关于Φ,的常数项h(0，χ)满足 [vxdmax-h(0, x)]Q = ^(Φ,, x)-h(0，X)]Q，由此令 χ = a，进行由 s，= VadmaMi(Oia)和 h，(φ,) = h ( Φ q, a)-h (0, a)表示的运算，将 s’和h’ (Φ,)的值存储在所述存储模块中，代替以Ddmax(a)进制展开，对以t-1进制展开后 的所述n，以VadmaM1 (0，a)进制展开，并用h ( Φ q，a) _h (0，a)代替VadmaM1 (0，a)的步骤。
10.一种记录有幂运算的运算程序的能够由电子计算机读取的记录介质，其特征在于所述幂运算的运算程序用于，由具有CPU和存储模块的电子计算机来运算关于非负整 数η的H的元素A的η次幂，其中， 令Fqk为阶数q的有限域Fq的k次扩域； H为Fqk的素数阶数r的乘法子群； Φ q为关于有限域Fq的元素的弗罗贝尼乌斯自同态映射， 并在电子计算机中执行输入步骤，输入所述非负整数η的值、所述阶数q的值、所述F^k的素数阶数r的值、由 AeHcFqk表示的元素A的值，并存储在所述存储模块中；初始化步骤，对存储运算结果Z的所述存储模块进行初始化； 第一运算步骤，从所述存储模块读出所述阶数q、所述元素A的值，令所述q与r的差为 s = q_r，从j = 0到j <「lo&s」重复进行由T[j] 一 A和A — A*A表示的代入运算，将所 述T[j]和所述A的值存储在所述存储模块中；展开步骤，从所述存储模块读出所述η和差s的值，根据以差s展开的下式 [式 48]
11.如权利要求10所述的能够由电子计算机读取的记录介质，其特征在于 设X" {Y}表示Xy,在使用整数变量χ分别由q(>c)、r(>c)、S(>c)给出所述阶数q、所述素数阶数r、所述 S时，在电子计算机中执行辅助输入步骤，输入所述q(x)、r(X)、S(X)各值，存储在所述存储模块中； 辅助展开步骤，从所述存储模块读出r (χ)和s(x)，用所述S(X)根据将r(x)以 s(x)进制展开的下式 [式 50]
12.如权利要求11所述的能够由电子计算机读取的记录介质，其特征在于 当所述系数Di (χ)中存在多个为最高次数dmax的系数Di (χ)时， 所述辅助存储步骤还包括，输入满足r (χ) |m(X)的m(X)的值，并存储在所述存储模 块中的步骤，在电子计算机中执行第二辅助确定步骤，令作为deg(Di (X))的最高次数dmax项的x ^=1的系数为Tdmax(q)， 从所述存储模块读出系数Di(X),在所述存储模块中对T(q，x)和U(q，x)的分配初 始值“0”，从i = 0到i <「degr(>c)/degS(>c)」重复进行代入运算，该代入运算中，当 deg^Jx)) =dmaX时，进行由T(q，x)—T(q，x )+Di ( χ ) Qi表示的代入运算，其他情况 下，进行由U(q，x) -U(q, x )+Di (X)Cii表示的代入运算，将T (q，x)和U(q，x )的值存 储在所述存储模块中，确定最高次数系数Tdmax (q)；第三辅助确定步骤，从所述存储模块读出m(X)和R(X)的值，用满足r(x) |m(X)的 最小次数的多项式m(X)，进行由W(q) -gcd (Tdfflax (q),m(q))和V(q) —W(q)表示的运算， 确定满足V(q) |m(q), gcd(Tdmax(Q), V(q)) = 1 的V (q)，将所述V (q)的值存储在所述存储模块中；第四辅助确定步骤，从所述存储模块读出V(q)和m(q)的值，利用扩展欧几里得互除法 确定满足g (q) V (q) = ν (mod m(q))的整数标量ν和g (q)，将所述标量ν和g (q)的值存储在所述存储模块中； 第五辅助确定步骤，替代所述辅助确定步骤，从所述存储模块读出Tdmax(q)、xdma\ Di(X)、Q各值，利用满足A" ITdmax (q) X dmaxI = Α" { Σ Di ( X ) Qi-Tdmax (q) x dmax) =A"{f(q, x)}的多项式f(q，x)和所述g(q)，根据Φ,ΥΑ) =A确定满足 Α" {ν X dmax} = A"{g(q)f(q, x)} = A"{h(q, x)}的多项式h(q，X)，将所述多项式h(q，x)的值存储在所述存储模块中；和 CPU从所述存储模块读出所述h(q，x)的值， 使该h(q，X)的关于q的常数项h(0，X)满足A"{vxdmax-h(0, χ)} = A"{h(q, x)-h(0, χ)},令 x = a，进行由 s’ = vadmax-h(0, a)和 h’ (q) = h(q，a)_h(0，a)表示的运算，将 s’ 和h’ (q)的值存储在所述存储模块中，代替以Ddmax (a)进制展开，对以s进行展开后的所述 η 以 VadmaMi (0，a)进制展开，并用 h(q，a)-h(0, a)代替 vadmax-h (0，a)的步骤。
全文摘要
本发明涉及能够快速进行运算的标量乘法或幂运算的运算方法、以及标量乘法或幂运算的程序。在电子计算机中，关于非负整数n的G的有理点Q的标量n乘法的运算方法和运算程序中，φq(Q)＝[q]Q＝[t-1]Q成立，由此对标量n以t-1进制展开，使用有理点的弗罗贝尼乌斯自同态映射φq取代t-1。另外，在电子计算机中，关于非负整数n的H的元素A的n次幂的幂运算方法和运算程序中，令q和r的差为s＝q-r，则对于H的非零元素A，φq(A)＝Aq＝As成立，由此对指数n以s进制展开，使用关于元素的弗罗贝尼乌斯自同态映射φq取代s。
文档编号G09C1/00GK101965602SQ20098010637
公开日2011年2月2日 申请日期2009年2月25日 优先权日2008年2月25日
发明者加藤英洋, 森川良孝, 赤根正刚, 野上保之 申请人:国立大学法人冈山大学
技术领域：
本发明涉及一种标量乘法的运算方法和记录有其运算程序的记录介质，通过将有 理点Q的标量η乘法的η基于t-Ι进制展开来提高标量乘法的运算速度，并涉及一种幂运 算的运算方法和记录有其运算程序的记录介质，通过对A的η次幂的η基于q-r进制展开 来提高幂运算的运算速度。
背景技术：
目前，利用因特网等电气通信线路的信息网络技术高度发展，不仅能利用网络取 得各种各样的信息，而且还能够提供如网络银行或向行政机关提交电子申请等各种服务。在使用上述服务时，需要进行认证处理，以确认服务的用户并不是冒充或虚构的， 而是恰当的用户，作为高可靠性的认证方法，多采用如下电子认证技术，即基于使用公钥和 私钥的公钥加密的电子认证技术。然而，在公钥加密方式的电子认证中，当公钥或私钥泄露时，需要立即变更公钥和 私钥，必须谨慎保管公钥和私钥，并且根据需要还需进行新公钥和私钥设定登记操作，使用 复杂，因此，如用户的名字或邮件地址那样，最近多使用以用户特有ID进行电子认证的基 于ID加密。另外，利用进行电子认证的认证装置对用户进行个人认证时，在认证装置中保存 了每个用户的简历，该简历信息本身为用户的个人信息，最近被指出存在会因该简历信息 泄露导致个人信息泄露的问题。因而，提出如下所述的群签名技术，S卩，在认证装置中，不是使用用户的个人信息 来进行认证，而是以多个用户为整体的群，通过使用表示属于该群的信息的群签名，不特别 指定用户而进行认证，由此，在认证装置中不保存个人信息并能够进行认证。在上述基于ID加密和群签名中所使用的运算，采用被称为配对的方法，其利用椭 圆曲线上的有理点的双线性对映射。所谓配对，其运算为，例如以P为素域Fq上的有理点， WQSk扩域F^k上的有理点输入P和Q，输出扩域F+qk的元素z，此时，若输入a倍的P和
b倍的Q，则输出ζ的ab次幂。而且，在此“k”称为嵌入次数，对于"F*qk，’，其正确的表示方
式如下式，但因文本限制在行文中记为"FVc ’’。[式1]
ΦP k
Vl在基于ID加密时的加密或解码处理，或群签名时的认证处理中，需要在尽可能短 的时间执行。尤其是在基于配对的加密方式等中，执行很多标量乘法和幂运算，因而期望能 够高速执行上述运算。
为此，以往使用二进制法或窗口法提高标量乘法和幂运算的速度。另外，在运算扩域的元素AeFqk的幂An时，通过使用弗罗贝尼乌斯映射φ : A-Atl消减运算次数提高运算速度。另外，提出了在标量乘法中也利用映射消减运算次数提高运算速度的方案(例如 参照专利文献1、专利文献2)。专利文献1 日本专利公开2004-271792号公报专利文献2 日本专利公开2007-41461号公报
发明内容
但是，公知的通过映射提高运算速度的方法，在当标量乘法中的标量η或幂运算 中的指数η远大于阶数q的情况下(n>>q)非常有效，然而，当标量η和指数η不是远大 于有限域Fq的阶数q时，与不使用提高运算速度的方法而直接执行标量乘法和幂运算的情 况相比，并没有显著的效果。尤其是在基于ID的加密中的加密或解码处理，及群签名中的认证处理中，当必须 使用带有标量η的标量乘法或带有指数η幂运算时，多数情况下标量η或指数η不是远大 于有限域Fq的阶数q，即使使用公知的提高运算速度的方法也不能得到很好的效果。本发明人有鉴于上述现状，对即使当标量η或指数η不是远大于有限域Fq阶数q 时，也能够高速地执行标量乘法或幂运算的运算方法展开研究，并得到本发明。本发明的标量乘法的运算方法中，设椭圆曲线为E/F, = x3+ax+b-y2 = 0，其中 a e Fq，b e Fq令，E(Fq)为由有限域Fq定义的椭圆曲线的有理点构成的加法群；E(F^k)为由有限域Fq的扩域F^k定义的椭圆曲线的有理点构成的加法群；为关于有限域Fq的有理点的弗罗贝尼乌斯自同态映射；t为弗罗贝尼乌斯自同态映射的迹；r为整除E (Fq)的阶数#E (Fq) = q+1-t的素数阶数；E[r]为阶数为素数r的有理点集合；[j]为j倍的有理点的映射；G为包含于满足G = E[r] Π Ker(Φq-[q])
的E (Fqk)中的有理点集合，利用具有CPU和存储模块的电子计算机来运算关于非负整数η的G的有理点Q的 标量η乘法，本发明的标量乘法的运算方法包括输入步骤，CPU输入所述非负整数η的值、所述迹t的值、和由QGGcE(Fqk)表示 的有理点Q的值，并存储在所述存储模块中；初始化步骤，CPU将存储运算结果Z的所述存储模块初始化；展开步骤，对于G的有理点Q，
Φ,(Q) = [q]Q = [t_l]Q 成立，由此 CPU设s = t-1，根据将所述η以s进制展开的下式，[式2]N = ^cMsi, 0 < c[i] < S从i = 0开始重复进行规定次数的由C[i] — s和η — (n-c[i])/s表示的代 入运算，将各系数c [i]和非负整数η的值存储在所述存储模块中；运算步骤，CPU从所述存储模块读出所述有理点Q和所述系数c [i]，从i = 0开始 重复进行规定次数的由Q[i] =c[i]Q表示的运算，将各Q[i]的值存储在所述存储模块中； 禾口合成步骤，CPU替代为t-Ι，根据由关于有理点的弗罗贝尼乌斯自同态映射表 示下式的标量乘法nQ[式3]nQ =》 ·])
i从所述存储模块读出Q[i]和运算结果Z，从i = 0开始重复规定次数的由 Ζ-Ζ+Φ； (Q[i])表示的代入运算，将标量乘法的运算结果Z存储在存储模块中。进而，在本发明的标量乘法的运算方法中，在利用整数变量X分别由q(>c)、r(>c)、t(>c)给出所述椭圆曲线的有限域Fq的 阶数q、整除#E(Fq)的素数阶数r、弗罗贝尼乌斯自同态映射的迹t时，包括辅助输入步骤，CPU输入所述q(>c)、r(>c)、t(>c)各值，存储在所述存储模块中；辅助展开步骤，CPU从所述存储模块读出Hx)和t(x)的值，令所述s(x)= t(x)_l，根据将r(x)以S(X)进制展开的下式[式4]
fdeg r(%)/degs (%)]
r(x)= Yj DiOOsOOi, 0 < degCDiCx)) < deg(s(x))
i=0从i = o 到 i<[deg r(x)/deg s(x)]重复进行由 Di(X) - r(x) %s(x)和 r(x) — (r(x)-Di(x))/s(x)表示的代入运算，将各系数Di ( χ )和r ( χ )的值记录在所 述存储模块中；辅助抽出步骤，CPU抽出所述被存储的系数03>0中，deg(Di(x))为最大的 Ddfflax(x),存储在所述存储模块中；辅助确定步骤，CPU从所述存储模块读出Ddmax ( χ )、Di ( χ )、Q的值，使用满足Φ/max ([Ddfflax ( χ )]Q) =Σ Φ ([ (χ)]0)-Φ(1<1ω3χ(
0) = ^(Φ,, x)]Q的多项式f ( Φ q，x )，根据Φ qkQ = Q，确定满足[Ddmax(X)JQ = ^(Φ,, x)=x)]Q的多项式h ( Φ ,，χ )，将所述多项式h ( Φ q，X )的值存储在所述存储模块中；和
CPU令χ = a将所述s进制展开替换为由s = Ddfflax (a)构成的Ddfflax (a)进制展开， 替换为Ddmax(a)并使用所述多项式h(c^，a)的步骤。而且，在本发明的标量乘法的运算方法中，
当所述系数Di ( χ )中存在多个为最高次数dmax的系数Di ( χ )时，所述辅助输入步骤还包括，CPU输入满足r(X) Im(X)的m(X)的值，并存储在所 述存储模块中的步骤，并具有第二辅助确定步骤，CPU令deg^J χ ))的最高次数dmax项，即，χ “的系数为 ^ ($(1)，从所述存储模块读出系数01(>0，在所述存储模块中对11((^，χ)和υ(Φ,，χ) 分配初始值“0”，从i = 0到i <「degr(>c)/degS(>c)」为止重复进行代入运算，该代入运 算中，当 deg^Jx)) = dmax 时，表示为 Τ(Φ,，χ) — Τ(Φ,，x )+Di ( χ ) Φ J，其他情况下， 表示为υ(Φ,，χ)χ HDi(X) Φ ，将Τ(Φ,，χ)和υ(Φ,，χ)的值存储在存储模 块中，确定最高次数系数Tdmax(CK)；第三辅助确定步骤，CPU从存储模块读出m(X)和R(X)的值，使用满足 H χ ) Im(X)的最小次数的多项式m(X)，进行由W(Cj5q) 一 gccKTjc^)，m(c^))和 ν(Φ,) -ΚΦ,)表示的代入运算，确定满足ν(Φ,) |πι(Φ(1),δο(1(Τ(1ω3Χ(Φ(1),ν(Φ(1)) =1的V ( Φ ，将所述V ( Φ 的值存储在存储模块中；第四辅助确定步骤，CPU从所述存储模块读出V(Cj5q)和m(c^)的值，利用扩展欧 几里得互除法确定满足δ(φ )ν(φ ) = v(mod !!!(Φ,))的整数标量ν和g( Φ)的值，将所述标量ν和g( Φ)存储在所述存储模块中；第五辅助确定步骤，替代所述辅助确定步骤，CPU从所述存储模块读出Tdmax ( Φ 、 x dmaxJi(X)、Q各值，使用满足[Tdfflax ( Φ q) XdmaxJQ=E Φ ([Ο (χ)]0)-[Τ,ω3Χ(Φ ) XdmaxJQ= [ ΧΦ,，x)]Q的多项式f (Φ q，χ )和所述g (Φ ，根据Φ qkQ = Q确定满足[VXdmaxJQ = [g(c^)f(cK，x)]Q = ^(Φ,, x)]Q的多项式h ( Φ ,，χ )，将所述多项式h ( Φ q，X )的值存储在所述存储模块中；和CPU从所述存储模块读出所述h ( Φ q，X )的值，使该h ( Φ q，X )的关于Φ q的常数项h (0，X )满足[vx^-h (0, x)]Q = [h((^，x)-h (0, x)]Q，由此令χ = a，进行由 s，= vadmax-h (0，a)和 h，( Φ = h ( Φ q，a) _h (0，a)表示的运 算，将s’和h’ (Φ,)的值存储在所述存储模块中，代替以D-Ja)进制展开，对t-1进制展开后的所述n，以VadmaM1(OA)进制展开， 并用 h ( Φ q，a) -h (0，a)代替 vadmax-h (0，a)的步骤。另外，在本发明的幂运算的运算方法中，令Fqk为阶数q的有限域Fq的k次扩域，H为F^k的素数阶数r的乘法子群，Φ q为关于有限域Fq的元素的弗罗贝尼乌斯自同态映射，
利用具有CPU和存储模块的电子计算机运算关于非负整数η的H的元素A的η次 幂的幂运算，本发明的幂运算的运算方法包括 输入步骤，CPU输入所述非负整数η的值、所述阶数q的值、所述F^k的素数阶数r 的值、由AeHcFqk表示的元素A的值，并存储在所述存储模块中；初始化步骤，CPU对存储运算结果Z的所述存储模块进行初始化；第一运算步骤，CPU从所述存储模块读出所述阶数q、所述元素A的值，令所述q与 r的差为s = q-r，从j = 0到j <「lo&s」重复由T[j] 一 A和A — A*A表示的代入运算， 将所述T[j]和所述A的值存储在所述存储模块中；展开步骤，CPU从所述存储模块读出所述η和差s的值，根据由差s展开的下式[式5]n = ^c[i]si, ο < c[i] < s
i从i = 0开始重复规定次数的由c[i] — s和η — (n-c[i])/s表示的代入运 算，将各系数c [i]和非负整数η的值存储在存储模块中；第二运算步骤，CPU从存储模块读出c[i]和所述η的值，根据A[i] = Ac[i], 初始化A[i] = 1，在c[i]&l时，从i = 0开始重复规定次数的由A[i] — A[i]*T[j]和 c[i] — c[iV2表示的代入运算，将A[i]和c[i]的值存储在存储模块中；和合成步骤，CPU从存储模块读出各A[i]，根据下式[式6]An=P] φ (A[i])从i = 0开始重复规定次数的由Ζ —Ζ* Φ ^(Ati])表示的幂运算，将计算的结果 Z存储在存储模块中。进而，本发明的幂运算的运算方法中，设Χ~{Υ}表示 χγ，在用整数变量X分别由q(X)、r(>c)、S(>c)给出所述阶数q、所述素数阶数r、所 述s时，包括辅助输入步骤，CPU输入所述q(>c)、r(>c)、S(>c)各值，存储在所述存储模块中；辅助展开步骤，CPU从所述存储模块读出r(X)和s(x)，用所述S(X)根据将 r(x)以s(x)进制展开的下式[式7]
r(x)= Yi DiOOsOrf, 0<deg(Di(x))<deg(s(x))
i=0从 i = 0 至Ij i <「degr(x)/degs(x)」重复由 Di(X) —r(x) %s(x)禾口 r(x) — (r(x)-Di(x))/s(x)表示的代入运算，将所述系数Di ( χ )和r ( χ )存储在所述存储模块中； 辅助抽出步骤，CPU抽出被存储的系数Di (X) ^,deg(Di(x))为最大的Ddfflax ( χ )， 存储在所述存储模块中；辅助确定步骤，CPU从所述存储模块读出所述Ddmax ( X )、Di ( X )、q的值，使用满足(A"{Ddfflax(x)})"{qdfflax} =Α"{ Σ ^dmax-Di(X)qiI =A"{f(q, x)}的多项式f(q，X)，根据C^k(A) =A，确定满足A" (Ddfflax (x)} =Α"{ Σ ^ ^ax-Di ( χ ) Qi-QdmaxI =A"{h(q, χ)}的多项式h(q，X)，将所述多项式h(q，x)的值存储在所述存储模块中；和CPU令χ = a将所述s进制展开的所述η替换为由s = Ddmax(a)构成的Ddmax(a) 进制展开，用所述多项式h(q，a)替换D-Ja)的步骤。而且，在本发明的幂运算的运算方法中，当所述系数Di(X)中存在多个为最高次数dmax的系数Di (X)时，所述辅助存储步骤还包括，CPU输入满足r(x) Im(X)的m(x)的值，存储在所述 存储模块中的步骤，并具有第二辅助确定步骤，CPU令deg (Di (X))的最高次数dmax的项，即x dmax的系数为 Tdfflax (q)，从所述存储模块读出系数Di (X)，在所述存储模块中对T (q，x)和U(q，x )的分 配初始值“0”，从i = 0到i <「degr(>c)/degS(>c)」重复进行代入运算，该代入运算中， 当 deg^Jx)) = dmax 时，表示为 T (q，x) — T(q，x )+Di ( x ) q、其他情况下，表示为 U (q， x) —U(q，XHDi(X)qS将T(q，x)和U(q，x)的值存储在所述存储模块中，确定最高次 数系数Tdmax (q)；第三辅助确定步骤，CPU从所述存储模块读出m(X)和R(X)的值，使用满 足r(X)lm(X)的最小次数的多项式m(X)，进行由W(q) - gcd (Tdfflax (q), m(q))和 V(q) — W(q)表示的运算，确定满足 V (q) I m (q)，gcd (Tdmax (q)，V (q)) =1的V(q)，将所述V(q)的值存储在所述存储模块中；第四辅助确定步骤，CPU从所述存储模块读出V(q)和m(q)的值，利用扩展欧几里 得互除法确定满足g(q)V(q) = ν (mod m(q))的整数标量ν和g(q)，将所述标量ν和g(q)的值存储在所述存储模块中；第五辅助确定步骤，替代所述辅助确定步骤，CPU从所述存储模块读出Tdmax(q)、 X dmax^ Di ( χ )、Q 各值，利用满足 A" ITdmax (q) χ dmaxI = Α"{ Σ Di(X) Qi-Tdmax (q) χ “)= A"{f(q, x)}的多项式f(q，x)和所述g(q)，根据(^k(A) =A，确定满足Α" {ν χ dmaxI = A"{g(q)f(q, x)} = A"{h(q, x)}的多项式h(q，X )，将所述多项式h(q，X )的值存储在所述存储模块中；和CPU从所述存储模块读出所述h(q，X)的值，使该h(q，X)的关于q的常数项h(0，x)满足A'lvx^-h (0, x)} = A"{h(q, x)_h(0，x)}，
令χ = a，进行由 s’ = vadmax-h(0, a)和 h，(q) = h(q，a)_h(0，a)表示的运算， 将S’和h’ (q)的值存储在所述存储模块中，代替以Ddmax(a)进制展开，对以s进行展开后 的所述η以vadmax_h (0，a)进制展开，并用h (q, a) _h (0，a)代替VadmaM1 (0，a)的步骤。另外，本发明的记录有标量乘法的运算程序且能够被电子计算机读取的记录介质 中，记录有如下所述标量乘法的运算程序，设椭圆曲线为E/F, = x3+ax+b-y2 = 0，其中 a G Fq，b e Fq
令，E(Fq)为由有限域Fq定义的椭圆曲线的有理点构成的加法群；E(F^k)为由有限域Fq的扩域F^k定义的椭圆曲线的有理点构成的加法群；为关于有限域Fq的有理点的弗罗贝尼乌斯自同态映射；t为弗罗贝尼乌斯自同态映射的迹；r为整除E (Fq)的阶数#E (Fq) = q+1-t的素数阶数；EM为阶数为素数r的有理点集合；[j]为j倍的有理点的映射；G为包含于满足G = E[r] Π Ker(<j5r[q])的E(F^k)中的有理点集合，利用具有CPU和存储模块的电子计算机执行关于非负整数η的G的有理点Q的标 量η乘法，该运算程序在电子计算机中执行输入步骤，输入所述非负整数η的值、所述迹t的值、和由Q EGc=E(Fqk)表示的有 理点Q的值，并存储在所述存储模块中；初始化步骤，将存储运算结果Z的所述存储模块初始化；展开步骤，令对于G的有理点Q，(^(Q) = [q]Q = [t_l]Q 成立，由此设s = t-Ι，根据将所述η以s进制展开的下式，[式8]N = ^ Cplsi, 0 < C[l] < S从i =0开始重复进行规定次数的由C[i] — 和η — (n_C[i])/s表示的代 入运算，将各系数c [i]和非负整数η的值存储在所述存储模块中；运算步骤，从所述存储模块读出所述有理点Q，非负整数η和所述系数c[i]，从i =0开始重复规定次数的由Q[i] = c[i]Q表示的运算，将各Q[i]的值存储在所述存储模 块中；和合成步骤，替代为t-Ι，根据由关于有理点的弗罗贝尼乌斯自同态映射表示下 式的标量乘法nQ[式9]
从所述存储模块读出Q[i]和运算结果Z，从i = 0开始重复规定次数的由 Ζ-Ζ+Φ； (Q[i])表示的代入运算，将标量乘法的运算结果Z存储在存储模块中。进而，在本发明的记录有标量乘法的运算程序且能够被电子计算机读取的记录介 质中，在分别由整数变量X由q(>c)、r(>c)、t(>c)给出所述椭圆曲线的有限域Fq的阶 数q、整除#E(Fq)的素数阶数r、弗罗贝尼乌斯自同态映射Φ q的迹t时，由电子计算机执行 如下步骤辅助输入步骤，输入所述9(乂)、1~(>0 3(>0各值，存储在所述存储模块中；辅助展开步骤，从所述存储模块读出r(x )和t(x)的值，令所述S(X)= t(x)_l，根据将r(x)以S(X)进制展开的下式[式10]
τω= Yj Di(X)SOOi, 0 < deg(Di(x)) < deg(s(x)) i=0从i = 0 到 i<[deg r(%)/deg重复进行由 Di(X) - r(x) % s(x)和 r(x) — (r(x)-Di(x))/s(x)表示的代入运算，将各系数Di ( χ )和r ( χ )的值记录在所 述存储模块中；辅助抽出步骤，抽出所述被存储的系数Di(X)中，degQJx))为最大的 Ddfflax(x),存储在所述存储模块中； 辅助确定步骤，从所述存储模块读出Ddfflax ( χ )、Di ( χ )、Q的值，使用满足Φ/"χ(
0) =Σ Φ ([ (χ)]0)-Φ(1<1ω3χ(
0) = ^(Φ,, x)]Q的多项式f ( Φ q，X )，根据Φ qkQ = Q，确定满足[Ddmax(X)JQ = ^(Φ,, χ)=X)]Q的多项式!!(Φ,，乂)，将所述多项式11((^，x)的值存储在所述存储模块中；和令χ = a将所述s进制展开替换为由s = Ddmax(a)构成的D-Ja)进制展开，替 换为Ddmax(a)并使用所述多项式h(c^，a)的步骤。而且，本发明的记录有标量乘法的运算程序且能够被电子计算机读取的记录介质 中，当所述系数Di (X)中存在多个为最高次数dmax的系数Di (X)时，所述辅助输入步骤还包括，输入满足r(X) Im(X)的m(X)的值，存储在所述存储 模块中的步骤，并由所述电子计算机执行如下步骤第二辅助确定步骤，令degQJx))的最高次数dmax项，即x “的系数为 ^ ($(1)，从所述存储模块读出系数01(>0，在所述存储模块中对11((^，χ)和υ(Φ,，χ) 分配初始值“0”，从i = 0到i <「degr ( χ ) /degs ( χ )」重复进行代入运算，该代入运算中，当deg^Jx)) =dmax时，表示为Τ(Φ,，χ)x )+Di ( χ ) Φ J，其他情况下，表示为
υ(Φ,，χ) — υ(Φ,，XHDi(X) Φ/，将Τ(Φ,，χ)禾口 υ(Φ,，χ)的值存储在存储模块中，确 定最高次数系数Tdmax(Cttl)；第三辅助确定步骤，从存储模块读出m(X)和R(X)的值，使用满足r(x) Im(X) 的最小次数的多项式m( χ )，进行由W(Cj5q) —gccKUc^)，m(c^))和ν(Φ,) -ΚΦ,) 表示的代入运算，确定满足ν(Φ5) |m(c^)，gCd(Tdmax((^)，V((^)) =1
的V ( Φ ，将所述V ( Φ 的值存储在存储模块中；第四辅助确定步骤，从所述存储模块读出ν(Φ,)和m(c^)的值，利用扩展欧几里 得互除法确定满足δ(φ )ν(φ ) = v(mod !!!(Φ,))的整数标量ν和g( Φ)的值，将所述标量ν和g( Φ)存储在所述存储模块中；第五辅助确定步骤，替代所述辅助确定步骤，从所述存储模块读出Tdmax(CK)、 X dmaxJi(X)、Q各值，使用满足[Tdfflax ( Φ q) XdmaxJQ=E Φ ([Ο (χ)]0)-[Τ,ω3Χ(Φ ) XdmaxJQ= [ ΧΦ,，x)]Q的多项式 ΧΦ,，x)和所述g(c^)，根据^KkQ = Q确定满足[VXdmaxQ= [δ(Φ )Γ(Φ(1, x)]Q = ^(Φ,, x)]Q的多项式!!(Φ,，乂)，将所述多项式11((^，x)的值存储在所述存储模块中；和从所述存储模块读出所述!!(Φ,，x)的值，使该!!(Φ,，x)的关于Φ,的常数项h(0，x)满足[vx^-h (0, x)]Q = ^(Φ,, x)-h (0, x)]Q，令χ = a，进行由 s，= vadmax-h(0, a)和 h，( Φ = h ( Φ q，a)-h (0, a)表示的运 算，将s’和h’ (Φ,)的值存储在所述存储模块中，代替以D-Ja)进制展开，对t-1进制展开的所述n，以VadmaM1(OA)进制展开，并 用 h ( Φ q，a) -h (0，a)代替 vadmax-h (0，a)的步骤。另外，本发明的记录有幂运算的运算程序且能够被电子计算机读取的记录介质 中，如下所述幂乘法的运算程序，令，Fqk为阶数q的有限域Fq的k次扩域，H为F^k的素数阶数r的乘法子群，φ q为关于有限域Fq的元素的弗罗贝尼乌斯自同态映射，利用具有CPU和存储模块的电子计算机运算对于非负整数η的H的元素A的η次 幂的幂运算，该运算程序在电子计算机中执行输入步骤，输入所述非负整数η的值、所述阶数q的值、所述F^k的素数阶数r的 值、由AEHcFqk表示的元素A的值，并存储在所述存储模块中；初始化步骤，对存储运算结果Z的所述存储模块进行初始化；第一运算步骤，从所述存储模块读出所述阶数q、所述元素A的值，令所述q与r的 差为s = q_r，从j = 0到j <「lo&s」重复由T[j] 一 A和A — A*A表示的代入运算，将所述T[j]和所述A的值存储在所述存储模块中；展开步骤，从所述存储模块读出所述η和差s的值，根据由差s展开的下式[式11] i从i =0开始重复规定次数的由c[i] — 和η — (n_c[i])/s表示的代入运 算，将各系数c [i]和非负整数η的值存储在存储模块中；第二运算步骤，从存储模块读出c[i]和所述η的值，根据A[i] = f[i]，初始化A[i] =1，在c[i]&l时，从i = 0开始重复规定次数的由A[i] —A[i]*T[j]和c[i] — c[i]/2 表示的代入运算，将A [i]和c[i]的值存储在存储模块中；和合成步骤，CPU从存储模块读出各A[i]，根据下式[式12]Α^ΡΙΦ^ΑΜ)从i = 0开始重复规定次数的由Ζ —Ζ* Φ ^(Ati])表示的幂运算，将计算的结果 Z存储在存储模块中。进而，本发明的记录有幂运算的运算程序的记录介质中，设Χ~{Υ}表示 ΧΥ，在用整数变量X分别由q(>c)、r(>c)、S(>c)给出所述阶数q、所述素数阶数r、所 述s时，由电子计算机中执行如下步骤辅助输入步骤，输入所述9(>0、1~(>0、8(>0各值，存储在所述存储模块中；辅助展开步骤，从所述存储模块读出r ( X )和s ( X )，用所述s ( X )根据将Hx) 以S(X)进制展开的下式[式13]
fdeg r(x)/deg s(%)l
r(x) = Yj DiOOsOOi, 0 < Cleg(DiOO) < deg (s(x)) i=0从i = 0 至Ij i <「degr ( χ ) /degs (x)」重复由 Di(X)^r(X) %s(x)禾口 r(x) — (r(x)-Di(x))/s(x)表示的代入运算，将所述系数Di ( χ )和r ( χ )存储在所述 存储模块中；辅助抽出步骤，抽出被存储的系数Di(X)中，deg(Di(x))为最大的Ddmax ( χ )，存 储在所述存储模块中；辅助确定步骤，从所述存储模块读出所述Ddfflax ( X )、Di ( X )、q的值，使用满足(A" (Ddfflax (X)})" {qdmax} = Α" { Σ ^ ^ax-Di ( x ) q1} =A" {f (q, x)}的多项式f(q，X)，根据C^k(A) =A，确定满足A" (Ddfflax (x)} =A"{ Σ ^ ^ax-Di ( x ) Qi-QdmaxI = A" {h (q, x)}的多项式h (q，Χ )，将所述多项式h (q，X )的值存储在所述存储模块中；和
令χ = a将所述s进制展开的所述η替换为由s = Ddmax(a)构成的Ddfflax (a)进制 展开，替换为Ddmax (a)并使用所述多项式h(q，a)的步骤。而且，在本发明的记录有幂运算的运算程序的记录介质中，当所述系数Di ( χ )中存在多个为最高次数dmax的系数Di ( χ )时，所述辅助存储步骤还包括，输入满足r(X) Im(X)的m(X)的值，存储在所述存储 模块中的步骤，在电子计算机中执行如下步骤 第二辅助确定步骤，令degQJx))的最高次数dmax的项，S卩Xdmax的系数为 Tdfflax (q)，从所述存储模块读出系数Di (X)，在所述存储模块中对T (q，x)和U(q，x )的分 配初始值“0”，从i = 0到i <「degr(>c)/degS(>c)」重复进行代入运算，该代入运算中， ^deg(Di(x)) = dmax 时，表示为 T (q，x) — T(q，x )+Di ( x ) q、其他情况下，表示为 U (q， x) —U(q，XHDi(X)qS将T(q，x)和U(q，x)的值存储在所述存储模块中，确定最高次 数系数Tdmax (q)；第三辅助确定步骤，从所述存储模块读出m(x)和R(x)的值，使用满 Mr(X)Im(X)的最小次数的多项式m(X)，进行由W(q) - gcd (Tdfflax (q), m(q))和 V(q) — W(q)表示的运算，确定满足V (q) I m (q)，gcd (Tdmax (q)，V (q)) =1的V (q)，将所述V (q)的值存储在所述存储模块中；第四辅助确定步骤，从所述存储模块读出V(q)和m(q)的值，利用扩展欧几里得互 除法确定满足g(q)V(q) = ν (mod m(q))的整数标量ν和g (q)，将所述标量ν和g (q)的值存储在所述存储模块中；第五辅助确定步骤，替代所述辅助确定步骤，从所述存储模块读出Tdfflax (q)、X dma\ Di(X)、Q各值，利用满足A" (Tdfflax (q) x dmax} = A" { Σ Di(X) Qi-Tdmax (q) x dmax) = A" {f (q, x)}的多项式f(q，x)和所述g(q)，根据(^k(A) =A,确定满足Α" {ν χ dmaxI = A" {g (q) f(q, x)} = A"{h(q, x)}的多项式h (q，Χ )，将所述多项式h (q，X )的值存储在所述存储模块中；和CPU从所述存储模块读出所述h (q，X )的值，使该h (q，X )的关于q的常数项h (0，X )满足Α" {ν X —-h (0，x)} = A" {h (q，x ) _h (0，x )}，令x = a，进行由 s’ = vadmax-h(0, a)和 h，(q) = h(q，a)_h(0，a)表示的运算， 将S’和h’ (q)的值存储在所述存储模块中，代替以Ddmax(a)进制展开，对以s进行展开后 的所述η以vadmax_h (0，a)进制展开，并用h (q, a) _h (0，a)代替VadmaM1 (0，a)的步骤。发明效果本发明利用弗罗贝尼乌斯自同态映射Φ q消减运算次数，尤其是在标量乘法中，对 于G的有理点Q，使= [q]Q = [t-l]Q成立，或者是在幂运算时，令q与r的差为s = q-r,对于H的非零元素A，使
Φ^Α) = Aq = As成立，由此，对标量η以t-1进制展开，或对指数(Χ t数)η以s进制展开，通过替 换为t-Ι并使用有理点的弗罗贝尼乌斯映射，或替换为s并使用元素的弗罗贝尼乌斯自 同态映射Φ q，使得即使在标量乘法中的标量n，或幂运算中的指数η不是远大于阶数q时， 也能够减少运算次数，提高运算速度。尤其是在以配对为基础的基于ID加密或群签名等中使用椭圆曲线作为双线性对 曲线的配对，在使用该双线性对曲线时，使用整数变量X预先给出阶数q(x)、整除#E(Fq) 的素数阶数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)，在标量乘法中，将Hx)以 t ( X ) -1进制展开，并设在该Wt(X)-I进制展开时导入的系数Di ( χ )中最高次数的系数 Di(X) SDdmax(X),将该Ddmax(X)置换为多项式h(c^，χ )，由此进一步消减运算次数，另 夕卜，在幂运算中，将r(x)以S(X) = q(x)-r(x)进制展开，并设在该以s(x)进制展开 时导入的系数Di(X)中最高次数的系数Di(X)为Ddmax(X),将该Ddmax (χ)置换为多项式 h (Φ ,，χ )，由此能够进一步消减运算次数，提高运算速度。而且，当存在多个为最高次数的dmax WDi (X)时，使用满足r ( χ ) |m( χ )的最小 次数的多项式m (χ)，确定满足V (q) I m (q)，gcd (Tdmax (q)，V (q)) =1的V (q)，并使用满足g(q)V(q)三ν (mod m(q))的整数标量V，在标量乘法中，替代以Ddfflax ( x )进制展 开，对以t-Ι进制展开后的标量η以VXdmaM1 (0，X)进制展开，通过用h(q，x)-h(0, χ) 代替vXd X_h(0，χ )，进一步消减运算次数，另外，在幂运算中，代替Ddmax(X)进制展开， 对以s进制展开后的指数η以vxdmax-h(0，X)进制展开，通过用h(q，x)-h(0, x )代替 ν χ dmaMi(C), χ )，进一步消减运算次数，提高运算速度。
图1具有标量乘法的运算程序和幂运算的运算程序的电子计算机。图2是标量乘法的运算程序的流程图。图3是标量乘法的运算程序的流程图。图4是用于求取Ddmax (X)和多项式!!(Φ,，x)的辅助程序的流程图。图5是标量乘法的运算程序的流程图。图6是用于求取!!(Φ,，X )禾Π ν X dmax-h(0, χ )的辅助程序的流程图。图7是幂运算的运算程序的流程图。图8是幂运算的运算程序的流程图。图9是用于求取Ddmax (X)和多项式h(q，x)的辅助程序的流程图。图10是幂运算的运算程序的流程图。图11是用于求取多项式h(q，X )禾Π ν X dmaM1 (0，x )的辅助程序的流程图。符号说明10电子计算机
IlCPU12存储装置
13存储器14 总线15输入输出控制部20电气通信线路30客户端
具体实施例方式本发明的目的是提高标量乘法和幂运算的运算速度，虽然标量乘法和幂运算的运 算本身不同，但使用相同方法提高运算速度，能够消减他们的运算次数，从而能够提高运算 速度。首先对标量乘法进行说明，然后再对幂运算进行说明。首先，设椭圆曲线为E/F, = x3+ax+b-y2 = 0，其中 a G Fq，b e Fq定义E(Fq)由有限域Fq定义的椭圆曲线的有理点构成的加法群；E (Fqk)由有限域Fq的扩域E (Fqk)定义的椭圆曲线的有理点构成的加法群；关于有限域Fq的有理点的弗罗贝尼乌斯自同态映射；t:弗罗贝尼乌斯自同态映射的迹；r 整除E (Fq)的阶数#E (Fq) = q+1-t的素数阶数；EM 阶数为素数r的有理点集合；[j] :j倍的有理点的映射；G 包含于满足G = E[r] Π Ker ( Φ「[q])的E(F^k)中的有理点集合。然后，运算关于非负整数η的G的有理点Q的标量η乘法，即nQ。而且，在本实施 方式中，所设定的标量乘法是在配对运算时进行的，一般标量η不远大于阶数r。另夕卜，由于 r = q+1-t,因此 0 三 q+r-t (mod r)。再次，对标量η以t-1进制展开，则标量η不远大于阶数r，因此为η = Cjt-1)+C。，或η = (t-1)'+C1U-I)+C00由于(^(Q)= [q]Q = [t_l]Q，因此在 η = C1 (t_l)+C。，nQ 时，nQ 如下所示，nQ = [C1U-I)+C0] Q= [Ciq]Q+[C0]Q= cji(1([C1]Q) + [C(1]Q。另夕卜，当n = (t-lV+Qa-D+Co时，nQ如下所示nQ = [ (t-1) '+C1 (t_l) +C0] Q= [q] [q]Q+[Ciq]Q+[C0]Q= (^((^(QD + c^aCjQHECjQ。在此，C1和Ctl与t-1同等或略小，而且能够使用有理点的弗罗贝尼乌斯自同态映 射，由此能够减少运算次数。因而，能够提高标量乘法的运算速度。另外，通常进行配对运算时，多是使用已知的双线性对曲线，预先由整数变量X 给出阶数q(x)、整除#E(Fq)的素数阶数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)。在此，考虑[r]Q= [q+l-t]Q = 0，设用t(x)_l除r(x)而未除尽。即，r(x)表示为
[r ( χ ) Q = Σ [Di(X) U(X)-DiJQ =Σ Φ ； ([Di (( χ ) ]Q),以t(x)_l进制展开，令Di(X)中最高次数者为Ddmax(X)。然后，将定义为Φ/"χ(
0) =Σ Φ (
0)-Φ^χ(
0)= [f(Φ,, x)]Q的以Φ q和x为变量的二元多项式!!(Φ,，X)导入。进而，根据Φ qkQ = Q，将定义为[Ddmax(X)JQ = ^(Φ,, χ) Φ广ax]Q= ^(Φ,, x)]Q的以Φ q和x为变量的二元多项式!!(Φ,，X)导入。即，该多项式!!(Φ,，X)，能 够将Di (χ)中最高次数的Ddmax(x)，替换为以和χ为变量的多项式!!(Φ,，>0，能够抑 制向次数小于最高次数的运算。特别是χ =a时，将以t-Ι进制展开后的标量η进一步以 Ddfflax(a)进制展开，并用h(c^，χ)替换Ddfflax(a)，由此，能够大大减少运算次数，提高标量乘 法的运算速度。另外，当在Di ( χ )中有多个最高次数者时，用dmax表示最高次数，设作为最高次 数dmax项的Xdmax的系数为Tdmax(c^)，使用满足Hx) |m(X)的最小次数的多项式m( χ ) 确定满足ν(Φ5) |m(c^)，gCd(Tdmax((^)，V((^)) =1的ν(Φ,)。在此，多项式m(X)可以使用割圆多项式等。然后，使用扩展欧几里得互除法确定满足δ(φ )ν(φ ) = v(mod !!!(Φ,))的整数标量ν和g ( Φ ，作为[Tdfflax ( Φ q) XdmaxJQ=E Φ ([Ο (χ)]0)-[Τ,ω3Χ(Φ ) XdmaxJQ= [f(c^，x)]Q导入以Φ,和X为变量的二元多项式f( Φ ,，X)。进一步，使用g ( Φ ，并根据Φ qkQ = Q，令[VXdmaxJQ =x) (Γ(Φ,, x)]Q = ^(Φ,, x)]Q，导入以φ^和χ为变量的二元多项式!!(Φ,，X)。然后，使!!(Φ,，x)的关于Φ,的常数项h(0，x)满足[vx^-h (0, x)]Q = ^(Φ,, x)-h (0, x)]Q令χ =a，s，= vadmax h(0，a)，h，(Φ,) = h ( Φ q，a) _h (0，a)，替换以 Ddmax (a)进制 展开，将以t-1进制展开后的标量η以VadmaMi (0，a)进制展开，使用h ( Φ q，a) _h (0，a)替代 va^x-hO)，a)，由此能够减少运算次数，因而能够提高标量乘法的运算速度。在此，h’ (Φ,) 表示，在二元多项式!!(Φ,，χ)中，因令χ =a而成为Φ q这一个变量。以上对标量乘法进行了说明，但在幂运算中，定义Fqk 阶数q的有限域Fq的k次扩域；H :Fqk的素数阶数r的乘法子群；Φ q 关于有限域Fq的元素的弗罗贝尼乌斯自同态映射，进行关于非负整数η的H的元素A的η次方。令q与r的差为s = q~r,该s置换 标量乘法中的t-i，只需将上述说明改为幂运算，省略详细说明。在幂运算中，最高次数部分的运算能够置换为低次数的运算，从而能够减少运算次数，提高幂运算的运算速度。下面，使用已知的双线性对曲线说明具体的例子。作为埋入次数8的双线性对曲线，已知由r(x) = x4-8x2+25，t(x) = (2x3-ll x+15)/15 给出的整除#E(Fq)的素数阶数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)。此时，对r (χ)以t( χ )_1进制展开，利用弗罗贝尼乌斯自同态映射，得到2r(x) = (15 χ ) Φ,+(-5 χ 2+50)，0 = (15 χ) Φ,+ (-5 χ 2+50) (mod r ( χ ))因此，Di(X)成为D0(X) = -5 Χ2+50,D^ χ ) = 15 χ。其中，由于Dtl(X)为最高次数，因此，除Dq (Χ)以外移动到右侧，而得到-5 χ2+50 = 15 Χ Φ,对该式整理得到X2-IO = 3 χ Φ,ο因此，在进行关于非负整数η的G的有理点Q的标量η乘法，或关于非负整数η的 H的元素A的η次幂中，对于非负整数η，将η以t_l进制展开，进而以x 2_10进制展开，用 15 χ 代替x2-10，由此能够利用弗罗贝尼乌斯自同态映射Φ q来运算G的有理点标量η 乘法或H的元素A的η次幂，减少运算次数，提高幂运算的运算速度。作为其他埋入次数8的双线性对曲线，在由r ( χ ) = x8-x 4+1,t ( χ ) = χ 5- χ +1给出整除#E(F(1)的素数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)时，将 r(x)以t( χ )-1进制展开，使用弗罗贝尼乌斯自同态映射，得到r( χ ) = χ0 三 βφ^+ Οιιο Ι r(x))。因此，Di(X)成为D0(X) = -1，D1(X) = x3。其中，由于D1 ( χ )为最高次数，因此，除D1 ( χ ) 以外移动到右侧，得到X3(J)q = -I两边同时乘以得到X3 = -(J)tJ115因此，在进行关于非负整数η的G的有理点Q的标量η乘法，或关于非负整数η的H 的元素A的η次幂中，对于非负整数η，将η以t_l进制展开，进而以x 3进制展开，用_ Φ ；1 代替χ 3，从而能够使用关于有理点的弗罗贝尼乌斯自同态映射来运算G的有理点的标 量η乘法或H的元素A的η次幂，能够减少运算次数提高幂运算的运算速度。另外，在埋入次数10的双线性对曲线中，已知由
r ( χ ) = 25 χ 4+25 χ 3+15 χ 2+5 χ +1，t ( χ ) = 10 χ 2+5 χ +3 给出整除#E(F(1)的素数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)。此时，将r (X)以t( X )_1进制展开，通过使用弗罗贝尼乌斯自同态映射，得到8r(x) = 2 Φ q2- Φ q+ (5 χ +2),0 = 2 Φ q2- Φ q+ (5 χ +2) (mod r(x))因此，Di(X)成为D0( χ ) = 5 χ +2,D^ χ ) = -1，D2(χ) =2。其中Dtl(X)为最高次数，因此，除Dq (Χ)以外移动到右侧，得到5χ+2 = ^Φ^+Φ,ο因此，在进行关于非负整数η的G的有理点Q的标量η乘法，或关于非负整数η 的H的元素A的η次幂中，对于非负整数η，将η以t_l进制展开，进而以5 χ +2进制展开， 用-2 Φ q2+ Φ q代替5 χ +2，由此能够利用弗罗贝尼乌斯自同态映射Φ q来运算G的有理点标 量η乘法或H的元素A的η次幂，减少运算次数，提高幂运算的运算速度。另外，在埋入次数12的双线性对曲线中，已知由r( χ ) = 36 χ 4_36 χ 3+18 χ 2_6 χ +1，t ( χ ) = 6 χ 2+1给出整除#E(F(1)的素数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)。此时，将r(χ)以t( χ )_1进制展开，通过使用弗罗贝尼乌斯自同态映射，得到r(x) = Φq2+ (-6 χ +3) Φq+ (_6 χ +1)，0 = Φ,2+ (-6 χ +3) Φq+ (-6 χ +1) (mod r ( χ ))。因此，Di(X)成为D0( χ ) = -6 χ +1，Di( χ ) = -6 χ +3,D2 ( χ ) = 1。其中D。(x)和01(>0为最高次数，因此，除Dtl(X)和01(>0 (^得到最高次数的 X以外项移动到右侧，得到6 χ (Φ,+1) = φ^+βφ,+ ο在此，若设g(c^) = (^4-(^2+1，则满足8(3(1((^+1，8((^)) = 1，利用扩展欧几里 得互除法得到( φq+l)-1E φ,2 (1-φq) (mod g( Φ)。因此，两边同乘以\2(1-(^)，得到6x = Φ^Ι-Φ^) ((^2+3(^+1)。因此，在进行关于非负整数η的G的有理点Q的标量η乘法，或关于非负整数η 的H的元素A的η次幂中，对于非负整数η，将η以t_l进制展开，进而以6 χ进制展开，用 Φ,2(1-Φ(1)(Φ q2+3 Φ q+l)代替6 χ，由此能够利用弗罗贝尼乌斯自同态映射Φ q来运算G的 有理点标量η乘法或H的元素A的η次幂，减少运算次数，提高幂运算的运算速度。
作为更具体的例子，设X = 825 (10位)。此时，r = 16656811746301 (44 位)t = 4083751(22 位)。此时，由于
6 χ = 4950(13bits) = Φ,2(I"Φ,) (φ,'+βφ,+ )因此，在进行G的有理点的标量η乘法或H的元素A的η次幂时，使用有关有理点 的弗罗贝尼乌斯自同态映射变换为13位左右的标量乘法或幂运算后，进行运算，能够 大幅减少运算次数。另外，在埋入次数18的双线性对曲线中，由r(x) = χ 6+37 χ 3+343，t(x) = (x 4+16 χ+7)/7给出整除#E(F(1)的素数r(x)、弗罗贝尼乌斯自同态映射的迹t(x)。此时，将r(χ)以t( χ )_1进制展开，通过使用弗罗贝尼乌斯自同态映射，得到r(x) = (7 χ2)) Φ,+ (21 x 3+343)0 = (7 χ2) Φ J (21 χ 3+343) (mod r(x))。因此，Di(X)成为D0(X) = 21 X3_343，D1(X) = 7 X20其中Dtl(X)为最高次数，因此，除Dq(Χ)以外移动到右侧，得到21 χ 3-343 = 7 χ2Φ9,对该式整理，得到χ 3-49 = χ2Φ 0因此，在进行关于非负整数η的G的有理点Q的标量η乘法，或关于非负整数η的 H的元素A的η次幂中，对于非负整数η，将η以t_l进制展开，进而以x 3_49进制展开，用 Χ2Φ,代替χ 3_49，由此能够利用弗罗贝尼乌斯自同态映射Φ q来运算G的有理点标量η乘 法或H的元素A的η次幂，减少运算次数，提高幂运算的运算速度。最后，对标量乘法的运算程序和幂运算的运算程序进行说明。而且，在本实施方式 中，标量乘法的运算程序和幂运算的运算程序是在由电子计算机执行基于ID加密或群签 名等时，作为一个子程序来执行的。如图1所示，执行标量乘法的运算程序和幂运算的运算程序的电子计算机10具 有执行运算处理的CPUll ；和由存储所需程序或数据的硬盘等存储装置12、能够展开执行 所需程序并临时存储运算中生成的数据的RAM构成的存储器13。图1中，14为总线。在本 实施方式中，在存储装置12中存储有主程序、标量乘法的运算程序/幂运算的运算程序等 各种程序、以及这些程序所要使用的数据。电子计算机10，在用作例如群签名中的认证装置时，与因特网等电气通信线路20 连接，接收从连接在该电气通信线路20上的客户端装置30发送来的群签名的签名数据，临 时存储于存储器13中，根据群签名用的程序判断签名数据的合法性而进行认证处理。图1 中，15为电子计算机10的输入输出控制部。在判断签名数据的合法性的处理中，多是执行标量乘法的运算程序和幂运算的运算程序，以下，对标量乘法的运算程序和幂运算的运算程序进行说明。而且，本发明的标量 乘法的运算程序和幂运算的运算程序并限于在群签名处理中使用，其能够用于多种用途。 并且，本发明的标量乘法的运算程序和幂运算的运算程序，可以是记录在存储装置12中或 能够由电子计算机读取的记录介质中，或者从服务器下载到记录装置中的，还可以是构成 为半导体电路，即以硬件形式构成的。首先，说明基于t-Ι进制展开的标量乘法nQ。图2为用于求取标量乘法nQ( = Ζ)的流程图。执行标量乘法的运算程序，电子 计算机发挥标量乘法器的作用。如图2所示，最初，CPUll通过电气通信线路20、输入输出 控制部15从客户端装置30输入标量IuE(Fq)的弗罗贝尼乌斯自同态映射的迹t和有理点 QeGcE(Fqk)的值，存储在存储器13中(步骤S101)。此时，电子计算机用作输入装置。然后，CPUll在存储器装置13中设定要保持的运算结果Z，并对Z初始化(Z — 0) (步骤S102)。因此电子计算机用作输入装置。CPUll对输入的Q执行有2恂表示的运算 (步骤 S103)。 在步骤S103中，令T[j] = 2JQ,CPUll从存储器13读出Q、t的值，执行如下动作(l)for(j = 0 ;j <「Iog2S」；j++)(2)T[j]—Q(3)Q —Q+Q(4)End for。在此，(1)中的「log2s」准确意义上应为[式14]
卩Og2 Sl
9但因文本的原因，用「」来标记。在此，CPUll令s = t-Ι，设j为自然数，从j = 0 到j <「lo&s」反复执行由T[j] — Q和Q — Q+Q表示的代入运算，将运算结果值存储在存 储器13中。而且，以下动作用使用的「」与上同。接着，令t-l = s,CPUll从存储器11读出c[i]、s、标量η的值，用作转换装置，将 标量η，根据[式15]
Hogs.nl
η = ^ C^si, 0 < c[i] < s i=0以s进制展开(步骤S104)。在此，i为自然数，i的大小由η决定。在步骤S104中，进行s进制展开运算，CPUll执行以下动作(l)for(i = O ;i <「logsn」；i++)(2)c[i] ^ n% s(3)n — (n_c[i])/s(4) End for
在此，“ ％，，表示余数。即，CPUll从存储器13读出c [i]、s、η的值，从i = 0到i <「logsn」反复执行由c [i] — s和η — (n-c [i]) /s表示的代入运算，将各系数c [i]、 和标量η的值存储在存储器13中。
然后，在本实施方式中，电子计算机用作第二运算装置进行Q[i] =c[i]Q运算 (步骤 S105)。在步骤S105中，用二进制法，CPUll执行以下动作(l)for(i = 0 ;i <「logsn」；i++)(2)Q[i]—0(3)for(j = 0 ；c[i] ！ = 0 ；i++)(4)if(c[i]&l)(5)Q[i] — Q[i]+T[j](6) End if(7)C[i] — c[i]/2(8) End for(9) End forBP, CPUll从i = 0到i <「logsn」利用Q[i] — 0的代入运算对存储在存储器13 中的Q[i]初始化，并重复执行以下运算。CPUll从存储器13读出系数Q[i]、T[i]，从j = 0到c[i] ！ =0，重复执行如下代入运算，即，在c[i]&l时执行由Q[i] — Q[i]+T[j]表示 的代入运算，在其他情况下执行由c[i] — c[i]/2表示的代入运算，将各Q[i]和系数c[i] 存储在存储器13中。接着，电子计算机作为合成装置，使用在步骤S105中运算的Q[i]，利用[式 16]
Hogs nl
IiQ=艺
i=0对标量乘法nQ进行合成(步骤S106)。在步骤S106中，CPU执行以下动作(l)for(i = 0 ;i <「logsn」；i++)(2)Z - Ζ+Φ； (Q[i])(3) End forBP, CPUll从存储器13读出Q[i]、的值，从i = 0到1 <「logsn」重复执行由 Z — Ζ+Φ； (Q[i])表示的代入运算，将Z的值存储在存储器13中。然后，电子计算机作为输出装置，从输入输出控制部15输出Z的值作为标量乘法 的运算程序的执行结果(步骤S107)，结束标量乘法的运算程序。由此，对标量η进行IogsIi 分割，因而能够通过使用Φ q将椭圆二倍计算的运算次数较少为大致l/logsn。另外，在用整数变量X分别以q(>c)、r(>c)、t(>c)来确定椭圆曲线的有限域Fq 的阶数q、整除#E(Fq)的素数阶数r、弗罗贝尼乌斯自同态映射Φq的迹t时，将r ( χ )以 t(x)_l展开，从而令由
[r(x)]Q =Σ [Di(X) (t(x)-l)i]Q =Σ Φ ； ([Di ( χ ) ]Q)表示的Di(X)中最高次数者为Ddmax(X),并使用由Φ/"χ(
9=Σ Φ (
0)-Φ^χ(
0)
= [f(Φ,, x)]Q表示的多项式 ΧΦ,，X)，根据cj\kQ = Q，使用由[Ddmax(X)JQ = ^(Φ,, x) Φ广ax]Q= ^(Φ,, x)]Q表示的多项式h ( Φ ,，χ )禾Π Ddmax (χ),来提高标量乘法nQ的运算速度。即，在Ddmax ( χ )和多项式h ( Φ ,，χ)被确定时，设χ = a，对标量η以Ddmax (a)进 制展开，并用ΜΦ,，χ)替换Ddmax (a)，从而减少运算次数。当Ddmax ( χ )和多项式h ( Φ ,，χ )被确定时，在标量乘法nQ中执行标量乘法的运算 程序，电子计算机作为标量乘法器使用。此时，如图3所示，最初CPUll输入标量n，令χ = 8,8 = 0^(8)^' (Φ,) =h(c^，a)，并输入有理点Q EGcE(Fqk)各值，存储在存储器I3 中(步骤S201)。此时，电子计算机用作输入装置。接着，电子计算机作为初始化装置。S卩，CPUll在存储器13中设定保持运算结果 的Z，并对其初始化为Z —0 (步骤S202)。然后，电子计算机用作第一运算装置。S卩，CPUll 对输入的Q预先运算2力(步骤S203)。步骤S203的运算与步骤S103的动作相同，省却其 说明。然后，电子计算机用作第一展开装置，用[式17]
『logs nl
η = ^ c^s1, 0 < c[i] < s i=0对标量η以s进制展开(步骤S204)。步骤S204中的s进制展开与步骤S104中 的展开动作相同，省略其说明。然后，电子计算机用作第二展开装置，使用h’ (Φ,)和c [i]，并利用[式18] k-1η = ^ Ηφη1, 0 < d[i] < S
i=0对标量η以Φ q进制展开(步骤S205)。在步骤S205中，进行Φ q进制展开，CPUll执行以下动作(1)Τ(Φ ) - 1(2)for(i = 0 ;i <「logsn」；i++)(3)d[i] - c[i](4)if(d[i]彡 s)(5)for(j = 0 ;j <「logsd[i]」；j++)(6)e[j] - d[i]% s(7)d[i] - (d[i]-e[j])% s
(8) End for(9)υ(Φ ) - 1(10) for (j = 0 ;j <「logsd[i]」；j++)(11)υ(Φ ) - {U(c^)*e[j]*h，(Φ ) '}% (Φ,'-Ι)(12) End for(13)Τ(Φ ) 一 {!"(Φ^+ΜΦ,)*!!，(Φ ) }% (Φ,'-Ι)(14) End if
(15)else(16)Τ(Φ ) 一 {T(c^)+d[i]*h，(Φ ) }% (Φ,'-Ι)(17)End else(18) End forBP, CPUll对存储在存储器13中的Τ(Φ,)初始1。CPUll从存储器13读出c[i] 的值，进行d[i] —c[i]的代入运算，并将d[i]的值存储在存储器13中。然后CPU从存 储器13读出d[i]、s的值，在满足d[i]彡s时，从j = 0到j <「logs d[i]」反复执行由 e[j] -d[i]%siPd[i] 一(d[i]-e[j])%s 表示的代入运算，在进行了 υ(Φ) —1 的 初始化后，从 j = 0 到 j < riogsd[i]J 反复执行由 υ(Φ,) — {U(c^)*e[j]*h’ (Φ,)^ % (Φ,'-Ι)表示的代入运算，然后执行由 Τ(Φ,) — {T(c^)+d[i]*h，(Φ,)1} % (Φ^-Ι)表 示的代入运算，将Τ(Φ,)的值存储在存储器13中。CPU11，在不满足d[i] > s时，执行由 Τ(Φ,) 一 {Τ(Φ,)+(1[ ]^'(Φ(1) }% (Φ^-1)表示的代入运算，将Τ(Φ,)的值存储在存储 器13中。CPUll从i = 0到i <「logsn」反复执行以上运算，将各i的d[i]、Τ(Φ)的值 存储在存储器13中。而且，在将标量η以Φ q进制展开时，以进制展开的系数d[i]比s大。CPUll 将进制展开的系数d[i]与s相比较，在判断为进制展开的系数d[i]比s大时(步 骤S206 =NO)，通过相对于以Φ q展开的系数d[i]取s的余数而进行调整，以使Φ q展开的系 数d[i]比s小(步骤S207)。此时，电子计算机在步骤S206中用作比较装置，在步骤S207
中用作调整装置。在步骤S207中，电子计算机执行以下动作(1) until(Vd[i]<s)(2)for(i = 0 ;i < k-1 ；i++)(3)d[i] — the i_th coefficient of Τ(Φ)(4)if(d[i]彡 s)(5) the i_th coefficient of !"(Φ) 一 0(6)for(j = 0 ;j <「logsd[i]」；j++)(7)e[j] - d[i]% s(8)d[i] - (d[i]-e[j])% s(9) End for(10)υ(Φ ) - 1(ll)for(j = 0 ;j <「logsd[i]」；j++)(12)υ(Φ,) 一 {U(c^)*e[j]*h，(Φ,'-Ι)
(13) End for (H)T(Cj5q) — {Τ(Φ )+υ(Φ(1)*Φ(1 }% (Φ,'-Ι)(15) End if(16) End for(17)End untilS卩，CPUll从存储器13读出Τ(Φ,)的第i个系数的值，在d[i]中存储其值，将d[i] 与s的值相比较。CPU11，在满足d[i]彡s时，对Τ(Φ,)的第i个系数存储0、从j = 0到 j <「logsd[i]」重复执行由 e[j] —d[i]%s 禾口d[i] — (d[i]_e[j])% s表示的代入运算，然后，在进行了 υ(Φ,) — 1的初始化 后，从 j = o 到 j <「iogsd[i]」重复执行由 υ(Φ,) — {u(c^)*e[j]*h，(Φ,'-ι) 表示的代入运算，接着，执行由τ(φ,) — {Τ(Φ )+υ(Φ(1)*Φ(1 }% (Φ^-Ι)表示的代入运算， 将τ(φ,)的值存储在存储器13中。CPU11，在不满足d[i] > S时，不进行上述一系列的运 算。CPUll从i = 0到i < k-ι重复执行上述运算，直到满足Vd[i]<s。接着，电子计算机作为第二运算装置，进行Q[i] = d[i]Q的运算(步骤S208)。在步骤S208中，使用二进制法，CPUll执行以下动作(l)for(i = 0 ;i < k ；i++)(2)Q[i]—0(3)for(j = 0 ；d[i] ！ = 0 ；i++)(4)if(d[i]&l)(5)Q[i] — Q[i]+T[j](6) End if(7)d[i] — d[i]/2(8) End for(9) End for即，CPUll从存储器13读出d[i]和T[j]的值，令Q[i] — 0，对Q[i]初始化后， 在满足d[i]&l时，执行由Q[i] — Q[i]+T[j]表示的代入运算，在不满足d[i]&l时，执行由 d[i] — d[i]/2表示的代入运算，将Q[i]和d[i]的值存储在存储器13中。然后，电子计算机用作合成装置，使用由步骤S208运算的Q[i]，利用[式19]
k-1
i=0对标量乘法nQ进行合成(步骤S209)。在步骤S209中，CPUl 1执行以下动作(l)for(i = 0 ;i < k ；i++)(2)Z - Ζ+Φ； (Q[i])(3) End forBP, CPUll从存储器13读出Z和Q[i]的值，从i = 0到i < k重复执行由 Ζ-Ζ+φ;(0[ ])表示的代入运算，将Z的值存储在存储器13中。CPUll从输入输出控制部15输出Z的值。S卩，电子计算机用作输入装置，输入Z作为标量乘法的运算程序的执行 结果(步骤S210)，宛城标量乘法的运算程序。由此，对标量η进行IogsIi分割，因而能够通 过使用Φ q将椭圆二倍计算的运算次数较少为大致ClegDdmax ( χ ) /degr ( χ )。由于预先给出椭圆曲线的有限域Fq的阶数q ( χ )，整除#E (Fq)的素数阶数r ( χ )， 弗罗贝尼乌斯自同态映射Φ q的迹t ( χ )，因而能够预先确定Ddfflax ( χ )和多项式h (Φ ,，χ )， 所以也可以预先将Ddmax(X)和多项式!!(Φ,，χ)与q(x)、r(>c)和t(x) —同安装到标 量乘法的运算程序中，也可以用r(χ)和t( χ )根据以下辅助程序求出Ddmax(X)和多项式 h( Φ。χ )。在电子计算机启动辅助程序时，如图4所示，首先用作输入装置。S卩，CPUll输入 r(x)和t(x)的值并存储在存储器13中(步骤S221)。然后，电子计算机用作展开装置，使用输入的t ( X )，令t ( X ) -1 = s ( X )，利用[式 20]
『deg r(x)/degs (χ)1
Γω = Z Di(X)S(X)S O^deg(DiOO)(5(χ))
i=0 将r(x)以s(x)进制展开(步骤S222)。在此，i的大小由r(x)和s(x)自动 决定。在步骤S222中，作为S(X)进制展开的运算，CPUll执行以下动作(l)for(i = 0 ;i <「degr ( x )/degs ( x )」；i++)(2)Di(X) —r(x) % s(x)(3)r(x) — (r ( x ) -Di ( x )) /s ( x )(4) End forBP, CPUll 从存储器 13 读出 r(x)和 s(x)的值，从 i = 0 到 i < degr(x)/ degs(x)重复执行由 Di(X) —r(x) % S(x)和 r(x) — (HX)-Di(X)Vs(X)表示的 代入运算，将Di(X)和r( χ的值存储在存储器13中。然后，电子计算机用作抽出装置，抽出deg^Jx))为最大者，作SDdfflax (X)输出 (步骤S223)。即，CPUll从存储器13读出Di(X)的值并进行比较，将最大的Di ( x )作为 Ddfflax ( Χ )并将其值存储在存储器13中。然后，电子计算机用作运算装置。S卩，CPUll进行[式21]
fdeg r(x)/degs (χ)1
h(ctvx) =^DiOO&ifd腿)-Ddmax (χ)
i=0的运算，确定多项式!!(Φ,，x )，将其值存储在存储器13中，并输出(步骤S224)。 如上所述，在电子计算机使用辅助程序，能够求出Ddmax(X)和多项式ΜΦ,，x)。通过将 Ddfflax(X)和多项式ΜΦ,，Χ)用于图3的步骤201，能够使图3所示标量乘法中椭圆二倍计 算的运算次数较少为大致ClegDdmax ( χ ) /degr ( x )。另外，使用整数变量X并分别预先由q(>c)、r(>c)、t(>c)确定椭圆曲线的有限域Fq、整除#E (Ftl)的素数阶数r(x)、弗罗贝尼乌斯自同态映射的迹t，并且将Hx)以 t(x)_l进制展开，从而由[r(x)]Q =Σ [Di ( χ ) (t ( χ )-1) iJ Q = Σ Φ ； ([Di ( χ ) ]Q) 表示Di ( χ )，当Di ( χ )中最高次数dmax为多个时，设作为最高次数dmax的项的 Χ “的系数为Tdmax ( Φ ，使用满足r ( χ ) I m ( χ )的最小次数的多项式m ( χ )，确定满足ν(Φ5) |m(c^)，gCd(Tdmax((^)，V((^)) =1的V ( Φ ，并利用扩展欧几里得互除法确定满足Ε(Φ )ν(Φ ) = v(mod !!!(Φ,))的标量ν和g ( Φ ，使用满足[Tdfflax ( Φ q) XdmaxJQ=E Φ ([Ο (χ)]0)-[Τ,ω3Χ(Φ ) XdmaxJQ= [f(c^，x)]Q的多项式f ( Φ q，x )和g ( Φ ，根据Φ qkQ = Q，来确定满足[VXdmaxJQ = [g(c^)f(cK，x)]Q = ^(Φ,, x)]Q的多项式!!(Φ,，乂)，并使该11((^，x)的关于Φ,的常数项h(0，x)满足[vx^-h(0, x)]Q = ^(Φ,, x)-h(0, x)]Q，从而提高标量乘法nQ的运算速度。即，令χ =a，s，= vadmax-h (0，a)，h，(Φ,) = h ( Φ q，a) _h (0，a)，代替以 Ddmax (a) 进制展开，而将标量η以vadmax-h (0，a)进制展开，用h ( Φ q，a) _h (0，a)代替vadmax-h (0，a)， 由此消减运算次数。当确定了s，= VadmaMi(Oia)，h，(Φ,) = h ( Φ q, a)-h (0, a)时，在标量乘法 nQ 中， 执行标量乘法的运算程序，电子计算机用作标量乘法器。此时，如图5所示，首先CPUll输 入标量 n，令 χ =a、标量 s，= Vadmax-h(0，a)、h，(Φ,) = h ( Φ q，a) _h (0，a)，并输入有理点
QEGcE(Fqk)的值，存储在存储器13中(步骤S301)。此时，电子计算机用作输入装置。接着，电子计算机用作初始化装置，CPUll在存储器13中设定保持运算结果的Z， 并进行Z —0的初始化(步骤S302)。然后电子计算机用作第一运算装置，CPUll读出存 储在存储器13中的Q的值，预先进行2力的运算，存储在存储器13中(步骤S303)。步骤 S303的运算与步骤S103的运算动作相同，CPUll进行的处理也相同，省略其说明。然后，电子计算机用作第一展开装置，利用[式 2幻
flog s η!
η= I OScDW
i=0将标量η以s，进制展开(步骤S304)。步骤S304中的S，进制展开与步骤S204 中的s进制展开的动作相同，CPUll进行的处理也相同，省略其说明。接着，电子计算机用作第二展开装置，使用h’ (Φ,)和c [i]，并根据[式2幻 k-1η = ^ d[i]<^q[, 0 < d[i] < s'
i=0
将标量η以Φ q进制展开(步骤S305)。步骤S305中的Φ q进制展开，除了标量 s，( = vadmax-h(0, a))与步骤S205中的标量M = Ddfflax(a))不同以外，与步骤205中以s 进制展开动作相同，CPUll进行的处理也相同，省略其说明。步骤S305中的进制展开中，进制展开的系数大于s，。如上所述，在进 制展开的系数比s’大时(步骤S306 :N0)，相对Φ q进制展开的系数取S’的余数而进行调 整，以使进制展开的系数比s’小(步骤S307)。步骤S307中的运算，除标量S’ (= VadmaM1 (0，a))与步骤S207中的标量s ( = Ddmax(a))不同以外，与步骤S207的运算动作相 同，CPUll进行的处理也相同，因此省略其说明。此时，电子计算机在步骤S306中用作比较 装置，在步骤S307中用作调整装置。接着，电子计算机用作第二运算装置，进行Q[i] =d[i]Q的运算(步骤S308)。在 步骤S308中，利用二进制法，步骤S308的运算与步骤S208的运算动作相同，CPUll进行的 处理也相同，省略其说明。接着，电子计算机用作合成装置，使用在步骤S308中运算的Q[i]，利用[式24]
权利要求
一种标量乘法的运算方法，其特征在于设椭圆曲线为E/Fq＝x3+ax+b y2＝0，其中a∈Fq，b∈Fq令，E(Fq)为由有限域Fq定义的椭圆曲线的有理点构成的加法群；E(Fqk)为由有限域Fq的扩域Fqk定义的椭圆曲线的有理点构成的加法群；φq为关于有限域Fq的有理点的弗罗贝尼乌斯自同态映射；t为弗罗贝尼乌斯自同态映射φq的迹；r为整除E(Fq)的阶数#E(Fq)＝q+1 t的素数阶数；E[r]为阶数为素数r的有理点集合；[j]为j倍的有理点的映射；G为包含于满足G＝E[r]∩Ker(φq [q])的E(Fqk)中的有理点集合，利用具有CPU和存储模块的电子计算机来运算关于非负整数n的G的有理点Q的标量n乘法，所述运算方法包括输入步骤，CPU输入所述非负整数n的值、所述迹t的值、和由表示的有理点Q的值，并存储在所述存储模块中；初始化步骤，CPU将存储运算结果Z的所述存储模块初始化；展开步骤，对于G的有理点Q，φq(Q)＝[q]Q＝[t 1]Q成立，由此CPU令s＝t 1，根据将所述n以s进制展开的下式，[式39] <mrow><mi>n</mi><mo>=</mo><munder> <mi>Σ</mi> <mi>i</mi></munder><mi>c</mi><mo>[</mo><mi>i</mi><mo>]</mo><msup> <mi>s</mi> <mi>i</mi></msup><mo>,</mo><mn>0</mn><mo>≤</mo><mi>c</mi><mo>[</mo><mi>i</mi><mo>]</mo><mo>≤</mo><mi>s</mi> </mrow>从i＝0开始重复进行规定次数的由C[i]←n％s和n←(n c[i])/s表示的代入运算，将各系数c[i]和非负整数n的值存储在所述存储模块中；运算步骤，CPU从所述存储模块读出所述有理点Q和所述系数c[i]，从i＝0开始重复进行规定次数的由Q[i]＝c[i]Q表示的运算，将各Q[i]的值存储在所述存储模块中；和合成步骤，用弗罗贝尼乌斯自同态映射φq取代t 1，标量乘法nQ表示为下式[式40] <mrow><mi>nQ</mi><mo>=</mo><munder> <mi>Σ</mi> <mi>i</mi></munder><msup> <msub><mi>φ</mi><mi>q</mi> </msub> <mi>i</mi></msup><mrow> <mo>(</mo> <mi>Q</mi> <mo>[</mo> <mi>i</mi> <mo>]</mo> <mo>)</mo></mrow><mo>,</mo> </mrow>CPU根据该式，从所述存储模块读出Q[i]和运算结果Z，从i＝0开始重复规定次数的由Z←Z+φqi(Q[i])表示的代入运算，将标量乘法的运算结果Z存储在存储模块中。FPA00001208044000011.tif
2.如权利要求1所述的标量乘法的运算方法，其特征在于在利用整数变量χ分别由q(>c)、r(>c)、t(>c)给出所述椭圆曲线的有限域Fq的阶数q、整除#E(Fq)的素数阶数r、弗罗贝尼乌斯自同态映射的迹t时，包括辅助输入步骤，CPU输入所述q(>c)、r(>c)、t(>c)各值，存储在所述存储模块中； 辅助展开步骤，CPU从所述存储模块读出Hx)和t(x)的值，令所述s(x)= t(x)_l，根据将r(x)以s(x)进制展开的下式 [式 41]
3.如权利要求2所述的标量乘法的运算方法，其特征在于 当所述系数Di (χ)中存在多个为最高次数dmax的系数Di (χ)时， 所述辅助输入步骤还包括，CPU输入满足r (χ) |m(X)的m(X)的值，并存储在所述存 储模块中的步骤， 并具有第二辅助确定步骤，CPU令作为degQJx))的最高次数dmax项的Xdmax的系数为 U Φ)，从所述存储模块读出系数Di (χ)，在所述存储模块中对Τ(Φ,，χ)和υ(Φ,，χ) 分配初始值“0”，从i = 0到i <「degr(>c)/degS(>c)」重复进行如下代入运算，该代入运 算中，当deg^Jx)) = dmax时，进行由Τ(Φ,，χ)x )+Di ( χ ) Φ /表示的代入运算，其他情况下，进行由υ(Φ,，χ)XHDi(X) Φ^表示的代入运算，将Τ(Φ,，χ)和υ(Φ,，χ)的值存储在存储模块中，确定最高次数系数Tdmax(CK)；第三辅助确定步骤，CPU从所述存储模块读出m(X)和R(X)的值，用满足 H χ ) Im(X)的最小次数的多项式m(X)，进行由W(Cj5q) 一 gccKTjc^)，m(c^))和 ν(Φ,) -ΚΦ,)表示的代入运算，确定满足 ν(Φ,) ImQ^gccKUc^)，V(Cj5q)) = 1 的V ( Φ ，将所述V ( Φ 的值存储在存储模块中；第四辅助确定步骤，CPU从所述存储模块读出V( Φ 和m(c^)的值，利用扩展欧几里 得互除法确定满足三 ν (mod m((j5q))的整数标量ν和g ( Φ 的值，将所述标量ν和g ( Φ 存储在所述存储模块中； 第五辅助确定步骤，替代所述辅助确定步骤，CPU从所述存储模块读出Tdmax(CK)、 χ “、Di ( χ )、Q 各值，使用满足[Tdmax (Φ,) χ dmax] Q=E Φ / ([Di ( χ ) ] Q) - [Tdfflax (Φ q)dmax] Q = [ΜΦ,，x)]Q的多项式ΜΦ,，x)和所述β(Φ )，根据= 9确定满足 [ν X dmaxJQ= [g(c^)f(cK，x)]Q= ^(Φ,, x)]Q的多项式h(c^，\)，将所述多项式11((^，χ)的值存储在所述存储模块中；和 CPU从所述存储模块读出所述h(c^，χ)的值， 使该ΜΦ,，χ)的关于Φ,的常数项h(0，χ)满足 [vxdmax-h(0, x)]Q = ^(Φ,, x)-h(0，x)]Q，由此令 χ = a，进行由 s，= VadmaMi(Oia)和 h，(φ,) = h ( Φ q, a)-h (0, a)表示的运算，将 s’和h’ (Φ,)的值存储在所述存储模块中，代替以Ddmax(a)进制展开，对以t-1进制展开后 的所述n，以VadmaM1 (0，a)进制展开，并用h ( Φ q，a) _h (0，a)代替VadmaM1 (0，a)的步骤。
4. 一种幂运算的运算方法，其特征在于 令Fqk为阶数q的有限域Fq的k次扩域，H为Fqk的素数阶数r的乘法子群，Φ q为关于有限域Fq的元素的弗罗贝尼乌斯自同态映射，利用具有CPU和存储模块的电子计算机来运算关于非负整数η的H的元素A的η次幂 的幂运算，所述运算方法包括输入步骤，CPU输入所述非负整数η的值、所述阶数q的值、所述F^k的素数阶数r的值、 由AEHcFqk表示的元素A的值，并存储在所述存储模块中；初始化步骤，CPU对存储运算结果Z的所述存储模块进行初始化； 第一运算步骤，CPU从所述存储模块读出所述阶数q、所述元素A的值，令所述q与r的 差为s = q_r，从j = 0到j <「lo&s」重复进行由T[j] 一 A和A — A*A表示的代入运算， 将所述T[j]和所述A的值存储在所述存储模块中；展开步骤，CPU从所述存储模块读出所述η和差s的值，根据以差s展开的下式 [式 42]
5.如权利要求4所述的幂运算的运算方法，其特征在于 设X" {Y}表示Xy,在使用整数变量χ分别由q(>c)、r(>c)、S(>c)给出所述阶数q、所述素数阶数r、所述 s时，包括辅助输入步骤，CPU输入所述q(>c)、r(>c)、S(>c)各值，存储在所述存储模块中； 辅助展开步骤，CPU从所述存储模块读出Hx)和S(X)，用所述S(X)根据将r (X) 以S(X)进制展开的下式 [式 44]
6.如权利要求5所述的幂运算的运算方法，其特征在于当所述系数Di (χ)中存在多个为最高次数dmax的系数Di (χ)时， 所述辅助存储步骤还包括，CPU输入满足r (χ) |m(X)的m(X)的值，并存储在所述存 储模块中的步骤， 并具有第二辅助确定步骤，CPU令作为degQJx))的最高次数dmax项的Xdmax的系数为 Tdfflax (q)，从所述存储模块读出系数Di (X)，在所述存储模块中对T (q，x)和U(q，x )的分 配初始值“0”，从i = 0到i <「degr (χ)/degs ( χ )」重复进行代入运算，该代入运算中， ^deg(Di(x)) =dmax时，进行由T(q，χ) —T(q，x )+Di ( χ ) Qi表示的代入运算，其他情 况下，进行由U(q，x) -U(q, x )+Di (X)Cii表示的代入运算，将T (q，x)和U(q，x )的值 存储在所述存储模块中，确定最高次数系数Tdmax (q)；第三辅助确定步骤，CPU从所述存储模块读出m(X)和R(X)的值，用满足r(x) |m(x)的最小次数的多项式m(X)，进行由ff(q) — gcd (Tdfflax (q), m(q))和 V(q) — W(q)表示的运算，确定满足V(q) Im(q), gcd(Tdmax(Q), V(q)) = 1 的V (q)，将所述V (q)的值存储在所述存储模块中；第四辅助确定步骤，CPU从所述存储模块读出V(q)和m(q)的值，利用扩展欧几里得互 除法确定满足g (q) V (q) = ν (mod m(q))的整数标量ν和g (q)，将所述标量ν和g (q)的值存储在所述存储模块中； 第五辅助确定步骤，替代所述辅助确定步骤，CPU从所述存储模块读出Tdfflax (q)、X dma\ Di ( X )、Q 各值，利用满足 A" (Tdfflax (q) χ dmax} =Α"{ Σ Di ( χ ) Qi-Tdmax (q) χ dmax) =A"{fq, x)}的多项式f(q，x)和所述g(q)，根据Φ,ΥΑ) =A确定满足 Α" {ν X dmax} = A"{g(q)f(q, x)} = A"{h(q, x)}的多项式h(q，X)，将所述多项式h(q，x)的值存储在所述存储模块中；和 CPU从所述存储模块读出所述h(q，x)的值， 使该h(q，X)的关于q的常数项h(0，X)满足 A"{vxdmax-h (0, x)} = A"{h(q, x)-h (0, x)},令 x = a，进行由 s’ = vadmax-h(0, a)和 h’ (q) = h(q，a)_h(0，a)表示的运算，将 s’ 和h’ (q)的值存储在所述存储模块中，代替以Ddmax (a)进制展开，对以s进行展开后的所述 η 以 VadmaMi (0，a)进制展开，并用 h(q，a)-h(0, a)代替 vadmax-h (0，a)的步骤。
7. —种记录有标量乘法的运算程序的能够由电子计算机读取的记录介质，其特征在于所述标量乘法的运算程序用于，由具有CPU和存储模块的电子计算机来运算关于非负 整数η的G的有理点Q的标量η乘法，其中，设椭圆曲线为 E/F, = x3+ax+b-y2 = 0，其中 a G Fq，b e Fq 令，E(Fq)为由有限域Fq定义的椭圆曲线的有理点构成的加法群；E(F^k)为由有限域Fq的扩域F^k定义的椭圆曲线的有理点构成的加法群；Φ q为关于有限域Fq的有理点的弗罗贝尼乌斯自同态映射；t为弗罗贝尼乌斯自同态映射的迹；r为整除E(Fq)的阶数#E(Fq) = q+1-t的素数阶数；E[r]为阶数为素数r的有理点集合；[j]为j倍的有理点的映射；G为包含于满足G = E[r] η ΚθΓ(ΦΓ[α])的E (Fqk)中的有理点集合，并在电子计算机中执行输入步骤，输入所述非负整数η的值、所述迹t的值、和由QEGc=E(Fqk)表示的有理 点Q的值，并存储在所述存储模块中；初始化步骤，将存储运算结果Z的所述存储模块初始化； 展开步骤，对于G的有理点Q， Φ q(Q) = [q]Q = [t_l]Q 成立，由此 令s = t-Ι，根据将所述η以s进制展开的下式， [式 45]
8.如权利要求7所述的能够由电子计算机读取的记录介质，其特征在于 在利用整数变量χ分别由q(>c)、r(>c)、t(>c)给出所述椭圆曲线的有限域Fq的阶数 q、整除#E(Fq)的素数阶数r、弗罗贝尼乌斯自同态映射Φ q的迹t时，在电子计算机中执行 辅助输入步骤，输入所述q(x)、r(X)、t(X)各值，存储在所述存储模块中； 辅助展开步骤，从所述存储模块读出r ( χ )和t ( χ )的值，令所述s ( χ ) = t ( χ ) -1，根 据将r(x)以S(X)进制展开的下式 [式 47]
9.如权利要求8所述的能够由电子计算机读取的记录介质，其特征在于 当所述系数Di (χ)中存在多个为最高次数dmax的系数Di (χ)时，所述辅助输入步骤还包括，输入满足r (χ) |m(X)的m(X)的值，并存储在所述存储模 块中的步骤，在电子计算机中执行第二辅助确定步骤，令作为degQi (χ))的最高次数dmax项的Xdmax的系数为 U Φ)，从所述存储模块读出系数Di (χ)，在所述存储模块中对Τ(Φ,，χ)和υ(Φ,，χ) 分配初始值“0”，从i = 0到i <「degr(>c)/degS(>c)」重复进行如下代入运算，该代入运 算中，当deg^Jx)) = dmax时，进行由Τ(Φ,，χ)x )+Di ( χ ) Φ /表示的代入运算，其他情况下，进行由υ(Φ,，χ)x)+DiX) Φ 表示的代入运算，将Τ(Φ,，χ)和υ(Φ,，χ)的值存储在存储模块中，确定最高次数系数Tdmax(CK)；第三辅助确定步骤，从所述存储模块读出m((X)和R(x)的值，用满足r(x) |m(X) 的最小次数的多项式m( χ )，进行由W(Cj5q) —gccKUc^)，πΚΦ))和ν(Φ,) -ΚΦ,) 表示的代入运算，确定满足ν(Φ,) ImQ^gccKUc^)，V(Cj5q)) = 1 的V ( Φ ，将所述V ( Φ 的值存储在存储模块中；第四辅助确定步骤，CPU从所述存储模块读出V( Φ 和m(c^)的值，利用扩展欧几里 得互除法确定满足Ε(Φ )ν(Φ )三 ν (mod m(c^))的整数标量ν和g ( Φ 的值，将所述标量ν和g ( Φ 存储在所述存储模块中； 第五辅助确定步骤，替代所述辅助确定步骤，CPU从所述存储模块读出Tdmax(CK)、 χ dmaxJi (χ)、Q 各值，使用满足[Tdmax(Cttl) XdmaxJQ=E Φ ([ (χ)]0)-[Τ(1ω3Χ(Φ(1) xdmax]Q =[ΜΦ,，x)]Q的多项式ΜΦ,，x)和所述β(Φ )，根据= 9确定满足 [VXdmaxJQ= [g(c^)f(cK，x)]Q= ^(Φ,, x)]Q的多项式h(c^，\)，将所述多项式11((^，χ)的值存储在所述存储模块中；和 从所述存储模块读出所述h(c^，X)的值， 使该h(c^，χ)的关于Φ,的常数项h(0，χ)满足 [vxdmax-h(0, x)]Q = ^(Φ,, x)-h(0，X)]Q，由此令 χ = a，进行由 s，= VadmaMi(Oia)和 h，(φ,) = h ( Φ q, a)-h (0, a)表示的运算，将 s’和h’ (Φ,)的值存储在所述存储模块中，代替以Ddmax(a)进制展开，对以t-1进制展开后 的所述n，以VadmaM1 (0，a)进制展开，并用h ( Φ q，a) _h (0，a)代替VadmaM1 (0，a)的步骤。
10.一种记录有幂运算的运算程序的能够由电子计算机读取的记录介质，其特征在于所述幂运算的运算程序用于，由具有CPU和存储模块的电子计算机来运算关于非负整 数η的H的元素A的η次幂，其中， 令Fqk为阶数q的有限域Fq的k次扩域； H为Fqk的素数阶数r的乘法子群； Φ q为关于有限域Fq的元素的弗罗贝尼乌斯自同态映射， 并在电子计算机中执行输入步骤，输入所述非负整数η的值、所述阶数q的值、所述F^k的素数阶数r的值、由 AeHcFqk表示的元素A的值，并存储在所述存储模块中；初始化步骤，对存储运算结果Z的所述存储模块进行初始化； 第一运算步骤，从所述存储模块读出所述阶数q、所述元素A的值，令所述q与r的差为 s = q_r，从j = 0到j <「lo&s」重复进行由T[j] 一 A和A — A*A表示的代入运算，将所 述T[j]和所述A的值存储在所述存储模块中；展开步骤，从所述存储模块读出所述η和差s的值，根据以差s展开的下式 [式 48]
11.如权利要求10所述的能够由电子计算机读取的记录介质，其特征在于 设X" {Y}表示Xy,在使用整数变量χ分别由q(>c)、r(>c)、S(>c)给出所述阶数q、所述素数阶数r、所述 S时，在电子计算机中执行辅助输入步骤，输入所述q(x)、r(X)、S(X)各值，存储在所述存储模块中； 辅助展开步骤，从所述存储模块读出r (χ)和s(x)，用所述S(X)根据将r(x)以 s(x)进制展开的下式 [式 50]
12.如权利要求11所述的能够由电子计算机读取的记录介质，其特征在于 当所述系数Di (χ)中存在多个为最高次数dmax的系数Di (χ)时， 所述辅助存储步骤还包括，输入满足r (χ) |m(X)的m(X)的值，并存储在所述存储模 块中的步骤，在电子计算机中执行第二辅助确定步骤，令作为deg(Di (X))的最高次数dmax项的x ^=1的系数为Tdmax(q)， 从所述存储模块读出系数Di(X),在所述存储模块中对T(q，x)和U(q，x)的分配初 始值“0”，从i = 0到i <「degr(>c)/degS(>c)」重复进行代入运算，该代入运算中，当 deg^Jx)) =dmaX时，进行由T(q，x)—T(q，x )+Di ( χ ) Qi表示的代入运算，其他情况 下，进行由U(q，x) -U(q, x )+Di (X)Cii表示的代入运算，将T (q，x)和U(q，x )的值存 储在所述存储模块中，确定最高次数系数Tdmax (q)；第三辅助确定步骤，从所述存储模块读出m(X)和R(X)的值，用满足r(x) |m(X)的 最小次数的多项式m(X)，进行由W(q) -gcd (Tdfflax (q),m(q))和V(q) —W(q)表示的运算， 确定满足V(q) |m(q), gcd(Tdmax(Q), V(q)) = 1 的V (q)，将所述V (q)的值存储在所述存储模块中；第四辅助确定步骤，从所述存储模块读出V(q)和m(q)的值，利用扩展欧几里得互除法 确定满足g (q) V (q) = ν (mod m(q))的整数标量ν和g (q)，将所述标量ν和g (q)的值存储在所述存储模块中； 第五辅助确定步骤，替代所述辅助确定步骤，从所述存储模块读出Tdmax(q)、xdma\ Di(X)、Q各值，利用满足A" ITdmax (q) X dmaxI = Α" { Σ Di ( X ) Qi-Tdmax (q) x dmax) =A"{f(q, x)}的多项式f(q，x)和所述g(q)，根据Φ,ΥΑ) =A确定满足 Α" {ν X dmax} = A"{g(q)f(q, x)} = A"{h(q, x)}的多项式h(q，X)，将所述多项式h(q，x)的值存储在所述存储模块中；和 CPU从所述存储模块读出所述h(q，x)的值， 使该h(q，X)的关于q的常数项h(0，X)满足A"{vxdmax-h(0, χ)} = A"{h(q, x)-h(0, χ)},令 x = a，进行由 s’ = vadmax-h(0, a)和 h’ (q) = h(q，a)_h(0，a)表示的运算，将 s’ 和h’ (q)的值存储在所述存储模块中，代替以Ddmax (a)进制展开，对以s进行展开后的所述 η 以 VadmaMi (0，a)进制展开，并用 h(q，a)-h(0, a)代替 vadmax-h (0，a)的步骤。
全文摘要
本发明涉及能够快速进行运算的标量乘法或幂运算的运算方法、以及标量乘法或幂运算的程序。在电子计算机中，关于非负整数n的G的有理点Q的标量n乘法的运算方法和运算程序中，φq(Q)＝[q]Q＝[t-1]Q成立，由此对标量n以t-1进制展开，使用有理点的弗罗贝尼乌斯自同态映射φq取代t-1。另外，在电子计算机中，关于非负整数n的H的元素A的n次幂的幂运算方法和运算程序中，令q和r的差为s＝q-r，则对于H的非零元素A，φq(A)＝Aq＝As成立，由此对指数n以s进制展开，使用关于元素的弗罗贝尼乌斯自同态映射φq取代s。
文档编号G09C1/00GK101965602SQ20098010637
公开日2011年2月2日 申请日期2009年2月25日 优先权日2008年2月25日
发明者加藤英洋, 森川良孝, 赤根正刚, 野上保之 申请人:国立大学法人冈山大学
最新回复(0)