図面 (/)

技術 多基底べき乗積演算方法、この方法を実施する装置、プログラムおよびプログラムを記憶した記憶媒体

出願人 日本電信電話株式会社
発明者 星野文学
出願日 2002年1月25日 (18年11ヶ月経過) 出願番号 2002-017204
公開日 2003年7月30日 (17年4ヶ月経過) 公開番号 2003-216035
状態 未査定
技術分野 複合演算 特定演算一般(初等関数/乱数発生/非基数) 暗号化・復号化装置及び秘密通信
主要キーワード 積演算装置 参照出力 適用位置 自乗演算 参照法 演算テーブル 積演算結果 作成コスト
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2003年7月30日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (5)

課題

演算テーブル参照過程自乗を含む演算過程を分離する行程を採用することに対応して最大べきの桁数に比例する中間結果保存領域を用意する構成を採用して多基底のべき乗積演算に必要な自乗演算演算コストを削減し、演算実行時のテーブルに必要な記憶領域のコストを削減する多基底べき乗積演算方法、この方法を実施する装置、プログラムおよびプログラムを記憶した記憶媒体を提供する。

解決手段

可換群の元の多基底の整数べき乗の積を演算する多基底べき乗積演算方法において、最大べきの桁数に比例する中間結果を保存する中間結果保存領域を確保することによりテーブル参照過程と自乗を含む演算過程を分離する多基底べき乗積演算方法。

概要

背景

近年公開鍵暗号方法デジタル署名その他の情報セキュリティ技術分野において大量の署名ゼロ知識証明の如き一括検証、或いは電子投票の様な大規模プロトコルが提案されている。これらの大規模な情報セキュリティサービスを実現する場合、大量のべきの積を計算しなければならないことがある。即ち、入力g0、g1、g2、・・・・、gn-1および正整数e0、e1、e2、・・・・、en-1に対してiが0から(n−1)に到る整数べき乗の積
i=0Πn-1giei
を出力することが求められる。この時、べきgiei を1個づつ計算してからこれらの積を出力するより高速に計算する以下の計算方法が知られている。但し、kは、

概要

演算テーブル参照過程自乗を含む演算過程を分離する行程を採用することに対応して最大べきの桁数に比例する中間結果保存領域を用意する構成を採用して多基底のべき乗積演算に必要な自乗演算演算コストを削減し、演算実行時のテーブルに必要な記憶領域のコストを削減する多基底べき乗積演算方法、この方法を実施する装置、プログラムおよびプログラムを記憶した記憶媒体を提供する。

可換群の元の多基底の整数べき乗の積を演算する多基底べき乗積演算方法において、最大べきの桁数に比例する中間結果を保存する中間結果保存領域を確保することによりテーブル参照過程と自乗を含む演算過程を分離する多基底べき乗積演算方法。

目的

この発明は、演算テーブル参照過程と自乗を含む演算過程を分離する行程を採用することに対応して最大べきの桁数に比例する中間結果保存領域を用意する構成を採用して上述の問題を解消した多基底のべき乗積演算に必要な自乗演算の演算コストを削減し、演算実行時のテーブルに必要な記憶領域のコストを削減する多基底べき乗積演算方法、この方法を実施する装置、プログラムおよびプログラムを記憶した記憶媒体を提供するものである。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

可換群の元の多基底整数べき乗の積を演算する多基底べき乗積演算方法において、最大べきの桁数に比例する中間結果を保存する中間結果保存領域を確保することによりテーブル参照過程自乗を含む演算過程を分離することを特徴とする多基底べき乗積演算方法。

請求項2

請求項1に記載される多基底べき乗積演算方法において、テーブル参照過程の間に同じテーブルを連続的に使用し、使用完了後にテーブルを破棄することによリ、テーブル保持に必要な記憶領域を削減することを特徴とする多基底べき乗積演算方法。

請求項3

請求項1に記載される多基底べき乗積演算方法において、テーブル参照法に単一の基底、複数の基底或いはスライディング法を使用することを特徴とする多基底べき乗積演算方法。

