(57)【要約】【課題】  有限体の二乗演算方法及び二乗演算装置を提供する。【解決手段】  有限体ＧＦ（２n）の決定多項式が    【数７８】2005010783.tif 000101  と表現され、有限体の要素ＡがＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）と表現されるとき、要素Ａの二乗演算を行う装置における有限体の二乗演算方法において、（ａ）所定の係数ｍi、ｌij、Ｖ0、Ｖij及びＶを決定する場合、ｉが１からｔまで変わる自然数であるときにｋiに対する所定の条件を満足するｍiを決定し、ｊが２からｍiまで変わるときにｎ、ｋi及びｊからｌijを決定し、ｎ、ｌij及びｋiからｎビットのＶ0及びＶijをそれぞれ決定し、ｍiに対して所定の数式によってＶを求めるステップと、（ｂ）ｋi及びｎによって所定の係数ｓiを決定し、Ｖをｓiだけそれぞれ循環置換するステップと、（ｃ）（ｂ）ステップで循環置換された結果及び要素Ａを排他的論理和演算するステップと、（ｄ）（ｃ）ステップの演算結果を所定の順序に従って再配置して、二乗演算の最終結果として出力するステップとを含む有限体の二乗演算方法。【選択図】      図１
2005010783.tif 000002
【特許請求の範囲】
【請求項１】
有限体ＧＦ（２n、ｎは奇数）の決定多項式が
【数１】
2005010783.tif 000067
と表現され、前記有限体の要素ＡがＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）と表現されるとき、要素Ａの二乗演算を行う装置における有限体の二乗演算方法において、
（ａ）所定の係数ｍi、ｌij、Ｖ0、Ｖij及びＶを決定する場合、ｉが１からｔまで変わる自然数であるときにｋiに対する所定の条件を満足するｍiを決定し、ｊが２からｍｉまで変わるときにｎ、ｋi及びｊからｌijを決定し、ｎ、ｌij及びｋiからｎビットのＶ0及びＶijをそれぞれ決定し、ｍiに対する
【数２】
2005010783.tif 000068
によってＶを求めるステップと、
（ｂ）ｋi及びｎによって所定の係数ｓiを決定し、Ｖをｓiだけそれぞれ循環置換するステップと、
（ｃ）前記（ｂ）ステップで循環置換された結果及び要素Ａを排他的論理和演算するステップと、
（ｄ）前記（ｃ）ステップの演算結果を所定の順序に従って再配置して、二乗演算の最終結果として出力するステップと、
を含むことを特徴とする有限体の二乗演算方法。
【請求項２】
前記（ａ）ステップのｍiは、前記所定の条件として、ｋiに対して
【数３】
2005010783.tif 000069
を満足するように決定されることを特徴とする請求項１に記載の有限体の二乗演算方法。
【請求項３】
前記（ａ）ステップのｌijは、
【数４】
2005010783.tif 000070
によって決定されることを特徴とする請求項１に記載の有限体の二乗演算方法。
【請求項４】
前記（ａ）ステップのＶ0は、
【数５】
2005010783.tif 000071
によって決定され、
前記（ａ）ステップのＶijは、
ｋiが奇数である場合またはｋiが偶数であり、ｊが奇数である場合には、
【数６】
2005010783.tif 000072
によって決定され、
ｋi、ｊがいずれも偶数である場合には、
【数７】
2005010783.tif 000073
によって決定される
ことを特徴とする請求項１に記載の有限体の二乗演算方法。
【請求項５】
前記（ｂ）ステップのｓiは、ｋi及びｎに対して
【数８】
2005010783.tif 000074
（ｏｄｄは奇数、ｅｖｅｎは偶数）
によって決定されることを特徴とする請求項１に記載の有限体の二乗演算方法。
【請求項６】
前記（ｄ）ステップの再配置は、前記（ｃ）ステップの演算結果Ｃ’をＣ’＝ｃ0’ｃ1’…ｃn-1’とし、要素Ａの二乗演算の結果をＡ2＝ｃ0ｃ1…ｃn-1とするとき、ｃiは、
【数９】
2005010783.tif 000075
によって得ることを特徴とする請求項１に記載の有限体の二乗演算方法。
【請求項７】
有限体ＧＦ（２n，ｎは奇数）の決定多項式が
【数１０】
2005010783.tif 000076
と表現され、前記有限体の要素ＡがＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）と表現されるとき、要素Ａの二乗演算を行う装置において、
（ａ）所定の係数ｍi、ｌij、Ｖ0、Ｖij及びＶを決定する場合、ｉが１からｔまで変わる自然数であるときにｋiに対する所定の条件を満足するｍiを決定し、ｊが２からｍiまで変わるときにｎ、ｋi及びｊからｌijを決定し、ｎ、ｌij及びｋiからｎビットのＶ0及びＶijをそれぞれ決定し、ｍiに対する
【数１１】
2005010783.tif 000077
によってＶを求めるステップと、
（ｂ）ｋi及びｎによって所定の係数ｓiを決定し、Ｖをｓiだけそれぞれ循環置換するステップと、
を含んで二乗演算に必要な係数を計算する係数計算部と、
複数の排他的論理和演算手段を備え、前記係数計算部の計算結果によって要素Ａを入力して排他的論理和演算を行う排他的論理和演算部と、
前記排他的論理和演算部の出力を所定の順序に従って再配置して、二乗演算の最終結果として出力する再配置部と、
を含むことを特徴とする有限体の二乗演算装置。
【請求項８】
前記再配置部は、
前記排他的論理和演算部の演算結果Ｃ’をＣ’＝ｃ0’ｃ1’…ｃn-1’とし、要素Ａの二乗演算の結果をＡ2＝ｃ0ｃ1…ｃn-1とするとき、ｃiは、
【数１２】
2005010783.tif 000078
によってｃj’をｃiに再配置することを特徴とする請求項７に記載の有限体の二乗演算装置。
【請求項９】
有限体ＧＦ（２n，ｎは偶数）の決定多項式が
【数１３】
2005010783.tif 000079
と表現され、前記有限体の要素ＡがＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）と表現されるとき、要素Ａの二乗演算を行う装置における有限体の二乗演算方法において、
（ａ）所定の係数ｍi、ｌij、Ｖ0、Ｖij及びＶを決定する場合、ｉが１からｔまで変わる自然数であるときにｋiに対する所定の条件を満足するｍiを決定し、ｊが２からｍiまで変わるときにｎ、ｋi及びｊからｌijを決定し、ｎ、ｌij及びｋｉからｎビットのＶ0及びＶijをそれぞれ決定し、ｍiに対する
【数１４】
2005010783.tif 000080
によってＶを求めるステップと、
（ｂ）ｋi及びｎによって所定の係数ｓiを決定し、Ｖをｓiだけ所定の置換式によってそれぞれ置換するステップと、
（ｃ）要素Ａを利用して
2005010783.tif 000081
を求め、前記（ｂ）ステップの置換結果及び前記
2005010783.tif 000082
の要素を排他的論理和演算するステップと、
（ｄ）前記（ｃ）ステップの演算結果を所定の順序に従って再配置して、二乗演算の最終結果として出力するステップと、
を含むことを特徴とする有限体の二乗演算方法。
【請求項１０】
前記（ａ）ステップのｍiは、前記所定の条件として、ｋiに対して
【数１５】
2005010783.tif 000083
を満足するように決定されることを特徴とする請求項９に記載の有限体の二乗演算方法。
【請求項１１】
前記（ａ）ステップのｌijは、
【数１６】
2005010783.tif 000084
によって決定されることを特徴とする請求項９に記載の有限体の二乗演算方法。
【請求項１２】
前記（ａ）ステップのＶ0は、
【数１７】
2005010783.tif 000085
によって決定され、
前記（ａ）ステップのＶijは、
ｋiが偶数である場合またはｋi、ｊがいずれも奇数である場合には、
【数１８】
2005010783.tif 000086
によって決定され、
ｋiが奇数であり、ｊが偶数である場合には、
【数１９】
2005010783.tif 000087
によって決定される
ことを特徴とする請求項９に記載の有限体の二乗演算方法。
【請求項１３】
前記（ｂ）ステップのｓiは、ｋi及びｎに対して
【数２０】
2005010783.tif 000088
（ｏｄｄは奇数、ｅｖｅｎは偶数）
によって決定されることを特徴とする請求項９に記載の有限体の二乗演算方法。
【請求項１４】
前記（ｂ）ステップの置換が
2005010783.tif 000089
と表現されるとき、要素Ａに対して
【数２１】
2005010783.tif 000090
による置換が行われることを特徴とする請求項９に記載の有限体の二乗演算方法。
【請求項１５】
前記（ｃ）ステップの
2005010783.tif 000091
は、
【数２２】
2005010783.tif 000092
によって決定されることを特徴とする請求項９に記載の有限体の二乗演算方法。
【請求項１６】
前記（ｄ）ステップの再配置は、前記（ｃ）ステップの演算結果Ｃ’をＣ’＝ｃ0’ｃ1’…ｃn-1’とし、要素Ａの二乗演算の結果をＡ2＝ｃ0ｃ1…ｃn-1とするとき、ｃiは、
【数２３】
2005010783.tif 000093
によって得ることを特徴とする請求項９に記載の有限体の二乗演算方法。
【請求項１７】
有限体ＧＦ（２n，ｎは偶数）の決定多項式が
【数２４】
2005010783.tif 000094
と表現され、前記有限体の要素ＡがＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）と表現されるとき、要素Ａの二乗演算を行う装置において、
（ａ）所定の係数ｍi、ｌij、Ｖ0、Ｖij及びＶを決定する場合、ｉが１からｔまで変わる自然数であるときにｋiに対する所定の条件を満足するｍiを決定し、ｊが２からｍiまで変わるときにｎ、ｋi及びｊからｌijを決定し、ｎ、ｌij及びｋiからｎビットのＶ0及びＶijをそれぞれ決定し、ｍiに対する
【数２５】
2005010783.tif 000095
によってＶを求めるステップと、
（ｂ）ｋi及びｎによって所定の係数ｓiを決定し、Ｖをｓiだけ所定の置換式によってそれぞれ置換するステップと、
を含んで二乗演算に必要な係数を計算する係数計算部と、
複数の排他的論理和演算手段を備え、要素Ａを入力として所定の数式による要素Ａの変換値
2005010783.tif 000096
を求め、前記係数計算部で計算された置換結果及び前記
2005010783.tif 000097
を再び排他的論理和演算する排他的論理和演算部と、
前記排他的論理和演算部の出力を所定の順序に従って再配置して、二乗演算の最終結果として出力する再配置部と、
を含むことを特徴とする有限体の二乗演算装置。
【請求項１８】
前記排他的論理和演算部は、
要素Ａを入力として
【数２６】
2005010783.tif 000098
によって
2005010783.tif 000099
を求める複数の排他的論理和演算手段を備えることを特徴とする請求項１７に記載の有限体の二乗演算装置。
【請求項１９】
前記再配置部は、
前記排他的論理和演算部の演算結果Ｃ’をＣ’＝ｃ0’ｃ1’…ｃn-1’とし、要素Ａの二乗演算の結果をＡ2＝ｃ0ｃ1…ｃn-1とするとき、ｃiは
【数２７】
2005010783.tif 000100
によってｃj’をｃiに再配置することを特徴とする請求項１７に記載の有限体の二乗演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限体の二乗演算方法及び二乗演算装置に関する。
【背景技術】
【０００２】
有限体ＧＦ（２n）は、２n個の要素を含む数値系である。有限体の各要素がｎビットで表現できるという事実によって、有限体の実際的な応用が可能である。例えばエラー訂正コードや楕円曲線暗号系をハードウェアで実現するような実際的な応用では、ＧＦ（２n）の計算を頻繁に使用する。リードソロモンコードを符号化／復号化する装置はＧＦ（２n）の計算を行わなければならず、楕円曲線暗号系の暗号／解読装置はｎを大きい値とするＧＦ（２n）の計算を行わなければならない。
有限体ＧＦ（２）は、次の式１のような加算、積算規則を有し、その要素が２進数０、１だけの数値系である。
【数２８】
2005010783.tif 000003
【０００３】
すなわち、加算はビット排他的論理和（以下、“ＸＯＲ”）演算であり、積算はビット論理積（以下、“ＡＮＤ”）演算である。
有限体ＧＦ（２n）（ｎ＞１）は２n個の要素を含む数値系であるが、この数値系における加算及び積算はＧＦ（２）の係数を有するｎ次多項式のモジュロ演算に対応する。この多項式を有限体決定多項式とし、この多項式の一根をαとするとき、有限体の一要素は、次の式２のような標準表現を有する。
【数２９】
2005010783.tif 000004
【０００４】
ＧＦ（２n）の２要素の積は、αに関する多項式積算後、決定多項式によるモジュロ演算で決定される。ＧＦ（２n）の２要素の和は、αに関する多項式加算で定義される。
有限体ＧＦ（２n）の決定多項式を次の式３のように表現し、αを決定多項式の根とする。
【数３０】
2005010783.tif 000005
【０００５】
ここで、ｎは任意の自然数であり、ｔとｋiとは０＜ｔ、ｋi＜ｎである。
有限体の要素Ａに対してＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）であれば、要素Ａの二乗Ａ2は、次の式４のように要素Ａ及び要素Ａのαに関する多項式積算後、ｆ（α）によるモジュロ演算で決定される。
【数３１】
2005010783.tif 000006
【０００６】
式４で示されるような二乗演算を行うための従来技術には、次のようなものがある。なお、以下では、面積複雑度とはハードウェアのサイズすなわちゲート数のことをいい、時間複雑度とはハードウェアのゲート遅延のことをいう。ＳＥＣ（Standards for Efficient Cryptography）及びＡＮＳＩ（American National Standards Institute、米国規格協会） Ｘ９.６２のような暗号化技術の標準では、楕円曲線暗号系に必要な係数を定義し、いくつかの有限体係数を推奨している。有限体係数を決定するために、この２つの標準が最も幅広く使用されている。このため、この２つの標準が、各暗号化技術の汎用性を判断するときの基準として使用される。なお、以下では、ｎは有限体の次元をいう。
【０００７】
非特許文献１は、決定多項式が三項式Ｘn＋Ｘk＋１である場合、ｎ及びｋの値に対する二乗演算の結果を整理したものを開示している。この技術は数式が最適化されているため、面積複雑度及び時間複雑度の側面で効率的な結果を示す。しかし、決定多項式が五項式である場合については言及されていない。
【０００８】
非特許文献２は、有限体ＧＦ（２n）でｎ＋１が素数であり、２∈Ｚn+1が原始要素であるとき、異常基底を使用し、決定多項式がＡＯＰ（All One Polynomial）であれば、再配置によって二乗演算ができることを示している。しかし、当該ｎ及び決定多項式が前記標準に含まれていない。
【０００９】
特許文献１は、ｎが偶数であり、有限体ＧＦ（２n）がＧＦ（２）＜ＧＦ（２n/2）＜ＧＦ（２n）の条件を満たす場合、ＧＦ（２n）の演算はＧＦ（２n/2）の演算を利用して実現できることを示し、このような方法を利用した二乗演算装置を提案している。しかし、有限体の表現方式が標準の表現方式と異なるので、互換性に問題がある。更に、前記標準におけるｎはほとんど奇数であるので、この技術が適用される場合は少ない。
【００１０】
特許文献２では、循環基底を使用して二乗演算を実現する。循環基底は、ｍ＝（２n−１）／Δ≧ｎ，Δ≧ｎを満足する２n−１の最小の約数Δに対して、１,αΔ,α2Δ,α3Δ,…,α(m-1)Δとなる。この場合、再配置によって二乗演算が行われる。しかし、この技術を適用するためには、基底変換が要求されるが、条件を満足するΔの値が相当大きい値であるので、その基底変換が非常に複雑になる。
【００１１】
非特許文献３は、二乗演算の入力要素を予め決められた原理で分離し、その分離した要素を積算装置に入力する方法を開示している。この二乗演算装置のうち積算装置を除外した部分は、３.５ｎ個のゲートで構成される。これは、約ｎ／２個のゲートで構成される非特許文献１の発明と比較して非効率的である。
非特許文献４は、正規基底を使用するので、再配置によって二乗演算が行われる。しかし、要求される基底変換は非常に複雑である。
【００１２】
したがって、従来技術に現れたような複雑な基底変換がなく、面積複雑度及び時間複雑度を減らすことができる二乗演算方法及び二乗演算装置が必要である。
【特許文献１】K.Aoki, "Scheme for arithmetic operations in finite field and group operations over elliptic curves realizing improved computational speed”, 2001（米国特許第６,２６６,６８８号明細書、第６,２０２,０７６号明細書）
【特許文献２】Lambert, “Method and apparatus for implementing arithmetical operations in finite fields", 2001（欧州特許第１,０７６,２８４ Ａ１号明細書）
【非特許文献１】H.Wu, “Bit-parallel finite field multiplier and squarer using polynomial basis”, IEEE Transaction on Computers, Vol.51, No.7, 2002, pp.750〜758
【非特許文献２】C.H.Kim, “A new hardware architecture for operations in GF(2n), IEEE Transaction on Computers, Vol.51, No.1, 2002, pp.90〜92
【非特許文献３】G.Orlando, “Squaring architecture for GF(2n) and its application in cryptographic systems”, Electronics Letters, Vol.36, No.13, 2000, pp.1116〜1117
【非特許文献４】C.C.Wang, “VLSI architectures for computing multiplications and inverses in GF(2M)”, IEEE Transactions on Computers, Vol.C-34, No.8, 1985, pp.709〜717
【発明の開示】
【発明が解決しようとする課題】
【００１３】
そこで、本発明が解決しようとする技術的課題は、有限体の決定多項式の二乗演算に必要な係数を定義し、その定義された係数に対して必要な排他的論理演算を行い、その排他的論理演算の結果を再配置して二乗演算を行う有限体の二乗演算方法及び装置を提供することである。
【課題を解決するための手段】
【００１４】
前記課題を解決するための本発明は、有限体ＧＦ（２n、ｎは奇数）の決定多項式が
【数３２】
2005010783.tif 000007
と表現され、前記有限体の要素ＡがＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）と表現されるとき、要素Ａの二乗演算を行う装置における有限体の二乗演算方法において、（ａ）所定の係数ｍi、ｌij、Ｖ0、Ｖij及びＶを決定する場合、ｉが１からｔまで変わる自然数であるときにｋiに対する所定の条件を満足するｍiを決定し、ｊが２からｍｉまで変わるときにｎ、ｋi及びｊからｌijを決定し、ｎ、ｌij及びｋiからｎビットのＶ0及びＶijをそれぞれ決定し、ｍiに対する
【数３３】
2005010783.tif 000008
によってＶを求めるステップと、（ｂ）ｋi及びｎによって所定の係数ｓiを決定し、Ｖをｓiだけそれぞれ循環置換するステップと、（ｃ）前記（ｂ）ステップで循環置換された結果及び要素Ａを排他的論理和演算するステップと、（ｄ）前記（ｃ）ステップの演算結果を所定の順序に従って再配置して、二乗演算の最終結果として出力するステップとを含むことを特徴とする。
【００１５】
次に、本発明は、有限体ＧＦ（２n，ｎは奇数）の決定多項式が
【数３４】
2005010783.tif 000009
と表現され、前記有限体の要素ＡがＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）と表現されるとき、要素Ａの二乗演算を行う装置において、（ａ）所定の係数ｍi、ｌij、Ｖ0、Ｖij及びＶを決定する場合、ｉが１からｔまで変わる自然数であるときにｋiに対する所定の条件を満足するｍiを決定し、ｊが２からｍiまで変わるときにｎ、ｋi及びｊからｌijを決定し、ｎ、ｌij及びｋiからｎビットのＶ0及びＶijをそれぞれ決定し、ｍiに対する
【数３５】
2005010783.tif 000010
によってＶを求めるステップと、（ｂ）ｋi及びｎによって所定の係数ｓiを決定し、Ｖをｓiだけそれぞれ循環置換するステップとを含んで二乗演算に必要な係数を計算する係数計算部と、複数の排他的論理和演算手段を備え、前記係数計算部の計算結果によって要素Ａを入力して排他的論理和演算を行う排他的論理和演算部と、前記排他的論理和演算部の出力を所定の順序に従って再配置して、二乗演算の最終結果として出力する再配置部とを含むことを特徴とする。
【００１６】
また、本発明は、有限体ＧＦ（２n，ｎは偶数）の決定多項式が
【数３６】
2005010783.tif 000011
と表現され、前記有限体の要素ＡがＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）と表現されるとき、要素Ａの二乗演算を行う装置における有限体の二乗演算方法において、（ａ）所定の係数ｍi、ｌij、Ｖ0、Ｖij及びＶを決定する場合、ｉが１からｔまで変わる自然数であるときにｋiに対する所定の条件を満足するｍiを決定し、ｊが２からｍiまで変わるときにｎ、ｋi及びｊからｌijを決定し、ｎ、ｌij及びｋｉからｎビットのＶ0及びＶijをそれぞれ決定し、ｍiに対する
【数３７】
2005010783.tif 000012
によってＶを求めるステップと、（ｂ）ｋi及びｎによって所定の係数ｓiを決定し、Ｖをｓiだけ所定の置換式によってそれぞれ置換するステップと、（ｃ）要素Ａを利用して
2005010783.tif 000013
を求め、前記（ｂ）ステップの置換結果及び前記
2005010783.tif 000014
の要素を排他的論理和演算するステップと、（ｄ）前記（ｃ）ステップの演算結果を所定の順序に従って再配置して、二乗演算の最終結果として出力するステップとを含むことを特徴とする。
【００１７】
さらに、本発明は、有限体ＧＦ（２n，ｎは偶数）の決定多項式が
【数３８】
2005010783.tif 000015
と表現され、前記有限体の要素ＡがＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）と表現されるとき、要素Ａの二乗演算を行う装置において、（ａ）所定の係数ｍi、ｌij、Ｖ0、Ｖij及びＶを決定する場合、ｉが１からｔまで変わる自然数であるときにｋiに対する所定の条件を満足するｍiを決定し、ｊが２からｍiまで変わるときにｎ、ｋi及びｊからｌijを決定し、ｎ、ｌij及びｋiからｎビットのＶ0及びＶijをそれぞれ決定し、ｍiに対する
【数３９】
2005010783.tif 000016
によってＶを求めるステップと、（ｂ）ｋi及びｎによって所定の係数ｓiを決定し、Ｖをｓiだけ所定の置換式によってそれぞれ置換するステップとを含んで二乗演算に必要な係数を計算する係数計算部と複数の排他的論理和演算手段を備え、要素Ａを入力として所定の数式による要素Ａの変換値
2005010783.tif 000017
を求め、前記係数計算部で計算された置換結果及び前記
2005010783.tif 000018
を再び排他的論理和演算する排他的論理和演算部と、前記排他的論理和演算部の出力を所定の順序に従って再配置して、二乗演算の最終結果として出力する再配置部とを含むことを特徴とする。
【発明の効果】
【００１８】
本発明によれば、暗号化技術の標準におけるほとんどの場合に適用できるので、汎用性を満足しつつ、面積複雑度及び時間複雑度の側面でも効率的である。
【発明を実施するための最良の形態】
【００１９】
以下、本発明を実施するための最良の形態について図面を参照して詳細に説明する。
【００２０】
図１は、有限体ＧＦ（２n）でｎが奇数であるときの、本発明による有限体の二乗演算装置のブロック図である。有限体の二乗演算装置は、係数計算部１０、ＸＯＲ演算部１２及び再配置部１４を備える。
係数計算部１０は、決定多項式の二乗演算に必要な係数を計算する。ＸＯＲ演算部１２は、係数計算部１０から出力される係数及び要素Ａに対してＸＯＲ演算を行う。再配置部１４は、ＸＯＲ演算部１２から出力される演算結果を再配置して、二乗演算の最終値として出力する。
【００２１】
前記構成による動作をさらに詳細に説明すれば、次の通りである。
有限体ＧＦ（２n）（ｎは奇数）の決定多項式を次の式５のように定義する。
【数４０】
2005010783.tif 000019
【００２２】
ある有限体の要素ＡをＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）とすれば、要素Ａの二乗は次の式６のように表現できる。
【数４１】
2005010783.tif 000020
【００２３】
二乗演算の結果であるＣもＧＦ（２n）に属する。
式５で、決定多項式ｆ（ｘ）は、ｘn＋１と
2005010783.tif 000021
の和で構成され、ｎ、ｔ、ｋiによって積算装置の面積複雑度及び時間複雑度が決定される。
【００２４】
Ｃに含まれる各要素を求めるために必要な係数ｍi、ｌij、ｌ、Ｖ0、Ｖij及びＶを次のように定義する。
各ｉ＝１,２,…,ｔに対してｋi＝１であれば、係数ｍi＝０とする。
整数ｒ≧２に対して、ｋiが次の式７を満足すれば、係数ｍi＝ｒと定義する。
【数４２】
2005010783.tif 000022
【００２５】
０でないｍi（ｉ＝１,２,…,ｔ）に対して係数ｌij（ｊ＝２,３,…,ｍi）を次の式８のように定義する。
【数４３】
2005010783.tif 000023
【００２６】
ｋiが偶数であれば、ｌは次の式９のように定義し、ｋiが偶数でなければ、ｌ＝０である。
【数４４】
2005010783.tif 000024
（ｅｖｅｎは偶数）
【００２７】
Ｖ0は、次の式１０のように定義される。
【数４５】
2005010783.tif 000025
【００２８】
それぞれ０でないｍiに対してＶij（ｊ＝２,３,…,ｍi）を定義する。当該ｉに対するｋiが奇数である場合またはｋiが偶数であり、ｊが奇数である場合には、Ｖijは次の式１１のように定義される。
【数４６】
2005010783.tif 000026
【００２９】
ｋi及びｊがいずれも偶数である場合、Ｖijは次の式１２の通りである。
【数４７】
2005010783.tif 000027
【００３０】
係数計算部１０は、係数から最終的にＶi及びＶに対する次の式１３のような計算結果を出力する。
【数４８】
2005010783.tif 000028
【００３１】
次いで、ｋi（ｉ＝１,２,…,ｔ）に対してｓiを次の式１４のように定義する。
【数４９】
2005010783.tif 000029
（以下、数式で、ｏｄｄは奇数、ｅｖｅｎは偶数）
【００３２】
式１４から得たｓ1ないしｓtのそれぞれに対してＶを循環置換し、それらの結果をＸＯＲ演算し、再び要素ＡとＸＯＲ演算する。その結果をＣ’とすれば、Ｃ’は次の式１５のように表現できる。
【数５０】
2005010783.tif 000030
【００３３】
式１５から得られる演算結果Ｃ’は、要素ＡのＸＯＲ演算式として表現される。ＸＯＲ演算部１２は、式１５によるＸＯＲ演算を行う。
式１５から得られるＣ’をＣ’＝ｃ0’ｃ1’…ｃn-1’とすれば、Ｃ’からＡ2＝ｃ0ｃ1…ｃn-1のｃiは、次の式１６の通りである。
【数５１】
2005010783.tif 000031
【００３４】
再配置部１４は、式１５から得られた結果を式１６によって再配置して、二乗演算の最終結果として出力する。
以上のように構成された二乗演算装置の面積複雑度及び時間複雑度を計算すれば、次の通りである。本発明の実施の形態に係る二乗演算装置には、ＸＯＲ演算を行う部分がある。そこで必要なＸＯＲ演算数は、次の式１７の通りである。
【数５２】
2005010783.tif 000032
【００３５】
式１７の“step３”は再配置によるものであるので、ＸＯＲ演算は不要である。特に、ｔ＝１である場合、すなわち決定多項式が三項式である場合、ｋ1が次の式１８を満足すれば、必要なＸＯＲ演算数は、次の式１９のように表現される。
【数５３】
2005010783.tif 000033
【００３６】
【数５４】
2005010783.tif 000034
【００３７】
本発明の二乗演算装置による時間複雑度を正確に記述するのは難しい。ただし、例えば、時間複雑度が最悪値になる場合を記述することはできる。本発明では、二乗演算装置がＸＯＲゲートを使用しているため、時間複雑度はＸＯＲゲートによる遅延で表現することができる。一般的な場合、ＸＯＲゲートによる遅延は最大で次の式２０のように決定される。
【数５５】
2005010783.tif 000035
【００３８】
特に、ｔ＝１であり、ｋ1が式１８を満足する場合、ＸＯＲゲートによる遅延は、次の式２１の通りである。
【数５６】
2005010783.tif 000036
【００３９】
ｎ＝１１である場合の、各係数及び複雑度の演算結果について説明する。決定多項式がＸ11＋Ｘ2＋１であるとき、ｔ＝１であり、ｋ1＝２である。ｎ、ｔ、ｋiから二乗演算に必要な係数が次のように決定される。式７ないし式１１によって、ｍ1＝２、ｌ12＝１、ｌ＝１、Ｖ0＝ａ6ａ7ａ8ａ9ａ10００００００、Ｖ12＝０００００ａ10０００００が決定され、決定された結果から式１３によって、Ｖ1＝０００００ａ10０００００、Ｖ＝ａ6ａ7ａ8ａ9ａ10ａ10０００００に決定される。
式１４によってｓ1＝７であり、式１５によってＣ’は、次の式２２のように決定される。
【数５７】
2005010783.tif 000037
【００４０】
Ｃ’に対して式１４による再配置を実行すれば、次の式２３のようなＡ2＝ｃ0ｃ1ｃ2…ｃ9ｃ10の結果を得る。
【数５８】
2005010783.tif 000038
【００４１】
図２は、式２３の結果を複数のＸＯＲ演算手段２１及び再配置手段２２で実現した二乗演算装置を示す図である。
図２に示すように、二乗演算装置は、面積複雑度の側面では６個のＸＯＲ演算手段からなり、時間複雑度の側面では１つのＸＯＲゲート遅延を有することが分かる。
【００４２】
本発明の他の実施例で、決定多項式がＸ11＋Ｘ4＋Ｘ2＋Ｘ＋１である場合を説明する。この決定多項式によれば、ｔ＝３、ｋ1＝１、ｋ2＝２、ｋ3＝４である。
ｔ、ｋ1、ｋ2、ｋ3から得られる係数は、次の式２４の通りである。
【数５９】
2005010783.tif 000039
【００４３】
式２４の係数からＶ2＝０００００ａ10０００００であり、Ｖ3＝０００００ａ9ａ10００００であり、Ｖは次の式２５のように決定される。
【数６０】
2005010783.tif 000040
【００４４】
式１４によって、ｓ1＝１、ｓ2＝７、ｓ3＝８が決定され、それにより、Ｃ’は次の式２６のように決定される。
【数６１】
2005010783.tif 000041
【００４５】
式１６によって再配置を行えば、Ｃは次の式２７のように求められる。
【数６２】
2005010783.tif 000042
【００４６】
図３は、式２７の結果を複数のＸＯＲ演算手段３１及び再配置手段３２で実現した二乗演算装置を示す図である。図４は、図３に示された二乗演算装置でＸＯＲ演算手段の数をさらに減らした結果を示す図である。例えば、式２７でｃ2に当る
2005010783.tif 000043
の場合、
2005010783.tif 000044
となるので、結果的に
2005010783.tif 000045
の演算だけが必要である。したがって、ＸＯＲ演算手段の数を減らせる。他の例として
2005010783.tif 000046
の場合、
2005010783.tif 000047
の計算で共通となる
2005010783.tif 000048
を再活用すれば、ｃ5の計算に使われるＸＯＲ演算手段を一つ減らせる。図４は、図３に示された二乗演算装置に対して以上のような方法により数を減らしたＸＯＲ演算手段４１を示している。
【００４７】
図５は、有限体ＧＦ（２n）でｎが偶数であるとき、本発明による有限体の二乗演算装置のブロック図を示す。有限体の二乗演算装置は、係数計算部５０、ＸＯＲ演算部５２及び再配置部５４を備える。
係数計算部５０は、決定多項式の二乗演算に必要な係数を計算する。ＸＯＲ演算部５２は、係数計算部５０から出力される係数に対して排他的論理和の演算を行う。再配置部５４は、ＸＯＲ演算部５２から出力される演算結果を再配置して、二乗演算の最終結果として出力する。
【００４８】
前記構成による動作をさらに詳細に説明すれば、次の通りである。
有限体ＧＦ（２n）（ｎは偶数）の決定多項式をｎが奇数であるときと同様に式５のように定義すれば、それに属する要素ＡがＡ＝（α0,α1,α2,・・・,αn-1）∈ＧＦ（２n）のように表現されるとき、Ａ2は式６のように表すことができる。式６で二乗演算の結果であるＣもＧＦ（２n）に属する。
Ｃに含まれる各要素を求めるために、必要な係数ｍi、ｌij、ｌ、Ｖ0、Ｖij及びＶを次のように定義する。
各ｉ＝１,２,…,ｔに対してｋi＝１であれば、係数ｍi＝１とする。
整数ｒ≧２に対して、ｋiが次の式２８を満足すれば、ｍi＝ｒと定義する。
【数６３】
2005010783.tif 000049
【００４９】
それぞれが１でないｍi（ｉ＝１,２,…,ｔ）に対してｌij（ｊ−＝２,３,…,ｍi）は、次の式２９のように定義する。
【数６４】
2005010783.tif 000050
【００５０】
Ｖ0は次の式３０のように定義される。
【数６５】
2005010783.tif 000051
【００５１】
それぞれの１でないｍi（ｉ＝１,２,…,ｔ）に対してＶij（ｊ＝２,３,…,ｍi）は、ｉに対するｋiが偶数である場合またはｋi、ｊがいずれも奇数である場合には、次の式３１のように定義される。
【数６６】
2005010783.tif 000052
【００５２】
ｋiが奇数であり、ｊが偶数である場合には、Ｖijは次の式３２のように定義される。
【数６７】
2005010783.tif 000053
【００５３】
係数計算部５０は、係数から最終的にＶi及びＶに対してｍiが１ではないとき、次の式３３のような計算結果を出力する。
【数６８】
2005010783.tif 000054
【００５４】
ｋi（ｉ＝１,２,…,ｔ）に対してｓiを次の式３４のように定義する。
【数６９】
2005010783.tif 000055
【００５５】
次いで、要素Ａに対する
2005010783.tif 000056
を次の式３５のように定義する。
【数７０】
2005010783.tif 000057
【００５６】
演算記号
2005010783.tif 000058
は、次の式３６のように定義される。
【数７１】
2005010783.tif 000059
【００５７】
式３４から得たｓ1ないしｓtに対して式３６のように定義されたようにＶを置換し、その結果を全てＸＯＲ演算し、再び式３５の
2005010783.tif 000060
とＸＯＲ演算する。その結果をＣ’とすれば、Ｃ’は次の式３７のように表現できる。
【数７２】
2005010783.tif 000061
【００５８】
式３７から得られる演算結果Ｃ’は、要素ＡのＸＯＲ演算式として表現される。ＸＯＲ演算部８２は、式３７によるＸＯＲ演算を行う。
式３７から得られるＣ’をＣ’＝ｃ0’ｃ1’…ｃn-1’とすれば、Ｃ’からＡ2＝ｃ0ｃ1…ｃn-1のｃiは次の式３８の通りである。
【数７３】
2005010783.tif 000062
【００５９】
再配置部５４は、式３７で得られた結果を式３８によって再配置して、二乗演算の最終結果として出力する。
【００６０】
本発明による実施例で、決定多項式がＸ10＋Ｘ4＋Ｘ3＋Ｘ＋１である場合について説明する。この決定多項式によれば、ｔ＝３であり、ｋ1＝１、ｋ2＝３、ｋ3＝４である。
ｔ、ｋ1、ｋ2、ｋ3から得られる係数は、次の式３９の通りである。
【数７４】
2005010783.tif 000063
【００６１】
式３３によって、Ｖ2、Ｖ3及びＶは次の式４０のように求められる。
【数７５】
2005010783.tif 000064
【００６２】
式３４によって、ｓ1＝５、ｓ2＝６、ｓ3＝２に決定され、これによりＣ’は式３５ないし式３７によって次の式４１のように決定される。
【数７６】
2005010783.tif 000065
【００６３】
式４１によって得られたＣ’を式４２によって再配置すれば、次の式４２のような二乗演算の結果を得る。
【数７７】
2005010783.tif 000066
【００６４】
図６は、式４２による演算結果を複数のＸＯＲ演算手段６１及び再配置手段６２によって実現した二乗演算装置を示す図である。二乗演算装置は、面積複雑度の側面で２５個のＸＯＲゲートからなり、時間複雑度の側面で４個のＸＯＲゲート遅延を有する。
【００６５】
図７ないし図９は、従来技術と本発明との差異点を表で要約したものである。図７で本発明の場合、面積複雑度及び時間複雑度に対して決定多項式が三項式、すなわちＸn＋Ｘk＋１（１≦ｋ≦ｎ／２）である場合を考慮した。図８は、ＳＥＣの標準で定義された３個の有限体で従来技術と本発明とによる面積複雑度及び時間複雑度を比較して表で表したものである。二乗演算装置の入力は標準表現によると仮定する。図９は、従来技術と本発明との標準適用可否と基底変換如何、そしてその問題点を比較して示したものである。二乗演算装置の入力は標準表現によると仮定する。
【００６６】
表によれば、時間複雑度及び面積複雑度の側面で、本発明は従来技術より優秀な場合もあり、類似した場合もあり、非効率的な場合もある。しかし、従来技術の場合より効率的な非特許文献２の発明が適用される次元は標準になく、決定多項式が標準と異なるので、互換性に問題がある。また、特許文献２の発明と非特許文献４とは複雑な基底変換を要求する。一般的に、基底変換は約ｎ2個のゲートで構成され、約ｌｏｇ2ｎのゲート遅延が要求される。効率的な基底変換方法がなければ、従来技術は本発明に比べて非効率的である。非特許文献１は適用される決定多項式が一部三項式に過ぎないので制限的である。
また、ｎが偶数である場合にも、本発明は標準に与えられた全ての場合に適用可能であるので、汎用性を満足する。
【産業上の利用可能性】
【００６７】
本発明である有限体の二乗演算方法及び二乗演算装置は、基底変換が不要であり、決定多項式が三項式または五項式である場合に適用可能であるので、従来技術より標準適用に有利である。
【図面の簡単な説明】
【００６８】
【図１】本発明の一実施例による有限体の二乗演算装置のブロック図である。
【図２】式２３の結果を複数のＸＯＲ演算手段及び再配置手段で実現した二乗演算装置を示す図である。
【図３】式２７の結果を複数のＸＯＲ演算手段及び再配置手段で実現した二乗演算装置を示す図である。
【図４】図３に示された二乗演算装置でＸＯＲ演算手段の数をさらに減らした結果を示す図である。
【図５】本発明の他の実施例による有限体の二乗演算装置のブロック図である。
【図６】式４２の結果を複数のＸＯＲ演算手段及び再配置手段で実現した二乗演算装置を示す図である。
【図７】従来技術及び本発明による二乗演算装置の面積及び時間複雑度を比較した表である。
【図８】ＳＥＣで定義された３個の有限体で従来技術及び本発明による二乗演算装置の面積及び時間複雑度を比較した表である。
【図９】従来技術及び本発明による二乗演算装置の標準適用可否、基底変換如何及びその問題点を比較した表である。
【符号の説明】
【００６９】
１０    係数計算部
１２    ＸＯＲ演算部
１４    再配置部
【図１】
2005010783.tif 000102
【図２】
2005010783.tif 000103
【図３】
2005010783.tif 000104
【図４】
2005010783.tif 000105
【図５】
2005010783.tif 000106
【図６】
2005010783.tif 000107
【図７】
2005010783.tif 000108
【図８】
2005010783.tif 000109
【図９】
2005010783.tif 000110