(57)【要約】      （修正有）【課題】計算コストを減らし、スループットを向上させることができるスカラー倍演算装置を提供する。【解決手段】楕円曲線上の点Ｐをスカラー値ｋでスカラー倍演算するスカラー倍演算装置は、スカラー値ｋを基に第１の事前計算量を推定する最適事前計算量推定部１０１と、最適事前計算量推定部１０１により推定された第１の事前計算量で、楕円曲線上の点Ｐを基に事前計算を行う事前計算部１０２と、最適事前計算量推定部１０１により推定された第１の事前計算量を用いて、スカラー値ｋの内部表現ｍを生成する内部表現生成部１０３と、事前計算部１０２の事前計算の結果と内部表現生成部１０３により生成された内部表現ｍとを基に、楕円曲線上の点Ｐをスカラー値ｋでスカラー倍演算した結果ｋＰを出力するスカラー倍演算部１０４とを有する。【選択図】図１
2018146766.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線上の点をスカラー値でスカラー倍演算するスカラー倍演算装置であって、
前記スカラー値を基に第１の事前計算量を推定する推定手段と、
前記推定手段により推定された第１の事前計算量で、前記楕円曲線上の点を基に事前計算を行う事前計算手段と、
前記推定手段により推定された第１の事前計算量を用いて、前記スカラー値の内部表現を生成する生成手段と、
前記事前計算手段の事前計算の結果と前記生成手段により生成された内部表現とを基に、前記楕円曲線上の点を前記スカラー値でスカラー倍演算した結果を出力するスカラー倍演算手段と
を有することを特徴とするスカラー倍演算装置。
【請求項２】
前記推定手段は、前記事前計算手段の異なる事前計算量毎の内部表現のうちの０でない桁の個数に応じて、前記第１の事前計算量を推定することを特徴とする請求項１に記載のスカラー倍演算装置。
【請求項３】
前記推定手段は、前記事前計算手段の異なる事前計算量毎の内部表現のうちの０でない桁の個数と前記事前計算手段の事前計算量との和に応じて、前記第１の事前計算量を推定することを特徴とする請求項１又は２に記載のスカラー倍演算装置。
【請求項４】
前記推定手段は、前記事前計算手段の異なる事前計算量毎の内部表現のうちの０でない桁の個数と前記事前計算手段の事前計算量との和が最小になる場合の事前計算量を前記第１の事前計算量として推定することを特徴とする請求項１乃至３のいずれか１項に記載のスカラー倍演算装置。
【請求項５】
前記スカラー倍演算手段は、内部表現のうちの０でない桁の個数だけ加算を行うことを特徴とする請求項２乃至４のいずれか１項に記載のスカラー倍演算装置。
【請求項６】
前記事前計算手段は、前記推定手段により推定された第１の事前計算量だけ加算を行うことを特徴とする請求項３又は４に記載のスカラー倍演算装置。
【請求項７】
前記生成手段は、前記内部表現としてＭＯＦ表現を生成することを特徴とする請求項１乃至６のいずれか１項に記載のスカラー倍演算装置。
【請求項８】
前記事前計算手段は、前記楕円曲線上の点に対する３以上の奇数倍を計算することを特徴とする請求項１乃至７のいずれか１項に記載のスカラー倍演算装置。
【請求項９】
前記事前計算手段は、前記推定手段により推定された第１の事前計算量だけ、前記楕円曲線上の点に対する２倍値を加算する処理を繰り返すことを特徴とする請求項８に記載のスカラー倍演算装置。
【請求項１０】
前記スカラー倍演算手段は、前記内部表現の各桁が０でない場合には、前記楕円曲線上の点に対して前記各桁の値でスカラー倍した値を加算することを特徴とする請求項２乃至５のいずれか１項に記載のスカラー倍演算装置。
【請求項１１】
前記生成手段は、前記内部表現を最上位ビットから順に生成することを特徴とする請求項１乃至１０のいずれか１項に記載のスカラー倍演算装置。
【請求項１２】
前記スカラー倍演算手段は、最上位ビットから順に処理することを特徴とする請求項１乃至１１のいずれか１項に記載のスカラー倍演算装置。
【請求項１３】
前記生成手段と前記スカラー倍演算手段は、並列に処理を行うことを特徴とする請求項１乃至１２のいずれか１項に記載のスカラー倍演算装置。
【請求項１４】
前記推定手段と前記事前計算手段は、並列に処理を行うことを特徴とする請求項１乃至１３のいずれか１項に記載のスカラー倍演算装置。
【請求項１５】
楕円曲線上の点をスカラー値でスカラー倍演算するスカラー倍演算方法であって、
推定手段により、前記スカラー値を基に第１の事前計算量を推定するステップと、
事前計算手段により、前記推定された第１の事前計算量で、前記楕円曲線上の点を基に事前計算を行うステップと、
生成手段により、前記推定された第１の事前計算量を用いて、前記スカラー値の内部表現を生成するステップと、
スカラー倍演算手段により、前記事前計算の結果と前記内部表現とを基に、前記楕円曲線上の点を前記スカラー値でスカラー倍演算した結果を出力するステップと
を有することを特徴とするスカラー倍演算方法。
【請求項１６】
コンピュータを、請求項１乃至１４のいずれか１項に記載されたスカラー倍演算装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スカラー倍演算装置、スカラー倍演算方法及びプログラムに関する。
【背景技術】
【０００２】
公開鍵暗号方式として、楕円曲線暗号の普及が進んでいる。Standards for Efficient Cryptography Group（ＳＥＣＧ）は、楕円曲線暗号の商用利用を進めるため、推奨する楕円曲線パラメータをＳＥＣ ２で提供している。また、アメリカ標準技術研究所（ＮＩＳＴ）は、ｆｉｐｓ １８６−３において、楕円曲線暗号を使ったＤＳＡである、ＥＣＤＳＡを規格化している。
【０００３】
楕円曲線暗号の処理では、スカラー倍演算という計算を行う必要がある。スカラー倍演算は、ｋを整数値、Ｐを楕円曲線上の点としたとき、ｋＰを計算する演算のことである。素体を使った楕円曲線上のスカラー倍演算では、一般的にNon-Adjacent Form（ＮＡＦ）表現を使う。この表現を使ったスカラー倍演算は、２進数表現を使ったスカラー倍演算よりも少ない加算回数でｋＰを求めることができる（特許文献１参照）。
【０００４】
ＮＡＦ表現は、２ビットのウィンドウ幅で生成される場合は、各桁の値が０，１,−１のいずれかで生成される。さらに広いウィンドウ幅で生成される場合は、各桁の値の絶対値はさらに大きい値をとることができるようになる（特許文献２参照）。
【０００５】
また、ＮＡＦ表現と似た表現であるＭＯＦ表現が使われることがある。ＭＯＦ表現とは、left-to-right、すなわち、最上位ビットから順に生成することもできる表現である。スカラー倍演算のアルゴリズムとして用いられるwindow-NAFアルゴリズムは、ＮＡＦ表現を用いて計算を行うアルゴリズムだが、ＭＯＦ表現と組み合わせて計算を行うこともできる（特許文献３参照）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１３−１８６２０４号公報
【特許文献２】特開２０１３−７７３１３号公報
【特許文献３】特開２００５−３１６０３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
window-NAFアルゴリズムでは、事前計算を必要とする。必要な事前計算の量は、各アルゴリズムで使用する内部表現であるＮＡＦ表現やＭＯＦ表現のウィンドウ幅に応じて決まる。しかし、計算前にウィンドウ幅を決定する必要があるため、最適なウィンドウ幅がどのくらいなのかわからないという課題がある。また、ウィンドウ幅を１ビット増やす毎に、必要な事前計算の量が指数関数的に増加するため、ウィンドウ幅の調整が難しいという課題がある。
【０００８】
本発明の目的は、計算コストを減らし、スループットを向上させることができるスカラー倍演算装置、スカラー倍演算方法及びプログラムを提供することである。
【課題を解決するための手段】
【０００９】
本発明のスカラー倍演算装置は、楕円曲線上の点をスカラー値でスカラー倍演算するスカラー倍演算装置であって、前記スカラー値を基に第１の事前計算量を推定する推定手段と、前記推定手段により推定された第１の事前計算量で、前記楕円曲線上の点を基に事前計算を行う事前計算手段と、前記推定手段により推定された第１の事前計算量を用いて、前記スカラー値の内部表現を生成する生成手段と、前記事前計算手段の事前計算の結果と前記生成手段により生成された内部表現とを基に、前記楕円曲線上の点を前記スカラー値でスカラー倍演算した結果を出力するスカラー倍演算手段とを有する。
【発明の効果】
【００１０】
本発明によれば、計算コストを減らし、スループットを向上させることができる。
【図面の簡単な説明】
【００１１】
【図１】スカラー倍演算装置の構成例を示す図である。
【図２】ＭＯＦ表現の例を示す図である。
【図３】スカラー倍演算部の処理を示すフローチャートである。
【図４】事前計算部の処理を示すフローチャートである。
【図５】最適事前計算量推定部の処理を示すフローチャートである。
【図６】ＭＯＦ表現の生成方法を示す図である。
【図７】ＭＯＦ表現の生成アルゴリズムを示すフローチャートである。
【図８】図１の各構成要素が動作する時刻を示す図である。
【発明を実施するための形態】
【００１２】
図１は、本発明の実施形態によるスカラー倍演算装置の構成例を示す図である。スカラー倍演算装置は、セキュリティ技術の公開鍵暗号方式の一つである楕円曲線暗号の処理のために、スカラー倍演算を行う。スカラー倍演算は、ｋをスカラー値（整数値）、Ｐを楕円曲線上の点としたとき、ｋＰを計算する演算である。スカラー倍演算装置は、最適事前計算量推定部１０１と、事前計算部１０２と、内部表現生成部１０４とを有し、楕円曲線上の点Ｐをスカラー値ｋでスカラー倍演算する。スカラー倍演算装置は、スカラー値ｋ及び楕円曲線上の点Ｐを入力し、楕円曲線上の点Ｐをスカラー値ｋでスカラー倍演算した結果ｋＰを出力する。以下、スカラー倍演算装置のスカラー倍演算方法を説明する。
【００１３】
最適事前計算量推定部１０１は、スカラー値ｋを基に最適事前計算量を推定する。最適事前計算量推定部１０１で用いられるアルゴリズムの詳細は後述する。事前計算部１０２は、最適事前計算量推定部１０１によって求められた最適事前計算量の分だけ、楕円曲線上の点Ｐを基に事前計算を行い、事前計算結果を出力する。内部表現生成部１０３は、最適事前計算量推定部１０１によって求められた最適事前計算量を用いて、スカラー値ｋのＭＯＦ表現（内部表現）ｍを生成して出力する。ＭＯＦ表現の生成方法の詳細は後述する。スカラー倍演算部１０４は、事前計算部１０２の事前計算結果とＭＯＦ表現ｍと点Ｐとを基に、楕円曲線上の点Ｐをスカラー値ｋでスカラー倍演算した結果ｋＰを出力する。
【００１４】
図２は、内部表現生成部１０３により生成されるＭＯＦ表現ｍの例を示す図である。図２は、同じ値の数字を二進数表現とＭＯＦ表現で表している。二進数表現では、各桁の値を０または１として表しているが、ＭＯＦ表現では、各桁の値を０や負の数や正の数などで表すことができる。
【００１５】
図３は、スカラー倍演算部１０４のアルゴリズムを表すフローチャートである。スカラー倍演算部１０４は、window-NAFアルゴリズムを使ってｋＰを計算する演算部である。具体的には、スカラー倍演算部１０４は、スカラー値ｋのＭＯＦ表現ｍの各ビットの値に応じて、楕円曲線上の点の加算と２倍算を行うことで、ｋＰを求める。ステップＳ３０１では、スカラー倍演算部１０４は、変数Ｑの初期化を行うため、計算の途中結果を表す変数Ｑに∞を代入する。ここで、∞は、楕円曲線上の加算において０を表す点である。すなわち、Ｐ＋∞＝Ｐが成り立つ。次に、ステップＳ３０２では、スカラー倍演算部１０４は、ループ変数であるｉに、初期値である（スカラー値ｋのＭＯＦ表現ｍのビット長）の値を代入する。次に、ステップＳ３０３では、スカラー倍演算部１０４は、ループ変数ｉの更新を行うため、ループ変数ｉにｉ−１を代入する。次に、ステップＳ３０４では、スカラー倍演算部１０４は、変数Ｑの値を２倍する。つまり、スカラー倍演算部１０４は、ループ１回毎に楕円曲線上の点の二倍算を変数Ｑに対して行う。次に、ステップＳ３０５では、スカラー倍演算部１０４は、ＭＯＦ表現ｍのｉビット目の値ｍiが０であるか否かを判定し、０であると判定した場合にはステップＳ３０７に処理を進め、０でないと判定した場合にはステップＳ３０６に処理を進める。ステップＳ３０６では、スカラー倍演算部１０４は、楕円曲線上の点の加算を行うため、ｍiＰを途中結果Ｑに加え、ステップＳ３０７に処理を進める。具体的には、ｍiＰの点は事前計算部１０２で事前に求められているはずなので、スカラー倍演算部１０４は、その事前結果ｍiＰをＱに加算する。ステップＳ３０７では、スカラー倍演算部１０４は、ループ変数ｉが０より大きいか否かを判定し、０より大きいと判定した場合にはステップＳ３０３に処理を戻し、０より大きくないと判定した場合にはステップＳ３０８に処理を進める。ステップＳ３０８では、スカラー倍演算部１０４は、変数Ｑの値をｋＰの計算結果として出力して終了する。
【００１６】
図３の中では、ステップＳ３０４の２倍算とステップＳ３０６の加算が重い処理である。このうち、ステップＳ３０６の処理は、値ｍiが０であればスキップされる。スカラー倍演算部１０４は、ＭＯＦ表現ｍのうちの０でない桁の個数だけステップＳ３０６の加算を行う。すなわち、スカラー倍演算部１０４は、ＭＯＦ表現ｍの各桁ｍiが０でない場合には、楕円曲線上の点Ｐに対して各桁ｍiの値でスカラー倍した値ｍiＰを加算する。よって、スカラー倍演算１０４の演算コストは、ステップＳ３０６の実行回数が多いほど大きくなる。
【００１７】
図４は、事前計算部１０２のアルゴリズムを表すフローチャートである。事前計算部１０２が行う処理は、楕円曲線上の点Ｐに対する３以上の奇数倍の点３Ｐ，５Ｐ，７Ｐ，・・・等を事前計算として求めておくことである。ステップＳ４０１では、事前計算部１０２は、変数ＱとＲを初期化するため、変数Ｑに点２Ｐを代入し、変数Ｒに点Ｐを代入する。次に、ステップＳ４０２では、事前計算部１０２は、ループ変数ｉに初期値１を代入する。次に、ステップＳ４０３では、事前計算部１０２は、事前計算１回分の処理を行うため、ループ１周前の事前計算結果Ｒの点に変数Ｑ（＝２Ｐ）を加算する。変数Ｑは、楕円曲線上の点Ｐに対する２倍値２Ｐである。次に、ステップＳ４０４では、事前計算部１０２は、ステップＳ４０３で求めた計算結果Ｒを（２ｉ＋１）Ｐの事前計算結果として登録する。次に、ステップＳ４０５では、事前計算部１０２は、ループ変数ｉにｉ＋１を代入する。次に、ステップＳ４０６では、事前計算部１０２は、ループ変数ｉを参照し、事前計算できる個数の上限に達し、事前計算が完了したか否かを判定し、完了していないと判定した場合にはステップＳ４０３に処理を戻し、完了したと判定した場合には処理を終了する。これにより、事前計算部１０２は、楕円曲線上の点Ｐに対する３以上の奇数倍の点３Ｐ，５Ｐ，７Ｐ，・・・等を計算することができる。
【００１８】
図４の中では、ステップＳ４０１の２倍算とステップＳ４０３の加算が重い処理である。このうち、ステップＳ４０３の加算は、事前計算量の分だけ繰り返し実行される。よって、事前計算部１０２の演算コストは、ステップＳ４０３の実行回数が多いほど大きくなる。
【００１９】
事前計算部１０２の演算コストとスカラー倍演算１０４の演算コストが全体の処理コストになるが、図３及び図４の説明で、これらの演算コストは、ステップＳ３０６とＳ４０３がそれぞれ何回実行されるかに影響されることがわかる。ここで、ステップＳ３０６とＳ４０３はどちらも加算処理であるため、ステップＳ３０６とＳ４０３の演算コストは等しい。よって、全体の演算コストを最小にする事前計算量を見積もるために、ステップＳ３０６の実行回数とステップＳ４０３の実行回数との和が最小になるような事前計算量を、最適事前計算量推定部１０１で求める。
【００２０】
図５は、最適事前計算量推定部１０１のアルゴリズムを表すフローチャートである。ステップＳ５０１では、最適事前計算量推定部１０１は、暫定の最適事前計算量を保持するための変数ｒと、そのときのコストを保持するための変数ｍｉｎ＿ｃｏｓｔを初期化するため、変数ｒに０を代入し、変数ｍｉｎ＿ｃｏｓｔに∞を代入する。次に、ステップＳ５０２では、最適事前計算量推定部１０１は、ループ変数ｉを初期化するため、ループ変数ｉに事前計算量の最小値を代入する。次に、ステップＳ５０３では、最適事前計算量推定部１０１は、事前計算量をｉとして、Ｐ，３Ｐ，５Ｐ，・・・，（２ｉ＋１）Ｐを事前計算として用いる場合のｋのＭＯＦ表現ｍの０でない桁の個数を変数ｃｏｕｎｔに代入する。このとき、変数ｉはステップＳ３０６の実行回数を表しており、変数ｃｏｕｎｔはステップＳ４０３の実行回数を表している。変数ｃｏｕｎｔに代入される値の求め方は、後述する。次に、ステップＳ５０４では、最適事前計算量推定部１０１は、演算コストが最小であるかを判定するため、ステップＳ３０６の実行回数である変数ｉとステップＳ４０３の実行回数である変数ｃｏｕｎｔとの和が変数ｍｉｎ＿ｃｏｓｔより小さいか否かを判定する。そして、最適事前計算量推定部１０１は、変数ｍｉｎ＿ｃｏｓｔより小さいと判定した場合にはステップＳ５０５に処理を進め、変数ｍｉｎ＿ｃｏｓｔより小さくないと判定した場合にはステップＳ５０６に処理を進める。ステップＳ５０５では、最適事前計算量推定部１０１は、事前計算量ｉを暫定の最適事前計算量として変数ｒに代入し、変数ｉと変数ｃｏｕｎｔとの和を変数ｍｉｎ＿ｃｏｓｔに代入する。次に、ステップＳ５０６では、最適事前計算量推定部１０１は、ループ変数ｉにｉ＋１を代入する。次に、ステップＳ５０７では、最適事前計算量推定部１０１は、ループ変数ｉが事前計算量の最大値以下であるか否かを判定する。そして、最適事前計算量推定部１０１は、最大値以下であると判定した場合にはステップＳ５０３に処理を戻し、最大値以下でないと判定した場合にはステップＳ５０８に処理を進める。ステップＳ５０８では、最適事前計算量推定部１０１は、最適事前計算量として変数ｒの値を出力し終了する。事前計算部１０２は、ステップＳ４０６において、最適事前計算量ｒとループ変数ｉを比較し、事前計算量を決める。事前計算部１０２は、最適事前計算量推定部１０１により推定された最適事前計算量ｒだけ、ステップＳ４０３の加算を行う。
【００２１】
以上のように、最適事前計算量推定部１０１は、事前計算１０２の異なる事前計算量毎のＭＯＦ表現ｍのうちの０でない桁の個数ｃｏｕｎｔと事前計算部１０２の事前計算量ｉとの和が最小になる場合の事前計算量を最適事前計算量ｒとして推定する。
【００２２】
図６は、ステップＳ５０３及び内部表現生成部１０３のＭＯＦ生成アルゴリズムを説明するための概要図を表している。二進数表現６０１は、あるスカラー値ｋを二進数で表している。中間表現６０２は、２ｋ−ｋの値を表している。２ｋ−ｋはｋと同じ値であるため、二進数表現６０１と中間表現６０２は同じ値を表していることになる。ただし、中間表現６０２では、２ｋ−ｋの計算で各桁の繰り下がりは行わない。すなわち、ある桁の値が、２ｋでは“０”、ｋでは“１”のとき、中間表現６０２においてこの桁は“−１”となる。ＭＯＦ表現６０３は、中間表現６０２の複数の桁の値を１つの桁にまとめて表現したものになっている。このような手順により、内部表現生成部１０３は、スカラー値ｋについて、二進数表現６０１をＭＯＦ表現６０３に変換する。
【００２３】
図７は、ステップＳ５０３及び内部表現生成部１０３のＭＯＦ生成アルゴリズムを表すフローチャートである。なお、スカラー値ｋのビット長をｕと表した時、ｂu，ｂu-1，・・・，ｂ1，ｂ0は、中間表現６０２の形式で表されたｋの各ビットの値を表している。また、ｍu，ｍu-1，・・・，ｍ1，ｍ0は、本アルゴリズムで生成するＭＯＦ表現ｍの各ビットを表している。ステップＳ７０１では、内部表現生成部１０３は、ｋのビット長の値を変数ｊに代入し、ｍjの暫定値を保持する変数ｔに０を代入し、ＭＯＦ表現の０でない桁の個数を表す変数ｃｏｕｎｔに０を代入する。変数ｊは、次に出力すべき桁を表す変数である。変数ｃｏｕｎｔの値は、ステップＳ５０３で利用するものである。次に、ステップＳ７０２では、内部表現生成部１０３は、ループ変数ｉにｋのビット長を代入する。次に、ステップＳ７０３では、内部表現生成部１０３は、ｍjの暫定値ｔが０であるか否かを判定し、０であると判定した場合にはステップＳ７０４に処理を進め、０でないと判定した場合にはステップＳ７０７に処理を進める。ステップＳ７０４では、内部表現生成部１０３は、中間表現のｉビット目の桁ｂiが０であるか否かを判定し、０であると判定した場合にはステップＳ７０５に処理を進め、０でないと判定した場合にはステップＳ７０６に処理を進める。ステップＳ７０５では、内部表現生成部１０３は、暫定値ｔ及び中間表現ｂiが共に０であるため、ｍjに０を代入し、変数ｊにｊ−１を代入し、ステップＳ７１１に処理を進める。ステップＳ７０６では、内部表現生成部１０３は、中間表現ｂiが０ではないため、暫定値ｔにｂiを代入し、ステップＳ７１１に処理を進める。ステップＳ７０７では、内部表現生成部１０３は、中間表現のｉビット目の桁ｂiが０であるか否かを判定し、０であると判定した場合にはステップＳ７１１に処理を進め、０でないと判定した場合にはステップＳ７０８に処理を進める。ステップＳ７０８では、内部表現生成部１０３は、暫定値ｔが０でなく、中間表現ｂiも０でないため、暫定値ｔの更新をするべきか、または暫定値ｔをｍjとして出力するべきか否かを判定する。具体的には、暫定値ｔを更新した場合の値は（２j-iｔ＋ｂi）であるが、｜２j-iｔ＋ｂi｜Ｐの点を事前計算として既に持っている場合に限り、暫定値ｔを更新できる。そこで、内部表現生成部１０３は、最適事前計算量推定部１０１が出力する最適事前計算量ｒを基に、｜２j-iｔ＋ｂi｜Ｐの点を事前計算として既に持っているか否かを判定する。そして、内部表現生成部１０３は、その点を持っている場合にはステップＳ７０９に処理を進め、その点を持っていない場合にはステップＳ７１０に処理を進める。ステップＳ７０９では、内部表現生成部１０３は、ｍj，ｍj-1，・・・，ｍi+1を０として出力し、暫定値ｔに（２j-iｔ＋ｂi）を代入し、変数ｊにｉを代入し、ステップＳ７１１に処理を進める。Ｓ７１０では、内部表現生成部１０３は、暫定値ｔをｍjの値として出力し、変数ｃｏｕｎｔにｃｏｕｎｔ＋１を代入し、ｍj-1，ｍj-2，・・・，ｍi+1を０で出力し、暫定値ｔにｂiを代入し、変数ｊにｉを代入し、ステップＳ７１１に処理を進める。ステップＳ７１１では、内部表現生成部１０３は、ループ変数ｉにｉ−１を代入���る。次に、ステップＳ７１２では、内部表現生成部１０３は、ループ変数ｉが０以上であるか否かを判定し、０以上であると判定した場合にはステップＳ７０３に処理を戻し、０以上でないと判定した場合にはステップＳ７１３に処理を進める。ステップＳ７１３では、内部表現生成部１０３は、まだ出力していない暫定値ｔがあるか否かを確認するため、変数ｊが０以上であるか否かを判定し、０以上である場合にはステップＳ７１４に処理を進め、０以上でない場合には処理を終了する。ステップＳ７１４では、内部表現生成部１０３は、暫定値ｔをｍjの値として出力し、変数ｃｏｕｎｔにｃｏｕｎｔ＋１を代入し、残りの桁ｍj-1，ｍj-2，・・・，ｍ0の値として０を出力し、処理を終了する。
【００２４】
図８は、図１の最適事前計算量推定部１０１と事前計算部１０２と内部表現生成部１０３とスカラー倍演算部１０４が動作する時刻を表す図である。まず初めに、最適事前計算量推定部１０１と事前計算部１０２は、同時に動作を始め、並列に処理を行う。最適事前計算量推定部１０１が最適事前計算量ｒを決定し、その最適事前計算量ｒまで事前計算部１０２が事前計算を完了すると、内部表現生成部１０３とスカラー倍演算部１０４は、同時に動作を始め、並列に処理を行う。ＭＯＦ生成アルゴリズムとスカラー倍演算アルゴリズムはどちらも、最上位ビットから順に（left-to-rightで）処理を行うため、同期しながら処理を行う。内部表現生成部１０３はＭＯＦ表現ｍを最上位ビットから順に生成し、スカラー倍演算部１０４は最上位ビットから順に処理する。
【００２５】
以上のように、最適事前計算量推定部１０１は、事前計算の量として様々な量を仮定してＭＯＦ表現を生成した場合の各量に応じたｋＰの計算コストを見積もり、ｋＰの計算コストが最小になる最適事前計算量ｒを求める。具体的には、最適事前計算量推定部１０１は、スカラー値ｋをＭＯＦ表現で表した時の０でない桁の個数と必要な事前計算量の個数の和を計算コストと考え、これが最小になる最適事前計算量ｒを求める。内部表現生成部１０３は、ウィンドウ幅ではなく、最適事前計算量ｒを基にＭＯＦ表現ｍを生成する。スカラー倍演算装置は、ＭＯＦ表現ｍを使って最適事前計算量ｒを推定し、スカラー倍演算を行うことで、最小の計算コストでｋＰを求めることができるので、スループットが向上する。
【００２６】
（その他の実施形態）
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサがプログラムを読み出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【００２７】
なお、上記実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【００２８】
１０１  最適事前計算量推定部、１０２  事前計算部、１０３  内部表現生成部、１０４  スカラー倍演算部
【図１】
2018146766.tif 000003
【図２】
2018146766.tif 000004
【図３】
2018146766.tif 000005
【図４】
2018146766.tif 000006
【図５】
2018146766.tif 000007
【図６】
2018146766.tif 000008
【図７】
2018146766.tif 000009
【図８】
2018146766.tif 000010