請求項4

請求項1に記載される多基底べき乗積演算方法において、テーブル参照法で使用するテーブルの値を適応的に作成することを特徴とする多基底べき乗積演算方法。

請求項5

コンピュータを主要な構成部材として構成され、制御装置、中間結果保存領域、テーブル作成器、ウィンドウ、テーブル、テーブル参照器、群演算器、自乗および積算器を有する多基底べき乗積演算装置において、制御装置は中間結果保存領域にリセット信号送り、中間結果保存領域は、これにより、それぞれ単位元に初期化し、制御装置は、n個の群の元およびべきの組より未処理のものm個を選び、選んだm個の群の元およびべきをそれぞれテーブル作成器とウィンドウに入力し、制御装置はテーブル作成器を駆動し、テーブル作成器はテーブルを作成し、テーブル参照器は、ウィンドウの値をテーブルをインデックスとして参照、出力し、制御装置は群演算器を駆動し、中間結果保存領域の内容を更新し、制御装置は自乗および積算器を駆動してべき乗積演算結果を出力することを特徴とする多基底べき乗積演算装置。

請求項6

コンピュータを主要な構成部材として構成され、制御装置、中間結果保存領域、テーブル作成器、ウィンドウ、テーブル、テーブル参照器、群演算器、自乗および積算器を有する多基底べき乗積演算装置に対して、制御装置が中間結果保存領域にリセット信号を送り、中間結果保存領域は、これにより、それぞれ単位元に初期化すべき指令をし、制御装置が、n個の群の元およびべきの組より未処理のものm個を選び、選んだm個の群の元およびべきをそれぞれテーブル作成器とウィンドウに入力すべき指令をし、制御装置がテーブル作成器を駆動し、テーブル作成器はテーブルを作成すべき指令をし、テーブル参照器がウィンドウの値をテーブルをインデックスとして参照出力すべき指令をし、制御装置が群演算器を駆動して、中間結果保存領域の内容を更新すべき指令をし、制御装置が元およびべきの未処理の組をテーブル作成器とウィンドウに入力すべき指令をし、制御装置が自乗および積算器を駆動してべき乗積演算結果を出力すべき指令をすることを特徴とする多基底べき乗積演算プログラム

請求項7

コンピュータを主要な構成部材として構成され、制御装置、中間結果保存領域、テーブル作成器、ウィンドウ、テーブル、テーブル参照器、群演算器、自乗および積算器を有する多基底べき乗積演算装置に対して、制御装置が中間結果保存領域にリセット信号を送り、中間結果保存領域は、これにより、それぞれ単位元に初期化すべき指令をし、制御装置が、n個の群の元およびべきの組より未処理のものm個を選び、選んだm個の群の元およびべきをそれぞれテーブル作成器とウィンドウに入力すべき指令をし、制御装置がテーブル作成器を駆動し、テーブル作成器はテーブルを作成すべき指令をし、テーブル参照器がウィンドウの値をテーブルをインデックスとして参照出力すべき指令をし、制御装置が群演算器を駆動して、中間結果保存領域の内容を更新すべき指令をし、制御装置が元およびべきの未処理の組をテーブル作成器とウィンドウに入力すべき指令をし、制御装置が自乗および積算器を駆動してべき乗積演算結果を出力すべき指令をする多基底べき乗積演算プログラムを記憶したプログラム記憶媒体

技術分野

0001

この発明は、多基底べき乗積演算方法、この方法を実施する装置、プログラムおよびプログラムを記憶した記憶媒体に関し、特に、大規模な多基底のべき乗積演算に必要な自乗演算演算コストを削減し、演算実行時のテーブルに必要な記憶領域のコストを削減する多基底べき乗積演算方法、この方法を実施する装置、プログラムおよびプログラムを記憶した記憶媒体に関する。

背景技術

0002

