(57)【要約】【課題】少ないサイクル数で逆数演算が可能な逆数演算器を提供する。【解決手段】ｍビットのガロアフィールド上で、入力値の逆数を演算する逆数演算器１００が提供される。Ｕレジスタ１０、Ｖレジスタ１２に関して、最下位ビットから上位に向かってｙビットにわたり連続して０が含まれるとき、Ｕレジスタ１０、Ｖレジスタ１２をｙビット右シフトする。それと連動して、Ｖレジスタ１２、Ｇ１レジスタ１４に、ｙ回の１／Ｚ処理を行う。Ｕレジスタ１０、Ｖレジスタ１２の最下位ビットが両方１のとき、次数が高い方を、Ｕレジスタ１０とＶレジスタ１２の加算結果で更新する。またそれと連動して、Ｕレジスタ１０の次数が高いとき、Ｇ１レジスタ１４を、Ｇ１レジスタ１４とＧ２レジスタ１６の加算結果で更新し、Ｖレジスタ１２の次数が高いとき、Ｇ２レジスタ１６を、Ｇ１レジスタ１４とＧ２レジスタ１６の加算結果で更新する。【選択図】図１
2015203859.tif 000002
【特許請求の範囲】
【請求項１】
ｍビットのガロアフィールド上で、入力値の逆数を演算する逆数演算器であって、
ガロアフィールド上で法として使用すべき規約多項式をビットベクトル表現で格納するｍビットのＦレジスタと、
初期値として前記入力値を格納するｍビットのＵレジスタと、
初期値として、前記Ｆレジスタと同じ値を格納するｍビットのＶレジスタと、
初期値として１を格納するｍビットのＧ１レジスタと、
初期値として０を格納するｍビットのＧ２レジスタと、
演算処理部と、
を備え、
前記演算処理部は、
前記Ｕレジスタの下位ｎビット（ｎ＜ｍ）を参照し、最下位ビットから上位に向かってｙビット（ｙ≦ｎ）にわたり０が連続するとき、前記Ｕレジスタの値をｙビット右シフトするステップ（i）と、
前記ステップ（i）と連動して、前記Ｇ１レジスタにｙ回、１／Ｚ処理を行うステップであって、前記１／Ｚ処理は、その入力の最下位ビットが０である場合に、入力を１ビット右シフトした値を出力し、その入力の最下位ビットが１である場合にはその入力に法Ｆの値をガロアフィールド上で加算した後に１ビット右シフトした値を出力するものである、ステップ（ii）と、
前記Ｕレジスタの最下位ビットが０であるとき、前記ステップ（i）、(ii)を繰り返すステップ（iii）と、
前記Ｖレジスタの下位ｎビット（ｎ＜ｍ）を参照し、最下位ビットから上位に向かってｙビットにわたり０が連続するとき、前記Ｖレジスタの値をｙビット右シフトするステップ（iv）と、
前記ステップ（iv）と連動して、前記Ｇ２レジスタにｙ回、１／Ｚ処理を行うステップ(v)と、
前記Ｖレジスタの最下位ビットが０であるとき、前記ステップ（iv）、(v)を繰り返すステップ（vi）と、
前記ステップ（i）〜(vi)の結果、前記Ｕレジスタの最下位ビットと前記Ｖレジスタの最下位ビットが両方１となったとき、前記Ｕレジスタと前記Ｖレジスタの次数を比較するステップ（vii）と、
前記Ｕレジスタと前記Ｖレジスタのガロアフィールド上の加算を行い、加算結果を前記Ｕレジスタと前記Ｖレジスタのうち、次数が高い方に格納するステップ（viii）と、
前記Ｇ１レジスタと前記Ｇ２レジスタのガロアフィールド上の加算を行い、前記ステップ（vii）において前記Ｕレジスタの次数の方が高いとき、加算結果を前記Ｇ１レジスタに格納し、前記ステップ（vii）において前記Ｖレジスタの次数の方が高いとき、加算結果を前記Ｇ２レジスタに格納するステップ（ix）と、
前記ステップ(i)〜（ix）を、前記Ｕレジスタおよび前記Ｖレジスタの一方が１になるまで繰り返し、前記Ｕレジスタが１であるとき、前記Ｇ１レジスタの値を求めるべき逆数として出力し、前記Ｖレジスタが１であるとき、前記Ｇ２レジスタの値を求めるべき逆数として出力するステップ（x）と、
を備えることを特徴とする逆数演算器。
【請求項２】
前記演算処理部は、
前記Ｕレジスタおよび前記Ｖレジスタそれぞれの下位ｎビットを参照し、それぞれについて、最下位ビットから連続する０の個数ｙを判定するコントローラを含むことを特徴とする請求項１に記載の逆数演算器。
【請求項３】
前記演算処理部は、前記ステップ（i）（iii）（iv）（vi）を実行するよう構成されたシフター回路を含み、
前記シフター回路は、
前記Ｕレジスタと前記Ｖレジスタの値の一方を選択する第１セレクタと、
前記コントローラによる判定結果にもとづいて、前記第１セレクタの出力をｙビット右シフトするマルチビットシフタと、
を含むことを特徴とする請求項２に記載の逆数演算器。
【請求項４】
前記演算処理部は、
前記Ｕレジスタと前記Ｖレジスタのガロアフィールド上の加算を行う第１ＸＯＲゲートと、
前記第１ＸＯＲゲートおよび前記シフター回路の出力を受け、入力された値を、前記Ｕレジスタまたは前記Ｖレジスタに出力する第２セレクタと、
をさらに含むことを特徴とする請求項３に記載の逆数演算器。
【請求項５】
前記演算処理部は、前記Ｕレジスタと前記Ｖレジスタの次数を比較する次数比較器をさらに含み、
前記次数比較器の出力にもとづいて、前記Ｕレジスタおよび前記Ｖレジスタそれぞれのラッチイネーブルが制御されることを特徴とする請求項４に記載の逆数演算器。
【請求項６】
前記演算処理部は、前記ステップ（ii）を実行するよう構成された１／Ｚ演算部を含み、
前記１／Ｚ演算部は、
それぞれが入力に対して１／Ｚ処理を施すよう構成されている、縦続接続されたｎ個の１／Ｚ回路と、
前記Ｇ１レジスタと前記Ｇ２レジスタの値の一方を選択し、初段の前記１／Ｚ回路に出力する第３セレクタと、
を含むことを特徴とする請求項１から５のいずれかに記載の逆数演算器。
【請求項７】
前記演算処理部は、
前記Ｇ１レジスタと前記Ｇ２レジスタのガロアフィールド上の加算を行う第２ＸＯＲゲートと、
前記１／Ｚ演算部の出力および前記第２ＸＯＲゲートの出力を受け、入力された値を、前記Ｇ１レジスタまたは前記Ｇ２レジスタに出力する第４セレクタと、
をさらに含むことを特徴とする請求項６に記載の逆数演算器。
【請求項８】
前記演算処理部は、前記Ｕレジスタと前記Ｖレジスタの次数を比較する次数比較器をさらに含み、
前記次数比較器の出力にもとづいて、前記Ｇ１レジスタおよび前記Ｇ２レジスタそれぞれのラッチイネーブルが制御されることを特徴とする請求項７に記載の逆数演算器。
【請求項９】
前記１／Ｚ回路は、
入力の最下位ビットと前記Ｆレジスタの論理積を生成するＡＮＤゲートと、
前記ＡＮＤゲートの出力と前記入力の排他的論理積を生成する第３ＸＯＲゲートと、
前記第３ＸＯＲゲートの出力を１ビット右シフトする１ビットシフタと、
を含むことを特徴とする請求項６に記載の逆数演算器。
【請求項１０】
ｍビットのガロアフィールド上で、入力値の逆数を演算する方法であって、
ｍビットのＦレジスタに、ガロアフィールド上で法として使用すべき規約多項式をビットベクトル表現で格納するステップと、
ｍビットのＵレジスタに、初期値として前記入力値を格納するステップと、
ｍビットのＶレジスタに、初期値として前記Ｆレジスタと同じ値を格納するステップと、
ｍビットのＧ１レジスタに、初期値として１を格納するステップと、
ｍビットのＧ２レジスタに、初期値として０を格納するステップと、
前記Ｕレジスタの下位ｎビット（ｎ＜ｍ）を参照し、最下位ビットから上位に向かってｙビット（ｙ≦ｎ）にわたり０が連続するとき、前記Ｕレジスタの値をｙビット右シフトするステップ（i）と、
前記ステップ（i）と連動して、前記Ｇ１レジスタにｙ回、１／Ｚ処理を行うステップであって、前記１／Ｚ処理は、その入力の最下位ビットが０である場合に、入力を１ビット右シフトした値を出力し、その入力の最下位ビットが１である場合にはその入力に法Ｆの値をガロアフィールド上で加算した後に１ビット右シフトした値を出力するものである、ステップ（ii）と、
前記Ｕレジスタの最下位ビットが０であるとき、前記ステップ（i）、(ii)を繰り返すステップ（iii）と、
前記Ｖレジスタの下位ｎビット（ｎ＜ｍ）を参照し、最下位ビットから上位に向かってｙビットにわたり０が連続するとき、前記Ｖレジスタの値をｙビット右シフトするステップ（iv）と、
前記ステップ（iv）と連動して、前記Ｇ２レジスタにｙ回、１／Ｚ処理を行うステップ(v)と、
前記Ｖレジスタの最下位ビットが０であるとき、前記ステップ（iv）、(v)を繰り返すステップ（vi）と、
前記ステップ（i）〜(vi)の結果、前記Ｕレジスタの最下位ビットと前記Ｖレジスタの最下位ビットが両方１となったとき、前記Ｕレジスタと前記Ｖレジスタの次数を比較するステップ（vii）と、
前記Ｕレジスタと前記Ｖレジスタのガロアフィールド上の加算を行い、加算結果を前記Ｕレジスタと前記Ｖレジスタのうち、次数が高い方に格納するステップ（viii）と、
前記Ｇ１レジスタと前記Ｇ２レジスタのガロアフィールド上の加算を行い、前記ステップ（vii）において前記Ｕレジスタの次数の方が高いとき、加算結果を前記Ｇ１レジスタに格納し、前記ステップ（vii）において前記Ｖレジスタの次数の方が高いとき、加算結果を前記Ｇ２レジスタに格納するステップ（ix）と、
前記ステップ(i)〜（ix）を、前記Ｕレジスタおよび前記Ｖレジスタの一方が１になるまで繰り返し、前記Ｕレジスタが１であるとき、前記Ｇ１レジスタの値を求めるべき逆数として出力し、前記Ｖレジスタが１であるとき、前記Ｇ２レジスタの値を求めるべき逆数として出力するステップ（x）と、
を備えることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ガロア体上の逆数演算器に関する。
【背景技術】
【０００２】
近年、楕円曲線暗号方式が注目を集めている。楕円曲線暗号方式は、従来主流となっているＲＳＡ方式と同程度のセキュリティを、より短いビット長のキーを用いて実現でき、また処理時間も短時間で済むという利点を有する。この特徴により、低消費電力が求められる組み込み機器への適用が期待される。
【０００３】
楕円曲線暗号方式では、１６０ビットから５１２ビット程度のビット長で表現される有限体（ガロアフィールドあるいはガロア体という）という体型での加減乗除演算を行う必要がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００３−２７１０５６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
このうち、特に除算ならびに逆数演算は処理が複雑であることから、できるだけ除算を回避するアルゴリズムが考案されているが、すべての除算をなくすことはできず、除算処理には多くのサイクル数を要しており、ボトルネックとなっていた。所定の時間内で決められた処理を完了するためには、クロック数を高める必要があり、消費電力が増大する一因となっている。
【０００６】
本発明はかかる状況においてなされたものであり、そのある態様の例示的な目的のひとつは、少ないサイクル数で逆数演算が可能な逆数演算器の提供にある。
【課題を解決するための手段】
【０００７】
本発明のある態様は、ｍビットのガロアフィールド上で、入力値の逆数を演算する逆数演算器に関する。逆数演算器は、ガロアフィールド上で法として使用すべき規約多項式をビットベクトル表現で格納するｍビットのＦレジスタと、初期値として入力値を格納するｍビットのＵレジスタと、初期値として、Ｆレジスタと同じ値を格納するｍビットのＶレジスタと、初期値として１を格納するｍビットのＧ１レジスタと、初期値として０を格納するｍビットのＧ２レジスタと、演算処理部と、を備える。演算処理部は、Ｕレジスタの下位ｎビット（ｎ＜ｍ）を参照し、最下位ビットから上位に向かってｙビット（ｙ≦ｎ）にわたり０が連続するとき、Ｕレジスタの値をｙビット右シフトするステップ（i）と、ステップ（i）と連動して、Ｇ１レジスタにｙ回、１／Ｚ処理を行うステップであって、１／Ｚ処理は、その入力の最下位ビットが０である場合に、入力を１ビット右シフトした値を出力し、その入力の最下位ビットが１である場合にはその入力に法Ｆの値をガロアフィールド上で加算した後に１ビット右シフトした値を出力するものである、ステップ（ii）と、Ｕレジスタの最下位ビットが０であるとき、ステップ（i）、(ii)を繰り返すステップ（iii）と、Ｖレジスタの下位ｎビット（ｎ＜ｍ）を参照し、最下位ビットから上位に向かってｙビットにわたり０が連続するとき、Ｖレジスタの値をｙビット右シフトするステップ（iv）と、ステップ（iv）と連動して、Ｇ２レジスタにｙ回、１／Ｚ処理を行うステップ(v)と、Ｖレジスタの最下位ビットが０であるとき、ステップ（iv）、(v)を繰り返すステップ（vi）と、ステップ（i）〜(vi)の結果、Ｕレジスタの最下位ビットとＶレジスタの最下位ビットが両方１となったとき、ＵレジスタとＶレジスタの次数を比較するステップ（vii）と、ＵレジスタとＶレジスタのガロアフィールド上の加算を行い、加算結果をＵレジスタとＶレジスタのうち、次数が高い方に格納するステップ（viii）と、Ｇ１レジスタとＧ２レジスタのガロアフィールド上の加算を行い、ステップ（vii）においてＵレジスタの次数の方が高いとき、加算結果をＧ１レジスタに格納し、ステップ（vii）においてＶレジスタの次数の方が高いとき、加算結果をＧ２レジスタに格納するステップ（ix）と、ステップ(i)〜（ix）を、ＵレジスタおよびＶレジスタの一方が１になるまで繰り返し、Ｕレジスタが１であるとき、Ｇ１レジスタの値を求めるべき逆数として出力し、Ｖレジスタが１であるとき、Ｇ２レジスタの値を求めるべき逆数として出力するステップ（x）と、を備える。
【０００８】
この態様によると、拡張ユークリッドアルゴリズムを用い、ｎビットを単位として演算処理を進めることで、少ないサイクル数で逆数を演算できる。
【０００９】
演算処理部は、ＵレジスタおよびＶレジスタそれぞれの下位ｎビットを参照し、それぞれについて、最下位ビットから連続する０の個数ｙを判定するコントローラを含んでもよい。
【００１０】
演算処理部は、ステップ（i）（iii）（iv）（vi）を実行するよう構成されたシフター回路を含んでもよい。シフター回路は、ＵレジスタとＶレジスタの値の一方を選択する第１セレクタと、コントローラによる判定結果にもとづいて、第１セレクタの出力をｙビット右シフトするマルチビットシフタと、を含んでもよい。
この場合、ＵレジスタとＶレジスタをシフトするマルチビットシフタを共有できるため、ハードウェア資源を節約できる。
【００１１】
演算処理部は、ＵレジスタとＶレジスタのガロアフィールド上の加算を行う第１ＸＯＲゲートと、第１ＸＯＲゲートおよびシフター回路の出力を受け、入力された値を、ＵレジスタおよびＶレジスタに出力する第２セレクタと、をさらに含んでもよい。
【００１２】
演算処理部は、ＵレジスタとＶレジスタの次数を比較する次数比較器をさらに含んでもよい。次数比較器の出力にもとづいて、ＵレジスタおよびＶレジスタそれぞれのラッチイネーブルが制御されてもよい。
【００１３】
演算処理部は、ステップ（ii）を実行するよう構成された１／Ｚ演算部を含んでもよい。１／Ｚ演算部は、それぞれが入力に対して１／Ｚ処理を施すよう構成されている、縦続接続されたｎ個の１／Ｚ回路と、Ｇ１レジスタとＧ２レジスタの値の一方を選択し、初段の１／Ｚ回路に出力する第３セレクタと、を含んでもよい。
この場合、Ｇ１レジスタとＧ２レジスタに１／Ｚ処理を施す回路ユニットを共有できるため、ハードウェア資源を節約できる。
【００１４】
演算処理部は、Ｇ１レジスタとＧ２レジスタのガロアフィールド上の加算を行う第２ＸＯＲゲートと、１／Ｚ演算部の出力および第２ＸＯＲゲートの出力を受け、入力された値を、Ｇ１レジスタおよびＧ２レジスタに出力する第４セレクタと、をさらに含んでもよい。
【００１５】
演算処理部は、ＵレジスタとＶレジスタの次数を比較する次数比較器をさらに含んでもよい。次数比較器の出力にもとづいて、Ｇ１レジスタおよびＧ２レジスタそれぞれのラッチイネーブルが制御されてもよい。
【００１６】
１／Ｚ回路は、入力の最下位ビットとＦレジスタの論理積を生成するＡＮＤゲートと、ＡＮＤゲートの出力と入力の排他的論理積を生成する第３ＸＯＲゲートと、第３ＸＯＲゲートの出力を１ビット右シフトする１ビットシフタと、を含んでもよい。
これにより、最小の構成要素で１／Ｚ演算が可能となる。
【００１７】
なお、以上の構成要素の任意の組み合わせや、本発明の構成要素や表現を、方法、装置、システムなどの間で相互に置換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１８】
本発明のある態様によれば、少ないサイクル数で逆数演算が可能となる。
【図面の簡単な説明】
【００１９】
【図１】実施の形態に係る逆数演算器のブロック図である。
【図２】図１の逆数演算器の具体的な構成例を示すブロック図である。
【図３】１／Ｚ回路の構成例を示すブロック図である。
【発明を実施するための形態】
【００２０】
以下、本発明を好適な実施の形態をもとに図面を参照しながら説明する。各図面に示される同一または同等の構成要素、部材、処理には、同一の符号を付するものとし、適宜重複した説明は省略する。また、実施の形態は、発明を限定するものではなく例示であって、実施の形態に記述されるすべての特徴やその組み合わせは、必ずしも発明の本質的なものであるとは限らない。
【００２１】
図１は、実施の形態に係る逆数演算器１００のブロック図である。逆数演算器１００は、ｍビット（ｍは２以上の整数）のガロアフィールド上で、入力値Ｘの逆数Ｘ−１を演算する。逆数演算器１００は、それぞれが変数を格納するＵレジスタ１０、Ｖレジスタ１２、Ｇ１レジスタ１４、Ｇ２レジスタ１６と、各レジスタの値に所定の演算処理を施す演算処理部２０と、を備える。Ｕレジスタ１０、Ｖレジスタ１２、Ｇ１レジスタ１４、Ｇ２レジスタ１６それぞれのビット長は等しくｍである。
【００２２】
（概要）
逆数演算器１００の演算アルゴリズムの概要を説明する。
Ｕレジスタ１０、Ｖレジスタ１２それぞれに関して、最下位ビットから上位に向かってｙビットにわたり連続して０が含まれるとき、Ｕレジスタ１０、Ｖレジスタ１２をｙビット右シフトする。それと連動して、Ｖレジスタ１２、Ｇ１レジスタ１４に、ｙ回の１／Ｚ処理を行う。Ｕレジスタ１０、Ｖレジスタ１２の最下位ビットが両方１のとき、次数が高い方を、Ｕレジスタ１０とＶレジスタ１２の加算結果で更新する。またそれと連動して、Ｕレジスタ１０の次数が高いとき、Ｇ１レジスタ１４を、Ｇ１レジスタ１４とＧ２レジスタ１６の加算結果で更新し、Ｖレジスタ１２の次数が高いとき、Ｇ２レジスタ１６を、Ｇ１レジスタ１４とＧ２レジスタ１６の加算結果で更新する。これを繰り返し、逆数を演算する。
【００２３】
（レジスタ）
ガロアフィールド上において、法Ｆとして使用すべき規約多項式は、ビットベクトル表現で、演算処理部２０のＦレジスタ１８に格納されている。Ｕレジスタ１０は、その初期値として入力値Ｘを格納する。Ｖレジスタ１２は、その初期値として、Ｆレジスタ１８と同じ値を格納する。Ｇ１レジスタ１４は、その初期値として１を格納する。Ｇ２レジスタ１６は、初期値として０を格納する。
【００２４】
（演算処理部）
続いて、演算処理部２０の行う処理を説明する。
ステップ（i）
Ｕレジスタ１０の下位ｎビット（ｎ＜ｍ）を参照し、最下位ビットから上位に向かってｙビット（ｙ≦ｎ）にわたり０が連続するとき、Ｕレジスタ１０の値をｙビット右シフトする。本実施の形態ではｎ＝４の場合を説明する。
【００２５】
ステップ（ii）
ステップ（i）と連動して、Ｇ１レジスタ１４にｙ回、１／Ｚ処理を行う。
１／Ｚ処理は、その入力の最下位ビットが０である場合に、入力を１ビット右シフトした値を出力し、その入力の最下位ビットが１である場合にはその入力に法Ｆの値をガロアフィールド上で加算した後に１ビット右シフトした値を出力するものである。ガロアフィールド上における加算は、ＸＯＲ（排他的論理和）演算である。
【００２６】
ステップ（iii）
Ｕレジスタ１０の最下位ビットが０であるとき、ステップ（i）、(ii)を繰り返す。
【００２７】
ステップ（iv）
Ｖレジスタ１２の下位ｎビット（ｎ＜ｍ）を参照し、最下位ビットから上位に向かってｙビットにわたり０が連続するとき、Ｖレジスタ１２の値をｙビット右シフトする。
ステップ(v)
ステップ（iv）と連動して、Ｇ２レジスタにｙ回、１／Ｚ処理を行う。
【００２８】
ステップ（vi）
Ｖレジスタ１２の最下位ビットが０であるとき、ステップ（iv）、(v)を繰り返す。
【００２９】
ステップ（vii）
上述のステップ（i）〜(vi)の結果、Ｕレジスタ１０の最下位ビットとＶレジスタ１２の最下位ビットが両方１となったとき、Ｕレジスタ１０とＶレジスタ１２の次数を比較する。次数は、レジスタに格納される各ビットのうち、最上位の１が、最下位ビットから何ビット目に位置するかを表す。
【００３０】
ステップ（viii）
Ｕレジスタ１０とＶレジスタ１２のガロアフィールド上の加算を行い、加算結果をＵレジスタ１０とＶレジスタ１２のうち、次数が高い方に格納する。
【００３１】
ステップ（ix）
Ｇ１レジスタ１４とＧ２レジスタ１６のガロアフィールド上の加算を行う。そしてステップ（vii）においてＵレジスタ１０の次数の方が高いとき、加算結果をＧ１レジスタ１４に格納する。反対にステップ（vii）においてＶレジスタ１２の次数の方が高いとき、加算結果をＧ２レジスタ１６に格納する。
【００３２】
ステップ（x）
以上のステップ(i)〜（ix）を、Ｕレジスタ１０およびＶレジスタ１２の一方が１になるまで繰り返す。そしてＵレジスタ１０が１となったとき、Ｇ１レジスタ１４の値を求めるべき逆数Ｘ−１として出力し、Ｖレジスタ１２が１となったとき、Ｇ２レジスタ１６の値を求めるべき逆数Ｘ−１として出力する。
【００３３】
続いて演算処理部２０の構成例を説明する。
【００３４】
図２は、図１の逆数演算器１００の具体的な構成例を示すブロック図である。
演算処理部２０は、コントローラ２２、シフター回路３０、第１ＸＯＲゲート４０、次数比較器４２、１／Ｚ演算部５０、第２ＸＯＲゲート６０、第２セレクタ６２、第４セレクタ６６を備える。
【００３５】
コントローラ２２は、Ｕレジスタ１０およびＶレジスタ１２それぞれの下位ｎビットを参照し、それぞれについて、最下位ビットから連続する０の個数ｙを判定する。コントローラ２２は、ステップ（iii）に関連してＵレジスタ１０の最下位ビットが０か否か、ステップ（vi）に関連してＶレジスタ１２の最下位ビットが０か否かを判定する。
【００３６】
コントローラ２２は、判定結果にもとづいて、第１セレクタ３２、次数比較器４２、第３セレクタ６４を制御する。
【００３７】
シフター回路３０は、ステップ（i）（iii）（iv）（vi）に関連する処理を実行するよう構成される。具体的にはシフター回路３０は、第１セレクタ３２、マルチビットシフタ３４を含む。第１セレクタ３２は、Ｕレジスタ１０とＶレジスタ１２の値のうち、コントローラ２２から指示された一方を選択する。すなわち、コントローラ２２がＵレジスタ１０に関するステップ（i）を実行するとき、第１セレクタ３２はＵレジスタ１０を選択し、コントローラ２２がＶレジスタ１２に関する処理（iv）を実行するとき、第１セレクタ３２はＶレジスタ１２を選択する。
【００３８】
マルチビットシフタ３４には、コントローラ２２により検出されたビット数ｙが入力される。マルチビットシフタ３４は、第１セレクタ３２の出力を、ｙビット右シフトする。
【００３９】
次数比較器４２は、ステップ（vii）と関連して、Ｕレジスタ１０の次数ｄｅｇ（Ｕ）と、Ｖレジスタ１２の次数ｄｅｇ（Ｖ）を比較する。次数比較器４２の出力は、次数ｄｅｇ（Ｕ）の方が高いときにＵを示し、次数ｄｅｇ（Ｖ）の方が高いときにＶを示すものとする。
【００４０】
第１ＸＯＲゲート４０は、ステップ（vii）に関連する処理を行う。すなわち第１ＸＯＲゲート４０は、Ｕレジスタ１０とＶレジスタ１２のガロアフィールド上の加算であるＸＯＲ演算を行う。
【００４１】
第２セレクタ６２は、第１ＸＯＲゲート４０およびシフター回路３０の出力を受け、選択した一方を、Ｕレジスタ１０およびＶレジスタ１２に出力する。
Ｕレジスタ１０およびＶレジスタ１２は、それぞれのラッチイネーブル信号がアサートされると、その値が更新される。次数比較器４２の出力がＵを示すとき、Ｕレジスタ１０のラッチイネーブルがアサートされ、第２セレクタ６２の出力がＵレジスタ１０に格納される。反対に、次数比較器４２の出力がＶを示すとき、Ｖレジスタ１２のラッチイネーブルがアサートされ、第２セレクタ６２の出力がＶレジスタ１２に格納される。これにより、ステップ（viii）の処理が可能となる。
【００４２】
１／Ｚ演算部５０は、ステップ（ii）を実行するよう構成される。１／Ｚ演算部５０は、縦続接続されたｎ個の１／Ｚ回路５２と、第３セレクタ６４と、を含む。
１／Ｚ回路５２はそれぞれ、入力に対して１／Ｚ処理を施すよう構成されている。第３セレクタ６４は、Ｇ１レジスタ１４とＧ２レジスタ１６の値の一方を選択し、初段の１／Ｚ回路５２に出力する。コントローラ２２による制御下で、第３セレクタ６４はステップ（ii）においてＧ１レジスタ１４を選択し、ステップ（v）においてＧ２レジスタ１６を選択する。
【００４３】
第２ＸＯＲゲート６０は、ステップ（ix）に関連して、Ｇ１レジスタ１４とＧ２レジスタ１６のガロアフィールド上の加算を行う。
【００４４】
第４セレクタ６６は、１／Ｚ演算部５０の出力および第２ＸＯＲゲート６０の出力を受け、入力された値を、Ｇ１レジスタ１４およびＧ２レジスタ１６に出力する。Ｇ１レジスタ１４およびＧ２レジスタ１６は、それぞれのラッチイネーブル信号がアサートされると、その値が更新される。次数比較器４２の出力がＵを示すとき、Ｇ１レジスタ１４のラッチイネーブルがアサートされ、第４セレクタ６６の出力がＧ１レジスタ１４に格納される。反対に、次数比較器４２の出力がＶを示すとき、Ｇ２レジスタ１６のラッチイネーブルがアサートされ、第４セレクタ６６の出力がＧ２レジスタ１６に格納される。これにより、ステップ（ix）の処理が可能となる。
【００４５】
図３は、１／Ｚ回路５２の構成例を示すブロック図である。１／Ｚ回路５２は、ＡＮＤゲート５４、第３ＸＯＲゲート５６、１ビットシフタ５８を含む。
ＡＮＤゲート５４は、入力の最下位ビットとＦレジスタ１８の論理積（ＡＮＤ）を生成する。第３ＸＯＲゲート５６は、ＡＮＤゲート５４の出力と入力の排他的論理積（ＸＯＲ）を生成する。１ビットシフタ５８は、第３ＸＯＲゲート５６の出力を１ビット右シフトする。
【００４６】
以上が逆数演算器１００の具体的な構成である。
【００４７】
この逆数演算器１００によれば、拡張ユークリッドアルゴリズムを用い、ｎビットを単位として演算処理を進めることで、少ないサイクル数で逆数Ｘ−１を演算できる。サイクル数を減らすことにより、逆数演算器１００を低周波数で動作させることが可能となるため、消費電力を低減できる。
【００４８】
あるいは、従来と同じクロック周波数で動作させた場合、演算処理に要する時間を短縮できる。
【００４９】
以上、本発明について、実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下、こうした変形例について説明する。
【００５０】
（第１変形例）
図２のシフター回路３０では、単一のマルチビットシフタ３４を、Ｕレジスタ１０とＶレジスタ１２の右シフト処理について共用したが、２系統のマルチビットシフタ３４を設けてもよい。
【００５１】
（第２変形例）
図２の１／Ｚ演算部５０では、Ｇ１レジスタ１４とＧ２レジスタ１６に対する１／Ｚ処理を、１系統の１／Ｚ回路群で共用したが、２系統の１／Ｚ回路群を設けてもよい。
【００５２】
実施の形態にもとづき、特定の語句を用いて本発明を説明したが、実施の形態は、本発明の原理、応用を示しているにすぎず、実施の形態には、請求の範囲に規定された本発明の思想を逸脱しない範囲において、多くの変形例や配置の変更が可能である。
【符号の説明】
【００５３】
１００…逆数演算器、１０…Ｕレジスタ、１２…Ｖレジスタ、１４…Ｇ１レジスタ、１６…Ｇ２レジスタ、１８…Ｆレジスタ、２０…演算処理部、２２…コントローラ、３０…シフター回路、３２…第１セレクタ、３４…マルチビットシフタ、４０…第１ＸＯＲゲート、４２…次数比較器、５０…１／Ｚ演算部、５２…１／Ｚ回路、５４…ＡＮＤゲート、５６…第３ＸＯＲゲート、５８…１ビットシフタ、６０…第２ＸＯＲゲート、６２…第２セレクタ、６４…第３セレクタ、６６…第４セレクタ。
【図１】
2015203859.tif 000003
【図２】
2015203859.tif 000004
【図３】
2015203859.tif 000005