(57)【特許請求の範囲】
【請求項１】
乗数Ｘと被乗数Ｙの積の剰余Ｒを法Ｚのもとで計算するガロア体ＧＦ(２^m)上の剰余演算器であって、
被乗数Ｙの先頭ビットMSBが１である場合に乗数Ｘを通過させるゲートＧ１、
暫定剰余Ｒ'と前記通過による値とを加算する加算器ＡＤＤ、
前記加算器の加算値ＳＵＭの先頭ビットMSBが１である場合に法Ｚを通過させるゲートＧ２、及び、前記加算器の加算値ＳＵＭの先頭ビットMSBが１である場合に当該加算値から法Ｚを減算する減算器ＳＵＢとを有し、
前記減算器の減算値を１ビットシフトさせた値を次のクロックで前記暫定剰余Ｒ'とする課程を、クロック毎に繰り返し行うことにより前記剰余Ｒを計算する
ことを特徴とする前記剰余演算器。
【請求項２】
請求項１の剰余演算器において、
前記前記加算器の加算値ＳＵＭの先頭ビットMSBをシフトレジスタＳに取り込むことにより前記積の法Ｚによる商Ｓを計算することを特徴とする前記剰余演算器。
【請求項３】
乗数Ｘと被乗数Ｙの積の剰余Ｒを法Ｚのもとで計算するガロア体ＧＦ(２^m)上の剰余演算器であって、
被乗数Ｙの先頭ビットMSBが１である場合に乗数Ｘを通過させるゲートＧ１、
暫定剰余Ｒ'と前記通過による値とを加算する加算器ＡＤＤ、
前記加算器の加算値ＳＵＭの先頭ビットMSBが１である場合に法Ｚを通過させるゲートＧ２、
前記加算器の加算値ＳＵＭの先頭ビットMSBが１である場合に当該加算値から法Ｚを減算する減算器ＳＵＢ、及び、
１ビットワイヤシフト回路Ｔとを有する剰余演算器を、
Ｎ段継続接続させ、かつ、前記被乗数ＹをＮビットシフトレジスタで構成し、
最後の剰余演算器の値を次のクロックで先頭の剰余演算器の暫定剰余Ｒ'とする課程を、クロック毎に繰り返し行うことにより前記剰余Ｒを計算する
ことを特徴とする前記剰余演算器。
【請求項４】
請求項３の剰余演算器において、
前記前記加算器の加算値ＳＵＭの先頭ビットMSBをＮビットシフトレジスタＳに取り込むことにより前記積の法Ｚによる商Ｓを計算することを特徴とする前記剰余演算器。
【請求項５】
乗数Ｘのべき乗Ｘ^ｎの剰余Ｒを法Ｚのもとで計算するガロア体ＧＦ(２^m)若しくは ＧＦ(ｐ)上の剰余演算器であって、
剰余演算器の出力である暫定剰余ＲＸ^mを前記乗数Ｘと被乗数Ｙの双方のレジスタに格納することにより乗数Ｘの２のべき乗を計算するべき乗剰余演算部と、
べき乗数ｎを定めるレジスタ部と、
剰余演算器の出力である暫定剰余ＲＸ^nから前記べき乗剰余演算部で計算された項の直積を計算する直積剰余演算部とで構成される
ことを特徴とする前記剰余演算器。
【請求項６】
乗数Ｘと被乗数Ｙの積の剰余Ｒを法Ｚのもとで計算するガロア体ＧＦ(ｐ)上の剰余演算器であって、
被乗数Ｙの先頭ビットMSBが１である場合に乗数Ｘを通過させるゲートＧ１、
暫定剰余Ｒ'と前記通過による値とを加算する加算器ＡＤＤ、
前記加算器の加算値ＳＵＭ０から法Ｚを減算する減算器ＳＵＢ０、
当該減算の結果ボローが出ない場合に１とするフラグＢＮ０、及び、
フラグＢＮ０の値により加算値ＳＵＭ０又は当該減算値を選択するマルチプレクサＭＰＸ０からなる剰余の加算回路と、
前記マルチプレクサＭＰＸ０の出力をワイヤシフトする回路Ｔ、
前記ワイヤシフト後の値ＳＵＭ１から法Ｚを減算する減算器ＳＵＢ１、
当該減算の結果ボローが出ない場合に１とするフラグＢＮ１、及び、
フラグＢＮ１の値により加算値ＳＵＭ１又は当該減算値を選択するマルチプレクサＭＰＸ１からなるワイヤシフト回路とで構成され、
前記マルチプレクサＭＰＸ１の出力される値を次のクロックで前記暫定剰余Ｒ'とする課程を、クロック毎に繰り返し行うことにより前記剰余Ｒを計算する
ことを特徴とする前記剰余演算器。
【請求項７】
請求項６の剰余演算器において、
前記フラグＢＮ０の出力を減算値シフトレジスタＳＢ０に、前記フラグＢＮ１の出力を減算値シフトレジスタＳＢ１にそれぞれクロック毎に取り込み、シフトレジスタＳＢ１の値を１ビットシフトしてシフトレジスタＳＢ０の値と加算することにより前記積の法Ｚによる商Ｓを計算することを特徴とする前記剰余演算器。
【請求項８】
乗数Ｘと被乗数Ｙの積の剰余Ｒを法Ｚのもとで計算するガロア体ＧＦ(ｐ)上の剰余演算器であって、
被乗数Ｙの先頭ビットMSBが１である場合に乗数Ｘを通過させるゲート、
暫定剰余Ｒ'と前記通過による値とを加算する加算器、
前記加算器の加算値を倍にするワイヤシフトする回路、
前記倍の値から法Ｚ、２Ｚ、及び３Ｚをそれぞれ減算する減算器及び
前記減算器のボローが出ない場合の信号を入力とし、それぞれの減算器の出力側に設けられたトランスミッションゲートを制御する信号を出力するデコーダとで構成され、
前記トランスミッションゲートが出力する値を次のクロックで前記暫定剰余Ｒ'とする課程を、クロック毎に繰り返し行うことにより前記剰余Ｒを計算する
ことを特徴とする前記剰余演算器。
【請求項９】
請求項８の剰余演算器において、
前記デコーダの出力を減算値シフトレジスタに、前記デコーダの出力を減算値シフトレジスタにそれぞれクロック毎に取り込み、シフトレジスタの値を１ビットシフトしてシフトレジスタの値と加算することにより前記積の法Ｚによる商Ｓを計算することを特徴とする前記剰余演算器。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、楕円曲線暗号等で用いる剰余演算、べき乗剰余演算に最適なガロア体上の剰余演算器に関する。
【０００２】
【従来の技術】
１９８０年代に、アフィン空間上の楕円曲線において定義された演算が群を形成し、特に剰余演算で有限体（ガロア体）となる場合に、その演算がマイクロコンピュータ等で効率的に計算できるものの、その計算が超大であることから暗号への応用が考えられた。この楕円曲線暗号方式は従来のＤＳＡ方式やＲＳＡ方式に比べ、より短いビット長の鍵（キー）で同程度のセキュリティを実現できることが分かり、近年注目されている。例えば、キーの長さが１０２４ビットのＲＳＡ方式と比べ、キーの長さが２２４ビットの楕円曲線暗号方式は１／７程度の計算量で済ませることができる。そこで、楕円曲線暗号方式を用いた応用分野として、ＩＣカード、特に無線ＩＣカードに向いていると考えられた。無線ＩＣカードでは、第三者が容易に通信データを傍受することが可能であり、データの暗号化が避けて通れない。無線ＩＣカードは、非接触でゲートを通過できるメリットを享受できるものの、反面、その短い通過時間の間に暗号を解読し、認証を行わなければならない。そこで、楕円曲線暗号方式で剰余演算等を効率的に行う剰余演算器等を提供する必要がある。
上記剰余演算等を行う場合、例えば、３２ビット程度の乗算器を搭載した専用ＬＳＩ若しくはプロセッサで、長いキーのビット長を３２ビット毎に分割して計算して行く方式等で計算し、その計算もなるべく割り算を回避するアルゴリズムが採用されている。チップサイズを小さくするための工夫である。上記ルゴリズムとしては、例えば、モンゴメリ(Montgomery)法を使うと計算時間が短くなることが知られている。
【０００３】
【従来の技術の問題点】
しかし、ビット数の少ない乗算器を使う方法には問題点も多い。複雑なアルゴリズムを用いるために計算量が多くなり、短い時間で計算する必要からクロックを速くせざるを得ず、消費電流が多くなる欠点がある。また、計算途中のデータをレジスタ等に保存せねばならず、数多くのレジスタを使用するのでそれ程回路量を減らすことはできない。
消費電流の増加は無線ＩＣカード、特に外部から電磁波の形で電力を供給するタイプの無線ＩＣカードに制約を与える。チップサイズの大きさは、大量に供給される場合の無線ＩＣカードのコストを高くするだろう。
【発明が解決しようとする課題】
本発明は上記課題を解決するためになされたもので、比較的低速のクロックで動作し、かつ、楕円曲線暗号等で用いる剰余演算、べき乗剰余演算に最適なガロア体上の剰余演算器等を提供することを目的にする。
【０００４】
【課題を解決するための手段】
本発明では上記課題を達成するために、剰余を先取りする演算若しくはアルゴリズム（以下、剰余先取り演算と言う。）を採用し、かつ、動作クロック数を減らす為の回路構成等を採用する。
【０００５】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して詳細に説明する。まず、本発明による第一の実施例の基礎を説明する。図１は、ｍ次既約多項式を法とするガロア体ＧＦ(２^m)における剰余演算器の剰余先取り演算を示す原理図でもある。図１において、ｍ＝２２４の場合は、レジスタＸ(３０１)、Ｒ(３０２)、Ｚ(３０３)、及びＴＰ(３１１)はそれぞれ２２４＋１ビットのレジスタ長を持つ。レジスタＹ(３０４)及びＳ(３０５)は同じく２２４＋１ビットの左シフトレジスタである。ゲートＧ１(３０６)は制御信号が１の場合に２２５ビットバスのデータをそのまま通過させ、制御信号が０の場合に２２５ビットバスのデータを全て０とするＡＮＤゲートであって、実際には２２５ヶの２入力ＡＮＤゲートで構成される。ゲートＧ２(３０７)も同様である。加算器ＡＤＤ(３０８)は２２５ビット同士のデータの加算を行う。実際にはガロア体ＧＦ(２^m)上の演算では桁上げ（キャリ）を考慮する必要がないので、２２５ヶの２入力ＥＸＯＲ素子で構成することができる。減算器ＳＵＢ(３０９)は２２５ビット同士のデータの減算を行う。この場合も借り（ボロー）を考慮する必要がないので、その構成は加算器ＡＤＤ(３０８)と全く同じにすることができる。ワイヤシフト回路Ｔ(３１０)は結線の変更によって次数を一つ上げる場合に使われる。従って、回路としての内容はない。なお、一時レジスタＴＰは前回のクロックの際に生成された暫定剰余を保持し、演算の連鎖を防止するために設けられている。
【０００６】
次に、図１の回路がどのように動作するかを説明する。図１では、法Ｚのもとで、被乗数Ｘと乗数Ｙの剰余演算が行われ、余りＲと商Ｓを求めることができる。即ち、ＸＹ  (modＺ)が計算される。さて、本発明による剰余先取り演算は、Ｙレジスタの先頭ビット(MSB)を取り出すことから始まる。その先頭ビットが１であればゲートＧ１においてＸの内容がそのまま加算器ＡＤＤにおいて加算される。しかし、その先頭ビットが０であればゲートＧ１において０が加算される。レジスタＹは左シフトレジスタであったから、１ビット毎のシフトを伴ったＹレジスタの全てのビットの加算は最終的にはＸとＹの積を計算したことになるだろう。しかし、本発明による剰余先取り演算ではその加算毎に法Ｚを差し引いているのが通常の演算と異なるところである。加算値ＳＵＭは法Ｚと比較され、等しいか、大きい場合に法Ｚを差し引く演算が行われる。即ち、法Ｚの先頭ビットが１であることが計算の前提になっているので、加算値ＳＵＭのMSBが１で減算を実行できる場合には、ゲートＧ２により前記加算値ＳＵＭから法Ｚが減算器ＳＵＢにより差し引かれる。しかし、加算値ＳＵＭのMSBが０であればこの減算はされない。このような減算を行う理由は、予め剰余に寄与しないＺの倍数を除去しておくことにある。また、除去したＺの倍数は商Ｓに一定の寄与をしていることに注意すべきである。Ｙレジスタのｋ(k=0,,,m-1)ビット目を取り扱っているとき、Ｚの倍数はＺの２^(m-k)倍であって、その値をシフトレジスタＳのLSBに取り込んでおくと、最終的にはｋ＝ｍとなって、シフトレジスタＳの値は商を意味することになる。加算値ＳＵＭのMSBをそのままシフトレジスタＳのLSBに取り込むのはこの為である。減算器ＳＵＢの出力は暫定剰余として剰余レジスタＲに取り込まれる。この暫定剰余は、Ｙレジスタのｋビット目を取り扱っているとき、その２^(m-k)倍の値が実際の剰余の意味になる。暫定剰余の初期値は０である。この暫定剰余は次の演算のために桁合わせを行う必要がある。クロックが一つ進み、Ｙレジスタの次の下位ビットが計算されるとき、予め剰余を先に足しておく演算が行われる。これが加算器ＡＤＤの存在する実際の意味である。本発明による剰余先取り演算は、前回の演算で残った暫定剰余を予め次の減算の前に加算しておくところにその特徴がある。加算に際し、ワイヤシフト回路Ｔにより次の桁に対しての桁合わせが行われている。ワイヤシフト回路Ｔは実際には結線の変更を行うのみであるから、何らクロックに依存していない事は重要である。この事実は後に計算に要するクロックを短縮させようとするときに役に立つ。
【０００７】
図１の回路動作の理解を図るためにここで簡単な計算を例示する。既約多項式の次数ｍ＝５で、６ビットのベクトルでＧＦ(２^5)上の元を表現できる場合である。
Ｘ＝Ｔ３＋Ｔ＋１、Ｙ＝Ｔ^4＋ Ｔ３＋Ｔ２＋１、Ｚ＝Ｔ^5＋Ｔ２＋１  としたとき、
Ｘ＝（００１０１１）、Ｙ＝（０１１１０１）、Ｚ＝（１００１０１）  と５次多項式をベクトル表現して、 ＸＹ  (modＺ)  即ち、
（００１０１１）（０１１１０１）    ｛ ｍｏｄ（１００１０１）｝
を計算する。
通常の計算では、左辺の積を求め次に割り算を実行するので、計算回数は１２回であり、単純計算では凡そ２倍のレジスタ長１１ビットを必要とする。この計算の様子は図２に示した。この計算では商が（０００１１０）で、余りが(０１０００１)である。
本発明による図１の剰余演算器では、以下のように計算する。まず、Ｙの先頭ビットから見てゆく。
▲１▼第一番目はＹ＝０なので、ＡＤＤへの入力は(００００００)、Ｒは初期値(００００００)であったからシフト後も(００００００)でその和ＳＵＭはやはり(００００００)で、ＳＵＭのMSBは０であり、ＳＵＢにおける減算はされない。従って、新しいＲも(００００００)である。
▲２▼第二番目のＹの先頭ビットはＹ＝１なので、 ＡＤＤへの入力は（００１０１１）であり、Ｒは依然として(００００００)であるので、和ＳＵＭは（００１０１１）、 ＳＵＭのMSBは０であり、ＳＵＢにおける減算はされないでＲの値を（００１０１１）に更新する。
▲３▼第三番目のＹの先頭ビットもＹ＝１なので、 ＡＤＤへの入力は（００１０１１）であり今度はＲは（００１０１１）であるが、 １ビットシフトされて加算される。
ＳＵＭ＝（００１０１１）＋(０１０１１０)＝(０１１１０１)。
ＳＵＭのMSBは０であり、ＳＵＢにおける減算はされない。そこで、Ｒ＝(０１１１０１)と更新される。
▲４▼第四番目のＹの先頭ビットはＹ＝１であり、 同様に１ビットシフトを考え、
ＳＵＭ＝（００１０１１）＋(１１１０１０)＝(１１０００１)。
ＳＵＭのMSBは１であり、ＳＵＢにおける減算（ＧＦ(２^m)上では加算と同じである。）がされる。従って、
Ｒ＝（１１０００１）＋（１００１０１）＝（０１０１００）。
第五番目のＹの先頭ビットはＹ＝０であり、 ＡＤＤへの入力は(００００００)、Ｒを１ビットシフトした値は(１０１０００)である。
ＳＵＭ＝（００００００）＋(１０１０００)＝(１０１０００)。
今度はＳＵＭのMSBは１であり、法Ｚとの引き算がＳＵＢにおいてなされる。
Ｒ＝(１０１０００)＋（１００１０１）＝（００１１０１）。
▲６▼第六番目のＹの先頭ビットはＹ＝１であり、 ＡＤＤへの入力は(００１０１１)、Ｒの１ビットシフト後の値との和は
ＳＵＭ＝(００１０１１)＋（０１１０１０）＝（０１０００１）。
ＳＵＭのＭＳＢは０なのでＳＵＢにおける減算はされず、更新後のＲ＝（０１０００１）である。
以上の計算は計算表として図３に示してある。
この結果、剰余Ｒは図２に示した通常の計算と一致する。なお、ＳＵＭのＭＳＢをシフトレジスタＳに取り込むと、その結果は商となる。法Ｚの全ての倍数を寄せ集めたからである。図３に示した計算表の枠で囲んだ部分が商Ｓで、Ｓ＝（０００１１０）であり、この結果も図２に示した通常の計算と一致している。
【０００８】
図４は、本発明による第一の実施例であって、ガロア体ＧＦ(２^m)上の剰余演算器で、図１の剰余演算器を高速化した回路である。図４において、同じ回路構成を持つ剰余演算器３(１１２)、剰余演算器２(１１３)、剰余演算器１(１１４)、及び剰余演算器０(１１５)はそれぞれ図１に示した剰余演算器の中核部分であり、この順番で継続接続している。図４の剰余演算器は１クロックでＹレジスタ(１０４)の４ビット分をまとめて処理する回路構成となっている。Ｘレジスタ(１０１)、Ｚレジスタ(１０３)、及びＲレジスタ(１０２)の構成は図１と同じである。ただ、 Ｘレジスタ及びＺレジスタは全ての剰余演算器と接続している。それぞれの演算の際に使用するからである。 Ｙレジスタ(１０４)とＳレジスタ(１０５)は、ここでは４ビット左シフトレジスタである。即ち、１クロックで４ビット分まとめてシフトする。Ｙレジスタの上位４ビットはそれぞれ剰余演算器３乃至０のＡＮＤゲート（例えばＧ１(１０６)）への制御入力となっている。Ｓレジスタの下位４ビットはそれぞれ剰余演算器３乃至０の加算値ＳＵＭのMSBからの制御出力を格納し、かつ、ＡＮＤゲート（例えばＧ２(１０７)）への入力となる。
【０００９】
さて、本発明による第一の実施例である図４の剰余演算器につきその動作を簡単に説明する。ここでは各剰余演算器は図３の剰余演算器と全く同じ動作をする。ただ、図１の剰余演算器が一段だけの計算でその暫定剰余を次のクロックに委ねるのに対し、図４の剰余演算器は４段連続して剰余を計算した後にその暫定剰余を次のクロックに委ねる点が異なっている。即ち、次段の剰余演算器に対しては１ビットワイヤシフト回路Ｔを通した後に、その計算後の暫定剰余が手渡される構成になっている。これは桁合わせもその都度行わなければならないからである。４段継続して計算された暫定剰余はＲレジスタに保存される。また、その暫定剰余は次のクロックの際は一時レジスタＴＰに保存されて、演算の連鎖を防止するように働く。一のクロックで４段継続して暫定剰余を計算する際、１ビットワイヤシフト回路Ｔが何らクロックに依存していないことが、４段継続した計算を可能にしていることに注意すべきであろう。即ち、一般的に言って、一回の演算により次数が１減少するのであって、次数とクロックとの直接の関係はない。このような考え方を進めると全くクロックがなくても剰余演算を実行することができることに気づく。剰余演算器をｎ段にし、ｎビットシフトレジスタを採用した場合はそのクロック数は１／ｎで済ませることができる。その演算時間は十分に短くなるが、その分ＬＳＩのチップサイズは大きくなる。各個の剰余演算器数を増やして演算時間を減らすのか、若しくはＬＳＩのパターン面積を減らすのか、あるいは消費電力の低減を優先するのかは、設計上の問題である。
この演算器における商の計算は、各剰余演算器での減算器ＳＵＢにおける減算がなされたか否かで商に寄与するか否かが決まり、一段の剰余演算で１次だけ次数が低下し、その結果その寄与の度合いは１／２倍づつ低下することを考慮して行わなければならない。従って、図４では、Ｙレジスタの４ビットシフトの構成に合わせて、Ｓレジスタも１クロックで４ビットシフトするシフトレジスタで構成されている。
【００１０】
図５は本発明による第二の実施例の基礎であって、ガロア体ＧＦ(２^m)上のべき乗剰余演算を示す原理図でもある。図５は主に３つの大きな構成を持つ。その第一はべき乗剰余演算部(４２１)で、ガロア体ＧＦ(２^m)上の元Ｘのべき乗（２^k乗）を計算する回路である。これにより、Ｘ^(２^k) (k=0,,,m-1)の剰余が計算される。その第二は直積剰余演算部(４２２)で、前記べき乗剰余演算部(４２１)で計算された項の直積を計算する回路である。ｎをｎ＝Σａk２^kと２進数表現した場合は、これによりＸ^(Σａk２^k) の剰余が計算される。その第三はべき乗数ｎを定めるレジスタ部(４２３)で、前記の如くｎを２進数表現した場合に、そのビットの値により前記直積を追加するか否かを決定する回路である。
べき乗剰余演算部(４２１)は、２２５ビットのＸレジスタ(４０１)、ＲＸ^mレジスタ(４０２)、ＴＰ１レジスタ(４１１)、及びＺレジスタ（図中省略）と、左シフトレジスタであるＹレジスタ(４０４)と、剰余演算器(４２４)（図４の剰余演算器と同じ構成を持つ）とで構成されている。このべき乗剰余演算部が図１の剰余演算器と大きく異なる点は、一旦計算された剰余ＲＸ^mを再びＸ及びＹレジスタの格納し、その後のクロックで格納された値同士の積の剰余が計算されることである。即ち、本発明によるべき乗剰余演算部は次数を２のべき乗分上げる演算をするために自分自身との積を連続して計算する回路構成としたことにその特徴がある。最初にＸと１との積の剰余が計算され、次にＸ同士の積でＸ^2の剰余、次にＸ^2同士の積でＸ^4の剰余、その後はＸ^8の剰余、 Ｘ^16の剰余、、、となる。これはＸ^(２^k) (k=0,,,m-1)の剰余を計算したことになる。なお、商を計算する必要がないので図１のＳレジスタはない。また、Ｚレジスタは、図５ではその表示が省略されている。
直積剰余演算部(４２２)は図１の剰余演算器とほぼ同じ回路構成を持つ。ＴＰ３レジスタ(４１６)はＹレジスタ(３０４)に、 ＴＰ２レジスタ(４１７)はＴＰレジスタ(３１１)に、 ＲＸ^nレジスタ(４１８)はＲレジスタ(３０２)にそれぞれ対応する。剰余演算器(４２５)も図４の剰余演算器と同じ構成を持つ。異なる点はＴＰ３レジスタに計算途中のＸの暫定べき乗剰余が格納され、直積が計算されるところである。その直積を計算する際のＸの暫定べき乗剰余はＲＸ^nレジスタに格納され、計算終了後には最終的なＸ^nのべき乗剰余が格納される。べき乗数（若しくは指数）ｎを定めるレジスタ部(４２３)は右シフトレジスタであるｎレジスタ(４１９)とゲート(４２０)で構成される。ｎをｎ＝Σａk２^kと２進数表現した場合は、 ｎ＝(ａm-1,ａm-2, , ,ａ1,ａ0）とベクトル表示でき、そのビットが１であれば直積が計算され、そのビットが０であれば直積を計算しないか、若しくは１との積が取られる。その計算課程がＸ^(２^k)を計算している段階では、ｎレジスタ(４１９)のLSBはｋビット目の値を示しており、その値はゲート(４２０)に対する制御信号としてこの段階の直積をＸの暫定べき乗剰余に追加するか否かを制御する。そのビットの値に従って直積を計算することはＸ^nの剰余を計算することと等価である。
【００１１】
本発明による上記べき乗剰余演算器を用いた簡単な演算例として、ガロア体ＧＦ(２^m)上の元Ｘの逆元Ｘ^(-1)を求めてみる。ガロア体ＧＦ(２^m)の逆元は本来もとの元Ｘから一意的に決まるはずである。ガロア体は有限体であるので、ある元Ｘのべき乗が法Ｚの下で剰余１になる。即ち、
Ｘ^n ≡ １  (mod  Ｚ)  for ∃n∈Ｚ
の場合に  Ｘ^(n-1)をＸの逆元とすることができる。
ここでは、まず逆元を通常の方法（逐次代入法）で計算してみる。
Ｘ＝Ｔ３＋Ｔ＋１    ベクトル表現（００１０１１）
Ｚ＝Ｔ^5＋Ｔ２＋１  ベクトル表現（１００１０１）
Ｙ＝ΣｂkＴ^k  とした場合、
ＸＹ＝Σｂk(Ｔ^kＸ)  であるから、図６の表を使って、
＝（００００１）ｂ4＋（１００１０）ｂ3＋（０１００１）ｂ2
＋（１０１１０）ｂ1＋（０１０１１）ｂ0
＝１
これから上位の次数を持つ項における係数が０であることを利用して次の連立一次方程式が成立する。
ｂ1＋ｂ3＝０、ｂ2＋ｂ0＝０、ｂ1＝０、ｂ3＋ｂ1＋ｂ0＝０、ｂ4＋ｂ2＋ｂ0＝１
これより  ｂ4＝１，ｂ0＝ｂ1＝ｂ2＝ｂ3＝０
∴Ｙ＝Ｔ^4
実際、  ＸＹ＝ (Ｔ３＋Ｔ＋１） Ｔ^4＝（ Ｔ２＋１）Ｚ＋１≡ １  (mod  Ｚ)である。
この計算は連立一次方程式の解を求めること、つまりマトリックス計算で逆マトリックスを計算する事と等価である。従って、２２４ビットの逆マトリックスを求める必要があり、現実的な計算方法ではない。
次に、手計算で上記の結果を検証してみよう。その計算は図７の計算表に示した。それによれば、Ｘの３１乗が剰余１を生成するので、Ｘの逆元はＸの３０乗であり、その剰余は（１００００）である。これは  Ｙ＝Ｔ^4  を意味し、逐次代入法と一致する結果である。
ガロア体の理論によれば、ガロア体ＧＦ(ｐ^m)の位数はｐ^m―１であり、その元Ｘに対し、
Ｘ^(ｐ^m―１)＝１  が成立する。ここで、ｐ＝２、ｍ＝５を代入すると、 Ｘ^(31)＝１であり、上記計算とも一致する。ところで、一般に２^m―１＝２^(m-1)＋２^(m-2)＋…＋２＋１、m＝５では３１＝２^4＋２^3＋２^2＋２＋１であり、ベクトル表現では（０１１１１１）である。このようなビットの規則性からＸのべき乗を効率よく計算して逆元の計算速度を向上させようとするアイデアが数多く提出されている。本発明では、そのようなアイデアに頼らず直接的にｎ＝（０１１１１０）として上記べき乗剰余演算器を用いてＸの逆元の剰余を計算することができる。その計算課程で出現する暫定剰余は図７の計算表と全く同じ結果になる。
【００１２】
図８は本発明による第二の実施例であって、ガロア体ＧＦ(２^m)上のべき乗剰余演算器で、図５のべき乗剰余演算器を高速化した回路である。図４と比べた場合、計算に要するクロック数を１／４短縮するために、４段連続して剰余演算器を継続接続した構成が採用されており、高速化を達成する手段は図４と同じである。Ｘレジスタ(２０１)、Ｚレジスタ(２０３)、 ＲＸ^mレジスタ(２０２)、ＴＰ１レジスタ(２１１)、 ＴＰ２レジスタ(２１７)、及びＲＸ^nレジスタ(２１８)はそれぞれ２２５ビットレジスタであり、Ｙレジスタ(２０４)、Ｓレジスタ(２０５)、及びＴＰ３レジスタ(２１６)はそれぞれ２２５ビットの４ビット左シフトレジスタであり、 ｎレジスタ(２９６)は２２５ビットの４ビット右シフトレジスタである。また、ゲートＧ３(２２０)はゲートＧ１(２０６)等と同じ構成であり、剰余演算器(２２５)も剰余演算器３乃至１(２１２乃至２１５)と同じ構成である。
図８の回路で、ある元Ｘの逆元を計算する場合がｎのビットが１である数が最大で、最も計算量の大きい場合である。ｍ＝２２４で、２２５ビットレジスタを用いた場合、ＸとＹの積の剰余を計算するのに５７クロックを要し、更に逆元の剰余を計算するのにその２２５倍のクロックを要する。一般的に上記剰余演算器をｎ段継続接続した場合、（ｍ＋１）２／ｎクロックを要する。
【００１３】
本発明の第一の実施例で提案した剰余演算器をＧＦ(２^m)ではなく、ＧＦ(ｐ)に拡張した場合にはどうなるだろうか。この場合には桁上げを考慮した加算(ADD)及び減算(SUB)を行わなければならない。 ＧＦ(２^m)上では、ＥＸＯＲで済ませることができたので桁上げを考慮する必要はなかった。減算するか否かは、 ＳＵＭ(MSB)の代わりにキャリー（ボロー）やコンパレータ（加算値とＺとの大小を比較する）を使って判断することになる。また、２２５ビット同士での演算ではキャリー（ボロー）も別途高速に計算する必要がある。しかし、回路構成のやり方は全く同じで行けると言うことを確認できるだろう。即ち、今まで提案された回路図は極めて汎用性が高い。
図９は、本発明の第三の実施例の基礎であって、ＧＦ(ｐ)上の剰余演算器で剰余先取り演算を採用した場合の原理図でもある。図９の剰余演算回路は大きく３つの部分に分けることができる。その第一は剰余の加算回路(５３１)で、暫定剰余Ｒ'と被乗数Ｘの加算を行い、その結果ＳＵＭ０と法Ｚを比較してＳＵＭ０の方が大きいか等しい場合に法Ｚを差し引く回路である。その第二はワイヤシフト回路(５３２)で、ワイヤシフトＴによりそのシフト後の値が法Ｚより大きいか等しい場合は法Ｚを差し引く回路である。その第三は商の計算回路(５３３)であって、引き算の結果出力された信号(S0、S1)を用いて積ＸＹの法Ｚに対する商を計算する回路である。
加算回路(５３１)の動作はＧＦ(２^m)の場合と基本的に同じである。最初にＹの上位ビット(MSB)を見て、１であればＸを加算(ＡＤＤ)し、０であれば加算しない。加算の相手方は暫定剰余Ｒ'であって、その初期値は０である。加算値(ＳＵＭ０)は法Ｚと比較され、その結果加算値が法Ｚよりも大きいか等しいときにのみ減算(ＳＵＢ０)がなされる。このような演算を行う理由は、予め剰余に寄与しない部分(Ｚの倍数)を取り除いておいて余計な演算を省略することにある。即ち、ＳＵＢ０−Ｚの減算の結果、ボローが出ない場合はフラグ(ＢＮ０)を立て、その値をラッチする。そのフラグの出力信号(S0)はマルチプレクサ(ＭＰＸ０)を制御し、その出力信号(S0)が０であればそのまま加算値(ＳＵＭ０)を、その出力信号(S0)が１であれば減算(ＳＵＢ０)後の減算値を選択し、その値が剰余レジスタＲに格納される。次のクロックの先頭で剰余レジスタＲの値は一時レジスタＴＰに移される。一時レジスタＴＰを設けた理由は演算の連鎖を防止するためである。
ワイヤシフト回路(５３２)において、一時レジスタＴＰの値は１ビットシフト(Ｔ)されて、中間的な暫定剰余となる。シフトする理由は次回の加算に備えて桁合わせするためである。ここで、シフトされた後の値が法Ｚと比較され、その値が法Ｚよりも大きいか等しいときにのみ減算(ＳＵＢ１)がなされる。その理由は、シフトによりその値がＺよりも大きくなった場合には、次回の計算での加算値(SUM)が２Ｚを越えてしまうから、これを防止するためである。この計算は剰余の加算回路の場合と全く同じに行われる。即ち、減算回路ＳＵＢ１はＳＵＢ０に、フラグＢＮ０はＢＮ１に、マルチプレクサＭＰＸ０はＭＰＸ１にそれぞれ対応する。ただ、取り扱うデータは異なっており、フラグＢＮ１の出力(S1)とマルチプレクサＭＰＸ１の出力（暫定剰余Ｒ'）となっている。そこで、その次のクロックにおいて、再び減算(ＳＵＢ０)の前に暫定剰余（Ｒ'）を先に足す演算(ＡＤＤ)が行われる。なお、比較結果(S0、S1)により商を計算することができる。この計算方法ではｍ＋１ビット同士の値の積に対してｍ＋１クロックの後、最終的な剰余Ｒが求まる。
商の計算回路(５３３)は今度は若干複雑になる。加算回路(５３１)で生成された出力信号(S0)は、Ｙレジスタのｋ(k=0,,,m-1)ビット目を取り扱っているとき、Ｚの倍数はＺの２^(m-k)倍であって、これが右シフトレジスタＳＵＢ０のLSBに取り込まれる。これに対しワイヤシフト回路(５３２)において生成された出力信号(S1)は、Ｙレジスタのｋ(k=0,,,m-1)ビット目を取り扱っているとき、Ｚの倍数はＺの２^(m-k-1)倍であって商Ｓへの寄与はその半分になる。従って、出力信号(S1)が右シフトレジスタＳＵＢ１のLSBに取り込まれた後、ワイヤ１ビット右シフト回路Ｔ^(-1)により桁合わせが行われ、商Ｓへの寄与として加算される。法Ｚの全ての倍数を寄せ集めた後は、その和は正しく商Ｓを意味する。
どのような場合に減算器(ＳＵＢ０、ＳＵＢ１)で減算された値がマルチプレクサにおいて選択されるかを図１０の表に示してある。この表は加算器ＡＤＤによる加算値ＳＵＭと法Ｚの値との大きさの関係を示した表で、その値を比較したときに加算値若しくはワイヤシフト後の値が法Ｚに等しいかより大きい場合には常に法Ｚを差し引くという関係を表している。表中の値０は減算値を使わないこと、即ちマルチプレクサ（ＭＰＸ０、ＭＰＸ１）で減算値を選択することを表し、表中の値１は減算値を使うこと、即ちマルチプレクサ（ＭＰＸ０、ＭＰＸ１）で減算値を選択しないことを表している。
【００１４】
本発明による剰余先取り演算を採用した場合に、ガロア体ＧＦ(ｐ)上の剰余演算が実際にはどのように行われるかの理解を計るために、具体的計算例を挙げておくことにする。
まず、上記回路の各部の関係を明らかにする。
（１）ＳＵＭ０＝Ｒ'＋ＸＹmsb
ここでＲ'は上位桁からの暫定剰余、ＹmsbはＹレジスタの最上位ビットである。
Ｒ＝ＳＵＭ０−Ｓ０Ｚ
ここでＳ０はＳＵＢ０による減算値を選択した場合に１，選択しない場合に０で、減算値レジスタＳＢ０に格納される値であり、図１１の計算表のＳＢ０に該当する。
（３）Ｒ'＝Ｒ２−Ｓ１Ｚ
ここでＳ１はＳＵＢ１による減算値を選択した場合に１，選択しない場合に０で、減算値レジスタＳＢ１に格納される値であり、図１１の計算表のＳＢ１に該当する。
Ｓ＝ＳＢ０＋ＳＢ１/２
２で割るのは桁合わせの為であり、ワイヤ１ビット左シフトＴに対応する。
次に  Ｘ＝１７、Ｙ＝２７、Ｚ＝３７の場合にどのように処理が進むのかを見てみよう。
Ｙのベクトル表現は（０１１０１１）である。
（１）０クロック目： Ｒ'＝０（初期値）、 Ｙmsb＝０
よって、ＳＵＭ０＝０＋ Ｘ０＝０、これは図１０のモード▲１▼に対応する。
Ｒ＝０−０Ｚ＝０、 Ｒ'＝０２−０Ｚ＝０
１クロック目： Ｒ'＝０、 Ｙmsb＝１
よって、ＳＵＭ０＝０＋ Ｘ１＝１７、これは図１０のモード▲１▼に対応する。
Ｒ＝１７−０Ｚ＝１７、 Ｒ'＝１７２−０Ｚ＝３４
２クロック目： Ｒ'＝３４、 Ｙmsb＝１
よって、ＳＵＭ０＝３４＋ Ｘ１＝５１、これは図１０のモード▲３▼に対応する。
Ｒ＝５１−１Ｚ＝１４、 Ｒ'＝１４２−０Ｚ＝２８
（４）３クロック目： Ｒ'＝２８、 Ｙmsb＝０
よって、ＳＵＭ０＝２８＋ Ｘ０＝２８、これは図１０のモード▲２▼に対応する。
Ｒ＝２８−０Ｚ＝２８、 Ｒ'＝２８２−１Ｚ＝１９
（５）４クロック目： Ｒ'＝１９、 Ｙmsb＝１
よって、ＳＵＭ０＝１９＋ Ｘ１＝３６、これは図１０のモード▲２▼に対応する。
Ｒ＝３６−０Ｚ＝３６、 Ｒ'＝３６２−１Ｚ＝３５
（６）５クロック目： Ｒ'＝３５、 Ｙmsb＝１
よって、ＳＵＭ０＝３５＋ Ｘ１＝５２、これは図１０のモード▲３▼に対応する。
Ｒ＝５２−１Ｚ＝１５
以上の処理を図１１の計算表にまとめてみた。
商Ｓの計算は  Ｓ＝（００１００１）＋（０００１１ｘ）/２
Ｓ＝９＋３＝１２  ...商
この結果、１７２７＝４５９＝１２３７...余り１５  を確認できた。
【００１５】
図１２は本発明による第三の実施例であって、図９に示したＧＦ(ｐ)上の剰余演算器を高速化した回路である。図９の回路においては、剰余の加算回路(５３１)とワイヤシフト回路(５３２)とを継続して計算する回路構成を採用しており、２２５ビット同士のデータの加算器(ADD)や減算器(SUB0、SUB1)の遅延時間が比較的大きいことを考えるとその計算時間の遅延を無視することはできない。そこで本発明による第三の実施例においては、図１０の関係を拡大して考えることにより、前記剰余の加算回路(５３１)とワイヤシフト回路(５３２)を一体化する構成を採用することにした。この一体化に際しては法Ｚの半分の値が出てこないように、予め加算値(SUM)の２倍の値と法Ｚ、その２倍の値、及びその３倍の値との比較を考える。何故なら、法Ｚの半分の値を取り扱うとその最下位のビットが無視されて計算が合わなくなるからである。それ故、値２Ｚはワイヤシフト回路で実現できたとしても、値３Ｚは予め計算しておかなければならなくなった。この計算は容易であるが、その値を剰余の計算の前にＺ'レジスタに格納せねばならず、その手間が増加する欠点がある。もっともチップ面積に余裕があるので有れば、加算器を一つ追加してＺ'レジスタを省略することができる。
図１２で、加算値(SUM)の２倍の値(2SUM)はワイヤ左シフト回路Ｔにより作る。また、法Ｚの２倍の値(2Z)も同様である。法Ｚの３倍の値(3Z)は前記の如く予め計算してＺ'レジスタに格納しておく。このとき減算器ＳＵＢ０、ＳＵＢ１、及びＳＵＢ２で行った減算の結果を図１３に示した。この表ではボローが出ない場合の変数BN2、BN1、及びBN0に対し、減算結果の場合分けが行われている。実際には起こり得るケースは、モード▲１▼、▲２▼、▲３▼、及び▲４▼の何れかに限られている。この何れかが選択されたとき、そのモードでの減算値、即ち2SUM、2SUM-Z、2SUM-2Z、若しくは2SUM-3Zが暫定剰余として一時レジスタＴＰ２に格納される。別個に一時レジスタＴＰ１を設けたのは、例によって演算の連鎖を防止するためである。最終的な剰余Ｒは、前記暫定剰余をワイヤ右シフト回路Ｔ^(-1)に通した後の値としてＲレジスタに格納する。これは現在取り扱っている桁に戻すための処理であり、予めワイヤ左シフト回路Ｔで２倍にしていた値を元に戻すためである。
商Ｓの計算は法Ｚのもとで減算した場合のＺの倍数を正確に評価することで得ることができる。当該桁で商への寄与はＺ/２の整数倍であり、その倍数を２進表現するとそのビットの値がそのままS0及びS1の値になる。このS0及びS1の値はそのまま商の計算回路(６３３)の減算レジスタＳＢ０及びＳＢ１のLSBに取り込まれる。商への寄与については
S0＝BN2_BN1BN0＋ BN2BN1BN0(▲３▼と▲４▼) 、
S1＝BN2_BN1_BN0＋BN2BN1BN0(▲２▼と▲４▼)としたときに、
最終的にＳ＝ＳＢ０＋ＳＢ１/２  で求めることができる。クロックが終了して必要なビットが前記減算レジスタに格納されると、Ｓレジスタには正しい商が取り込まれる。法Ｚの全ての倍数を寄せ集めたからである。その際、減算レジスタＳ０の値に対しワイヤ１ビット右シフト回路Ｔ^(-1)を通過させるのは、予め２倍していた商への寄与を元に戻すためである。
図１２の回路を図９の回路と比べた場合、後者が加算器１段、減算器２段及びマルチプレクサ２段であるのに対し、前者は加算器１段、減算器１段及びトランスミッションゲート１段であるから、遅延時間に関してはおよそ半分に減っており、明らかに高速化が達成されている。しかし、予め３Ｚを計算しておく不便若しくは加算器を一つ追加する負担もかなりのものである。
【００１６】
高速化したとはいえ、図１２の回路図による剰余演算器は問題点も多い。第一の問題は加算(ADD)でキャリーの出力が遅くなることである。ｍ＝２２４ビットのデータ同士の加算の場合、キャリールックアヘッド回路を用いても相当な遅延時間となるだろう。ただ、徒に分割して（３２ビットづつとか）演算するよりは、このキャリーを待つ方が速くなることは明らかである。むしろクロックを遅くした分消費電力が減るかも知れない。第二の問題は、現在提案している回路は未だ冗長度が高く、回路量が多いと言うことだろう。試算では単純にＬＳＩ化した場合のチップ面積を計算した場合、ＣＭＯＳ  1.2μmルールで約７mm２の面積を必要とする。しかし、ＩＣカードが折り曲げられた際にチップの破壊を防ぐためにはその面積が４mm２以下であることが望ましいと言われており、全体の回路量を減らす必要がある。
ここでは上記のような要請から加算器自体の面積を減らす方を優先して考えることにする。一般的な方法として、回路量を減らす為にクロック数を増やして同じ回路を何度も使う方法を考える。２２５ビットのデータ同士の加算や減算をそのまま行うのではなく、例えば、３２ビット毎に区切り３２ビット加算器等を用いて８回に分けて計算することが考えられる。また、レジスタ類もＲＡＭを使う構成とすると大幅に面積が減る。
図１４は、このような一例として２２５ビットのデータＸ、Ｙ、Ｚに対し、３２ビットＡＤＣ(キャリ付き加算器)を用いてＺ＝Ｘ＋Ｙを計算する回路を考案したものである。図１４では、３２ビット構成のＲＡＭとしてＲＡＭＺ(６４１)、ＲＡＭＹ(６４２)、及びＲＡＭＸ(６４３)を有し、それぞれ変数Ｘ、Ｙ、及びＺの値を格納するのに用いている。３２ビットのレジスタZadr(６４４)、Yadr(６４５) 、Xadr(６４６)はそれぞれ前記ＲＡＭの上位アドレスを指定するために用いる。 AdrCount(６４７)は３ビットのカウンターで、前記ＲＡＭの下位アドレスを指定するのに用いるが、全てのＲＡＭで共通に使われている。この例ではカウンターは３ビットであるから、前記８回のカウントを行う。前記上位アドレス及び前記回アドレスは組み合わされて、それぞれのＲＡＭのデコーダ部DecX(６４８)、 DecY(６４９)、及びDecZ(６５０)に入力され、前記変数の値を格納するのに用いられる。加算器ＡＤＣ(６５１)は３２ビットのデータ同士の加算をキャリ付きで行う。また、加算では発生したキャリを次の計算に用いるために、Cout(６５２)の値をCin(６５３)に入力する操作ををクロック毎に行わなければならない。なお、ＲＡＭを書き込みにするのか若しくは読み出しにするのかのモード変更は命令で行うことになるだろう。その際の書き込み信号（例えばWR_）や読み出し信号（例えばRD_）は省略してある。また、これらのＲＡＭは汎用性を持たせて、内部バスＢＵＳ(６５４)と接続させていることが望ましい。
【００１７】
ガロア体ＧＦ(ｐ)上のべき乗剰余演算器の回路は、本質的に図５の回路構成と同じである。異なる点は剰余演算器においてキャリやボローを考慮した演算を行わなければならないと言う点だけである。その回路構成は図１２のものと同様である。
【００１８】
本発明では剰余先取り演算方式を採用し、この方式によるガロア体ＧＦ(２^m)上の剰余演算器及びべき乗剰余演算器、ガロア体ＧＦ(ｐ)上の剰余演算器及びべき乗剰余演算器を、それぞれ提案している。本発明による剰余先取り演算方式は、上記回路群の類似性からも明らかなように、極めて汎用性の高い回路構成となっている。従って、それぞれの回路をマルチプレクサやゲートで切り替えて兼用することが可能である。例えば、ガロア体ＧＦ(ｐ)上のべき乗剰余演算器（図５）は多少のゲートの追加で他の剰余演算器（図９、図１２）と兼用させることができる。ガロア体ＧＦ(２^m)上の加算器等がＥＸＯＲで形成できることを考えれば、前記べき乗剰余演算器（図５）にガロア体ＧＦ(２^m)上の剰余演算器及びべき乗剰余演算器を組み合わせることも可能である。しかし、それ等は本発明の回路から容易に創作し、構成できるものであるので、この詳細な説明ではその記載を省略することにした。
【００１９】
【発明の効果】
本発明では剰余先取り演算方式を採用し、この方式によるガロア体ＧＦ(２^m)上の剰余演算器及びべき乗剰余演算器、ガロア体ＧＦ(ｐ)上の剰余演算器及びべき乗剰余演算器を、それぞれ提案することができた。繰り返し強調すれば、本発明による剰余先取り演算方式は、上記回路群の類似性からも明らかなように、基本的で極めて汎用性の高い回路で構成できる。従って、その他の回路構成の工夫を盛り込み易く、楕円曲線暗号方式の剰余演算、引いてはＩＣカード等の応用分野に容易に拡張可能である。また、機能面で見れば、本発明による剰余先取り演算方式は、特に、商を直接求めることができる点で優れている。これは本発明に係る剰余演算器が除算器の機能も併せ持つことを意味する。
【図面の簡単な説明】
【図１】第一の実施例の剰余演算器の剰余先取り演算を示す原理図
【図２】図１における通常の計算による課程を示す図
【図３】図１における本発明による計算表を示す図
【図４】図１の剰余演算器を高速化した回路図
【図５】第二の実施例の乗剰余演算を示す原理図
【図６】逐次代入法での項別の積の計算表を示す図
【図７】Ｘのべき乗剰余の計算表を示す図
【図８】図５のべき乗剰余演算器を高速化した回路図
【図９】第三の実施例の乗剰余演算を示す原理図
【図１０】加算値ＳＵＭと法Ｚの値との大きさの関係を示す図
【図１１】剰余演算の具体的計算例を示す図
【図１２】図９のべき乗剰余演算器を高速化した回路図
【図１３】図１２の減算器で行った減算の結果を示す図
【図１４】データＸ、Ｙ、Ｚに対し、キャリ付き加算器を用いてＺ＝Ｘ＋Ｙを計算する回路図
【符号の説明】
１０１  被乗数レジスタＸ          １１１  一時レジスタＴＰ
１０２  剰余レジスタＲ            １１２  剰余演算器３
１０３  法レジスタＺ              １１３  剰余演算器２
１０４  乗数レジスタＹ            １１４  剰余演算器１
１０５  商レジスタＳ              １１５  剰余演算器０
１０６  ゲートＧ１
１０７  ゲートＧ２
１０８  加算器ＡＤＤ
１０９  減算器ＳＵＢ
１１０  ワイヤシフト回路Ｔ
２０１  被乗数レジスタＸ          ２１１  一時レジスタＴＰ１
２０２  剰余レジスタＲ            ２１２  剰余演算器３
２０３  法レジスタＺ              ２１３  剰余演算器２
２０４  乗数レジスタＹ            ２１４  剰余演算器１
２０５  商レジスタＳ              ２１５  剰余演算器０
２０６  ゲートＧ１                ２１６  一時レジスタＴＰ３
２０７  ゲートＧ２                ２１７  一時レジスタＴＰ２
２０８  加算器ＡＤＤ              ２１８  暫定剰余レジスタＲＸ^ｎ
２０９  減算器ＳＵＢ              ２１９  べき乗数レジスタｎ
２１０  ワイヤシフト回路Ｔ        ２２０  ゲートＧ３
２２５  剰余演算器
３０１  被乗数レジスタＸ          ３１１  一時レジスタＴＰ１
３０２  剰余レジスタＲ
３０３  法レジスタＺ
３０４  乗数レジスタＹ
３０５  商レジスタＳ
３０６  ゲートＧ１
３０７  ゲートＧ２
３０８  加算器ＡＤＤ
３０９  減算器ＳＵＢ
ワイヤシフト回路Ｔ
４０１  被乗数レジスタＸ          ４２１  べき乗剰余演算部
４０２  剰余レジスタＲＸ^ｍ       ４２２  直積剰余演算部
４０４  乗数レジスタＹ            ４２３  ｎを定めるレジスタ部
４１１  一時レジスタＴＰ１        ４２４  剰余演算器
４１２  一時レジスタＴＰ３        ４２５  剰余演算器
４１７  一時レジスタＴＰ２
４１８  暫定剰余レジスタＲＸ^ｎ４１９  べき乗数レジスタｎ
４２０  ゲートＧ３
５３１  剰余の加算回路部
５３２  ワイヤシフト回路部
５３３  商の計算回路部
６３３  商の計算回路部            ６４７  AdrCount
６４１  RAMZ                      ６４８  DecZ
６４２  RAMY                      ６４９  DecY
６４３  RAMX                      ６５０  DecX
６４４  アドレスレジスタZadr     ６５１  ＡＤＣ
６４５  アドレスレジスタYadr     ６５２  Cout
６４６  アドレスレジスタXadr     ６５３  Cin
６５４  BUS
【図１】
0003732450.tif 000002
【図２】
0003732450.tif 000003
【図３】
0003732450.tif 000004
【図４】
0003732450.tif 000005
【図５】
0003732450.tif 000006
【図６】
0003732450.tif 000007
【図７】
0003732450.tif 000008
【図８】
0003732450.tif 000009
【図９】
0003732450.tif 000010
【図１０】
0003732450.tif 000011
【図１１】
0003732450.tif 000012
【図１２】
0003732450.tif 000013
【図１３】
0003732450.tif 000014
【図１４】
0003732450.tif 000015