近年公開鍵暗号方法デジタル署名その他の情報セキュリティ技術分野において大量の署名ゼロ知識証明の如き一括検証、或いは電子投票の様な大規模なプロトコルが提案されている。これらの大規模な情報セキュリティサービスを実現する場合、大量のべきの積を計算しなければならないことがある。即ち、入力g0、g1、g2、・・・・、gn-1および正整数e0、e1、e2、・・・・、en-1に対してiが0から(n−1)に到る整数べき乗の積
i=0Πn-1giei
を出力することが求められる。この時、べきgiei を1個づつ計算してからこれらの積を出力するより高速に計算する以下の計算方法が知られている。但し、kは、

0003

ID=000002HE=010 WI=027 LX=0465 LY=1000
とする。
計算方法1:
入力:g0、g1、g2、・・・・、gn-1および正整数e0、e1、e2、・・・・、en-1出力:G=i=0Πn-1giei
処理:
Step1:ei=j=0Σkeij2jなるeiのeij∈2進表現{0、1}をi∈{0、・・・・、n−1}、j∈{0、・・・・、k}に関して求める。

0004

Step2:G←1、J←kとする。
Step3:G←G2(自乗
Step4:
Step4.1:i←0とする。
Step4.2:もし、eij=1ならばG←G×gi(積)
Step4.3:もし、i<n−1ならi←i+1としてStep4.2へ移行する。
Step5:もし、j=0ならStep6へ移行し、さもなければj←j−1としてStep3へ移行する。

0005

Step6:Gを出力する。
この計算方法1は、出力を得るのにk回の自乗と平均nk/2回の乗算が必要である。HANDBOOK ofAPPLIED CRYPTOGRAPHY(ISBN O-8493-8523-7)のp.618 14.88 Algorithm Simultaneous multiple exponentiation にはこの方法の改良である以下の計算方法2が記述されている。
計算方法2:
入力:g0、g1、g2、・・・・、gn-1および正整数e0、e1、e2、・・・・、en-1
出力:G=i=0Πn-1giei
処理:
StepO:後述されるテーブル作成処理1にg0、g1、g2、・・・・、gn-1を入力し、演算テーブルG0、G1、・・・・、G2n-1を得る。

0006

Step1:ei=j=0Σkeij2jなるeiの2進表現eij∈{0、1}をi∈{0、・・・・、n−1}、j∈{0、・・・・、k}に関して求め、更に、Ij←i=0Σn-1eijをj∈{0、・・・・、k}に関して求める。
Step2:G←1、j←kとする。
Step3:G←G2(自乗)
Step4:G←G×Gij(乗算)
Step5:もし、j=0ならStep6へ移行し、さもなければj←j−1としてStep3へ移行する。

0007

Step6:Gを出力する。
テーブル作成処理1:
入力:g0、g1、・・・・、gn-1
出力:G0、G1、・・・・、G2n-1(演算テーブル)
処理:
Step1:i∈{0、...、2n−1}に関して以下の処理を実行する。
Step1.1:i=j=0Σn-12jijなるiの2進表現ij∈{0、1}をj∈{0、・・・・、n−1}に関して求める。

0008

Step1.2:Gi←j=0Πn-1gjijとする。
Step2:演算テーブルG0、G1、G2、・・・・、G2n-1を出力する。
このテーブル作成処理1は一見およそnの2n 回の乗算が必要に見えるが、実際はi<2jなるi、jに関する
G2j+i=gjGi
関係式を使用し、およそ2n 回の乗算で作成される。即ち、計算方法2においては、出力を得るにk回の自乗とおよそk回の乗算を必要とする他に、2n 個の演算テーブルを作成するにおよそ2n 回の乗算を必要としている。故に、必要な記憶領域および計算時間の面でnが大きい場合、計算方法2をそのまま実行することは事実上不可能である。

0009

従って、この計算方法2をnが非常に大きい場合に実際に実行するには、n個の入力を、充分に小さい正の整数m個づつの組にして、各組に対して計算方法2を実行する必要がある。一般に、nはmで割り切れる必要はないが、説明の簡単の為に、n=mr(rは正整数)であるとする。各組に対して計算方法2を実行する方法としては以下の計算方法3および計算方法4の2通りの方法がある。計算方法3:図5(a)を参照して計算方法3による群演算実行順序を説明する。

0010

入力:g0、g1、・・・・、gn-1および正整数e0、e1、e2、・・・・、en-1
出力:G=i=0Πn-1giei
処理:
Step1:G←1、J←0とする。
Step2:もし、J=rならStep6へ移行する。
Step3:計算方法2にgmj+0、gmj+1、・・・・、gmj+(m-1)および正整数
emj+0、emj+1、・・・・、emj+(m-1)を入力し、出力Gj=i=0Πm-1gmj+iemj+iを得る。

0011

Step4:G←G×Gjとする。
Step5:J←J+1としてStep2へ移行する。
Step6:Gを出力する`
計算方法4:図5(b)を参照して計算方法4による群演算実行順序を説明する。
入力:g0、g1、・・・・、gn-1および正整数e0、e1、・・・・、en-1
出力:G=i=0Πn-1giei
処理:
StepO:s∈{0、・・・・、r−1}に関して、テーブル作成処理1にgms+0、・・・・、gms+(m-1)を入力して、演算テーブルGs、0、・・・・、Gs、2m-1を得る。

0012

Step1:i∈{0、・・・・、n−1}、j∈{0、・・・・、k}に関してei=j=0Σkeij2jなるeiの2進表現eij∈{0、1}を求め、更に、s∈{0、・・・・、r−1}、j∈{0、・・・・、k}に関して、Isj←L=0Σm-12Lems+Ljを求める。
Step2:G←1、j←kとする。
Step3:G←G2(自乗)
Step4:
Step4.1:s←0とする。

0013

Step4.2:s≧rならばStep5へ移行する。
Step4.3:G←G×Gs、Isj(乗算)
Step4.4:s←s+1としてStep4.2へ移行する。
Step5:もし、j=0ならStep6へ移行し、さもなければj←j−1としてStep3へ移行する。
Step6:Gを出力する。
mは演算テーブルのサイズおよび作成コストによって決定される数であり、例えば、kが160〜1024程度ならmは一般に4〜6程度の整数となる。

0014

演算順序の変更
g1、g2、g3 を可換群の元であるものとすれば、可換群の群演算×には、以下の性質がある。
結合則:(g1×g2)×g3=g1×(g2×g3)
交換則:g1×g2=g2×g1
これらの性質を用いて、複数の群演算の実行順序を演算に有利に変更することができる場合がある。計算方法1ないし計算方法4が全て、多基底のべき乗の積と同じ値を出力することができるのはこの性質による。

発明が解決しようとする課題

0015

以上の従来の群演算の実行方法においては、演算テーブル参照過程の間に自乗を含む演算過程が必ず含まれていて、計算方法3は(n/m)×k回の自乗を実行する必要があり、計算方法4は(n/m)×2m 個の演算記憶領域を必要とする。従って、自乗の回数或いは演算テーブルのサイズの何れか一方はnに比例して大きくなり、これが演算コスト或いは記憶領域のコストの削減を阻んでいる。例えば、情報セキュリティ技術分野の電子投票にこの演算を適用する場合、nが投票者の数として見積もられることがある。国勢選挙ベルの大規模なアプリケーションを考えた場合、n=105〜107程度、m=4〜6程度と見積もられるところから、計算方法3或いは計算方法4は無視できないコストとなる。

0016

この発明は、演算テーブル参照過程と自乗を含む演算過程を分離する行程を採用することに対応して最大べきの桁数に比例する中間結果保存領域を用意する構成を採用して上述の問題を解消した多基底のべき乗積演算に必要な自乗演算の演算コストを削減し、演算実行時のテーブルに必要な記憶領域のコストを削減する多基底べき乗積演算方法、この方法を実施する装置、プログラムおよびプログラムを記憶した記憶媒体を提供するものである。

課題を解決するための手段

0017

請求項1:可換群の元の多基底の整数べき乗の積を演算する多基底べき乗積演算方法において、最大べきの桁数に比例する中間結果を保存する中間結果保存領域を確保することによりテーブル参照過程と自乗を含む演算過程を分離する多基底べき乗積演算方法を構成した。そして、請求項2:請求項1に記載される多基底べき乗積演算方法において、テーブル参照過程の間に同じテーブルを連続的に使用し、使用完了後にテーブルを破棄することによリ、テーブル保持に必要な記憶領域を削減する多基底べき乗積演算方法を構成した。

0018

また、請求項3:請求項1に記載される多基底べき乗積演算方法において、テーブル参照法に単一の基底、複数の基底或いはスライディング法を使用する多基底べき乗積演算方法を構成した。更に、請求項4:請求項1に記載される多基底べき乗積演算方法において、テーブル参照法で使用するテーブルの値を適応的に作成する多基底べき乗積演算方法を構成した。ここで、請求項5:コンピュータを主要な構成部材として構成されて、制御装置1、中間結果保存領域2、テーブル作成器3、ウィンドウ4、テーブル5、テーブル参照器6、群演算器7、自乗および積算器8を有する多基底べき乗積演算装置において、制御装置1は中間結果保存領域2にリセット信号送り、中間結果保存領域2は、これにより、それぞれ単位元に初期化し、制御装置1は、n個の群の元およびべきの組より未処理のものm個を選び、選んだm個の群の元およびべきをそれぞれテーブル作成器3とウィンドウ4に入力し、制御装置1はテーブル作成器3を駆動し、テーブル作成器3はテーブル5を作成し、テーブル参照器6は、ウィンドウ4の値をテーブル5をインデックスとして参照、出力し、制御装置1は群演算器7を駆動し、中間結果保存領域2の内容を更新し、制御装置1は自乗および積算器8を駆動してべき乗積演算結果を出力する多基底べき乗積演算装置を構成した。

0019

そして、請求項6:コンピュータを主要な構成部材として構成されて、制御装置1、中間結果保存領域2、テーブル作成器3、ウィンドウ4、テーブル5、テーブル参照器6、群演算器7、自乗および積算器8を有する多基底べき乗積演算装置に対して、制御装置1が中間結果保存領域2にリセット信号を送り、中間結果保存領域2は、これにより、それぞれ単位元に初期化すべき指令をし、制御装置1が、n個の群の元およびべきの組より未処理のものm個を選び、選んだm個の群の元およびべきをそれぞれテーブル作成器3とウィンドウ4に入力すべき指令をし、制御装置1がテーブル作成器3を駆動し、テーブル作成器3はテーブル5を作成すべき指令をし、テーブル参照器6がウィンドウ4の値をテーブル5をインデックスとして参照、出力すべき指令をし、制御装置1が群演算器7を駆動し、中間結果保存領域2の内容を更新すべき指令をし、制御装置1が元およびべきの未処理の組をテーブル作成器3とウィンドウ4に入力すべき指令をし、制御装置1が自乗および積算器8を駆動してべき乗積演算結果を出力すべき指令をする多基底べき乗積演算プログラムを構成した。

0020

また、請求項7:コンピュータを主要な構成部材として構成されて、制御装置1、中間結果保存領域2、テーブル作成器3、ウィンドウ4、テーブル5、テーブル参照器6、群演算器7、自乗および積算器8を有する多基底べき乗積演算装置に対して、制御装置1が中間結果保存領域2にリセット信号を送り、中間結果保存領域2は、これにより、それぞれ単位元に初期化すべき指令をし、制御装置1が、n個の群の元およびべきの組より未処理のものm個を選び、選んだm個の群の元およびべきをそれぞれテーブル作成器3とウィンドウ4に入力すべき指令をし、制御装置1がテーブル作成器3を駆動し、テーブル作成器3はテーブル5を作成すべき指令をし、テーブル参照器6がウィンドウ4の値をテーブル5をインデックスとして参照出力すべき指令をし、制御装置1が群演算器7を駆動し、中間結果保存領域2の内容を更新すべき指令をし、制御装置1が元およびべきの未処理の組をテーブル作成器3とウィンドウ4に入力すべき指令をし、制御装置1が自乗および積算器8を駆動してべき乗積演算結果を出力すべき指令をする多基底べき乗積演算プログラムを記憶したプログラム記憶媒体を構成した。

発明を実施するための最良の形態

0021

上述した通り、従来の群演算の実行方法においては、演算テーブル参照過程の間に自乗を含む演算過程が必ず含まれており、これが演算コスト或いは記憶領域のコストの削減を阻む原因となっていた。この発明は、演算テーブル参照過程と自乗を含む演算過程を分離する行程を採用することに対応して、最大べきの桁数に比例する中間結果保存領域を用意する。群演算実行順序は計算方法3の群演算実行順序に似ているが、テーブル参照を行っている間は自乗を行わず、代わりに対応する中間結果保存領域を選択して積演算を行う。

0022

計算方法5:
入力:g0、g1、・・・・、gn-1および正整数e0、e1、・・・・、en-1
出力:G=i=0Πn-1giei
一時領域:T0、T1、・・・・、TK-1
処理:
Step1:i∈{0、・・・・、n−1}、j∈{0、・・・・、k}に関してei=j=0Σkeij2jなるeiの2進表現eij∈{0、1}を求める。T0←1、・・・・、TK-1←1、s←0とする。

0023

[テーブル参照過程]
Step2:テーブル作成処理1にgms+0、・・・・、gms+(m-1)を入力し、演算テーブルG0、・・・・、G2m-1を得る。
Step3:j∈{0、・・・・、k}に関して以下演算を行う。
Step3.1:Ij←L=0Σm-12Lems+Ljとする。
Step3.2:Tj←Tj×GIj(乗算)
Step4:もし、s=r−1ならStep5へ移行し、さもなければテーブルG0、・・・・、G2m-1を破棄し、s←s+1としてStep2へ移行する。

0024

[自乗を含む過程]
Step5:G←1、j←kとする。
Step6:G←G2(自乗)
Step7:G←G×Tjとする。
Step8:もし、j=0ならStep9へ移行し、さもなければj←j−1としてStep6へ移行する。
Step9:Gを出力する。

0025

この発明における群演算実行順序の一例を図1を参照してに説明する。この例のテーブル参照は基本的に計算方法3のテーブル参照と同一であり、演算実行中に大きなテーブルを準備しておく必要はない。更に、この例はテーブル参照を行っている間は自乗を行わずに中間結果保存領域を選択しているだけであり、その演算コストは充分に小さい。自乗を含む演算は全てのテーブル参照が終了した後1度だけ実行され、この部分の自乗の演算コストは計算方法4の自乗の演算コストと同一であり充分に小さい。

0026

代表的なウィンドウの型を図2に示す。何れも、ウィンドウサイズ4の場合を示す。同じ行にあるウィンドウは同じテーブルから参照が行われる。通常は、kの分割数分の一時記憶領域を必要とする。テーブル作成は、nの分割数回行う必要がある。スライディングウィンドウ法に代表されるウィンドウサイズや適用位置が動的に決定される方法においてはk個の一時記憶領域を必要とする。図2(a)は計算方法3、4、5の分け方を示す。一時記憶領域はk=8個、テーブル作成回数はn/4=8/2=4回である。図2(b)は1個のテーブルには1個の基底しか使用しないk−ary法のウィンドウである。一時記憶領域はk/4=8/4=2個、テーブル作成回数はn=8回である。図2(c)は一般的な長方形のウィンドウである。一時記憶領域はk/2=8/2=4個、テーブル作成回数はn/2=4回である。

0027

ここで、テーブルの構成、テーブル参照の方法には自由度があり、一般に、指数e1、・・・・、enに含まれる何れのビットを参照のインデックスとして用いるかによって決定される。この例においては、指数e1、e2、・・・・、en に含まれるテーブルを引くビットの組み合わせをウインドウと呼ぶ。計算方法3ないし計算方法4が想定しているウインドウ以外のウインドウでも適用することができる。テーブル参照法について説明するに、どの様なテーブル参照法についても、使用されるテーブルの値をテーブル参照過程において参照が行われるエントリのみ適応的(動的)に作成する適応的テーブル参照法を適用することにより、処理コストを削減することができる。この発明においてもこの参照法を適用することができる。

0028

HANDBOOK ofAPPLIED CRYPTOGRAPHY(ISBN O-8493-8523-7)のp.615 14.82 Left-to-right k-ary exponentiation には、単一基底のべき計算に関するk-ary法を含むテーブル参照法が記載されている。この発明においては、この方法も、自乗演算を中間結果保存領域の選択に置き換え多基底のべき乗の積の演算法に適用することができる。この方法を適用することにより、中間結果保存領域のサイズを削減することができる。HANDBOOK of APPLIED CRYPTOGRAPHY(ISBN O-8493-8523-7)のp.616 14.85 Sliding-windowには、単一基底のべき計算に関するスライディング法を含むテーブル参照法が記載されている。この発明により、この方法も、自乗演算を中間結果保存領域の選択に置き換え多基底の纂乗の積の演算法に適用することができる。

0029

多基底べき乗積演算装置の実施例を、特に、図3を参照して説明する。図3の多基底べき乗積演算装置はコンピュータを主要な構成部材として構成される。図3において、1は制御装置、2は中間結果保存領域、3はテーブル作成器、4はウィンドウ、5はテーブル、6はテーブル参照器、7は群演算器、8は自乗および積算器である。
Step1 :制御装置1は中間結果保存領域2にリセット信号を送り、中間結果保存領域2は、これにより、それぞれ単位元に初期化される。

0030

Step2 :制御装置1は、n個の群の元およびべきの組より未処理のものm個を選び、処理済みとし、選んだm個の群の元およびべきをそれぞれテーブル作成器3とウィンドウ4に入力する。但し、未処理のものがm個に満たない場合は足りない分を群の単位元と0の組で補うものとする。図3において、m=3とされている。
Step3 :制御装置1はテーブル作成器3を駆動し、テーブル作成器3はテーブル5を作成する。

0031

Step4 :テーブル参照器6の各参照部1〜kは、各々の入力たるウィンドウ4の値をインデックスとしてテーブル5を参照し、出力する。
Step5 :制御装置1は群演算器7の各参照部1〜kを駆動し、中間結果保存領域2の内容を更新する。
Step6 :未処理の組が存在するなら、Step2へ移行する。
Step7 :制御装置1は自乗および積算器8を駆動してべき乗積演算結果を出力する。
図4は実施例の動作フローチャートである。

発明の効果

0032

以上の通りであって、従来の多基底べき乗積演算においては、演算テーブル参照過程の間に自乗を含む演算過程が必ず含まれており、これが演算コスト或いは記憶領域のコストの削減を阻む原因となっていた。これに対して、この発明は、演算テーブル参照過程と自乗を含む演算過程を分離し、これに対応して最大べきの桁数に比例する中間結果保存領域を用意する構成を採用し、テーブル参照を行っている間は自乗を行わずに対応する中間結果保存領域を選択して積演算を実行するものである。ここで、大規模な多基底のべき乗の積演算において、基底の数をnとし、mをm《nなる正整数とすることにより、大規模な多基底のべき乗の積演算に必要な自乗演算の演算コストを従来の計算方法3と比較して約m/nに削減することができ、また、実行時のテーブルに必要な記憶領域のコストを従来の計算方法4と比較して約m/nに削減することができできる。

図面の簡単な説明

0033

図1群演算実行順序の実施例を説明する図。
図2ウィンドウを説明する図。
図3実施例を説明する図。
図4実施例の動作フローチャート。
図5群演算実行順序の従来例を説明する図。

--

0034

1制御装置2中間結果保存領域
3テーブル作成器 4ウィンドウ
5 テーブル 6テーブル参照器
7 群演算器8自乗および積算器

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