【手続補正書】
【提出日】平成17年9月27日(2005.9.27)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所定の有限体の有限次拡大体上で、線形写像による異なる種類の複数の演算を行う演算回路を構成する回路構成方法であって、
前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いる前記拡大体上の基底を決定する第１の工程と、
前記第１の工程で決定した前記基底を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の工程と
を有する回路構成方法。
【請求項２】
前記第１の工程において、前記複数の演算のそれぞれについて、当該演算を行う前記演算回路ブロックの小規模化および演算時間の短縮の少なくとも一方を図る観点から、前記基底を決定する
請求項１に記載の回路構成方法。
【請求項３】
前記第１の工程において、第１の前記演算で第１の前記基底を用いることを決定し、第２の前記演算で第２の前記基底を用いることを決定し、
前記第２の工程において、前記第２の演算が前記第１の演算の結果を用いる場合に、前記第１の演算を行う第１の前記演算回路ブロックの演算結果を、前記第１の基底から第２の基底に変換して前記第２の演算回路ブロックに出力する変換回路ブロックを有する前記演算回路を構成する
請求項１に記載の回路構成方法。
【請求項４】
前記有限次拡大体は、所定の有限体上のｍ（ｍは整数）次拡大体であり、次数ｍが、複数通りに因数分解できる場合に、
前記第１の工程において、
前記複数通りの因数分解のそれぞれについて、拡大タワーを生成し、
それぞれの前記拡大タワーについて、当該拡大タワーを構成する各拡大についての基底を要素とする第１の集合を生成し、
それぞれの前記拡大タワーについて、前記第１の集合の複数の要素を乗じて得られた基底を要素とする第２の集合を生成し、
複数の前記第２の集合のなかから、前記線形空間上の基底を決定する
請求項１に記載の回路構成方法。
【請求項５】
前記線形空間が、ｐを素数、ｑ＝ｐm とした場合の有限次拡大体Ｆq 上の下記（１−１）で示されるｍ次拡大体であり、
【数１】
2004133617.tif 000001
次数ｍが、下記（１−２）に示すように、ｌ通りに因数分解可能であり、
【数２】
2004133617.tif 000002
上記（１−２）内の符号は下記（１−３）の要件を満たし、下記（１−３）のＮは自然数であり、
【数３】
2004133617.tif 000003
前記有限次拡大体Ｆq から、それぞれｋi 回の拡大を行うことにより、下記（１−４）に示すｌ個の前記拡大タワーを生成し、
【数４】
2004133617.tif 000004
下記（１−５）で示される次数の拡大についての基底を要素とする下記（１−６）で示すｌ個の前記第１の集合を生成し、
各列を構成する基底は、下記（１−７）のように定義され、
【数５】
2004133617.tif 000005
【数６】
2004133617.tif 000006
【数７】
2004133617.tif 000007
上記（１−７）内のｄは、下記（１−８）のように定義され、
下記（１−８）において、「×」は、直積を示し、
下記（１−９）で示されるように、下記（１−８）のＺ／（ｎ）は、整数全体の集合Ｚのｎによる剰余群を示し、ｎは、自然数Ｎの要素であり、
【数８】
2004133617.tif 000008
【数９】
2004133617.tif 000009
前記演算回路が行う複数の演算のそれぞれについて、（１−１）で示されるｍ次拡大体の上記（１−６）から得られる下記（１−１０）で示されるｌ個の前記第２の集合のなかから、当該演算に用いるデータ表現形式である基底を選択（決定）し、
下記（１−１０）が示すｌ個の前記第２の集合の各々は、（１−６）で示される前記第１の集合の複数の要素を乗じて得られる基底を要素とし、
【数１０】
2004133617.tif 000010
上記（１−１０）における各ｄは、下記（１−１１）によって定義され、次数ｍは下記（１−１２）の関係を満たす
【数１１】
2004133617.tif 000011
【数１２】
2004133617.tif 000012
請求項４に記載の回路構成方法。
【請求項６】
それぞれの前記拡大タワーについて、各拡大の原始根を要素とする前記第１の集合を規定する
請求項４に記載の回路構成方法。
【請求項７】
所定の有限体の有限次拡大体上で、線形写像による異なる種類の複数の演算を行う演算回路を構成する回路構成装置であって、
前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いる前記拡大体上の基底を決定する第１の手段と、
前記第１の手段が決定した前記基底を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の手段と
を有する回路構成装置。
【請求項８】
前記第１の手段は、第１の前記演算で第１の基底を用いることを決定し、
第２の前記演算で第２の前記基底を用いることを決定し、
前記第２の手段は、前記第２の演算が前記第１の演算の結果を用いる場合に、前記第１の演算を行う第１の前記演算回路ブロックの演算結果を、前記第１の基底から第２の基底に変換して前記第２の演算回路ブロックに出力する変換回路ブロックを有する前記演算回路を構成する
請求項７に記載の回路構成装置。
【請求項９】
コンピュータによって実行され、所定の有限体の有限次拡大体上で、線形写像による異なる種類の複数の演算を行う演算回路を構成する手順を記述したプログラムであって、
前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いる前記拡大体上の基底を決定する第１の手順と、
前記第１の手順で決定した前記基底を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の手順と
を有するプログラム。
【請求項１０】
前記第１の手順は、第１の前記演算で第１の前記基底を用いることを決定し、
第２の前記演算で第２の前記基底を用いることを決定し、
前記第２の手順は、前記第２の演算が前記第１の演算の結果を用いる場合に、前記第１の演算を行う第１の前記演算回路ブロックの演算結果を、前記第１の基底から第２の基底に変換して前記第２の演算回路ブロックに出力する変換回路ブロックを有する前記演算回路を構成する
請求項９に記載のプログラム。
【請求項１１】
所定の有限体の有限次拡大体上で、線形写像による異なる種類の複数の演算を行う演算回路であって、
前記演算の種類に応じて規定された相互に異なる基底を用いて構成された複数の演算回路ブロック
を有する演算回路。
【請求項１２】
第１の前記基底を用いて構成された第１の前記演算回路ブロックの演算結果を、第２の演算回路ブロックが用いる第２の前記基底に変換して前記第２の演算回路ブロックに出力する変換回路ブロック
をさらに有する請求項１１記載の演算回路。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
【課題を解決するための手段】
上述した従来技術の問題点を解決し、上述した目的を達成するために、第１の発明の回路構成方法は、所定の有限体の有限次拡大体上で、線形写像による異なる種類の複数の演算を行う演算回路を構成する回路構成方法であって、前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いる前記拡大体上の基底を決定する第１の工程と、前記第１の工程で決定した前記基底を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の工程とを有する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
第２の発明の回路構成装置は、所定の有限体の有限次拡大体上で、線形写像による異なる種類の複数の演算を行う演算回路を構成する回路構成装置であって、前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いる前記拡大体上の基底を決定する第１の手段と、前記第１の手段が決定した前記基底を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の手段とを有する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
第３の発明のプログラムは、コンピュータによって実行され、所定の有限体の有限次拡大体上で、線形写像による異なる種類の複数の演算を行う演算回路を構成する手順を記述したプログラムであって、前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いる前記拡大体上の基底を決定する第１の手順と、前記第１の手順で決定した前記基底を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の手順とを有する。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
第４の発明の演算回路は、所定の有限体の有限次拡大体上で、線形写像による異なる種類の複数の演算を行う演算回路であって、前記演算の種類に応じて規定された相互に異なる基底を用いて構成された複数の演算回路ブロックを有する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】削除
【補正の内容】
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】削除
【補正の内容】
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】削除
【補正の内容】