(57)【要約】【課題】剰余乗算器を用い、剰余乗算器が処理可能なビット長を越えるデータの剰余乗算を処理する剰余乗算処理装置を提供する。【解決手段】剰余乗算処理装置において、剰余乗算器１１３が処理できるビット長にあわせ、剰余乗算の対象データを分解する。剰余乗算器１１３の出力結果を用いて作成した、剰余乗算の計算に必要なデータを記憶装置１２３へ格納する。記憶領域の利用量が最小となるよう、一時データを逐次的に特定の記憶領域へ蓄積する。記憶領域へ蓄積された一時データを合わせ、剰余乗算器１１３が処理できるビット長を越えた剰余乗算の解を作成する。【選択図】図１
2011007820.tif 000002
【特許請求の範囲】
【請求項１】
剰余乗算を計算する剰余乗算器と、データを格納する記憶領域をもつ記憶装置を有し、前記剰余乗算器が処理できるビット長を越えた剰余乗算を計算する剰余乗算処理装置であって、
前記剰余乗算処理装置が計算過程で作成するデータを格納する前記記憶領域を指定する出力指示部を備えたことを特徴とする剰余乗算処理装置。
【請求項２】
請求項１記載の剰余乗算処理装置において、
前記剰余乗算処理装置が計算過程で作成するデータを指定された前記記憶領域へ格納する移動部を備えたことを特徴とする剰余乗算処理装置。
【請求項３】
請求項２記載の剰余乗算処理装置において、
前記剰余乗算処理装置の計算過程で格納されたデータから情報を前記記憶領域へ蓄積する第１の処理部を備えたことを特徴とする剰余乗算処理装置。
【請求項４】
請求項３記載の剰余乗算処理装置において、
前記剰余乗算器の入力に前記記憶領域が格納するデータの記憶領域を指定する入力部を備えたことを特徴とする剰余乗算処理装置。
【請求項５】
請求項４記載の剰余乗算処理装置において、
前記剰余乗算器が実装する剰余乗算の種類に応じて、前記剰余乗算器がモンゴメリ乗算を実装する場合には、前記剰余乗算器が処理できるビット長を越えたモンゴメリ乗算を計算し、前記剰余乗算器が古典的な剰余乗算を実装する場合には、前記剰余乗算器が処理できるビット長を越えた古典的な剰余乗算を計算する２倍剰余乗算部を備えたことを特徴とする剰余乗算処理装置。
【請求項６】
請求項４記載の剰余乗算処理装置において、
前記剰余乗算器が実装する剰余乗算の種類とは異なる、前記剰余乗算器が処理できるビット長を越えた剰余乗算を計算する２倍剰余乗算部を備えたことを特徴とする剰余乗算処理装置。
【請求項７】
請求項６記載の剰余乗算処理装置において、
前記剰余乗算器が実装する剰余乗算の種類とは異なる、剰余乗算の商を計算する第２の処理部を備えることを特徴とする剰余乗算処理装置。
【請求項８】
請求項５または７記載の剰余乗算処理装置において、
前記剰余乗算器が実装する剰余乗算の種類にあわせ、前記剰余乗算器が処理できるビット長を越えたデータを、前記剰余乗算器が処理できるビット長以下にデータの形式を変更する第３の処理部を備えたことを特徴とする剰余乗算処理装置。
【請求項９】
請求項８記載の剰余乗算処理装置において、
前記剰余乗算処理装置が計算過程で作成するデータのビット長を、前記剰余乗算器が処理できるデータのビット長以下に調整する第４の処理部を備えたことを特徴とする剰余乗算処理装置。
【請求項１０】
請求項５または６記載の剰余乗算処理装置において、
前記２倍剰余乗算部により、前記剰余乗算器が処理できるビット長を越えた剰余乗算を計算し、その計算結果に基づいて、暗号技術に基づく認証処理またはデータ暗号化処理を行うことを特徴とする剰余乗算処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュリティ技術に用いられる剰余乗算処理装置に関し、特にＩＣカード、ＰＤＡ、ＴＰＭ等の小型端末から、ストレージ装置やサーバ装置等の大型機器まで、各装置が搭載する暗号機器上の実装技術に関する。
【背景技術】
【０００２】
＜高速な剰余乗算の必要性＞
ＲＳＡ暗号などの公開鍵暗号では、重い計算処理である、べき乗の剰余乗算を計算する必要がある。そのため、高性能なＣＰＵを搭載できないＩＣカードや、処理が集中するストレージ装置やサーバ装置では、剰余乗算を処理するハードウェア（以降、剰余乗算器と呼ぶ）を用い、処理の重いべき乗の剰余乗算を高速にハードウェアで処理する。特に、古典的な剰余乗算やモンゴメリ乗算は、効率的な計算手法であり、多くの剰余乗算器がそれらの計算手法を採用している。
【０００３】
＜ＲＳＡ暗号の復号化＞
２０４８ビット等の、ビット長の長いＲＳＡ暗号を高速に処理するため、剰余乗算の演算処理を分割し、高速に剰余乗算を計算する手段が知られている。この手法で秘密鍵の情報を必要とする手法は古くから知られており、ＲＳＡ暗号の復号化（または署名生成）処理にて利用できる。
【０００４】
＜ＲＳＡ暗号の暗号化＞
秘密鍵の情報を用いずに、剰余乗算の演算処理を分割する手法も研究されている。ＲＳＡ暗号の暗号化（または署名検証）処理では、復号化（または署名生成）処理とは異なり、秘密の情報を用いる必要がない。暗号化（または署名検証）処理にも対応でき、剰余乗算器が処理できるビット長を越えた剰余乗算を、剰余乗算器を用い、高速に計算する研究が報告されている。従来の研究報告では、剰余乗算器が古典的な剰余乗算を実装する場合（非特許文献１と非特許文献２）と、モンゴメリ乗算を実装する場合（非特許文献３）に大別できる。
【非特許文献１】Ｗ．  Ｆｉｓｃｈｅｒ，  Ｊ．−Ｐ．  Ｓｅｉｆｅｒｔ：  “Ｉｎｃｒｅａｓｉｎｇ  ｔｈｅ  ｂｉｔｌｅｎｇｔｈ  ｏｆ  ｃｒｙｐｔｏ−ｃｏｐｒｏｃｅｓｓｏｒｓ”  ＣＨＥＳ２００２，  ｖｏｌ．  ２５２３  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．  ７１−−８１  （２００３）．
【非特許文献２】Ｂｅｎｏｉｔ  Ｃｈｅｖａｌｌｉｅｒ−Ｍａｍｅｓ，  Ｍａｒｃ  Ｊｏｙｅ，  ａｎｄ  Ｐａｓｃａｌ  Ｐａｉｌｌｉｅｒ：  “Ｆａｓｔｅｒ  Ｄｏｕｂｌｅ−Ｓｉｚｅ  Ｍｏｄｕｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  Ｆｒｏｍ  Ｅｕｃｌｉｄｅａｎ  Ｍｕｌｔｉｐｌｉｅｒｓ”  ＣＨＥＳ２００３，  ｖｏｌ．  ２７７９  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．  ２１４−２２７  （２００３）．
【非特許文献３】Ｍａｓａｙｕｋｉ  Ｙｏｓｈｉｎｏ，  Ｋａｔｓｕｙｕｋｉ  Ｏｋｅｙａ，  ａｎｄ  Ｃａｍｉｌｌｅ  Ｖｕｉｌｌａｕｍｅ．  Ｕｎｂｒｉｄｌｅｔｈｅ  Ｂｉｔ−Ｌｅｎｇｔｈ  ｏｆ  ａ  Ｃｒｙｐｔｏ−Ｃｏｐｒｏｃｅｓｓｏｒ  ｗｉｔｈ  Ｍｏｎｔｇｏｍｅｒｙ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ．Ｉｎ  Ｐｒｅｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＳＡＣ２００６  ｐｐ．  １８４−１９８（２００６）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１、非特許文献２、非特許文献３に紹介された従来技術による実現手法には、以下の課題がある。
【０００６】
課題１：計算に必要な記憶容量が多い。
【０００７】
課題１は、非特許文献１、非特許文献２、非特許文献３に共通の課題である。
【０００８】
剰余乗算またはべき乗の剰余乗算を高速に実現するため、計算過程で一時的なデータを格納する記憶領域が必要である。しかし、この記憶領域は、一般に、高速アクセスを可能とする、高価で容量が限られた記憶領域を用いる。前記の文献いずれにおいても、利用する記憶容量の最適化が検討されておらず、十分な容量の記憶領域を持たない暗号機器または演算に利用できる記憶領域が限定された暗号機器では、従来の実現手法が利用できない。
【０００９】
課題２：剰余乗算器が古典的な剰余乗算を実装する場合、剰余乗算器が処理できるビット長の２倍の剰余乗算を実行できない。
【００１０】
非特許文献１、非特許文献２では、剰余乗算器が古典的な剰余乗算を実装する場合を主対象に、剰余乗算器が処理できるビット長の２倍の剰余乗算を実現する手法を紹介している。紹介される手法では、正の整数をｗとすると、最大ｗビットのビット長の剰余乗算を処理できる剰余乗算器を用い、２ｗビットの剰余乗算を実行する際には、ｗビットのデータ同士を加算または減算した結果を、剰余乗算器に入力する必要がある。しかし、演算後のデータのビット長はｗ＋α（αは正の整数）であり、剰余乗算器の処理できる最大ビット長ｗを越えてしまうため、剰余乗算器を利用できなくなってしまう。
【００１１】
課題３：剰余乗算器がモンゴメリ乗算を実装する場合、剰余乗算器が処理できるビット長の２倍の剰余乗算を実行するには、大きな計算量を要する補正処理が必要である。
【００１２】
非特許文献３では、剰余乗算器がモンゴメリ乗算を実装する場合を主対象に、剰余乗算器が処理できるビット長の２倍の剰余乗算を実現する手法を紹介する。紹介される手法では、データの加算または減算した結果が剰余乗算器に入力できるビット長（ｗとする）を越えるとき、ｗビットのデータの加算または減算により、剰余乗算器に入力できるようデータのビット長を減らし、剰余乗算器が出力するデータに対し、再びｗビットのデータの加算または減算を行って、ｗを越えたビット長のデータの計算結果を得ている。そのため、ｗビットの加算または減算に係る計算処理が必要であり、全体の処理が遅くなってしまう。
【００１３】
本発明の目的は、上記の課題を克服し、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越えるデータの剰余乗算を処理する剰余乗算処理装置を提供することにある。
【００１４】
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１５】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。
【００１６】
すなわち、代表的なものの概要は、剰余乗算処理装置が計算過程で作成するデータを格納する記憶領域を指定する出力指示部を備えたものである。
【発明の効果】
【００１７】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。
【００１８】
すなわち、代表的なものによって得られる効果は、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算が処理できる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態において、同一の部材には原則として同一の符号を付け、繰り返しの説明は省略する。
【００２０】
＜本発明の概要＞
本発明では、剰余乗算を用いた剰余乗算を行う剰余乗算器において、剰余乗算器が許容できる剰余乗算のビット長を越える剰余乗算を実施する。
【００２１】
また、本発明では、対象とするディジタル化されたデータをメッセージと呼ぶ。本発明では、剰余乗算器が処理できるよう、入力された剰余乗算の対象となるメッセージを分解し、剰余乗算器に適した形式にメッセージを変換する。
【００２２】
さらに、変換されたメッセージを、剰余乗算器に入力できるサイズに合わせて変換した後、メモリ等の記憶領域に出力する。剰余乗算器はメッセージを記憶領域から読み出し、剰余乗算を実行する。得られた剰余乗算の剰余から、剰余乗算の種類に基づく、剰余乗算の商と剰余を求める。
【００２３】
剰余乗算の商とは、剰余乗算に関するある定義した式を満たすメッセージを指し、剰余乗算の剰余とは、剰余乗算器が実装する剰余乗算が出力するメッセージを指す。剰余乗算器のビット長を越えた剰余乗算を計算するため、剰余乗算器を用いて、剰余乗算の商と剰余の複数回の計算が必要であるが、全ての剰余と商を個別に保存しておく必要は無い。
【００２４】
そこで、メッセージを格納する適当な記憶領域を用意し、計算中に、用意した記憶領域に逐次的に剰余乗算の商と剰余の情報を蓄積する。蓄積した記憶領域内の情報を合成すると、最終的に剰余乗算器の処理できるビット長を越えた剰余乗算の解となるメッセージが得られる。
【００２５】
（実施の形態１）
＜剰余乗算処理装置を適用した通信システムの全体構成＞
図１により、本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムの全体構成について説明する。なお、図１に示す通信システムの全体構成は、後述する実施の形態２、５においても基本的に共通である。図１は本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムの全体構成を示す構成図である。
【００２６】
図１において、通信システムは、ネットワーク１５１によってコンピュータＡ１０１とコンピュータＢ１０２が接続されている。
【００２７】
コンピュータＡ１０１は、コンピュータ外部とのメッセージ入出力を行なう入出力インタフェース１１１、メッセージの変換処理(暗号処理も含む）を担当する処理装置１２１を装備する。処理装置１２１は、さらにメッセージの演算処理を担当する演算装置１２２と、メッセージを格納する記憶装置１２３に分けられる。
【００２８】
例えば、記憶装置１２３に格納されたプログラムを演算装置１２２が実行し、剰余乗算処理装置が含まれる処理装置１２１を実現する。演算装置１２２はＣＰＵ１１２や剰余乗算器１１３などの演算装置１２２から構成され、記憶装置１２３は揮発性のメモリであるＲＡＭ１３１、ＲＡＭ１４１、不揮発性のメモリであるＥＥＰＲＯＭ１３２、ＲＯＭ１３３から構成される。
【００２９】
ＣＰＵ１１２は、記憶装置１２３に対しメッセージの読みだし、書き込み等が処理できる。例えば、ＲＯＭ１３３にプログラム、ＥＥＰＲＯＭ１３２にプログラムに入力するメッセージ、ＲＡＭ１３１またはＲＡＭ１４１にプログラムの実行中に必要なメッセージを格納し、ＣＰＵ１１２はプログラムとメッセージを読み出し、プログラムの実行中にメッセージの書き込み等を実行する。
【００３０】
剰余乗算器１１３は、処理できるメッセージの最大のビット長が定められた、剰余乗算を実行する計算装置またはプログラムであり、ＲＡＭ１４１に格納されたメッセージのみにアクセスできる。剰余乗算器１１３は、ＲＡＭ１４１の固定領域に格納されたメッセージを、剰余乗算の乗数、被乗数、法とみなし、実装する剰余乗算（モンゴメリ乗算、古典的な剰余乗算など）に基づき、剰余乗算の演算結果（剰余）をＲＡＭ１４１に出力する。
【００３１】
実施の形態１と後述する実施の形態５では剰余乗算器１１３がモンゴメリ乗算を実装する場合を、後述する実施の形態２では剰余乗算器１１３が古典的な剰余乗算を実装する場合を想定する。
【００３２】
どのメッセージが剰余乗算の乗数、被乗数、法に該当するかを剰余乗算器１１３が判別できるよう、ＲＡＭ１４１内の記憶領域はラベル付けされており、乗数を入力する記憶領域をＸＡ、被乗数を入力する記憶領域をＸＢ、法を入力する記憶領域をＸＮ、剰余乗算器１１３が計算過程で利用する記憶領域をＸＷ、計算結果を出力する記憶領域をＸＲと呼ぶ。
【００３３】
従って、剰余乗算器１１３はＸＡに入力されたメッセージを乗数、ＸＢに入力されたメッセージを被乗数、ＸＮに入力されたメッセージを法とみなし、剰余乗算の演算結果（剰余）をＸＲに出力する。これらのラベル付けは固定でも、可変でも良く、また、各ラベルが指定する記憶領域が重なっていて（例えば、ＸＲとＸＡが指す記憶領域が同一である、など）もよい。
【００３４】
なお、剰余乗算器１１３は、最大ｗ＋ｈ（ｗは正の整数、ｈは０以上ｗ未満の整数）ビットのメッセージに対する剰余乗算を処理できるとする。
【００３５】
コンピュータＡ１０１内のプログラムは、予め、コンピュータＡ１０１内の記憶装置１２３に格納されていても良く、必要な際に入出力インタフェース１１１を介して接続するコンピュータ、または当該コンピュータが利用可能な物理媒体を介して上記記憶装置１２３に導入されてもよい。物理媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波やディジタル信号）を指す。
【００３６】
なお、図１示す構成において、コンピュータＡ１０１は、外部への入出力用に、キーボードやモニターと接続していてもよい。また、コンピュータＡ１０１内の演算装置１２２の構成に、乗算を実行する乗算器を加えても良く、乗算器を剰余乗算器の代わりとして用いても良い。
【００３７】
コンピュータＢ１０２は、コンピュータＡ１０１と同様の、入出力インタフェース１１１、処理装置１２１から構成される。
【００３８】
＜全体処理＞
次に、図２により、本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置１２１が行う全体処理について説明する。図２は本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置が行うメッセージの受け渡しの様子を示したシーケンス図であり、本発明の実施の形態１に係る剰余乗算処理装置の演算処理の対象はメッセージとして取り扱われている。メッセージは、ディジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。なお、図２に示すシーケンス図は、後述する各実施の形態においても共通である。
【００３９】
データ処理部１１５は、入出力インタフェース１１１あるいは記憶装置１２３を介してメッセージが入力されると（Ｓ２０１）、入力されたメッセージのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるようにメッセージを区切る。また、短い場合には、パディング処理により、メッセージを予め定めたビット長となるように設定する。以下、所定のビット長として２ｗビットに区切られている部分メッセージ（これ以降、部分メッセージをメッセージと呼ぶ）について説明する。ただし、ｗは正の整数とする。
【００４０】
データ処理部１１５は、メッセージを２倍剰余乗算部１１６に出力する（Ｓ２０２）。
【００４１】
２倍剰余乗算部１１６では、まず、入力されたメッセージを剰余乗算器１１３が実装する剰余乗算（モンゴメリ乗算、古典的な剰余乗算など）に適した形式に変換し、剰余乗算器１１３を用い、２ｗビットの剰余を計算する。２倍剰余乗算部１１６は、剰余乗算器１１３が実装する剰余乗算に適した形式からメッセージをデータ処理部１１５へ入力時の整数表現に変換し、データ処理部１１５へ出力する（Ｓ２０３）。
【００４２】
データ処理部１１５では、２ｗビットのメッセージを、入出力インタフェース１１１または記憶装置１２３へ出力する（Ｓ２０４）。
【００４３】
なお、データ処理部１１５と２倍剰余乗算部１１６のメッセージの受け渡しは、記憶装置１２３へのメッセージの書き込みと読み出し、またはネットワーク１５１を用いる。
【００４４】
＜２倍剰余乗算部の機能ブロック＞
次に、図３により、本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の２倍剰余乗算部１１６の構成について説明する。図３は本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の２倍剰余乗算部の構成を示す機能ブロック図である。なお、図３に示す機能ブロック図は、後述する各実施の形態においても共通である。
【００４５】
図３において、２倍剰余乗算部１１６は、表現処理部３０１、入出力処理部３０２、剰余処理部３０３、共通部３０４からなる。表現処理部３０１は、分割部３１１、合成部３１２からなる。入出力処理部３０２は、入力部３２１、補正部３２２、出力指示部３２３、蓄積部３２４からなる。剰余処理部３０３は、剰余乗算器取扱部３３１、商演算部３３２、移動部３３３、法変更部３３４、乗数変更部３３５からなる。共通部３０４は、加減乗算部３４１、剰余計算部３４２、条件判定部３４３からなる。
【００４６】
表現処理部３０１、入出力処理部３０２、剰余処理部３０３については、それぞれ後述する各実施の形態毎に説明することとし、ここでは共通部３０４について説明する。共通部３０４は、表現処理部３０１、入出力処理部３０２、剰余処理部３０３から呼び出せる共通の機能の集合である。
【００４７】
加減乗算部３４１は、加算、減算、乗算などの基本演算機能を有する。加減乗算部３４１は、記憶装置１２３に格納された、指定された二つのメッセージを入力としてみなし、加算実行時には二つのメッセージの値を加算した値をもつメッセージを作成し、減算実行時には一番目のメッセージの値から二番目のメッセージを減算した値をもつメッセージを作成し、乗算実行時には二つのメッセージの積の値をもつメッセージを作成し、指定された記憶装置１２３の記憶領域へ作成したメッセージを出力する。
【００４８】
剰余計算部３４２は、記憶装置１２３に格納された、指定された二つのメッセージを入力としてみなし、一番目のメッセージの値を二番目のメッセージの値で割った時の剰余の値をもつメッセージを作成し、指定された記憶装置１２３の記憶領域へ作成したメッセージを出力する。条件判定部３４３は、メッセージの値がある条件を満たすか否かを判定し、その判定結果をメッセージの出力元の機能ブロックへ出力する。
【００４９】
なお、蓄積部３２４と共通部３０４にて第１の処理部を構成し、剰余処理部３０３と共通部３０４にて第２の処理部を構成し、分割部３１１と共通部３０４にて第３の処理部を構成し、補正部３２２と共通部３０４にて第４の処理部を構成する。
【００５０】
以下では、各実施の形態において、コンピュータＡ１０１の２倍剰余乗算部１１６の処理の詳細を中心に説明する。
【００５１】
＜実施の形態１の概要＞
本実施の形態では、剰余乗算器１１３がモンゴメリ乗算を実装する場合、２倍剰余乗算部１１６が、２ｗビットからなるメッセージを対象に、モンゴメリ乗算に基づく剰余乗算を計算する第１の計算方法について説明する。ただし、ｗは正の整数とする。
【００５２】
＜２倍剰余乗算部の処理の概要＞
次に、図４により、本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の２倍剰余乗算部１１６の処理について説明する。図４は本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の２倍剰余乗算部の処理を示すシーケンス図であり、２倍剰余乗算部１１６の機能ブロックである表現処理部３０１、入出力処理部３０２、剰余処理部３０３のメッセージの受け渡しの様子を示している。
【００５３】
まず、表現処理部３０１へメッセージが入力される（Ｓ４０１）。表現処理部３０１は、入力したメッセージから、モンゴメリ乗算の計算用に変換したメッセージ（以降、モンゴメリ乗算用のメッセージと呼ぶ）を作成し、入出力処理部３０２へ出力する（Ｓ４０２）。入出力処理部３０２は、適当なメッセージまたは定数を選択し（詳細な処理内容は後述）、剰余処理部３０３へ出力する。
【００５４】
剰余処理部３０３は、後述する（式１）によって定義されたモンゴメリ乗算の商と剰余を計算し、入出力処理部３０２へ出力する。入出力処理部３０２と剰余処理部３０３は、上記のメッセージの交換処理を複数回繰り返す（Ｓ４０３、Ｓ４０４）。入出力処理部３０２は、複数個のモンゴメリ乗算用の商と剰余を合成したメッセージを、表現処理部３０１へ出力する（Ｓ４５１）。表現処理部３０１は、モンゴメリ乗算用の商と剰余を合成したメッセージをデータ処理部１１５へ出力する（Ｓ４５２）。
【００５５】
なお、表現処理部３０１、入出力処理部３０２、剰余処理部３０３のメッセージの受け渡しには、記憶装置１２３へのメッセージの書き込みと読み出しを用い、メッセージの受け渡しを実施する。ただし、ネットワーク１５１を用い、メッセージの受け渡しを実施しても良い。
【００５６】
＜表現処理部の処理＞
次に、コンピュータＡ１０１内の表現処理部３０１の行う分割処理と合成処理について説明する。
【００５７】
まず、表現処理部３０１の行う分割処理について説明する。表現処理部３０１は、メッセージをモンゴメリ乗算の計算に適した形式であるモンゴメリ乗算用のメッセージに変換する機能を有する。ただし、モンゴメリ乗算の計算に適した形式とは、２ｗビットの整数Ｘを上位側ｗビットの整数ｘ１と下位側ｗビットの整数ｘ０で表すように、変換した（式１）を満たす整数表現を指す。
【００５８】
Ｘ＝ｘ０２ｗ＋ｘ１        …（式１）
ただし、０≦Ｘ＜２2ｗかつ０≦ｘ０、ｘ１＜２ｗである。
【００５９】
まず、表現処理部３０１内の分割部３１１は、２ｗビットのメッセージＡ、メッセージＢ、メッセージＮを記憶装置１２３から読み込む（Ｓ４０１）。次に、分割部３１１は２ｗビットのメッセージＡ、２ｗビットのメッセージＢ、２ｗビットのメッセージＮを上位ｗビットと下位ｗビットに分け、（式１）を満たすよう、メッセージＡからメッセージａ１とメッセージａ０、メッセージＢからメッセージｂ１とメッセージｂ０、メッセージＮからメッセージｎ１とメッセージｎ０を作成する。従って、以下の式が成り立つ。
【００６０】
Ｎ＝ｎ０２ｗ＋ｎ１
Ａ＝ａ０２ｗ＋ａ１
Ｂ＝ｂ０２ｗ＋ｂ１
分割部３１１は、記憶装置１２３にメッセージｎ１とメッセージｎ０、メッセージａ１、メッセージａ０、メッセージｂ１、メッセージｂ０を出力する（Ｓ４０２）。
【００６１】
表現処理部３０１の行う合成処理について説明する。表現処理部３０１内の合成部３１２は、入出力処理部３０２が格納したメッセージｑsとメッセージｒsを用い、（ｒs２ｗ＋ｑs）の値を保持するメッセージＣを作成する機能を有する。
【００６２】
まず、表現処理部３０１内の合成部３１２は、メッセージｑｓとメッセージｒｓを記憶装置１２３から読み込む（Ｓ４５１）。次に、メッセージｑsとメッセージｒsを用い、（ｒs２ｗ＋ｑs）の値を保持するメッセージＣを作成する。従って、メッセージＣ、メッセージｒs、メッセージｑsには以下の式が成り立つ。
【００６３】
Ｃ＝ｒs２ｗ＋ｑs
合成部３１２は、共通部３０４における条件判定部３４３を用い、メッセージＣが条件式０≦Ｃ＜Ｎを満たすかを判定する。条件式を満たさない場合は、共通部３０４における剰余計算部３４２を用い、以下の式を満たすメッセージＣを作成する。
【００６４】
Ｃ＝（ｒs２ｗ＋ｑs）ｍｏｄ Ｎ
ただし、０≦Ｃ＜Ｎ＜２2ｗである。合成部３１２は、メッセージＣを記憶装置１２３へ出力する（Ｓ４５２）。
【００６５】
なお、表現処理部３０１の分割部３１１は、複数の分割処理の手法を有する。メッセージＮから、上位ｗビットのメッセージｎ０と下位ｗビットのメッセージｎ１に分割すると、剰余乗算の法になるメッセージｎ１が小さくなりすぎ、補正処理が増え、結果的に計算処理が増加することがある。この計算処理を減らすため、次式に基づき、メッセージｎ１の代わりに（２ｗ−ｎ１）の値を持つメッセージｎ’１を作成し、剰余乗算の法として用いる。
【００６６】
Ｎ＝（ｎ０＋１）２ｗ−（２ｗ−ｎ１）
＝ｎ’０２ｗ＋ｎ’１
ただし、ｎ’０＝ｎ０＋１かつｎ’１＝−（２ｗ−ｎ１）である。
【００６７】
＜入出力処理部の処理＞
次に、図５〜図８により、本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部３０２の処理について説明する。図５〜図８は本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【００６８】
ＭＵは、剰余処理部３０３を表し、剰余処理部３０３に入力するメッセージの組はＭＵの右辺の括弧内に、剰余処理部３０３から出力するメッセージの組は左辺の括弧内に表す。
【００６９】
入出力処理部３０２と剰余処理部３０３のメッセージの受け渡しには、記憶装置１２３を用いる。メッセージの格納領域として、ＲＡＭ１４１においてラベル付けされたＸＡ、ＸＢ、ＸＮ、ＸＲと、他の記憶領域（例えばＲＡＭ１３１）においてラベル付けされたＹＱ、ＹＲ、ＹＴ（メッセージの格納用に領域を定義）を用いる。
【００７０】
なお、入出力処理部３０２と剰余処理部３０３におけるメッセージ交換の際の記憶装置１２３の利用方法の詳細については、図１０と図１１を用いて後述する。
【００７１】
＜入出力処理＞
入力部３２１は、メッセージａ１をＸＡに、メッセージｂ１をＸＢに、メッセージｎ１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ出力する商を指すメッセージｑ１をＸＢに、剰余ｒ１を指すメッセージｒ１をＹＴに格納するよう指示する（Ｓ５０１）。
【００７２】
入力部３２１は、メッセージｎ０をＸＡに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ2をＸＡに、剰余を指すメッセージｒ2をＹＲに格納するよう指示する（Ｓ５０２）。
【００７３】
蓄積部３２４は、ＸＡに格納されたメッセージｑ2とＹＴに格納されたメッセージｒ１を加減乗算部３４１に入力し、（ｒ１−ｑ２）の値を持つメッセージｔ１をＹＱに格納する（Ｓ５０３）。
【００７４】
入力部３２１は、メッセージａ０をＸＡに、メッセージｂ０をＸＢに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ3をＸＡに、剰余を指すメッセージｒ3をＹＴに格納するよう指示する（Ｓ５０４）。
【００７５】
蓄積部３２４は、ＹＱに格納されたメッセージｔ１とＸＡに格納されたメッセージｑ３を加減乗算部３４１に入力し、（ｔ１−ｑ３）の値を持つメッセージｔ１をＹＱに格納するよう指示する。さらに、蓄積部３２４は、ＹＲに格納されたメッセージｒ2とＹＴに格納されたメッセージｒ３を加減乗算部３４１に入力し、（ｒ２＋ｒ３）の値を持つメッセージｒｓをＹＲに格納する（Ｓ５０５）。
【００７６】
入力部３２１は、加減乗算部３４１に対してメッセージを交換し、（ａ１＋ａ０）の値を持つメッセージ（ａ１＋ａ０）をＸＡに、（ｂ１＋ｂ０）の値を持つメッセージ（ｂ１＋ｂ０）をＸＢに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ4をＸＡに、剰余を指すメッセージｒ4をＹＴに格納するよう指示する（Ｓ５０６）。
【００７７】
蓄積部３２４は、ＹＱに格納されたメッセージｔ１とＸＡに格納されたメッセージｑ４を加減乗算部３４１に入力し、（ｔ１＋ｑ４）の値を持つメッセージｔ１をＸＢに格納する。さらに、蓄積部３２４は、ＹＴに格納されたメッセージｒ４とＸＡに格納されたメッセージｑ４を加減乗算部３４１に入力し、（ｒ４＋ｑ４）の値を持つメッセージｔ２をＹＴに格納する。さらに、蓄積部３２４は、ＸＢに格納されたメッセージｔ１とＹＲに格納されたメッセージｒｓとＹＴに格納されたメッセージｔ２を加減乗算部３４１に入力し、（−ｔ１＋ｔ２−ｒｓ）の値を持つメッセージｑｓをＹＱに格納する（Ｓ５０７）。
【００７８】
入力部３２１は、定数１をＸＢに、メッセージｎ１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ5をＸＢに、剰余を指すメッセージｒ5をＹＴに格納するよう指示する（Ｓ５０８）。
【００７９】
蓄積部３２４は、ＹＱに格納されたメッセージｑｓとＹＴに格納されたメッセージｒ５を加減乗算部３４１に入力し、（ｑｓ＋ｒ５）の値を持つメッセージｑｓをＹＱに格納する（Ｓ５０９）。
【００８０】
入力部３２１は、メッセージｎ０をＸＡに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ6をＸＡに、剰余を指すメッセージｒ6をＹＴに格納するよう指示する（Ｓ５１０）。
【００８１】
蓄積部３２４は、ＸＡに格納されたメッセージｑ６とＹＱに格納されたメッセージｑｓを加減乗算部３４１に入力し、（ｑｓ−ｑ６）の値を持つメッセージｑｓをＹＱに格納する。さらに、蓄積部３２４は、ＹＴに格納されたメッセージｒ６とＹＲに格納されたメッセージｒｓを加減乗算部３４１に入力し、（ｒｓ−ｒ６）の値を持つメッセージｒｓをＹＲに格納する（Ｓ５１１）。
【００８２】
＜乗数と被乗数の補正処理＞
補正部３２２は、剰余処理部３０３が適切に処理できるよう、メッセージの値を変更する機能を有する。例えば、剰余処理部３０３がメッセージｘに対し、０≦ｘ＜２ｗの値域を条件とする場合の、補正部３２２が関わる剰余乗算の計算処理を示すフローチャートを図６に示す。図６は、図５で示したフローチャートの各ステップに加え、補正部３２２の補正処理が加わる。
【００８３】
以降では、図６の補正部３２２の補正処理に関連するステップのみを説明する。
【００８４】
補正部３２２は、下記の式を用い、０≦ｑ１＜２ｗを満たすよう、ｑ１とｒ１の値を変更する。
【００８５】
ｑ１←ｑ１＋ｉ２ｗ
ｒ１←ｒ１−ｉｎ１
ただし、ｉは小さな整数である。また、ｑ１の値を変更する必要がない場合、ｉ＝０が成り立ち、Ｓ５０１ａの処理は不要である（Ｓ５０１ａ）。
【００８６】
補正部３２２は、下記の式を用い、０≦ａ１＋ａ０、ｂ１＋ｂ０＜２ｗを満たすよう、値を変更する。
【００８７】
ｔ３←ａ１＋ａ０＋ｉ２ｗ
ｔ４←ｂ１＋ｂ０＋ｊ２ｗ
ただし、ｉ、ｊは小さな整数である。また、ａ１＋ａ０、ｂ１＋ｂ０の値を変更する必要がない場合、ｉ＝０、ｊ＝０が成り立つ（Ｓ５０５ａ）。
【００８８】
入力部３２１は、メッセージｔ３をＸＡに、メッセージｔ４をＸＢに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３から商を指すメッセージｑ４をＸＡに、剰余を指すメッセージｒ４をＹＴに格納するよう指示する（Ｓ５０６ａ）。ただし、Ｓ５０５ａでｉ＝０かつｊ＝０が成り立つ場合、Ｓ５０６ａの代わりにＳ５０６を実行しても良い。
【００８９】
補正部３２２は、ＹＴに格納されたメッセージｒ４とＸＡに格納されたメッセージｔ３とＸＢに格納されたメッセージｔ４を加減乗算部３４１に入力し、（ｒ４＋ｉｔ４＋ｊｔ３）の値を持つメッセージｒ４としてＹＴに格納する（Ｓ５０６ｂ）。
【００９０】
補正部３２２は、下記の式を用い、０≦ｔ２＜２ｗを満たすよう、ｔ２の値を変更する。
【００９１】
ｔ２←ｔ２＋ｉ２ｗ
ただし、ｉは小さな整数である。また、ｔ２の値を変更する必要がない場合、ｉ＝０が成り立ち、Ｓ５０７ａの処理は不要である（Ｓ５０７ａ）。
【００９２】
補正部３２２は、ＹＴに格納されたメッセージｒ５とメッセージｉを加減乗算部３４１に入力し、（ｒ５＋ｉ）の値を持つメッセージｒ５としてＹＴに格納する（Ｓ５０８ａ）。
【００９３】
補正部３２２は、下記の式を用い、０≦ｑ５＜２ｗを満たすよう、ｑ５とｒ５の値を変更する。
【００９４】
ｑ５←ｑ５＋ｉ２ｗ
ｒ５←ｒ５−ｉｎ１
ただし、ｉは小さな整数である。また、ｑ５の値を変更する必要がない場合、ｉ＝０が成り立ち、Ｓ５０８ｂの処理は不要である（Ｓ５０８ｂ）。
【００９５】
＜入出力処理その２＞
図５の入出力処理部３０２の剰余乗算の計算処理を示すフローチャートにおいて、Ｓ５０２、Ｓ５０４、Ｓ５０６、Ｓ５１０において、ＸＮに定数１を設定した。しかし、ＸＮに設定する数は定数１である必要性はなく、どのような値の整数もＸＮに設定できる。
【００９６】
図７は、Ｓ５０２、Ｓ５０４、Ｓ５０６、Ｓ５１０において、定数２ｗ−１を用いた場合の入出力処理部３０２の剰余乗算の計算処理を示すフローチャートである。以下では、図７が示すフローチャートについて、図５が示すフローチャートと異なる点のみ、説明する。
【００９７】
入力部３２１は、メッセージｎ０をＸＡに、定数２ｗ−１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ2をＸＡに、剰余を指すメッセージｒ2をＹＲに格納するよう指示する（Ｓ５０２ｃ）。
【００９８】
補正部３２２は、ＸＡに格納されたメッセージｑ2を加減乗算部３４１に入力し、（−ｑ２）の値を持つメッセージｑ２をＸＡに格納する。また、補正部３２２は、ＹＲに格納されたメッセージｒ2とＸＡに格納されたメッセージｑ２を加減乗算部３４１に入力し、（ｒ２−ｑ２）の値を持つメッセージｒ２をＹＲに格納する（Ｓ５０２ｄ）。
【００９９】
入力部３２１は、メッセージａ０をＸＡに、メッセージｂ０をＸＢに、定数２ｗ−１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ3をＸＡに、剰余を指すメッセージｒ3をＹＴに格納するよう指示する（Ｓ５０４ｃ）。
【０１００】
補正部３２２は、ＸＡに格納されたメッセージｑ３を加減乗算部３４１に入力し、（−ｑ３）の値を持つメッセージｑ３をＸＡに格納する。また、補正部３２２は、ＹＴに格納されたメッセージｒ３とＸＡに格納されたメッセージｑ３を加減乗算部３４１に入力し、（ｒ３−ｑ３）の値を持つメッセージｒ３をＹＴに格納する（Ｓ５０４ｄ）。
【０１０１】
入力部３２１は、加減乗算部３４１に対してメッセージを交換し、（ａ１＋ａ０）の値を持つメッセージ（ａ１＋ａ０）をＸＡに、（ｂ１＋ｂ０）の値を持つメッセージ（ｂ１＋ｂ０）をＸＢに、定数２ｗ−１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ4をＸＡに、剰余を指すメッセージｒ4をＹＴに格納するよう指示する（Ｓ５０６ｃ）。
【０１０２】
補正部３２２は、ＸＡに格納されたメッセージｑ４を加減乗算部３４１に入力し、（−ｑ４）の値を持つメッセージｑ４をＸＡに格納する。また、補正部３２２は、ＹＴに格納されたメッセージｒ４とＸＡに格納されたメッセージｑ４を加減乗算部３４１に入力し、（ｒ４−ｑ４）の値を持つメッセージｒ４をＹＴに格納する（Ｓ５０６ｄ）。
【０１０３】
入力部３２１は、メッセージｎ０をＸＡに、定数２ｗ−１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ6をＸＡに、剰余を指すメッセージｒ6をＹＴに格納するよう指示する（Ｓ５１０ｃ）。
【０１０４】
補正部３２２は、ＸＡに格納されたメッセージｑ６を加減乗算部３４１に入力し、（−ｑ６）の値を持つメッセージｑ６をＸＡに格納する。また、補正部３２２は、ＹＴに格納されたメッセージｒ６とＸＡに格納されたメッセージｑ６を加減乗算部３４１に入力し、（ｒ６−ｑ６）の値を持つメッセージｒ６をＹＴに格納する（Ｓ５１０ｄ）。
【０１０５】
＜入出力処理その３＞
図５の入出力処理部３０２の剰余乗算の計算処理を示すフローチャートにおいて、Ｓ５０１、Ｓ５０８において、ＸＮに定数ｎ１を設定した。図８は、Ｓ５０１、Ｓ５０８において、定数２ｗ−ｎ１を用いた場合の入出力処理部３０２の剰余乗算の計算処理を示すフローチャートである。以下では、図８が示すフローチャートについて、図５が示すフローチャートと異なる点のみを説明する。
【０１０６】
入力部３２１は、メッセージａ１をＸＡに、メッセージｂ１をＸＢに、２ｗ−ｎ１の値を持つメッセージをＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ１をＸＢに、剰余ｒ１を指すメッセージｒ１をＹＴに格納するよう指示する（Ｓ５０１ｅ）。
【０１０７】
入力部３２１は、ｎ０＋１の値を持つメッセージをＸＡに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ2をＸＡに、剰余を指すメッセージｒ2をＹＲに格納するよう指示する（Ｓ５０２ｅ）。
【０１０８】
入力部３２１は、ＸＡに格納されたメッセージｑ2とＹＴに格納されたメッセージｒ１を加減乗算部３４１に入力し、（ｒ１＋ｑ２）の値を持つメッセージｔ１をＹＱに格納する（Ｓ５０３ｅ）。
【０１０９】
蓄積部３２４は、ＹＱに格納されたメッセージｔ１とＸＡに格納されたメッセージｑ３を加減乗算部３４１に入力し、（ｔ１−ｑ３）の値を持つメッセージｔ１をＹＱに格納する。さらに、蓄積部３２４は、ＹＲに格納されたメッセージｒ2とＹＴに格納されたメッセージｒ３を加減乗算部３４１に入力し、（−ｒ２＋ｒ３）の値を持つメッセージｒｓをＹＲに格納する（Ｓ５０５ｅ）。
【０１１０】
入力部３２１は、定数１をＸＢに、（２ｗ−ｎ１）の値を持つメッセージをＸＮに格納する。出力指示部３２３は、剰余処理部３０３から商を指すメッセージｑ5をＸＢに、剰余を指すメッセージｒ5をＹＴに格納するよう指示する（Ｓ５０８ｅ）。
【０１１１】
入力部３２１は、（ｎ０＋１）の値を持つメッセージをＸＡに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ6をＸＡに、剰余を指すメッセージｒ6をＹＴに格納するよう指示する（Ｓ５１０ｅ）。
【０１１２】
入力部３２１は、ＹＴに格納されたメッセージｒ６とＹＲに格納されたメッセージｒｓを加減乗算部３４１に入力し、（ｒｓ＋ｒ６）の値を持つメッセージｒｓをＹＲに格納する。さらに、入力部３２１は、ＸＡに格納されたメッセージｑ６とＹＱに格納されたメッセージｑｓを加減乗算部３４１に入力し、（ｑ６＋ｑｓ）の値を持つメッセージｑｓをＹＱに格納する（Ｓ５１１ｅ）。
【０１１３】
＜平方算への展開＞
なお、入出力処理部３０２の剰余乗算に関する処理は、メッセージＡとメッセージＢの値が等しい場合、即ち平方算の場合も含む。また、上記の２ｗビットの剰余乗算を繰り返し実行すると、２ｗビットのべき乗の剰余乗算が実現できる。
【０１１４】
＜剰余処理部の処理＞
次に、図９により、本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部３０３の処理について説明する。図９は本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートであり、剰余処理部３０３におけるモンゴメリ乗算の商ｑと剰余ｒの計算処理について示している。
【０１１５】
乗数変更部３３５は、剰余乗算を実行する前に、下記の式を用い、ＸＡに設定されたメッセージｘ、ＸＢに設定されたメッセージｙ、ＸＮに設定されたメッセージｚが０≦ｘ、ｙ＜ｚを満たすよう、メッセージｘとメッセージｙの値を変更する（Ｓ１００１）。
【０１１６】
ｘ←ｘ−ｉｚ
ｙ←ｙ−ｊｚ
ただし、ｉとｊは整数である。また、ｘとｙの値を変更する必要がない場合、ｉ＝ｊ＝０が成り立ち、Ｓ１００１と後述するＳ１０１４の処理は不要である。
【０１１７】
剰余乗算器取扱部３３１は、入力部３２１が、ＸＡ、ＸＢ、ＸＮに設定したメッセージに基づき、モンゴメリ乗算による剰余乗算の剰余を計算する。例えば、ＸＡにメッセージｘを、ＸＢにメッセージｙを、ＸＮにメッセージｚを設定した場合、以下の式で定義されるモンゴメリ乗算の剰余ｒをＸＲに出力する。
【０１１８】
ｒ←ｘｙ２−ｗｍｏｄ ｚ
ただし、ｘは乗数、ｙは被乗数、ｚは法である。次に、移動部３３３は、出力指示部３２３が指示したメッセージの格納領域へ、メッセージｒを移動する（Ｓ１００２）。
【０１１９】
法変更部３３４は、ＸＮに設定したメッセージの値を変更する。例えば、法変更部３３４は、条件判定部３４３を用い、ＸＮに設定したメッセージｚの値が条件式（ｚ＜２ｗ−1＋２ｗ−２）を満たすかを判定する（Ｓ１００３）。条件を満たせばＳ１００４へ、満たさなければＳ１００５へと進む。法変更部３３４は、加減乗算部３４１を用い、ＸＮに設定したメッセージｚの値を変更する。ｚ＋２ｗ−２の値を持つメッセージｚ’を作成する（Ｓ１００４）、またはｚ−２ｗ−２の値を持つメッセージｚ’を作成する（Ｓ１００５）。
【０１２０】
剰余乗算器取扱部３３１は、ＸＡ、ＸＢ、ＸＮに設定されたメッセージに基づき、モンゴメリ乗算による剰余乗算の剰余を計算する。ＸＡにメッセージｘを、ＸＢにメッセージｙを、ＸＮにメッセージｚ’を設定した場合、以下の式で定義されるモンゴメリ乗算の剰余ｒ’をＸＲに出力する。
【０１２１】
ｒ’←ｘｙ２−ｗｍｏｄ ｚ’
ただし、ｘは乗数、ｙは被乗数、ｚ’は法である。（Ｓ１００６）。
【０１２２】
商演算部３３２は、条件判定部３４３を用い、ＸＮに設定したメッセージｚの値から判別式を用い、メッセージβの値を設定する。条件式（ｚ＜２ｗ−1＋２ｗ−２）を満たせばＳ１００８へ、満たさなければＳ１００９へと進む（Ｓ１００７）。商演算部３３２は、メッセージβの値を１（Ｓ１００８）または（−１）とする（Ｓ１００９）。
【０１２３】
商演算部３３２は、加減乗算部３４１と剰余計算部３４２を用い、以下の式を満たすメッセージαを計算する（Ｓ１０１０）。
【０１２４】
α← ｘｙｚ2−４β(ｒ−ｒ’)z3 (ｍｏｄ ２４)
商演算部３３２は、条件判定部３４３を用い、メッセージαの値が条件式（α＞２３）を満たすかを判定する。条件を満たせばＳ１０１２へ、満たさなければＳ１０１３へと進む（Ｓ１０１１）。
【０１２５】
商演算部３３２は、加減乗算部３４１を用い、α−２４の値をもつメッセージαを作成する（Ｓ１０１２）。
【０１２６】
商演算部３３２は、加減乗算部３４１と剰余計算部３４２を用い、以下の式を満たすメッセージｑを計算し、出力指示部３２３が指示したメッセージの格納領域へ、メッセージｑを出力する（Ｓ１０１３）。
【０１２７】
ｑ← αｚ’＋４β(ｒ−ｒ’)
このとき、メッセージｑは、モンゴメリ乗算の商ｑであり、以下の式を満たす。
【０１２８】
ｘｙ＝ｑｚ＋ｒ２ｗ 
ただし、ｘは乗数、ｙは被乗数、ｒはモンゴメリ乗算の剰余、ｚは法である。
【０１２９】
乗数変更部３３５は、加減乗算部３４１を用い、以下の式を満たすメッセージｑを計算し、メッセージｑが格納されていた領域に、再びメッセージｑを格納する（Ｓ１０１４）。
【０１３０】
ｑ←ｑ＋ｉｘ＋ｊｙ−ｉｊｚ
なお、剰余乗算器１１３のビット長の制限によっては、図９に示すフローチャートを簡略化して、モンゴメリ乗算の商ｑと剰余ｒを計算してもよい。
【０１３１】
＜乗算器（剰余乗算器ではなく）を用いる場合＞
剰余乗算器１１３が乗算を実行できる場合、または剰余乗算器１１３以外に、演算装置として乗算を実行する乗算器が実装されている場合、剰余処理部３０３は、乗算を利用し、モンゴメリ乗算の商ｑとモンゴメリ乗算の剰余ｒを求めても良い。この計算方法は、ＸＮに定数を設定する、Ｓ５０２、Ｓ５０４、Ｓ５０６、Ｓ５１０などで利用できる。剰余乗算器取扱部３３１は、乗数ｘと被乗数ｙ用いて、以下の式を満たす積ｃを計算する。
【０１３２】
ｃ←ｘｙ
剰余処理部３０３は、ｃの下位ｗビットをモンゴメリ乗算の商、それ以外の上位ビットをモンゴメリ乗算の剰余とみなす。
【０１３３】
＜入出力処理部と剰余処理部の構成＞
入出力処理部３０２と剰余処理部３０３は、メッセージの交換に記憶装置１２３を用いる。
【０１３４】
次に、図１０および図１１により、本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムの記憶装置１２３へのメッセージの格納順序について説明する。図１０および図１１は、本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【０１３５】
図１０および図１１は、行と列をもつ表から構成される。最も左の列は、図５で示したフローチャートの各ステップと対応を取り、他の列は、メッセージを格納する記憶領域であるＸＲ、ＸＡ、ＸＢ、ＸＮ、ＹＱ、ＹＲ、ＹＴを意味する。各行には記憶領域内に格納されるメッセージを表し、「任意」は、格納されているメッセージはどのような値でもかまわない。
【０１３６】
また、上行から下行に順々に処理が実行され、「―」は以前の処理にて格納されたメッセージを格納し続ける状態を指す。また、ｙ、ｚは定数を表すメッセージであり、例えば図５が示すフローチャートでは、ｙ＝１、ｚ＝１であり、図７が示すフローチャートでは、ｙ＝１、ｚ＝２ｗ−１である。
【０１３７】
Ｓ５０１の第１行目では、ＸＡにメッセージａ１、ＸＢにメッセージｂ１、ＸＮにメッセージｎ１が格納される。他の記憶領域であるＸＲ、ＹＱ、ＹＲ、ＹＴに格納するメッセージは任意でよい。Ｓ５０１の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ１が格納される。他の記憶領域に格納するメッセージに変更はない。
【０１３８】
Ｓ５０１の第３行目では、ＹＴにもメッセージｒ１が格納される。Ｓ５０１の第４行目では、メッセージｎ１の値を変更したメッセージｎ’１がＸＮに格納される。Ｓ５０１の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’１が格納される。Ｓ５０１の第６行目では、ＸＢにモンゴメリ乗算の商であるメッセージｑ１が格納される。
【０１３９】
Ｓ５０２の第１行目では、ＸＡにメッセージｎ０、ＸＮにメッセージｚが格納される。他の記憶領域であるＸＲ、ＸＢ、ＹＱ、ＹＲ、ＹＴに格納するメッセージは任意でよい。Ｓ５０２の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ２が格納される。他の記憶領域に格納するメッセージに変更はない。
【０１４０】
Ｓ５０２の第３行目では、ＹＲにもメッセージｒ２が格納される。Ｓ５０２の第４行目では、メッセージｚの値を変更したメッセージｚ’がＸＮに格納される。Ｓ５０２の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’２が格納される。Ｓ５０２の第６行目では、ＸＡにモンゴメリ乗算の商であるメッセージｑ２が格納される。
【０１４１】
Ｓ５０３では、（ｒ１−ｑ２）の値をもつメッセージｔ１がＹＱに格納される。
【０１４２】
Ｓ５０４の第１行目では、ＸＡにメッセージａ０、ＸＢにメッセージｂ０、ＸＮにメッセージｚが格納される。Ｓ５０４の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ３が格納される。Ｓ５０４の第３行目では、ＹＴにもメッセージｒ３が格納される。
【０１４３】
Ｓ５０４の第４行目では、メッセージｚの値を変更したメッセージｚ’がＸＮに格納される。Ｓ５０４の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’３が格納される。Ｓ５０４の第６行目では、ＸＡにモンゴメリ乗算の商であるメッセージｑ３が格納される。
【０１４４】
Ｓ５０５の第１行目では、（ｔ１−ｑ３）の値をもつメッセージｔ１がＹＱに格納される。Ｓ５０５の第２行目では、（ｒ２＋ｒ３）の値をもつメッセージｒｓがＹＲに格納される。
【０１４５】
Ｓ５０６の第１行目では、（ａ１＋ａ０）の値を持つメッセージがＸＡに、（ｂ１＋ｂ０）の値を持つメッセージがＸＢに、メッセージｚがＸＮに格納される。Ｓ５０６の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ４が格納される。
【０１４６】
Ｓ５０６の第３行目では、ＹＴにもメッセージｒ４が格納される。Ｓ５０６の第４行目では、メッセージｚの値を変更したメッセージｚ’がＸＮに格納される。Ｓ５０６の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’４が格納される。Ｓ５０６の第６行目では、ＸＡにモンゴメリ乗算の商であるメッセージｑ４が格納される。
【０１４７】
Ｓ５０７の第１行目では、（ｔ１＋ｑ４）の値をもつメッセージｔ１がＸＢに格納される。Ｓ５０７の第２行目では、（ｑ４＋ｒ４）の値をもつメッセージｔ２がＹＴに格納される。Ｓ５０７の第３行目では、（‐ｔ１＋ｔ２−ｒｓ）の値を持つメッセージｑｓがＹＱに格納される。
【０１４８】
Ｓ５０８の第１行目では、ＸＡにメッセージｙ、ＸＮにメッセージｎ１が格納される。Ｓ５０８の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ５が格納される。Ｓ５０８の第３行目では、ＹＴにもメッセージｒ５が格納される。Ｓ５０８の第４行目では、メッセージｎ１の値を変更したメッセージｎ’１がＸＮに格納される。Ｓ５０８の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’５が格納される。Ｓ５０８の第６行目では、ＸＢにモンゴメリ乗算の商であるメッセージｑ５が格納される。
【０１４９】
Ｓ５０９では、（ｑｓ＋ｒ５）の値をもつメッセージｑｓがＹＱに格納される。
【０１５０】
Ｓ５１０の第１行目では、ＸＡにメッセージｎ０、ＸＮにメッセージｚが格納される。Ｓ５１０の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ６が格納される。Ｓ５１０の第３行目では、ＹＴにもメッセージｒ６が格納される。
【０１５１】
Ｓ５１０の第４行目では、メッセージｚの値を変更したメッセージｚ’がＸＮに格納される。Ｓ５１０の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’６が格納される。Ｓ５１０の第６行目では、ＸＡにモンゴメリ乗算の商であるメッセージｑ６が格納される。
【０１５２】
Ｓ５１１の第１行目では、（ｑｓ−ｑ６）の値をもつメッセージｑｓがＹＱに格納される。Ｓ５１１の第２行目では、（ｒｓ‐ｒ６）の値をもつメッセージｒｓがＹＲに格納される。
【０１５３】
＜応用例＞
実施の形態１では、剰余乗算器１１３がモンゴメリ乗算を実装し、２倍剰余乗算部１１６が、２ｗビットからなるメッセージを対象に、モンゴメリ乗算に基づく剰余乗算を計算する計算方法について説明した。実施の形態１に基づくモンゴメリ乗算を繰り返し用いる、または対象の２ｗビットからなるメッセージの値を変更すると、古典的な剰余乗算と同じ値をもつ剰余乗算の剰余が得られる。
【０１５４】
以上のように実施の形態１では、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算を処理することが可能である。
【０１５５】
（実施の形態２）
＜実施の形態２の概要＞
本実施の形態では、剰余乗算器１１３が古典的な剰余乗算を実装する場合、２倍剰余乗算部１１６が、２ｗビットからなるメッセージを対象に、古典的な剰余乗算に基づく剰余乗算を計算する第２の計算方法について説明する。
【０１５６】
＜２倍剰余乗算部の処理の概要＞
図１２より、本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の２倍剰余乗算部１１６の処理について説明する。図１２は本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の２倍剰余乗算部の処理を示すシーケンス図であり、２倍剰余乗算部１１６の機能ブロックである表現処理部３０１、入出力処理部３０２、剰余処理部３０３のメッセージの受け渡しの様子を示す。実施の形態２に係る剰余乗算処理装置を適用した通信システムの構成は実施の形態１と同様である。
【０１５７】
まず、表現処理部３０１へメッセージが入力される（Ｓ１１０１）。表現処理部３０１は、入力したメッセージを元に、古典的な剰余乗算の計算用に変換したメッセージ（以降、古典的な剰余乗算用のメッセージと呼ぶ）を作成し、入出力処理部３０２がアクセスできるメモリ領域へ出力する（Ｓ１１０２）。入出力処理部３０２は、メモリ領域から、古典的な剰余乗算用のメッセージを入力し、適当なメッセージ、または定数を選択し、剰余処理部３０３がアクセスできるメモリへ出力する。
【０１５８】
剰余処理部３０３は、メモリ領域から、古典的な剰余乗算用のメッセージおよび定数を用い、（式１）によって定義された古典的な剰余乗算の商と剰余を計算し、入出力処理部３０２がアクセスできるメモリ領域へ出力する。入出力処理部３０２、剰余処理部３０３は、上記の処理を複数回繰り返す（Ｓ１１０３、Ｓ１１０４）。入出力処理部３０２は、入力された複数個の古典的な剰余乗算用の商と剰余を合成したメッセージを、表現処理部３０１がアクセスできるメモリ領域へ出力する（Ｓ１１５１）。表現処理部３０１は、メモリ領域から、古典的な剰余乗算用の商と剰余を合成したメッセージを、データ処理部１１５へ出力する（Ｓ１１５２）。
【０１５９】
＜表現処理部の処理＞
本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の表現処理部３０１の行う分割処理と合成処理について説明する。
【０１６０】
まず、表現処理部３０１の行う分割処理について説明する。表現処理部３０１は、メッセージを古典的な剰余乗算の計算に適した形式である古典的な剰余乗算用のメッセージに変換する機能を有する。ただし、古典的な剰余乗算の計算に適した形式とは、２ｗビットの整数Ｘを上位側ｗビットの整数ｘ１と下位側ｗビットの整数ｘ０で表すように、変換した（式２）を満たす整数表現を指す。
【０１６１】
Ｘ＝ｘ１２ｗ＋ｘ０        …（式２）
ただし、０≦Ｘ＜２2ｗかつ０≦ｘ０、ｘ１＜２ｗである。
【０１６２】
まず、表現処理部３０１がもつ分割部３１１は２ｗビットのメッセージＡ、２ｗビットのメッセージＢ、２ｗビットのメッセージＮを記憶装置１２３から読み込む（Ｓ１１０１）。次に、分割部３１１は、各メッセージを上位ｗビットと下位ｗビットに分け、（式２）を満たすよう、メッセージＡからメッセージａ１とメッセージａ０、メッセージＢからメッセージｂ１とメッセージｂ０、メッセージＮからメッセージｎ１とメッセージｎ０を作成する。従って、以下の式が成り立つ。
【０１６３】
Ｎ＝ｎ１２ｗ＋ｎ０
Ａ＝ａ１２ｗ＋ａ０
Ｂ＝ｂ１２ｗ＋ｂ０
分割部３１１は、ＲＡＭ１３１などの記憶装置１２３にメッセージｎ１とメッセージｎ０、メッセージａ１、メッセージａ０、メッセージｂ１、メッセージｂ０を出力する（Ｓ１１０２）。
【０１６４】
次に、表現処理部３０１の行う合成処理について説明する。表現処理部３０１内の合成部３１２は、入出力処理部３０２が格納したメッセージｑsとメッセージｒsを用い、（ｒs２ｗ＋ｑs）の値を保持するメッセージＣを作成する機能を有する。
【０１６５】
まず、表現処理部３０１内の合成部３１２は、記憶装置１２３から、メッセージｑｓとメッセージｒｓを読み込む（Ｓ１１５１）。次に、（ｑｓ２ｗ＋ｒｓ）の値を持つメッセージＣを作成する。従って、メッセージＣ、メッセージｒs、メッセージｑsには以下の式が成り立つ。
【０１６６】
Ｃ＝ｒs２ｗ＋ｑs
合成部３１２は、共通部３０４における条件判定部３４３を用い、メッセージＣが条件式０≦Ｃ＜Ｎを満たすかを判定する。条件式を満たさない場合は、共通部３０４における剰余計算部３４２を用い、以下の式を満たすメッセージＣを作成する。
【０１６７】
Ｃ＝（ｒs２ｗ＋ｑs）ｍｏｄ Ｎ
ただし、０≦Ｃ＜Ｎ＜２2ｗである。合成部３１２は、メッセージＣを記憶装置１２３へ出力する（Ｓ１１５２）。
【０１６８】
なお、表現処理部３０１の分割部３１１は、複数の分割処理の手法を有する。例えば、分割部３１１は、剰余乗算器１１３あるいは剰余処理部３０３が処理できるメッセージのビット長に応じ、自由にメッセージＮから作成するメッセージｎ１とメッセージｎ０を変更する。ｗビットのメッセージＮの値をｉ倍し、ｉＮの値を持つメッセージの下位ｗビットと上位側の残りのビットに分けて、次式を満たす、メッセージｎ１’とメッセージｎ０’を作成する。
【０１６９】
ｉＮ＝ｎ１’２ｗ＋ｎ０’
＜入出力処理＞
次に、図１３〜図１５により、本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部３０２の処理について説明する。図１３〜図１５は本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【０１７０】
実施の形態１で用いた図５と同様、ＭＵは、剰余処理部３０３を表し、剰余処理部３０３に入力するメッセージの組はＭＵの右辺の括弧内に、剰余処理部３０３から出力するメッセージの組は左辺の括弧内に表す。
【０１７１】
また、実施の形態１と同様に、入出力処理部３０２と剰余処理部３０３のメッセージの受け渡しには、記憶装置１２３またはネットワーク１５１を用いる。メッセージの格納領域として、ＲＡＭ１４１におけるＸＡ、ＸＢ、ＸＮ、ＸＲと、他の記憶領域（例えばＲＡＭ１３１）におけるＹＱ、ＹＲ、ＹＴ（メッセージの格納用に領域を定義）を用いる。
【０１７２】
入力部３２１は、メッセージａ１をＸＡに、メッセージｂ１をＸＢに、メッセージｎ１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ１をＸＢに、剰余ｒ１を指すメッセージｒ１をＹＴに格納するよう指示する（Ｓ１２０１）。
【０１７３】
入力部３２１は、メッセージｎ０をＸＡに、定数２ｗをＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ2をＸＡに、剰余を指すメッセージｒ2をＹＲに格納するよう指示する（Ｓ１２０２）。
【０１７４】
入力部３２１は、ＸＡに格納されたメッセージｑ2とＹＴに格納されたメッセージｒ１を加減乗算部３４１に入力し、（ｒ１−ｑ２）の値を持つメッセージｔ１をＹＱに格納する（Ｓ１２０３）。
【０１７５】
入力部３２１は、メッセージａ０をＸＡに、メッセージｂ０をＸＢに、定数２ｗをＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ3をＸＡに、剰余を指すメッセージｒ3をＹＴに格納するよう指示する（Ｓ１２０４）。
【０１７６】
入力部３２１は、ＹＱに格納されたメッセージｔ１とＸＡに格納されたメッセージｑ３を加減乗算部３４１に入力し、（ｔ１−ｑ３）の値を持つメッセージｔ１をＹＱに格納する。さらに、入力部３２１は、ＹＲに格納されたメッセージｒ2とＹＴに格納されたメッセージｒ３を加減乗算部３４１に入力し、（ｒ２＋ｒ３）の値を持つメッセージｒｓをＹＲに格納する（Ｓ１２０５）。
【０１７７】
入力部３２１は、加減乗算部３４１に対してメッセージを交換し、（ａ１＋ａ０）の値を持つメッセージ（ａ１＋ａ０）をＸＡに、（ｂ１＋ｂ０）の値を持つメッセージ（ｂ１＋ｂ０）をＸＢに、定数２ｗをＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ4をＸＡに、剰余を指すメッセージｒ4をＹＴに格納するよう指示する（Ｓ１２０６）。
【０１７８】
入力部３２１は、ＹＱに格納されたメッセージｔ１とＸＡに格納されたメッセージｑ４を加減乗算部３４１に入力し、（ｔ１＋ｑ４）の値を持つメッセージｔ１をＸＢに格納する。さらに、入力部３２１は、ＹＴに格納されたメッセージｒ４とＸＡに格納されたメッセージｑ４を加減乗算部３４１に入力し、（ｒ４＋ｑ４）の値を持つメッセージｔ２をＹＴに格納する。さらに、入力部３２１は、ＸＢに格納されたメッセージｔ１とＹＴに格納されたメッセージｔ２とＹＲに格納されたメッセージｒｓを加減乗算部３４１に入力し、（−ｔ１＋ｔ２−ｒｓ）の値を持つメッセージｑｓをＹＱに格納する（Ｓ１２０７）。
【０１７９】
入力部３２１は、定数１をＸＢに、メッセージｎ１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３から商を指すメッセージｑ5をＸＢに、剰余を指すメッセージｒ5をＹＴに格納するよう指示する（Ｓ１２０８）。
【０１８０】
入力部３２１は、ＹＴに格納されたメッセージｒ５とＹＱに格納されたメッセージｑｓを加減乗算部３４１に入力し、（ｑｓ＋ｒ５）の値を持つメッセージｑｓをＹＱに格納する（Ｓ１２０９）。
【０１８１】
入力部３２１は、メッセージｎ０をＸＡに、定数２ｗをＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ6をＸＡに、剰余を指すメッセージｒ6をＹＴに格納するよう指示する（Ｓ１２１０）。
【０１８２】
入力部３２１は、ＸＡに格納されたメッセージｑ６とＹＱに格納されたメッセージｑｓを加減乗算部３４１に入力し、（ｑｓ−ｑ６）の値を持つメッセージｑｓをＹＱに格納する。さらに、入力部３２１は、ＹＴに格納されたメッセージｒ６とＹＲに格納されたメッセージｒｓを加減乗算部３４１に入力し、（ｒｓ−ｒ６）の値を持つメッセージｒｓをＹＲに格納する（Ｓ１２１１）。
【０１８３】
＜入出力処理：法の変更＞
図１３の入出力処理部３０２の剰余乗算の計算処理を示すフローチャートにおいて、ｒ１、ｒ４、ｒ５、ｑ１、ｑ４、ｑ５を計算する際、ＸＮにメッセージｎ１または定数２ｗを設定した。しかし、乗数と被乗数の値が法よりも大きくなる場合があるため、法の値を大きくするよう、他の値をもつメッセージを法として、設定しても良い。これには、予め、または必要時に、分割部３１１が表現処理部３０１の分割処理において、剰余乗算器１１３あるいは剰余処理部３０３が処理できるメッセージのビット長に応じ、ｗビットのメッセージＮの値をｉ倍またはｊ倍し、ｉＮまたはｊＮの値を持つメッセージの下位ｗビットと上位側の残りのビットに分けて、メッセージｎ１’とメッセージｎ０’、メッセージｎ１’’とメッセージｎ０’’を作成すればよい。
【０１８４】
ｉＮ＝ｎ１’２ｗ＋ｎ０’
ｊＮ＝ｎ１’’２ｗ＋ｎ０’’
図１４は、ｒ１、ｒ４、ｒ５、ｑ１、ｑ４、ｑ５の計算に、別の値のメッセージまたは定数を法として用いた場合の入出力処理部３０２の剰余乗算の計算処理を示すフローチャートである。以下では、図１３が示すフローチャートと異なる点のみを説明する。
【０１８５】
入力部３２１は、メッセージａ１をＸＡに、メッセージｂ１をＸＢに、メッセージｎ１’をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ１をＸＢに、剰余ｒ１を指すメッセージｒ１をＹＴに格納するよう指示する（Ｓ１２０１ｃ）。
【０１８６】
入力部３２１は、メッセージｎ０’をＸＡに、定数２ｗをＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ2をＸＡに、剰余を指すメッセージｒ2をＹＲに格納するよう指示する（Ｓ１２０２ｃ）。
【０１８７】
入力部３２１は、加減乗算部３４１に対してメッセージを交換し、（ａ１＋ａ０）の値を持つメッセージ（ａ１＋ａ０）をＸＡに、（ｂ１＋ｂ０）の値を持つメッセージ（ｂ１＋ｂ０）をＸＢに、定数２ｗ+１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ4をＸＡに、剰余を指すメッセージｒ4をＹＴに格納するよう指示する（Ｓ１２０６ｃ）。
【０１８８】
入力部３２１は、ＸＡに格納されたメッセージｒ４とＹＴに格納されたメッセージｑ４からメッセージｒ４’、メッセージｑ４’を計算し、それぞれＸＡ、ＹＴに格納する（Ｓ１２０６ｄ）。
【０１８９】
入力部３２１は、定数２ｗをＸＢに、メッセージｎ１’’をＸＮに格納する。出力指示部３２３は、剰余処理部３０３から商を指すメッセージｑ5をＸＢに、剰余を指すメッセージｒ5をＹＴに格納するよう指示する（Ｓ１２０８ｃ）。
【０１９０】
入力部３２１は、メッセージｎ０’’をＸＡに、定数２ｗをＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ6をＸＡに、剰余を指すメッセージｒ6をＹＴに格納するよう指示する（Ｓ１２１０ｃ）。
【０１９１】
＜補正処理＞
補正部３２２は、剰余処理部３０３が適切に処理できるよう、メッセージの値を変更する機能を有する。例として、剰余処理部３０３がメッセージｘに対し、０≦ｘ＜２ｗの値域を条件とする場合の、入出力処理部３０２の剰余乗算の計算処理を示すフローチャートを図１５に示す。図１５は、図１３で示したフローチャートの各ステップに加え、補正部３２２の補正処理が加わる。
【０１９２】
以降では、図１５の補正部３２２の補正処理に関連するステップのみを説明する。
【０１９３】
補正部３２２は、下記の式を用い、０≦ａ１＋ａ０、ｂ１＋ｂ０＜２ｗを満たすよう、値を変更する。
【０１９４】
ｔ３←ａ１＋ａ０＋ｉ２ｗ
ｔ４←ｂ１＋ｂ０＋ｊ２ｗ
ただし、ｉ、ｊは小さな整数である。また、ａ１＋ａ０、ｂ１＋ｂ０の値を変更する必要がない場合、ｉ＝０、ｊ＝０が成り立つ（Ｓ１２０５ａ）。
【０１９５】
入力部３２１は、メッセージｔ３をＸＡに、メッセージｔ４をＸＢに、定数２ｗをＸＮに格納する。出力指示部３２３は、剰余処理部３０３から商を指すメッセージｑ４をＸＡに、剰余を指すメッセージｒ４をＹＴに格納するよう指示する（Ｓ１２０６ａ）。ただし、Ｓ１２０５ａでｉ＝０かつｊ＝０が成り立つ場合、Ｓ１２０６ａの代わりにＳ１２０６を実行しても良い。
【０１９６】
補正部３２２は、ＹＴに格納されたメッセージｒ４とＸＡに格納されたメッセージｔ３とＸＢに格納されたメッセージｔ４を加減乗算部３４１に入力し、（ｒ４＋ｉｔ４＋ｊｔ３＋ｉｊ２ｗ）の値を持つメッセージｑ４としてＹＴに格納する（Ｓ１２０６ｂ）。
【０１９７】
補正部３２２は、下記の式を用い、０≦ｔ２＜２ｗを満たすよう、ｔ２の値を変更する。
【０１９８】
ｔ２←ｔ２＋ｉ２ｗ
ただし、ｉは小さな整数である。また、ｔ２の値を変更する必要がない場合、ｉ＝０が成り立ち、Ｓ１２０７ａの処理は不要である（Ｓ１２０７ａ）。
【０１９９】
補正部３２２は、ＹＴに格納されたメッセージｒ５とｉ２ｗの値を持つメッセージを加減乗算部３４１に入力し、ｑ５＋ｉの値を持つメッセージｑ５としてＹＴに格納する（Ｓ１２０８ａ）。
【０２００】
補正部３２２は、下記の式を用い、０≦ｑ５＜２ｗを満たすよう、ｑ５の値を変更する。
【０２０１】
ｑ５←ｑ５＋ｉ２ｗ
ただし、ｉは小さな整数である。また、ｑ５の値を変更する必要がない場合、ｉ＝０が成り立ち、Ｓ１２０８ａの処理は不要である（Ｓ１２０９ａ）。
【０２０２】
補正部３２２は、ＸＡに格納されたメッセージｑ６とｉｎ０の値を持つメッセージを加減乗算部３４１に入力し、ｑ６＋ｉｎ０の値を持つメッセージｑ６としてＸＡに格納する（Ｓ１２１０ａ）。
【０２０３】
＜剰余処理部の処理＞
次に、図１６により、本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部３０３の処理について説明する。図１６は本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートである。
【０２０４】
乗数変更部３３５は、剰余乗算を実行する前に、下記の式を用い、ＸＡに設定されたメッセージｘ、ＸＢに設定されたメッセージｙ、ＸＮに設定されたメッセージｚが０≦ｘ、ｙ＜ｚを満たすよう、メッセージｘとメッセージｙの値を変更する（Ｓ１６０１）。
【０２０５】
ｘ←ｘ−ｉｚ
ｙ←ｙ−ｊｚ
ただし、ｉとｊは整数である。また、ｘとｙの値を変更する必要がない場合、ｉ＝ｊ＝０が成り立ち、Ｓ１６０１と後述するＳ１６０６の処理は不要である。
【０２０６】
剰余乗算器取扱部３３１は、入出力処理部３０２が、ＸＡ、ＸＢ、ＸＮに設定したメッセージに基づき、古典的な剰余乗算による剰余乗算の剰余を計算する。例えば、ＸＡにメッセージｘを、ＸＢにメッセージｙを、ＸＮにメッセージｚを設定した場合、古典的な剰余乗算の剰余ｒは以下の式で定義される。
【０２０７】
ｒ←ｘｙ ｍｏｄ ｚ
ただし、ｘは乗数、ｙは被乗数、ｚは法である。
【０２０８】
次に、移動部３３３は、出力指示部３２３が指示したメッセージの格納領域へ、メッセージｒを移動する（Ｓ１６０２）。
【０２０９】
法変更部３３４は、ＸＮに設定したメッセージの値を変更する。例えば、ＸＮにメッセージｚを設定する場合、以下の式で定義されるメッセージｚ’をＸＮに出力する。（Ｓ１６０３）。
【０２１０】
ｚ’←ｚ＋１
ただし、加算に代えて減算により、即ち以下の式に従い、メッセージｚ’を計算しても良い。
【０２１１】
ｚ’←ｚ−１
剰余乗算器取扱部３３１は、ＸＡ、ＸＢ、ＸＮに設定されたメッセージに基づき、古典的な剰余乗算による剰余乗算の剰余を計算する。ＸＡにメッセージｘを、ＸＢにメッセージｙを、ＸＮにメッセージｚ’を設定した場合、以下の式で定義される古典的な剰余乗算の剰余ｒ’をＸＲに出力する。
【０２１２】
ｒ’←ｘｙ ｍｏｄ ｚ’
ただし、ｘは乗数、ｙは被乗数、ｚ’は法である。（Ｓ１６０４）。
【０２１３】
商演算部３３２は、以下の式を満たす古典的な剰余乗算の商ｑを計算し、出力指示部３２３が指示したメッセージの格納領域へ、古典的な剰余乗算の商ｑを出力する。
【０２１４】
ｘｙ＝ｑｚ＋ｒ 
ただし、ｘは乗数、ｙは被乗数、ｒは古典的な剰余乗算の剰余、ｚは法である。
【０２１５】
商演算部３３２は、加減乗算部３４１を用い、（ｒ−ｒ’）の値を持つメッセージｑを作成する（Ｓ１６０５）。
【０２１６】
商演算部３３２は、条件判定部３４３を用い、メッセージｑの値が負であるか（ｑ＜０を満たすか）判定する。メッセージｑの値が負であればＳ１６０７へ進み、非負であればＳ１６０８へと進む（Ｓ１６０６）。
【０２１７】
商演算部３３２は、加減乗算部３４１を用い、（ｑ＋ｚ＋１）の値を持つメッセージｑを作成する（Ｓ１６０７）。
【０２１８】
乗数変更部３３５は、下記の式に従い、メッセージｑの値を変更する（Ｓ１６０８）。
【０２１９】
ｑ←ｑ＋ｊｘ＋ｉｙ−ｉｊｚ
＜乗算器を利用できる場合＞
なお、剰余処理部３０３が、剰余乗算器１１３以外に、乗算器を利用できる場合、この乗算器を利用して、商ｑと剰余ｒを求めても良い。この計算方法は、ＸＮに定数を設定する、Ｓ１２０２、Ｓ１２０４、Ｓ１２０６、Ｓ１２１０などで利用できる。
【０２２０】
補正部３２２の働きは、剰余乗算器１１３を利用する計算方法と同様である。剰余乗算器取扱部３３１は、乗数ｘと被乗数ｙ用いて、以下の式を満たす積ｃを計算し、下位ｗビットを剰余とする。
【０２２１】
ｘｙ＝ｃ
次に、商演算部３３２は、残りの上位側のビットを商とみなす。
【０２２２】
＜入出力処理部と剰余処理部の構成＞
入出力処理部３０２と剰余処理部３０３は、メッセージの交換に記憶装置１２３を用いる。実施の形態１では、図１０と図１１を用い、記憶装置１２３へのメッセージの格納順序を示した。実施の形態２における、記憶装置１２３へのメッセージの格納順序は、実施の形態１と同様であり、各処理の対応関係が示せる。即ち、実施の形態２におけるＳ１２０１は、実施の形態１における、図１０が示すＳ５０１に対応する。同様に、Ｓ１２０２はＳ５０２、Ｓ１２０３はＳ５０３、Ｓ１２０４はＳ５０４、Ｓ１２０５はＳ５０５、Ｓ１２０６はＳ５０６、Ｓ１２０７はＳ５０７、Ｓ１２０８はＳ５０８、Ｓ１２０９はＳ５０９、Ｓ１２１０はＳ５１０、Ｓ１２１１はＳ５１１に対応する。また、定数を表すメッセージｙとメッセージｚは、ｙ＝１、ｚ＝２ｗである。
【０２２３】
＜応用例：ＸＡに剰余を出力する剰余乗算器＞
実施の形態１、実施の形態２では、ＸＡに入力されたメッセージを乗数、ＸＢに入力されたメッセージを被乗数、ＸＮに入力されたメッセージを法とみなし、演算結果（剰余）はＸＲに出力する剰余乗算器１１３を仮定した。この仮定とは異なり、剰余乗算器１１３が演算結果をＸＲではなく、ＸＡに出力（即ち、ＸＲとＸＡは同一のメッセージの格納領域を指す）する場合も、実施の形態１または実施の形態２と同様に、ＸＡ、ＸＢ、ＸＮ、ＹＱ、ＹＲ、ＹＴのみの記憶領域を用いて、本技術を適用できる。
【０２２４】
以上のように実施の形態２では、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算を処理することが可能である。
【０２２５】
（実施の形態３）
＜剰余乗算処理装置を適用した通信システムの全体構成＞
図１７により、本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムの全体構成について説明する。なお、図１７に示す通信システムの全体構成は、後述する実施の形態４においても基本的に共通である。図１７は本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムの全体構成を示す構成図である。
【０２２６】
図１７において、図１における構成図との違い（即ち、実施の形態１、実施の形態２との違い）は、記憶装置１２３と剰余乗算器１１３の構成にある。
【０２２７】
図１の構成図では、剰余乗算器１１３からメッセージの読み出し、書き込み等ができる記憶装置１２３はＲＡＭ１４１のみであったが、図１７の構成図では、全ての記憶装置１２３が剰余乗算器１１３からアクセスできる（従って、図１では区別されていたＲＡＭ１３１とＲＡＭ１４１の差分が無くなったため、図１７ではＲＡＭはＲＡＭ１３１に統一した）。
【０２２８】
本実施の形態における剰余乗算器１１３は、剰余乗算を実行する計算装置またはプログラムであり、記憶装置１２３の各メモリ上のメッセージの読み出し、または書き込み処理ができる。剰余乗算器１１３は、記憶装置１２３に格納されたメッセージの記憶領域によらず、自由に記憶装置１２３内のメッセージを剰余乗算の乗数、被乗数、法に設定でき、実装する剰余乗算の種類（モンゴメリ乗算または古典的な剰余乗算）に基づき、演算結果（剰余）を記憶装置１２３のいずれの記憶領域にも出力できる。
【０２２９】
本実施の形態では、便宜上、ＸＮ、ＸＱ、ＸＲ、ＸＴ、ＹＡ０、ＹＡ１、ＹＢ０、ＹＢ１、ＹＮ０、ＹＮ１を、メッセージを格納する記憶領域とした。なお、ＹＱ、ＹＲ、ＹＴは、図１７の揮発性メモリ１３１に配置してもよいし、他のメモリ領域に配置しても良い。
【０２３０】
また、剰余乗算器１１３が演算中に利用する記憶領域は上記の記憶装置１２３には含まない。剰余乗算器１１３が計算する剰余乗算は、最大ｗ＋ｈ（ｗは正の整数、ｈは０以上ｗ未満の整数）ビットのメッセージを対象とする。
【０２３１】
＜実施の形態３の概要＞
本実施の形態では、剰余乗算器１１３がモンゴメリ乗算を実装する場合、２倍剰余乗算部１１６が、２ｗビットからなるメッセージを対象に、モンゴメリ乗算に基づく剰余乗算を計算する第３の計算方法について説明する。ただし、ｗは正の整数とする。
【０２３２】
＜２倍剰余乗算部の処理の概要＞
本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の２倍剰余乗算部１１６の処理は、実施の形態１（図４のシーケンス図を参照）と同様である。
【０２３３】
＜表現処理部の処理＞
本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の表現処理部３０１の行う分割処理と合成処理について説明する。
【０２３４】
まず、表現処理部３０１の行う分割処理について説明する。表現処理部３０１は、メッセージをモンゴメリ乗算の計算に適した形式であるモンゴメリ乗算用のメッセージに変換する機能を有する。ただし、モンゴメリ乗算の計算に適した形式とは、２ｗビットの整数Ｘを上位側ｗビットの整数ｘ１と下位側ｗビットの整数ｘ０で表すように、変換した（式１）を満たす整数表現を指す。
【０２３５】
Ｘ＝ｘ０２ｗ＋ｘ１        …（式１）
ただし、０≦Ｘ＜２2ｗかつ０≦ｘ０、ｘ１＜２ｗである。
【０２３６】
まず、表現処理部３０１内の分割部３１１は記憶装置１２３から２ｗビットのメッセージＡ、２ｗビットのメッセージＢ、２ｗビットのメッセージＮを読み込む（Ｓ４０１）。次に、分割部３１１は、各メッセージを上位ｗビットと下位ｗビットに分け、（式１）を満たすよう、メッセージＡからメッセージａ１とメッセージａ０、メッセージＢからメッセージｂ１とメッセージｂ０、メッセージＮからメッセージｎ１とメッセージｎ０を作成する。従って、以下の式が成り立つ。
【０２３７】
Ｎ＝ｎ０２ｗ＋ｎ１
Ａ＝ａ０２ｗ＋ａ１
Ｂ＝ｂ０２ｗ＋ｂ１
分割部３１１は、メモリ領域のＹＮ１にメッセージｎ１を、ＹＮ０にメッセージｎ０を、ＹＡ１にメッセージａ１、ＹＡ０にメッセージａ０、ＹＢ１にメッセージｂ１、ＹＢ０にメッセージｂ０を出力する（Ｓ４０２）。
【０２３８】
次に、表現処理部３０１の行う合成処理について説明する。表現処理部３０１内の合成部３１２は、入出力処理部３０２がメモリ領域のＸＱに格納したメッセージｑsとＸＲに格納したメッセージｒsを用い、（ｒs２ｗ＋ｑs）の値を保持するメッセージＣを作成する機能を有する。
【０２３９】
まず、表現処理部３０１内の合成部３１２は、メッセージｑｓとメッセージｒｓを記憶装置１２３から読み込む（Ｓ４５１）。次に、メッセージｑｓとメッセージｒｓを用い、（ｒｓ２ｗ＋ｑｓ）の値を保持するメッセージＣを作成する。従って、メッセージＣ、メッセージｒs、メッセージｑsには以下の式が成り立つ。
【０２４０】
Ｃ＝ｒs２ｗ＋ｑs
合成部３１２は、共通部３０４における条件判定部３４３を用い、メッセージＣが条件式０≦Ｃ＜Ｎを満たすかを判定する。条件式を満たさない場合は、共通部３０４における剰余計算部３４２を用い、以下の式を満たすメッセージＣを作成する。
【０２４１】
Ｃ＝（ｒs２ｗ＋ｑs）ｍｏｄ Ｎ
ただし、０≦Ｃ＜Ｎ＜２2ｗである。
【０２４２】
合成部３１２は、メッセージＣを記憶装置１２３へ出力する（Ｓ４５２）。
【０２４３】
＜入出力処理部の処理＞
次に、図１８により、本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部３０２の処理について説明する。図１８は本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【０２４４】
ＭＵは、入出力処理部３０２と連携する、剰余処理部３０３を表し、ＭＵの入力変数は右辺の括弧内に、出力変数は左辺に表す。入出力処理部３０２は、各メッセージを格納するメモリ領域である、ＹＡ０、ＹＡ１、ＹＢ０、ＹＢ１、ＹＮ０、ＹＮ１、ＸＱ、ＸＲ、ＸＮ、ＸＴを用いる。
【０２４５】
入出力処理部３０２は、入力したモンゴメリ乗算用のメッセージを用い、剰余処理部３０３へモンゴメリ乗算用のメッセージを出力する機能を有する。また、剰余処理部３０３へ、出力するメッセージを適切にメモリ領域に格納し、２ｗビットのモンゴメリ乗算に基づく剰余乗算の剰余を計算する機能を有する。
【０２４６】
＜入出力処理＞
入力部３２１は、メッセージａ１を格納するＹＡ１を乗数、メッセージｂ１を格納するＹＢ１を被乗数、メッセージｎ１を格納するＹＮ１を法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ１をＸＲに、剰余ｒ１を指すメッセージｒ１をＸＴに出力するよう指示する。各メッセージの関係は、式（ａ１ｂ１＝ｑ１ｎ１＋ｒ１２ｗ）で表される（Ｓ１８０１）。
【０２４７】
入力部３２１は、メッセージｎ０を格納するＹＮ０を乗数、メッセージｑ１を格納するＸＲを被乗数、定数１をＸＮに格納後、ＸＮを法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ2をＸＲに、剰余を指すメッセージｒ2をＸＱに出力するよう指示する。各メッセージの関係は、式（ｑ１ｎ０＝ｑ２＋ｒ２２ｗ）で表される（Ｓ１８０２）。
【０２４８】
蓄積部３２４は、ＸＲに格納されたメッセージｑ2とＸＴに格納されたメッセージｒ１を加減乗算部３４１に入力し、（ｒ１−ｑ２）の値を持つメッセージ（ｒ１−ｑ２）をＸＲに格納する（Ｓ１８０３）。
【０２４９】
入力部３２１は、定数１を格納後にＸＴを乗数、メッセージ（ｒ１−ｑ２）を格納するＸＲを被乗数、メッセージｎ１を格納するＹＮ１を法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ３をＸＲに、剰余を指すメッセージｒ３をＸＮに出力するよう指示する。各メッセージの関係は、式（ｒ１−ｑ２＝ｑ３ｎ１＋ｒ３２ｗ）で表される（Ｓ１８０４）。
【０２５０】
蓄積部３２４は、ＸＮに格納されたメッセージｒ３とＸＱに格納されたメッセージｒ２を加減乗算部３４１に入力し、（ｒ３−ｒ２）の値を持つメッセージｑsをＸＱに格納する（Ｓ１８０５）。
【０２５１】
入力部３２１は、メッセージａ１を格納するＹＡ１を乗数、メッセージｂ０を格納するＹＢ０を被乗数、定数１を格納後、ＸＮを法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ４をＸＮに、剰余を指すメッセージｒ４をＸＴに出力するよう指示する。各メッセージの関係は、式（ａ１ｂ０＝ｑ４ｎ１＋ｒ４２ｗ）で表される（Ｓ１８０６）。
【０２５２】
蓄積部３２４は、ＸＲに格納されたメッセージｑsとＸＴに格納されたメッセージｒ4を加減乗算部３４１に入力し、（ｑs＋ｒ４）の値を持つメッセージｑsをＸＱに格納する。蓄積部３２４は、ＸＮに格納されたメッセージｑ４とＸＲに格納されたメッセージｑ３を加減乗算部３４１に入力し、（ｑ３＋ｑ４）の値を持つメッセージｒsをＸＲに格納する（Ｓ１８０７）。
【０２５３】
入力部３２１は、メッセージａ０を格納するＹＡ０を乗数、メッセージｂ１を格納するＹＢ１を被乗数、メッセージｎ１を格納すＹＮ１を法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ５をＸＮに、剰余を指すメッセージｒ５をＸＴに出力するよう指示する。各メッセージの関係は、式（ａ０ｂ１＝ｑ５ｎ１＋ｒ５２ｗ）で表される（Ｓ１８０８）。
【０２５４】
蓄積部３２４は、ＸＱに格納されたメッセージｑsとＸＴに格納されたメッセージｒ５を加減乗算部３４１に入力し、（ｑs＋ｒ５）の値を持つメッセージｑsをＸＱに格納する。蓄積部３２４は、ＸＮに格納されたメッセージｑ５とＸＲに格納されたメッセージｒsを加減乗算部３４１に入力し、（ｒs＋ｑ５）の値を持つメッセージｒsをＸＲに格納する（Ｓ１８０９）。
【０２５５】
入力部３２１は、メッセージｎ０を格納するＹＮ０を乗数、メッセージｒsを格納するＸＲを被乗数、定数１をＸＮに格納後、ＸＮを法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ６をＸＮに、剰余を指すメッセージｒ６をＸＴに格納するよう指示する。各メッセージの関係は、式（ｎ０ｒs＝ｑ６＋ｒ６２ｗ）で表される（Ｓ１８１０）。
【０２５６】
蓄積部３２４は、ＸＱに格納されたメッセージｑsとＸＮに格納されたメッセージｑ６を加減乗算部３４１に入力し、（ｑs−ｑ６）の値を持つメッセージｑsをＸＱに格納する（Ｓ１８１１）。
【０２５７】
入力部３２１は、メッセージａ０を格納するＹＡ０を乗数、メッセージｂ０を格納するＹＢ０を被乗数、定数１をＸＮに格納後、ＸＮを法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ７をＸＮに、剰余を指すメッセージｒ７をＸＴに格納するよう指示する。各メッセージの関係は、式（ａ０ｂ０＝ｑ7＋ｒ7２ｗ）で表される（Ｓ１８１２）。
【０２５８】
蓄積部３２４は、ＸＱに格納されたメッセージｑsとＸＮに格納されたメッセージｑ７を加減乗算部３４１に入力し、（ｑs＋ｑ７）の値を持つメッセージｑsをＸＱに格納する。蓄積部３２４は、ＸＲに格納されたメッセージｒ７とＸＴに格納されたメッセージｒ６を加減乗算部３４１に入力し、（ｒ７−ｒ６）の値を持つメッセージｒsをＸＲに格納する（Ｓ１８１３）。
【０２５９】
＜補正部の処理＞
本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の補正部３２２の処理は、実施の形態１と同様である。
【０２６０】
＜剰余処理部の処理＞
本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の剰余処理部３０３の処理は、実施の形態１と同様である。
【０２６１】
＜入出力処理部と剰余処理部の構成＞
入出力処理部３０２と剰余処理部３０３は、メッセージの交換に記憶装置１２３を用いる。
【０２６２】
次に、図１９により、本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムの記憶装置１２３へのメッセージの格納状態について説明する。図１９は、本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【０２６３】
図１９は、行と列をもつ表から構成される。最も左の列は、図１８で示したフローチャートの各ステップであり、他の列は、メッセージを格納する記憶領域であるＸＮ、ＸＱ、ＸＲ、ＸＴ、ＹＡ１、ＹＡ０、ＹＢ１、ＹＢ０、ＹＮ１、ＹＮ０を意味する。各行には記憶領域内に格納されるメッセージを表し、「任意」は、格納されているメッセージはどのような値でもかまわない。また、左の行が示すステップを実行後の、メッセージを各列に示す。ただし、「―」は以前の処理にて格納されたメッセージを格納し続ける状態を指す。また、定数を表すメッセージｚは、ｚ＝１である。
【０２６４】
以上のように実施の形態３では、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算を処理することが可能である。
【０２６５】
（実施の形態４）
＜実施の形態４の概要＞
実施の形態４では、剰余乗算器１１３が古典的な乗算を実装する場合、２倍剰余乗算部１１６が、２ｗビットからなるメッセージを対象に、古典的な剰余乗算に基づく剰余乗算を計算する第４の計算方法について説明する。実施の形態３との違いは、剰余乗算器１１３が実装する剰余乗算の種類である。
【０２６６】
＜２倍剰余乗算部の処理の概要＞
本発明の実施の形態４に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の２倍剰余乗算部１１６の処理は、実施の形態２（図１２のシーケンス図を参照）と同様である。
【０２６７】
＜表現処理部の処理＞
本発明の実施の形態４に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の表現処理部３０１の行う分割処理と合成処理について説明する。
【０２６８】
まず、表現処理部３０１の行う分割処理について説明する。表現処理部３０１は、メッセージを古典的な剰余乗算の計算に適した形式である古典的な剰余乗算用のメッセージに変換する機能を有する。ただし、古典的な剰余乗算の計算に適した形式とは、２ｗビットの整数Ｘを上位側ｗビットの整数ｘ１と下位側ｗビットの整数ｘ０で表すように、変換した（式１）を満たす整数表現を指す。
【０２６９】
Ｘ＝ｘ１２ｗ＋ｘ０        …（式１）
ただし、０≦Ｘ＜２2ｗかつ０≦ｘ０、ｘ１＜２ｗである。
【０２７０】
まず、表現処理部３０１がもつ分割部３１１に２ｗビットのメッセージＡ、２ｗビットのメッセージＢ、２ｗビットのメッセージＮを記憶装置１２３から読み込む（Ｓ１１０１）。次に、分割部３１１は、各メッセージを上位ｗビットと下位ｗビットに分け、（式１）を満たすよう、メッセージＡからメッセージａ１とメッセージａ０、メッセージＢからメッセージｂ１とメッセージｂ０、メッセージＮからメッセージｎ１とメッセージｎ０を作成する。従って、以下の式が成り立つ。
【０２７１】
Ｎ＝ｎ１２ｗ＋ｎ０
Ａ＝ａ１２ｗ＋ａ０
Ｂ＝ｂ１２ｗ＋ｂ０
分割部３１１は、メモリ領域のＹＮ１にメッセージｎ１を、ＹＮ０にメッセージｎ０を、ＹＡ１にメッセージａ１、ＹＡ０にメッセージａ０、ＹＢ１にメッセージｂ１、ＹＢ０にメッセージｂ０を出力する（Ｓ１１０２）。
【０２７２】
なお、表現処理部３０１の行う分割処理では、別の方法でメッセージを作成しても良い。例えば、分割部３１１は、剰余乗算器１１３あるいは剰余処理部３０３が処理できるメッセージのビット長に応じ、自由にメッセージＮから作成するメッセージを変更する。ｗビットのメッセージＮの値をｉ倍し、ｉＮの値を持つメッセージの下位ｗビットと上位側の残りのビットに分けて、メッセージｎ１’とメッセージｎ０’を作成してもよい。
【０２７３】
ｉＮ＝ｎ１’２ｗ＋ｎ０’
次に、表現処理部３０１の行う合成処理について説明する。表現処理部３０１内の合成部３１２は、入出力処理部３０２がメモリ領域ＸＱに格納したメッセージｑｓとＸＲに格納したメッセージｒｓを用い、（ｒｓ２ｗ＋ｑｓ）の値を保持するメッセージＣを作成する機能を有する。
【０２７４】
まず、表現処理部３０１内の合成部３１２は、記憶装置１２３から、メッセージｑsとメッセージｒsを読み込む（Ｓ１１５１）。次に、（ｑｓ２ｗ＋ｒｓ）の値を持つメッセージＣを作成する。従って、メッセージＣ、メッセージｒs、メッセージｑsには以下の式が成り立つ。
【０２７５】
Ｃ＝ｒs２ｗ＋ｑs
合成部３１２は、共通部３０４における条件判定部３４３を用い、メッセージＣが条件式０≦Ｃ＜Ｎを満たすかを判定する。条件式を満たさない場合は、共通部３０４における剰余計算部３４２を用い、以下の式を満たすメッセージＣを作成する。
【０２７６】
Ｃ＝（ｒs２ｗ＋ｑs）ｍｏｄ Ｎ
ただし、０≦Ｃ＜Ｎ＜２2ｗである。
【０２７７】
合成部３１２は、メッセージＣを記憶装置１２３へ出力する（Ｓ１１５２）。
【０２７８】
＜入出力処理部の処理＞
次に、図２０により、本発明の実施の形態４に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部３０２の処理について説明する。図２０は本発明の実施の形態４に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【０２７９】
ＭＵは、入出力処理部３０２と連携する、剰余処理部３０３を表し、ＭＵの入力変数は右辺の括弧内に、出力変数は左辺に表す。入出力処理部３０２は、各メッセージを格納するメモリ領域である、ＹＡ０、ＹＡ１、ＹＢ０、ＹＢ１、ＹＮ０、ＹＮ１、ＸＱ、ＸＲ、ＸＮ、ＸＴを用いる。
【０２８０】
入出力処理部３０２は、入力した古典的な剰余乗算用のメッセージを用い、剰余処理部３０３へ古典的な剰余乗算用のメッセージを出力する機能を有する。また、剰余処理部３０３へ、出力するメッセージを適切にメモリ領域に格納し、２ｗビットの古典的な剰余乗算に基づく剰余乗算の剰余を計算する機能を有する。
【０２８１】
＜入出力処理＞
入力部３２１は、メッセージａ１を格納するＹＡ１を乗数、メッセージｂ１を格納するＹＢ１を被乗数、メッセージｎ１を格納するＹＮ１を法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ１をＸＲに、剰余ｒ１を指すメッセージｒ１をＸＴに出力するよう指示する。各メッセージの関係は、式（ａ１ｂ１＝ｑ１ｎ１＋ｒ１）で表される（Ｓ１９０１）。
【０２８２】
入力部３２１は、メッセージｎ０を格納するＹＮ０、メッセージｑ１を格納するＸＲ、定数２ｗをＸＮに格納後、ＸＮを法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ2をＸＲに、剰余を指すメッセージｒ2をＸＱに出力するよう指示する。各メッセージの関係は、式（ｑ１ｎ０＝ｑ２２ｗ＋ｒ２）で表される（Ｓ１９０２）。
【０２８３】
蓄積部３２４は、ＸＲに格納されたメッセージｑ2とＸＴに格納されたメッセージｒ１を加減乗算部３４１に入力し、（ｒ１−ｑ２）の値を持つメッセージ（ｒ１−ｑ２）をＸＲに出力する（Ｓ１９０３）。
【０２８４】
入力部３２１は、定数２ｗをＸＴに格納後、ＸＴを乗数、メッセージ（ｒ１−ｑ２）を格納するＸＲを被乗数、メッセージｎ１を格納するＹＮ１を法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ３をＸＲに、剰余を指すメッセージｒ３をＸＮに出力するよう指示する。各メッセージの関係は、式（２ｗ（ｒ１−ｑ２）＝ｑ３ｎ１＋ｒ３）で表される（Ｓ１９０４）。
【０２８５】
蓄積部３２４は、ＸＮに格納されたメッセージｒ３とＸＱに格納されたメッセージｒ２を加減乗算部３４１に入力し、（ｒ３−ｒ２）の値を持つメッセージｑsをＸＱに出力する（Ｓ１９０５）。
【０２８６】
入力部３２１は、メッセージａ１を格納するＹＡ１を乗数、メッセージｂ０を格納するＹＢ０を被乗数、メッセージｎ１を格納するＸＮを法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ４をＸＮに、剰余を指すメッセージｒ４をＸＴに出力するよう指示する。各メッセージの関係は、式（ａ１ｂ０＝ｑ４ｎ１＋ｒ４）で表される（Ｓ１９０６）。
【０２８７】
蓄積部３２４は、ＸＲに格納されたメッセージｑsとＸＴに格納されたメッセージｒ4を加減乗算部３４１に入力し、（ｑs＋ｒ４）の値を持つメッセージｑsをＸＱに出力する。蓄積部３２４は、ＸＮに格納されたメッセージｑ４とＸＲに格納されたメッセージｑ３を加減乗算部３４１に入力し、（ｑ３＋ｑ４）の値を持つメッセージｒsをＸＲに出力する（Ｓ１９０７）。
【０２８８】
入力部３２１は、メッセージａ０を格納するＹＡ０を乗数、メッセージｂ１を格納するＹＢ１を被乗数、メッセージｎ１を格納するＹＮ１を法として設定する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ５をＸＮに、剰余を指すメッセージｒ５をＸＴに出力するよう指示する。各メッセージの関係は、式（ａ０ｂ１＝ｑ５ｎ１＋ｒ５）で表される（Ｓ１９０８）。
【０２８９】
蓄積部３２４は、ＸＱに格納されたメッセージｑsとＸＴに格納されたメッセージｒ５を加減乗算部３４１に入力し、（ｑs＋ｒ５）の値を持つメッセージｑsをＸＱに出力する。蓄積部３２４は、ＸＮに格納されたメッセージｑ５とＸＲに格納されたメッセージｒsを加減乗算部３４１に入力し、（ｒs＋ｑ５）の値を持つメッセージｒsをＸＲに出力する（Ｓ１９０９）。
【０２９０】
入力部３２１は、メッセージｎ０を格納するＹＮ０を乗数、メッセージｒsを格納するＸＲを被乗数、定数２ｗをＸＮに格納後、ＸＮを法として設定する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ６をＸＮに、剰余を指すメッセージｒ６をＸＴに出力するよう指示する。各メッセージの関係は、式（ｎ０ｒs＝ｑ６２ｗ＋ｒ６）で表される（Ｓ１９１０）。
【０２９１】
蓄積部３２４は、ＸＱに格納されたメッセージｑsとＸＮに格納されたメッセージｑ６を加減乗算部３４１に入力し、（ｑs−ｑ６）の値を持つメッセージｑsをＸＱに出力する（Ｓ１９１１）。
【０２９２】
入力部３２１は、メッセージａ０を格納するＹＡ０を乗数、メッセージｂ０を格納するＹＢ０を被乗数、定数２ｗをＸＮに格納後、ＸＮを法として設定する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ７をＸＮに、剰余を指すメッセージｒ７をＸＴに出力するよう指示する。各メッセージの関係は、式（ａ０ｂ０＝ｑ7ｎ１＋ｒ7）で表される（Ｓ１９１２）。
【０２９３】
入力部３２１は、ＸＱに格納されたメッセージｑsとＸＮに格納されたメッセージｑ７を加減乗算部３４１に入力し、（ｑs＋ｑ７）の値を持つメッセージｑsをＸＱに出力する。入力部３２１は、ＸＲに格納されたメッセージｒ７とＸＴに格納されたメッセージｒ６を加減乗算部３４１に入力し、（ｒ７−ｒ６）の値を持つメッセージｒsをＸＲに出力する（Ｓ１９１３）。
【０２９４】
＜補正部の処理＞
本発明の実施の形態４に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の補正部３２２の処理は、実施の形態２と同様である。
【０２９５】
＜剰余処理部の処理＞
本発明の実施の形態４に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の剰余処理部３０３の処理は、実施の形態２と同様である。
【０２９６】
＜入出力処理部と剰余処理部の構成＞
入出力処理部３０２と剰余処理部３０３は、メッセージの交換に記憶装置１２３を用いる。実施の形態３では、図１９を用い、記憶装置１２３へのメッセージの格納状態を示した。実施の形態４における、記憶装置１２３へのメッセージの格納順序は、実施の形態３と同様であり、各処理の対応関係が示せる。即ち、実施の形態３におけるＳ１８０１は、実施の形態４におけるＳ１９０１に対応する。同様に、Ｓ１８０２はＳ１９０２、Ｓ１８０３はＳ１９０３、Ｓ１８０４はＳ１９０４、Ｓ１８０５はＳ１９０５、Ｓ１８０６はＳ１９０６、Ｓ１８０７はＳ１９０７、Ｓ１８０８はＳ１９０８、Ｓ１８０９はＳ１９０９、Ｓ１８１０はＳ１９１０、Ｓ１８１１はＳ１９１１、Ｓ１８１２はＳ１９１２、Ｓ１８１３はＳ１９１３に対応する。また、定数を表すメッセージｚは、ｚ＝２ｗである。
【０２９７】
＜応用例＞
実施の形態３、実施の形態４で述べた技術は、剰余乗算器１１３が記憶装置１２３における全てのメモリへのアクセスができることを仮定した。この仮定とは異なり、剰余乗算器１１３がいくつかのメモリへアクセスできない場合も、実施の形態３または実施の形態４と同様に、ＹＡ０、ＹＡ１、ＹＢ０、ＹＢ１、ＹＮ０、ＹＮ１、ＸＱ、ＸＲ、ＸＮ、ＸＴのみの記憶領域を用いて、本技術を適用できる。
【０２９８】
以上のように実施の形態４では、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算を処理することが可能である。
【０２９９】
（実施の形態５）
＜実施の形態５の概要＞
実施の形態１〜４で説明した技術によれば、剰余乗算器１１３がモンゴメリ乗算を実装する場合には、剰余乗算器１１３の２倍のビット長のモンゴメリ乗算の計算を、剰余乗算器１１３が古典的な剰余乗算を実装する場合は、剰余乗算器１１３の２倍のビット長の古典的な剰余乗算を計算が実現できる。実施の形態５では、本技術により、剰余乗算器１１３の種類とは異なる、剰余乗算器１１３のビット長の２倍の剰余乗算の実現方法を示す。
【０３００】
モンゴメリ乗算を応用した、高速な剰余乗算が２分剰余乗算として知られている。この剰余乗算では、以下の式によって、剰余Ｒを求める。
【０３０１】
Ｒ＝ＸＹ（αＭ）（−１）ｍｏｄ  Ｎ  
ここで、ＸとＹは２ｎビット以下のメッセージ、Ｍはモンゴメリ定数であり、αはαｗが整数かつ条件式（０＜α＜１）を満たすような小数である。例えば、ｗが偶数とのとき、αの値として０．５が取れる。
【０３０２】
この２分剰余乗算は、モンゴメリ定数の値を変更したモンゴメリ乗算とみなせる。本実施の形態５では、モンゴメリ乗算を剰余乗算器１１３が実装する場合に、αを０．５とする、剰余乗算器１１３の２倍のビット長のモンゴメリ乗算（２分剰余乗算）の実現方法を示す。
【０３０３】
＜２倍剰余乗算部の処理の概要＞
図２１より、本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の２倍剰余乗算部１１６の処理について説明する。図２１は本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の２倍剰余乗算部の処理を示すシーケンス図であり、２倍剰余乗算部１１６の機能ブロックである表現処理部３０１、入出力処理部３０２、剰余処理部３０３のメッセージの受け渡しの様子を示している。実施の形態５に係る剰余乗算処理装置を適用した通信システムの構成は実施の形態１と同様である。
【０３０４】
まず、表現処理部３０１へメッセージが入力される（Ｓ２１０１）。表現処理部３０１は、入力したメッセージから、剰余乗算器１１３が実装するモンゴメリ乗算に適するよう、モンゴメリ乗算の計算用に変換したメッセージ（以降、モンゴメリ乗算用のメッセージと呼ぶ）を作成し、入出力処理部３０２へ出力する（Ｓ２１０２）。
【０３０５】
入出力処理部３０２は、適当なメッセージまたは定数を選択し（詳細な処理内容は後述）、剰余処理部３０３へ出力する（Ｓ２１０３）。剰余処理部３０３は、モンゴメリ乗算の剰余を計算し、入出力処理部３０２へ出力する（Ｓ２１０４）。
【０３０６】
入出力処理部３０２は、適当なメッセージまたは定数を選択し（詳細な処理内容は後述）、剰余処理部３０３へ出力する（Ｓ２１０５）。剰余処理部３０３は、古典的な剰余乗算の商と剰余を計算し、入出力処理部３０２へ出力する（Ｓ２１０６）。入出力処理部３０２は、適当なメッセージまたは定数を選択し（詳細な処理内容は後述）、剰余処理部３０３へ出力する（Ｓ２１０７）。
【０３０７】
剰余処理部３０３は、モンゴメリ乗算の商と剰余を計算し、入出力処理部３０２へ出力する（Ｓ２１０８）。以降、入出力処理部３０２と剰余処理部３０３は、上記のメッセージの交換処理を複数回繰り返し、入出力処理部３０２は、複数個の古典的な剰余乗算の商と剰余と、モンゴメリ乗算用の商と剰余を合成したメッセージを合成したメッセージを、表現処理部３０１へ出力する（Ｓ２１５１）。
【０３０８】
表現処理部３０１は、合成したメッセージをデータ処理部１１５へ出力する（Ｓ２１５２）。なお、表現処理部３０１、入出力処理部３０２、剰余処理部３０３のメッセージの受け渡しには、記憶装置１２３へのメッセージの書き込みと読み出しを用い、メッセージの受け渡しを実施する。ただし、ネットワーク１５１を用い、メッセージの受け渡しを実施しても良い。
【０３０９】
＜表現処理部の処理の概要＞
本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の表現処理部３０１の処理は、実施の形態１と同様である。
【０３１０】
ただし、実施の形態５で示す手法では、剰余乗算の法であるメッセージＮを分割したメッセージｎ１とメッセージｎ０の双方を法として用いる。従って、モンゴメリ乗算の条件である奇数の法を作成するよう、次式に基づき、メッセージｎ０の代わりに、（ｎ０＋１）の値を持つメッセージｎ’０を作成し、剰余乗算の法として用いても良い。この変換は、以下の式に基づいており、
Ｎ＝（ｎ０＋１）２ｗ−（２ｗ−ｎ１）
＝ｎ０２ｗ＋ｎ１
（ｎ０＋１）の値を持つメッセージｎ’０を用いる場合、メッセージｎ１の代わりに−（２ｗ−ｎ１）の値を持つメッセージｎ’１を用いる。
【０３１１】
＜入出力処理部の処理の概要＞
次に、図２２により、本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部３０２の処理について説明する。図２２は本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【０３１２】
ＭＵｃとＭＵｍは、それぞれ剰余処理部３０３を表す。入力するメッセージの組はそれぞれ、ＭＵｃまたはＭＵｍの右辺の括弧内に、剰余処理部３０３から出力するメッセージは左辺の括弧内に表す。なお、ＭＵｃ、ＭＵｍの説明は後述する。
【０３１３】
入出力処理部３０２と剰余処理部３０３のメッセージの受け渡しには、記憶装置１２３を用いる。メッセージの格納領域として、ＲＡＭ１４１におけるＸＡ、ＸＢ、ＸＮ、ＸＲと、他の記憶領域（例えばＲＡＭ１３１）におけるＹＱ、ＹＲ、ＹＴ（メッセージの格納用に領域を定義）を用いる。
【０３１４】
なお、入出力処理部３０２と剰余処理部３０３におけるメッセージ交換の際の記憶装置１２３の利用方法の詳細については、図２４と図２５を用いて後述する。
【０３１５】
＜入出力処理＞
入力部３２１は、メッセージａ１をＹＱに、メッセージｂ１をＸＢに、メッセージｎ１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ出力する商を指すメッセージｑ１をＸＢに、剰余ｒ１を指すメッセージｒ１をＹＴに格納するよう指示する（Ｓ２２０１）。
【０３１６】
入力部３２１は、メッセージｎ０をＸＡに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ2をＹＱに、剰余を指すメッセージｒ2をＹＲに格納するよう指示する（Ｓ２２０２）。
【０３１７】
蓄積部３２４は、ＹＲに格納されたメッセージｒ2とＹＴに格納されたメッセージｒ１を加減乗算部３４１に入力し、（ｒ１−ｒ２）の値を持つメッセージｒｓをＹＲに格納する（Ｓ２２０３）。
【０３１８】
入力部３２１は、メッセージａ０をＸＡに、メッセージｂ０をＸＢに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ3をＸＢに、剰余を指すメッセージｒ3をＹＴに格納するよう指示する（Ｓ２２０４）。
【０３１９】
蓄積部３２４は、ＹＲに格納されたメッセージｒｓとＹＴに格納されたメッセージｒ３を加減乗算部３４１に入力し、（ｒｓ−ｒ３）の値を持つメッセージｒｓをＹＲに格納するよう指示する（Ｓ２２０５）。
【０３２０】
入力部３２１は、加減乗算部３４１に対してメッセージを交換し、定数（２ｗ−１）をＸＡに、（ｑ２＋ｑ３）の値を持つメッセージ（ｑ２＋ｑ３）をＸＢに、メッセージｎ０をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ4をＸＢに、剰余を指すメッセージｒ4をＹＱに格納するよう指示する（Ｓ２２０６）。
【０３２１】
入力部３２１は、メッセージｎ１をＸＡに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、商を指すメッセージｑ5をＸＢに、剰余を指すメッセージｒ5をＹＴに格納するよう指示する（Ｓ２２０７）。
【０３２２】
蓄積部３２４は、ＹＲに格納されたメッセージｒｓとＹＱに格納されたメッセージｒ４を加減乗算部３４１に入力し、（ｒｓ＋ｒ４）の値を持つメッセージｑｓをＹＱに格納する。ついで、蓄積部３２４は、ＹＲに格納されたメッセージｑｓとＸＢに格納されたメッセージｑ５を加減乗算部３４１に入力し、（ｑ５−ｑｓ）の値を持つメッセージｑｓをＹＱに格納する。さらに、蓄積部３２４は、ＹＴに格納されたメッセージｒ５とＹＲに格納されたメッセージｒｓを加減乗算部３４１に入力し、（ｒ５−ｒｓ）の値を持つメッセージｒｓをＹＲに格納する（Ｓ２２０８）。
【０３２３】
入力部３２１は、加減乗算部３４１に対してメッセージを交換し、（ａ１＋ａ０）の値を持つメッセージ（ａ１＋ａ０）をＸＡに、（ｂ１＋ｂ０）の値を持つメッセージ（ｂ１＋ｂ０）をＸＢに、定数１をＸＮに格納する。出力指示部３２３は、剰余処理部３０３へ、出力する商を指すメッセージｑ６をＸＡに、剰余を指すメッセージｒ６をＹＴに格納するよう指示する（Ｓ２２０９）。
【０３２４】
蓄積部３２４は、ＸＡに格納されたメッセージｑ６とＹＱに格納されたメッセージｑｓを加減乗算部３４１に入力し、（ｑｓ＋ｑ６）の値を持つメッセージｑｓをＹＱに格納する。さらに、蓄積部３２４は、ＹＴに格納されたメッセージｒ６とＹＲに格納されたメッセージｒｓを加減乗算部３４１に入力し、（ｒｓ＋ｒ６）の値を持つメッセージｒｓをＹＲに格納する（Ｓ２２１０）。
【０３２５】
＜補正部の処理＞
本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の補正部３２２の処理は、実施の形態１（図４のシーケンス図を参照）と同様である。
【０３２６】
＜剰余処理部の処理＞
次に、図２３により、本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部３０３の処理について説明する。図２３は本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートである。
【０３２７】
本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ１０１内の剰余処理部３０３の処理は、２種類の異なる処理手続きＭＵｃ、ＭＵｍを有する。
【０３２８】
ＭＵｃは、実施の形態１における剰余処理部３０３の処理手続き（図９のフローチャートを参照）と同様であり、入力されたメッセージを乗数、被乗数、法とみなし、モンゴメリ乗算における剰余乗算の商と剰余を計算する。
【０３２９】
ＭＵｍは、入力されたメッセージを乗数、被乗数、法とみなし、古典的な剰余乗算における剰余乗算の商と剰余を計算する。実施の形態２における剰余処理部３０３の処理と同様であるが、実施の形態５では仮定する剰余乗算器１１３（剰余乗算の種類）が異なるため、図２３に示すように、ＭＵｍは実施の形態２と異なる処理手続きである。
【０３３０】
次に、ＭＵｍの処理手続きを説明する。
【０３３１】
乗数変更部３３５は、剰余乗算を実行する前に、下記の式を用い、ＸＢに設定されたメッセージｙ、ＸＮに設定されたメッセージｚが０≦ｙ＜ｚを満たすよう、メッセージｙの値を変更する（Ｓ２３０１）。
【０３３２】
ｙ←ｙ−ｊｚ
ただし、ｊは整数である。また、ｘとｙの値を変更する必要がない場合、ｉ＝ｊ＝０が成り立ち、Ｓ２３０１と後述するＳ２３１３の処理は不要である。
【０３３３】
剰余乗算器取扱部３３１は、入力部３２１が、ＸＡ、ＸＢ、ＸＮに設定したメッセージに基づき、モンゴメリ乗算による剰余乗算の剰余を計算する。ＸＡにメッセージｘ、ＸＢにメッセージｙ、ＸＮにメッセージｚを設定した場合、以下の式で定義されるモンゴメリ乗算の剰余ｙ’をＸＲに出力する。
【０３３４】
ｙ’←ｘｙ２−ｗｍｏｄ ｚ
ただし、ｘは乗数、ｙは被乗数、ｚは法である。次に、移動部３３３は、メッセージｙ’をＸＡへ移動する（Ｓ２３０２）。
【０３３５】
剰余乗算器取扱部３３１は、ＸＡ、ＸＢ、ＸＮに設定したメッセージに基づき、モンゴメリ乗算による剰余乗算の剰余を計算する。ＸＡにメッセージｘ、ＸＢにメッセージｙ’、ＸＮにメッセージｚが設定してあるので、以下の式で定義されるモンゴメリ乗算の剰余ｒをＸＲに出力する。
【０３３６】
ｒ←ｘｙ’２−ｗｍｏｄ ｚ
ただし、ｘは乗数、ｙ’は被乗数、ｚは法である。次に、移動部３３３は、出力格納部が指示したメッセージの格納領域へ、メッセージｒを移動する（Ｓ２３０３）。
【０３３７】
法変更部３３４は、加減乗算部３４１を用い、ＸＮに設定したメッセージｚの値を変更し、ｚ＋２の値を持つメッセージｚ’を作成し、ＸＮに格納する（Ｓ２３０４）。
【０３３８】
剰余乗算器取扱部３３１は、ＸＡ、ＸＢ、ＸＮに設定されたメッセージに基づき、モンゴメリ乗算による剰余乗算の剰余を計算する。ＸＡにメッセージｘを、ＸＢにメッセージｙを、ＸＮにメッセージｚ’を設定した場合、以下の式で定義されるモンゴメリ乗算の剰余ｒ’をＸＲに出力する。
【０３３９】
ｒ’←ｘｙ’２−ｗｍｏｄ ｚ’
ただし、ｘは乗数、ｙは被乗数、ｚ’は法である（Ｓ２３０５）。
【０３４０】
商演算部３３２は、条件判定部３４３を用い、ｒ−ｒ’が偶数であればＳ２３０９へ、奇数であればＳ２３０８へと進む（Ｓ２３０６）。商演算部３３２は、条件判定部３４３を用い、条件式（ｒ’≦ｒ）を満たせばＳ２３１１へ、満たさなければＳ２３１０へと進む。商演算部３３２は、メッセージδの値を１と設定する（Ｓ２３０８）。または、商演算部３３２は、メッセージδの値を０と設定する（Ｓ２３１１）。または、商演算部３３２は、メッセージδの値を２と設定する（Ｓ２３１０）。
【０３４１】
商演算部３３２は、加減乗算部３４１と剰余計算部３４２を用い、以下の式を満たすメッセージｑを計算する（Ｓ２３１２）。
【０３４２】
ｑ← (ｒ−ｒ’＋δｚ’)／２
商演算部３３２は、加減乗算部３４１と剰余計算部３４２を用い、以下の式を満たすメッセージｑを計算し、出力指示部３２３が指示したメッセージの格納領域へ、メッセージｑを出力する（Ｓ２３１３）。
【０３４３】
ｑ← ｑ＋ｊｘ
＜入出力処理部と剰余処理部の構成＞
次に、図２４および図２５により、本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムの記憶装置１２３へのメッセージの格納順序について説明する。図２４および図２５は、本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【０３４４】
図２４および図２５は、行と列をもつ表から構成される。最も左の列は、図２２および図２３で示したフローチャートの各ステップと対応を取り、他の列は、メッセージを格納する記憶領域であるＸＲ、ＸＡ、ＸＢ、ＸＮ、ＹＱ、ＹＲ、ＹＴを意味する。
【０３４５】
各行には記憶領域内に格納されるメッセージを表し、「任意」は、格納されているメッセージはどのような値でもかまわない。また、上行から下行に順々に処理が実行され、「―」は以前の処理にて格納されたメッセージを格納し続ける状態を指す。また、ｙ、ｚは定数を表すメッセージであり、例えば、図２４および図２５では、定数ｘは式（２2ｗ ｍｏｄ ｎ１）の値を持ち（即ち、ｙ＝２2ｗｍｏｄ ｎ１が成り立つ）、定数ｙはｙ＝２ｗ−１、定数ｚはｚ＝１である。
【０３４６】
Ｓ２２０１の第１行目では、ＹＱにメッセージａ１、ＸＢにメッセージｂ１、ＸＮにメッセージｎ１が格納される。Ｓ２２０１の第２行目では、ＸＡに定数ｘが格納される。Ｓ２２０１の第３行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ０が格納される。
【０３４７】
Ｓ２２０１の第４行目では、ＸＢにメッセージｒ０が格納される。Ｓ２２０１の第５行目では、ＸＡにメッセージａ１が格納される。Ｓ２２０１の第６行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ１が格納される。
【０３４８】
Ｓ２２０１の第７行目では、ＹＴにもメッセージｒ１が格納される。Ｓ２２０１の第８行目では、メッセージｎ１の値を変更したメッセージｎ’１がＸＮに格納される。Ｓ２２０１の第９行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’１が格納される。Ｓ２２０１の第１０行目では、ＸＢに古典的な剰余乗算の商であるメッセージｑ１が格納される。
【０３４９】
Ｓ２２０２の第１行目では、ＸＡにメッセージｎ０、ＸＮにメッセージｚが格納される。Ｓ２２０２の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ２が格納される。他の記憶領域に格納するメッセージに変更はない。
【０３５０】
Ｓ２２０２の第３行目では、ＹＲにもメッセージｒ２が格納される。Ｓ２２０２の第４行目では、メッセージｚの値を変更したメッセージｚ’がＸＮに格納される。Ｓ２２０２の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’２が格納される。Ｓ２２０２の第６行目では、ＸＢにモンゴメリ乗算の商であるメッセージｑ２が格納される。
【０３５１】
Ｓ２２０３では、（ｒ１−ｒ２）の値をもつメッセージｒｓがＹＲに格納される。
【０３５２】
Ｓ２２０４の第１行目では、ＸＡにメッセージａ０、ＸＢにメッセージｂ０、ＸＮにメッセージｚが格納される。Ｓ２２０４の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ３が格納される。Ｓ２２０４の第３行目では、ＹＴにもメッセージｒ３が格納される。Ｓ２２０４の第４行目では、メッセージｚの値を変更したメッセージｚ’がＸＮに格納される。
【０３５３】
Ｓ２２０４の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’３が格納される。Ｓ２２０４の第６行目では、ＸＡにモンゴメリ乗算の商であるメッセージｑ３が格納される。
【０３５４】
Ｓ２２０５では、（ｒｓ−ｒ３）の値をもつメッセージｒｓがＹＲに格納される。
【０３５５】
Ｓ２２０６の第１行目では、ＸＡに定数ｙ、ＸＢに（ｑ２＋ｑ３）の値をもつメッセージ（ｑ２＋ｑ３）が、ＸＮにメッセージｎ０が格納される。Ｓ２２０６の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ４が格納される。Ｓ２２０６の第３行目では、ＹＱにもメッセージｒ４が格納される。Ｓ２２０６の第４行目では、メッセージｎ０の値を変更したメッセージｎ’０がＸＮに格納される。
【０３５６】
Ｓ２２０６の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’４が格納される。Ｓ２２０６の第６行目では、ＸＢにモンゴメリ乗算の商であるメッセージｑ４が格納される。
【０３５７】
Ｓ２２０７の第１行目では、ＸＡにメッセージｎ１、ＸＮに定数ｚが格納される。Ｓ２２０７の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ５が格納される。Ｓ２２０７の第３行目では、ＹＴにもメッセージｒ５が格納される。Ｓ２２０７の第４行目では、定数ｚの値を変更した定数ｚ’がＸＮに格納される。
【０３５８】
Ｓ２２０７の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’５が格納される。Ｓ２２０７の第６行目では、ＸＢにモンゴメリ乗算の商であるメッセージｑ５が格納される。
【０３５９】
Ｓ２２０８の第１行目では、（−ｒｓ−ｒ４＋ｑ５）の値をもつメッセージｑｓがＹＱに格納される。Ｓ２２０８の第２行目では、（−ｒｓ＋ｒ５）の値を持つメッセージｒｓがＹＲに格納される。
【０３６０】
Ｓ２２０９の第１行目では、（ａ１＋ａ０）の値を持つメッセージがＸＡに、（ｂ１＋ｂ０）の値を持つメッセージがＸＢに、定数ｚがＸＮに格納される。Ｓ２２０９の第２行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ６が格納される。Ｓ２２０９の第３行目では、ＹＴにもメッセージｒ６が格納される。Ｓ２２０９の第４行目では、定数ｚの値を変更した定数ｚ’がＸＮに格納される。
【０３６１】
Ｓ２２０９の第５行目では、ＸＲにモンゴメリ乗算の剰余であるメッセージｒ’６が格納される。Ｓ２２０９の第６行目では、ＸＡにモンゴメリ乗算の商であるメッセージｑ６が格納される。
【０３６２】
Ｓ２２１０の第１行目では、（ｑｓ＋ｑ６）の値をもつメッセージｑｓがＹＱに格納される。Ｓ２２１０の第２行目では、（ｒｓ＋ｒ６）の値をもつメッセージｒｓがＹＲに格納される。
【０３６３】
＜応用例＞
実施の形態５では、剰余乗算器１１３の種類とは異なる、剰余乗算器１１３の２倍のビット長の剰余乗算の実現方法の一例として、剰余乗算器１１３がモンゴメリ乗算を実装する場合に、剰余乗算器１１３のビット長の２倍の２倍剰余乗算の実現方法を示した。本技術の他の利用例として、例えば、剰余乗算器１１３がモンゴメリ乗算を実装する場合に、剰余乗算器１１３のビット長の２倍の古典的な剰余乗算が実現できる。
【０３６４】
また、剰余乗算器１１３が古典的な剰余乗算を実装する場合にも、剰余乗算器１１３のビット長の２倍のモンゴメリ乗算、または２分割剰余乗算を実現できる。
【０３６５】
また、実施の形態５では、実施の形態１と同様の構成の通信システム（図1を参照）を用いた。他に本技術が適用できる通信システムの構成として、例えば、実施の形態３と同様の通信システムがある。
【０３６６】
また、ＲＳＡの署名検証や暗号化処理などでは、剰余乗算器１１３がモンゴメリ乗算を実装する場合、事前計算として、モンゴメリ定数の自乗を必要とする場合がある。実施の形態５で説明した本技術を用いると、この事前計算の計算処理が軽く、または不要になるように、他の剰余乗算への変更が可能であり、計算の高速化にも貢献できる。
【０３６７】
また、実施の形態１、２、５では、剰余乗算器１１３が利用する記憶領域は重複しないように、即ち、ＸＲ、ＸＡ、ＸＢ、ＸＮが異なる記憶領域を指すように説明した。しかし、これらの記憶領域が同一の領域を指しても、容易に本技術は実現可能である。
【０３６８】
以上のように実施の形態５では、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算を処理することが可能である。
【０３６９】
（実施の形態６）
実施の形態１〜５で述べた技術は、ＲＳＡ暗号、ＥｌＧａｍａｌ暗号やＤＳＡ暗号、さらに楕円暗号、乱数生成など、剰余乗算を利用する全ての処理に適用できる。本技術により実現できる暗号技術の例として、ＲＳＡ暗号におけるメッセージの暗号化処理について説明する。
【０３７０】
図２６により、本発明の実施の形態６に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置１２１が行う全体処理について説明する。図２６は本発明の実施の形態６に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置が行うメッセージの受け渡しの様子を示したシーケンス図である。
【０３７１】
データ処理部１１５は、入出力インタフェース１１１あるいは記憶装置１２３を介して公開鍵とメッセージが入力されると（Ｓ２６０１）、入力されたメッセージのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるようにメッセージを区切る。また、短い場合には、パディング処理により、メッセージを予め定めたビット長となるように設定する。以下、所定のビット長として２ｗビットに区切られている部分メッセージ（これ以降、部分メッセージをメッセージと呼ぶ）について説明する。ただし、ｗは正の整数とする。
【０３７２】
データ処理部１１５は、メッセージを２倍剰余乗算部１１６に出力する（Ｓ２６０２）。
【０３７３】
２倍剰余乗算部１１６では、まず、入力されたメッセージを剰余乗算器１１３が実装する剰余乗算（モンゴメリ乗算または古典的な剰余乗算）に適した形式に変換し、剰余乗算器１１３を用い、２ｗビットの剰余を計算する。２倍剰余乗算部１１６は、剰余乗算器１１３が実装する剰余乗算に適した形式からメッセージをデータ処理部１１５へ入力時の整数表現に変換し、データ処理部１１５へ出力する（Ｓ２６０３）。
【０３７４】
Ｓ２６０２とＳ２６０３により、２ｗビットのメッセージに対し、２ｗビットの剰余乗算が１回計算された。ＲＳＡ暗号の暗号化処理では、べき乗の剰余乗算が要求されるため、２ｗビットの剰余乗算を複数繰り返せばよい。繰り返しの剰余乗算の処理が終了すると、データ処理部１１５では、べき乗の剰余乗算を計算した２ｗビットのメッセージを、入出力インタフェース１１１または記憶装置１２３へ出力する（Ｓ２６０４）。
【０３７５】
なお、データ処理部１１５と２倍剰余乗算部１１６のメッセージの受け渡しには、記憶装置１２３へのメッセージの書き込みと読み出し、またはネットワーク１５１を用い、メッセージの受け渡しを実施する。
【０３７６】
なお、２倍剰余乗算部１１６の処理内容、仮定するシステム環境は、他の実施の形態と共通である。
【０３７７】
ＲＳＡ暗号における暗号化処理の他に、復号化処理、ディジタル署名の生成、ディジタル署名の検証処理に本技術が適用できる。特に、ディジタル署名の生成と検証を用いると、暗号技術による認証手段が提供できる。
【０３７８】
＜応用例＞
各実施の形態では、剰余乗算器１１３のビット長のｋ（０＜ｋ≦２）倍の剰余乗算の演算方法を示したが、本技術を再帰的に利用し、ビット長のｋ’（＞２）倍化にも対応できる。例として、本技術の再帰的な利用により、剰余乗算器１１３の最大ビット長の４倍化が可能である。
【０３７９】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【産業上の利用可能性】
【０３８０】
本発明は、セキュリティ技術に用いられる剰余乗算処理装置に関し、特に、サーバ、ストレージ、ＩＣカード等に搭載される暗号機器への実装に適用可能である。
【図面の簡単な説明】
【０３８１】
【図１】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムの全体構成を示す構成図である。
【図２】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置が行うメッセージの受け渡しの様子を示したシーケンス図である。
【図３】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の２倍剰余乗算部の構成を示す機能ブロック図である。
【図４】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の２倍剰余乗算部の処理を示すシーケンス図である。
【図５】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図６】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図７】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図８】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図９】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートである。
【図１０】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【図１１】本発明の実施の形態１に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【図１２】本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の２倍剰余乗算部の処理を示すシーケンス図である。
【図１３】本本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図１４】本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図１５】本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図１６】本発明の実施の形態２に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートである。
【図１７】本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムの全体構成を示す構成図である。
【図１８】本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図１９】本発明の実施の形態３に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【図２０】本発明の実施の形態４に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図２１】本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の２倍剰余乗算部の処理を示すシーケンス図である。
【図２２】本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図２３】本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートである。
【図２４】本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【図２５】本発明の実施の形態５に係る剰余乗算処理装置を適用した通信システムのコンピュータＡ内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【図２６】本発明の実施の形態６に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置が行うメッセージの受け渡しの様子を示したシーケンス図である。
【符号の説明】
【０３８２】
１０１…コンピュータＡ、１０２…コンピュータＢ、１１１…入出力インタフェース、１１２…ＣＰＵ、１１３…剰余乗算器、１１５…データ処理部、１１６…２倍剰余乗算部、１２１…処理装置、１２２…演算装置、１２３…記憶装置、１３１…ＲＡＭ（揮発性メモリ１）、１３２…ＥＥＰＲＯＭ（不揮発性メモリ）、１３３…ＲＯＭ（不揮発性メモリ）、１４１…ＲＡＭ（揮発性メモリ２）、１５１…ネットワーク、３０１…表現処理部、３０２…入出力処理部、３０３…剰余処理部、３０４…共通部、３１１…分割部、３１２…合成部、３２１…入力部、３２２…補正部、３２３…出力指示部、３２４…蓄積部、３３１…剰余乗算器取扱部、３３２…商演算部、３３３…移動部、３３４…法変更部、３３５…乗数変更部、３４１…加減乗算部、３４２…剰余計算、３４２…剰余計算部、３４３…条件判定部。
【図１】
2011007820.tif 000003
【図２】
2011007820.tif 000004
【図３】
2011007820.tif 000005
【図４】
2011007820.tif 000006
【図５】
2011007820.tif 000007
【図６】
2011007820.tif 000008
【図７】
2011007820.tif 000009
【図８】
2011007820.tif 000010
【図９】
2011007820.tif 000011
【図１０】
2011007820.tif 000012
【図１１】
2011007820.tif 000013
【図１２】
2011007820.tif 000014
【図１３】
2011007820.tif 000015
【図１４】
2011007820.tif 000016
【図１５】
2011007820.tif 000017
【図１６】
2011007820.tif 000018
【図１７】
2011007820.tif 000019
【図１８】
2011007820.tif 000020
【図１９】
2011007820.tif 000021
【図２０】
2011007820.tif 000022
【図２１】
2011007820.tif 000023
【図２２】
2011007820.tif 000024
【図２３】
2011007820.tif 000025
【図２４】
2011007820.tif 000026
【図２５】
2011007820.tif 000027
【図２６】
2011007820.tif 000028