JP2009301265A - 倍数判定方法、倍数判定装置および倍数判定プログラム - Google Patents

Abstract

【課題】 少ない計算量で高速に倍数判定を実施する。
【解決手段】 近似商算出処理（Ｓ１０）において、第１整数（Ａ）を第２整数（Ｎ）で割った場合の真の商に対する近似の商について、２のべき乗を第２整数で割った場合の商を用いて、真の商および近似の商の関係に基づく所定のビット数分の下位ビットの値が算出される。仮定商算出処理（Ｓ２０）において、第１整数は第２整数で割り切れると仮定した場合の商について、所定のビット数分の下位ビットの値が算出される。判定処理（Ｓ３０）において、近似商算出処理および仮定商算出処理の算出値の差が真の商および近似の商の関係に基づく所定の上限値より大きい場合に、第１整数は第２整数の倍数ではないと判定される。
【選択図】 図１

Description

本発明は、倍数判定方法、倍数判定装置および倍数判定プログラムに関する。

ある整数Ａが別の整数Ｎの倍数であるか否かを判定する倍数判定は、データ転送処理、暗号処理、信号処理、画像処理、画像圧縮／伸長処理やグラフィックス処理等で使用されている。例えば、ネットワークを介してＭＰＥＧ−２ＴＳ（Moving Picture Experts Group phase 2 Transport Stream）により動画像データや音声データを伝送するシステムでは、送信側で動画像データや音声データのエンコードにより生成されたＭＰＥＧ−２ＴＳが複数のパケット（バイト長：１８８）に分割して送信され、受信側で受信データのバイト長が１８８の倍数であるか否かの倍数判定を用いて伝送エラーの有無が検証される。また、暗号技術には、暗号化用の鍵および復号用の鍵が同一である共通鍵暗号方式と暗号化用の鍵および復号用の鍵が異なる公開鍵暗号方式とがあり、公開鍵暗号方式で鍵に用いられる素数を生成する際に倍数判定が使用される。

倍数判定の従来手法としては、整数Ａを整数Ｎで割った場合の剰余Ｒを除算により求めて剰余Ｒが０であるか否かを判定する手法が知られている。この手法では、回復法、非回復法やＳＲＴ法等の除算を用いることで、計算量を削減することが可能である。また、別の従来手法としては、モンゴメリ法等の剰余算を使用し、整数Ａを整数Ｎで割った場合の剰余Ｒを除算ではなく主に乗算により求めて剰余Ｒが０であるか否かを判定する手法が知られている。この手法では、除算が乗算に置き換えられることで、計算量が削減されるという利点がある。

なお、倍数判定回路に関しては、クロック周波数の高速化、入力信号等のビット数に対する回路規模の増大の抑制や演算時間の低減を実現するための技術が考案されている（例えば、特許文献１を参照）。また、除算装置に関しては、除数および被除数の特性に拘わらず高速に除算を実施するための技術が考案されている（例えば、特許文献２を参照）。モンゴメリ・リダクション装置に関しては、モンゴメリ・リダクションを少ない計算量で実現するための技術が考案されている（例えば、特許文献３を参照）。
特開平１０−３０７７０７号公報 特開平５−２５７６５０号公報 特開２０００−１０４７９号公報

倍数判定において、回復法、非回復法やＳＲＴ法等の除算を使用した従来手法では、加減算の回数を少なくすることはできるものの、除算を実施するため、非常に大きな多倍長数に関する倍数判定等にはある程度の計算量が必要になる。また、倍数判定において、モンゴメリ法等の剰余算を使用した従来手法では、剰余を効率的に求めることはできるが、計算量が十分に削減されるとは言い難い。

本発明は、このような問題に鑑みてなされたものであり、少ない計算量で高速に倍数判定を実施することを目的とする。

第１整数を第２整数で割った場合の真の商に対する近似の商について、２のべき乗を第２整数で割った場合の商を用いて、真の商および近似の商の関係に基づく所定のビット数分の下位ビットの値が算出される（近似商算出工程）。第１整数は第２整数で割り切れると仮定した場合の商について、所定のビット数分の下位ビットの値が算出される（仮定商算出工程）。近似商算出工程および仮定商算出工程の算出値の差が真の商および近似の商の関係に基づく所定の上限値より大きい場合に、第１整数は第２整数の倍数ではないと判定される（判定工程）。

近似商算出工程、仮定商算出工程および判定工程は除算や剰余算を使用することなく簡易な演算により実現されるため、少ない計算量で高速に倍数判定を実施することができる。

以下、本発明の実施形態について図面を用いて説明する。

図１は、本発明の一実施形態を示している。本発明の一実施形態において、倍数判定処理は、近似商算出処理（ステップＳ１０）、仮定商算出処理（ステップＳ２０）および判定処理（ステップＳ３０）を含んでいる。詳細については後述するが、近似商算出処理では、整数Ａを整数Ｎで割った場合の真の商Ｑｔに対する近似の商Ｑａについて、所定のビット数（整数Ａのビット数を２進表現した際のビット数以上）分の下位ビットの値が算出される。仮定商算出処理では、整数Ａは整数Ｎで割り切れると仮定した場合の商Ｑｐについて、所定のビット数分の下位ビットの値が算出される。判定処理では、仮定商算出処理および近似商算出処理の算出値の差が所定の上限値（整数Ａのビット数）より大きい場合に、整数Ａは整数Ｎの倍数ではないと判定される。

なお、整数Ａ、Ｎの双方が偶数である場合には、整数Ａ、Ｎを「２^ｋ×Ａ’」、「２^ｋ×Ｎ’」（Ａ’、Ｎ’の少なくとも一方は奇数）に置き換えることができ、整数Ａ’、Ｎ’に関する倍数判定の結果を整数Ａ、Ｎに関する倍数判定の結果として使用することができる。また、整数Ａが奇数であり整数Ｎが偶数である場合には、整数Ａ、Ｎの最下位ビットを参照するだけで、整数Ａは整数Ｎの倍数ではないと判定することができる。従って、ここでは、整数Ｎは奇数であるものとする。

図２は、倍数判定処理を具現するハードウェアの構成例を示している。図１の倍数判定処理（ステップＳ１０〜Ｓ３０）は、例えば、図２（ａ）、（ｂ）に示すようなハードウェア構成により具現される。図２（ａ）のハードウェア構成では、プログラムに従って各種処理を実施するＣＰＵ（Central Processing Unit）１１と、ＣＰＵ１１により実行される各種プログラム（倍数判定用プログラムを含む）やＣＰＵ１１により使用される各種データを格納するメモリ装置１２とが設けられており、ＣＰＵ１１により図１の倍数判定処理が実現される。図２（ｂ）のハードウェア構成では、プログラムに従って各種処理を実施するＣＰＵ２１と、ＣＰＵ２１により実行される各種プログラムやＣＰＵ２１により使用される各種データを格納するメモリ装置２２と、ＣＰＵ２１に代わって倍数判定処理を実施する倍数判定装置２３とが設けられており、倍数判定装置２３により図１の倍数判定処理が実現される。

図３は、ＭＰＥＧ−２ＴＳ伝送システムの一例を示している。図１の倍数判定処理（ステップＳ１０〜Ｓ３０）は、例えば、図３に示すようなＭＰＥＧ−２ＴＳ伝送システムにおいて使用される。ＭＰＥＧ−２ＴＳ伝送システム３０では、送信装置３１および受信装置３２がネットワーク３３を介して接続されている。送信装置３１においては、動画像データや音声データのエンコード処理によりＭＰＥＧ−２ＴＳが生成され、そのＭＰＥＧ−２ＴＳが複数のパケット（バイト長：１８８）に分割される。そして、複数のパケットをバッファリングして送信データが生成され、所望のタイミングでネットワーク３３に送信データが出力される。受信装置３２においては、ネットワーク３３を介して送信装置３１からデータを受信すると、受信データのバイト長および１８８に関する倍数判定（図１の倍数判定処理を使用）によるデータ長エラーチェックが実施され、その後、その他のエラーチェックが実施される。各種エラーチェックで伝送エラーが検出された場合には、受信データが破棄される。一方、各種エラーチェックで伝送エラーが検出されなかった場合には、続いて、ＭＰＥＧ−２ＴＳのデコード処理が実施される。

図４は、素数生成システムの一例を示している。図１の倍数判定処理（ステップＳ１０〜Ｓ３０）は、ＭＰＥＧ−２ＴＳ伝送システムだけでなく、例えば、図４に示すような素数生成システムにおいても使用される。素数生成システム４０は、乱数生成部４１、ふるい処理部４２（演算部４３およびメモリ部４４を具備）および素数判定部４５を有している。乱数生成部４１は、奇数をランダムに生成して素数候補としてふるい処理部４２に出力する。ふるい処理部４２において、演算部４３は、メモリ部４４に予め格納されている小さな素数（３、５、７、１１、１３、１７、１９、・・・）を読み出し、乱数生成部４１から出力された素数候補およびメモリ部４４から読み出された素数に関する倍数判定（図１の倍数判定処理を使用）を実施する。乱数生成部４１から出力された素数候補はメモリ部４４から読み出された素数の倍数ではないと判定されなかった場合、乱数生成部４１から出力された素数候補が合成数であるため、演算部４３は、乱数生成部４１に対して素数候補の再出力を要求する。一方、乱数生成部４１から出力された素数候補はメモリ部４４から読み出された素数の倍数ではないと判定された場合、演算部４３は、素数候補を素数判定部４５に出力する。素数判定部４５は、ふるい処理部４２（演算部４３）から出力された素数候補が素数であるか否かを判定する。ふるい処理部４２から出力された素数候補は素数ではないと判定された場合（ふるい処理部４２から出力された素数候補は合成数であると判定された場合）、素数判定部４５は、乱数生成部４１に対して素数候補の再出力を要求する。一方、ふるい処理部４２から出力された素数候補は素数ではないと判定されなかった場合、素数判定部４５は、素数候補を実用素数として出力する。

図５は、近似商算出処理の詳細を示している。図１の近似商算出処理（ステップＳ１０）では、例えば、図５に示すような処理フローにより、整数Ａを整数Ｎで割った場合の真の商Ｑｔに対する近似の商Ｑａの下位ｉビット（Ｑａ［ｉ−１：０］）の値が算出される。近似商算出処理では、まず、整数Ａ、整数Ａのビット数ａ、整数Ｎおよび商に関する算出ビット数ｉが入力される（ステップＳ１０１）。次に、変数ｊの値が０に設定されるとともに、変数Ｑａの全要素の値が０に設定される（ステップＳ１０２）。そして、変数ｊの値が入力値ａと一致するか否かが判定される（ステップＳ１０３）。ステップＳ１０３で変数ｊの値は入力値ａと一致しないと判定されると、入力値Ａ［ａ−ｊ−１］が１であるか否かが判定される（ステップＳ１０４）。ステップＳ１０４で入力値Ａ［ａ−ｊ−１］は１であると判定された場合には、変数Ｑａ［ｉ−１：０］の値に２の（ａ−ｊ−１）乗を整数Ｎで割った場合の商の下位ｉビットの値が足されて変数Ｑａ［ｉ−１：０］の値が更新される（ステップＳ１０５）。一方、ステップＳ１０４で入力値Ａ［ａ−ｊ−１］は１ではないと判定された場合には、変数Ｑａ［ｉ−１：０］の値は更新されない。そして、変数ｊの値がインクリメントされる（ステップＳ１０６）。この後、ステップＳ１０３で変数ｊの値が入力値ａと一致するか否かが再び判定される。即ち、ステップＳ１０３で変数ｊの値は入力値ａと一致すると判定されるまでステップＳ１０３〜Ｓ１０６が繰り返し実施される。ステップＳ１０３で変数ｊの値は入力値ａと一致すると判定されると、変数Ｑａの値が出力される（ステップＳ１０７）。

なお、２の（ａ−ｊ−１）乗を整数Ｎで割った場合の商は、２のａ乗を整数Ｎで割った場合の商Ｑｗに基づいて算出される。２の（ａ−１）乗を整数Ｎで割った場合の商は、商Ｑｗに対して１ビット分の右シフトを実施した結果（Ｑｗ＞＞１）である。また、２の（ａ−２）乗を整数Ｎで割った場合の商は、商Ｑｗに対して２ビット分の右シフトを実施した結果（Ｑｗ＞＞２）である。即ち、２の（ａ−ｐ）乗を整数Ｎで割った場合の商は、商Ｑｗに対してｐビット分の右シフトを実施した結果（Ｑｗ＞＞ｐ）である。これを利用して、２の（ａ−ｊ−１）乗を整数Ｎで割った場合の商が算出される。また、２のａ乗を整数Ｎで割った場合の商Ｑｗについては、メモリ等により予め保持していてもよいが、フェルマー／オイラーの定理に基づき、２のべき乗を整数Ｎで割った場合の商の値は整数Ｎに依存したべき乗値を境に巡回することを利用して、整数Ｎの条件に応じて容易に算出することができる。

図６は、２のべき乗を１１で割った場合の商および剰余の関係を示している。例えば、整数Ａのビット数ａおよび整数Ｎが１１であるときに２のａ乗を整数Ｎで割った場合の商Ｑｗを算出することを考える。２のべき乗を１１で割った場合の剰余および剰余の奇遇性は図６に示すようになり、２の１乗から２の１１乗までを１１で割った場合の剰余の奇遇性が２の１１乗を１１で割った場合の商Ｑｗ（１１’ｂ０００１０１１１０１０）に対応する。また、２のｍ乗を１１で割った場合の剰余と２の（ｍ＋１０）乗を１１で割った場合の剰余とは同一になる。従って、２の１１乗を１１で割った場合の商Ｑｗについては、２の０乗から２の９乗までを１１で割った場合の剰余の奇遇性に対応する値から容易に算出することができる。

このように、２のａ乗を整数Ｎで割った場合の商Ｑｗについては、２の０乗から２の（Ｎ−２）乗までを整数Ｎで割った場合の剰余の奇遇性に対応する値を予め保持していれば、ビットローテーション等を使用して容易に算出することができる。整数Ｎが小さい場合には、２の０乗から２の（Ｎ−２）乗までを整数Ｎで割った場合の剰余の奇遇性に対応する値をメモリにより予め保持しておき、その値に基づいて２のａ乗を整数Ｎで割った場合の商Ｑｗを算出することで、商Ｑｗをメモリにより予め保持する場合に比べてメモリ使用量を大幅に削減することが可能である。

図７は、仮定商算出処理の詳細を示している。図１の仮定商算出処理（ステップＳ２０）では、例えば、図７に示すような処理フローにより、整数Ａは整数Ｎで割り切れると仮定した場合の商Ｑｐの下位ｉビット（Ｑｐ［ｉ−１：０］）の値が算出される。仮定商算出処理では、まず、整数Ａ、整数Ｎおよび商に関する算出ビット数ｉが入力される（ステップＳ２０１）。次に、変数ｊの値が入力値ｉに設定されるとともに、変数Ａ’［２ｉ−１：０］の値が入力値Ａ［２ｉ−１：０］に設定される（ステップＳ２０２）。そして、変数ｊの値が０であるか否かが判定される（ステップＳ２０３）。ステップＳ２０３で変数ｊの値は０ではないと判定されると、変数Ａ’［０］の値が１であるか否かが判定される（ステップＳ２０４）。ステップＳ２０４で変数Ａ’［０］の値は１であると判定された場合には、変数Ｑｐ［ｉ−ｊ］の値が１に設定され（ステップＳ２０５）、その後、変数Ａ’［２ｉ−１：０］の値から入力値Ｎ［ｉ−１：０］が引かれて変数Ａ’［２ｉ−１：０］の値が更新される（ステップＳ２０６）。一方、ステップＳ２０４で変数Ａ’［０］の値は１ではないと判定された場合には、変数Ｑｐ［ｉ−ｊ］の値が０に設定される（ステップＳ２０７）。この後、変数Ａ’［２ｉ−１：０］の値に対して１ビット分の右シフトが実施されて変数Ａ’［２ｉ−１：０］の値が更新される（ステップＳ２０８）。そして、変数ｊの値がデクリメントされる（ステップ２０９）。この後、ステップＳ２０３で変数ｊの値が０であるか否かが再び判定される。即ち、ステップＳ２０３で変数ｊの値は０であると判定されるまでステップＳ２０３〜Ｓ２０９が繰り返し実施される。ステップＳ２０３で変数ｊの値は０であると判定されると、変数Ｑｐの値が出力される（ステップＳ２１０）。

図８は、判定処理の詳細を示している。図１の判定処理（ステップＳ３０）では、例えば、図８に示すような処理フローにより、整数Ａは整数Ｎの倍数ではないと言えるか否かが判定される。判定処理では、まず、近似商算出処理（図５）の出力値Ｑａ、仮定商算出処理（図７）の出力値Ｑｐ、整数Ａのビット数ａおよび商に関する算出ビット数ｉが入力される（ステップＳ３０１）。そして、入力値Ｑａ［ｉ−１：０］、Ｑｐ［ｉ−１：０］の差が入力値ａより大きいか否かが判定される（ステップＳ３０２）。ステップＳ３０２で入力値Ｑａ［ｉ−１：０］、Ｑｐ［ｉ−１：０］の差は入力値ａより大きいと判定された場合には、変数ｒの値が１に設定される（ステップＳ３０３）。一方、ステップＳ３０２で入力値Ｑａ［ｉ−１：０］、Ｑｐ［ｉ−１：０］の差は入力値ａより大きくないと判定された場合には、変数ｒの値が０に設定される（ステップＳ３０４）。そして、変数ｒの値が出力される（ステップＳ３０５）。

ここで、整数Ａを整数Ｎで割った場合の真の商Ｑｔおよび近似の商Ｑａの関係について説明する。整数Ａの２進表現が整数Ａのビット数ａおよび整数Ｎのビット数ｎを用いて（ｙ_ａ−１，ｙ_ａ−２，・・・，ｙ_ｎ，・・・，ｙ_１，ｙ_０）で表される場合、整数Ａは、「ｙ_ａ−１×２^ａ−１＋ｙ_ａ−２×２^ａ−２＋・・・＋ｙ_ｎ×２^ｎ＋・・・＋ｙ_１×２^１＋ｙ_０×２^０」に置き換えることができる。また、２の（ａ−ｐ）乗は、２のａ乗を整数Ｎで割った場合の商Ｑｗを用いて「（Ｑｗ＞＞ｐ）×Ｎ＋Ｒ_ａ−ｐ」に置き換えることができる。

真の商Ｑｔは、整数Ａの２進表現におけるビットｙ_ａ−ｐの値が１である場合に、商Ｑｗに対してｐビット分の右シフトを実施した結果を商の部分和に足し、更に、剰余Ｒ_ａ−ｐを剰余の部分和に足し、剰余の部分和が整数Ｎ以上になるのに伴って剰余の部分和から整数Ｎを引いて商の部分和に１を足すという処理を逐次的に実施することで最終的に得られる商の部分和である。これに対して、近似の商Ｑａは、整数Ａの２進表現におけるビットｙ_ａ−ｐの値が１である場合に、商Ｑｗに対してｐビット分の右シフトを実施した結果を商の部分和に足すという処理を逐次的に実施することで最終的に得られる商の部分和である。従って、真の商Ｑｔおよび近似の商Ｑａの差の最大値が整数Ａの２進表現において値が１であるビットの数になることは明らかである。これは、真の商Ｑｔおよび近似の商Ｑａの差が整数Ａのビット数ａより大きくならないことを意味する。別の言い方をすると、真の商Ｑｔと近似の商Ｑａとでは、整数Ａのビット数ａを２進表現した際のビット数ａ’分の下位ビットのみに関して異なっている可能性があるということである。

そこで、本発明の一実施形態の倍数判定処理では、整数Ａを整数Ｎで割った場合の真の商Ｑｔに対する近似の商Ｑａの下位（ａ’＋α）ビットの値と整数Ａは整数Ｎで割り切れると仮定した場合の商Ｑｐの下位（ａ’＋α）ビットの値との差が整数Ａのビット数ａより大きい場合に、整数Ａは整数Ｎの倍数ではないと判定される。なお、整数Ａを整数Ｎで割った場合の真の商Ｑｔと整数Ａは整数Ｎで割り切れると仮定した場合の商Ｑｐとの間には相関関係はないため、各αに対して、整数Ａが整数Ｎで割り切れないにも拘わらず、商Ｑａの下位（ａ’＋α）ビットの値と商Ｑｐの下位（ａ’＋α）ビットの値との差が整数Ａのビット数ａより大きくならない確率は、１／２である。

次に、整数Ａが１６７５（１１’ｂ１１０１０００１０１１）であり、整数Ｎが１１（４’ｂ１０１１）である場合の倍数判定について説明する。なお、実際に整数Ａを整数Ｎで割った場合、商は１５２であり、剰余は３である。整数Ａのビット数ａが１１であり、整数Ａのビット数ａを２進表現した際のビット数ａ’が４であるため、例えば、商に関する算出ビット数ｉを５とする。近似商算出処理においては、１６７５は「２^１０＋２^９＋２^７＋２^３＋２^１＋２^０」に置き換えられることから、２の１１乗を１１で割った場合の商Ｑｗ（１１’ｂ０００１０１１１０１０）を利用して、「Ｑｗ＞＞１」の下位５ビット、「Ｑｗ＞＞２」の下位５ビット、「Ｑｗ＞＞４」の下位５ビット、「Ｑｗ＞＞８」の下位５ビット、「Ｑｗ＞＞１０」の下位５ビットおよび「Ｑｗ＞＞１１」の下位５ビットの値が足されることにより、商Ｑａの下位５ビットの値が算出される。従って、商Ｑａの下位５ビットの値として２２（５’ｂ１０１１０）が算出される。仮定商算出処理においては、１６７５（１１’ｂ１１０１０００１０１１）の１ビット目の値が１であることから、商Ｑｐの１ビット目の値は１に決定され、これに伴って、１６７５（１１’ｂ１１０１０００１０１１）から１１（４’ｂ１０１１）を引いた値（１１’ｂ１１０１０００００００）が算出される。１６７５から１１を引いた値（１１’ｂ１１０１０００００００）の２ビット目、３ビット目、４ビット目および５ビット目の値はいずれも０であることから、商Ｑｐの２ビット目、３ビット目、４ビット目および５ビット目の値はいずれも０に決定される。従って、商Ｑｐの下位５ビットの値として１（５’ｂ００００１）が算出される。判定処理においては、商Ｑａの下位５ビットの値（２２）と商Ｑｐの下位５ビットの値（１）との差（２１）が１１より大きいことから、１６７５は１１の倍数ではないと判定される。

以上のような本発明の一実施形態の倍数判定処理においては、近似商算出処理は高々ａ回のｉビットの加算およびビットシフトにより実現され、仮定商算出処理はｉ回のｉビットの減算およびビットシフトにより実現され、判定処理は１回のｉビットの減算により実現される。例えば、整数Ａのビット数ａが１０２４であり、整数Ｎのビット数ｎが３２である場合、除算を使用した従来手法では、１０２４回の３２ビットの減算が必要であり、ＳＲＴ法の適用により演算回数が１／２に減少したとしても、５１２回の３２ビットの減算が必要である。また、整数Ｎのビット数ｎが３２から６４に増加すると、５１２回の６４ビットの減算が必要になる。これに対して、本発明の一実施形態の倍数判定処理では、整数Ａのビット数ａが１０２４であることから、商に関する算出ビット数ｉを１１とした場合、整数Ｎのビット数ｎに拘わらず、近似商算出処理は高々１０２４回の１１ビットの加算およびビットシフトにより実現され、仮定商算出処理は１１回の１１ビットの減算およびビットシフトにより実現され、判定処理は１回の１１ビットの減算により実現される。従って、従来手法に比べて、少ない計算量で高速に倍数判定が実施される。

図９は、倍数判定装置の一例を示している。図１の倍数判定処理を専用のハードウェア（例えば、図２（ｂ）の倍数判定装置２３）により実現する場合には、例えば、図９に示すような倍数判定装置が使用される。倍数判定装置５０は、近似商算出部５１、仮定商算出部５２および判定部５３を有している。なお、倍数判定装置５０においては、整数Ａのビット数ａおよび整数Ｎのビット数ｎが１０２４以下であり、商に関する算出ビット数ｉが３２以下であるものとしている。

近似商算出部５１は、外部入力信号ｓｔａｒｔ＿ｉｎ、ｄｉｖｉｄｅｎｄ＿ｉｎ［１０２３：０］、ｄｉｖｉｄｅｎｄ＿ｂｉｔ＿ｉｎ［１０：０］、ｒｏｔａｔｉｏｎ＿ｃｎｔ＿ｉｎ［１０：０］、ｍｏｄｅ＿ｉｎを受けて、信号ｑａ［３１：０］を出力する。仮定商算出部５２は、外部入力信号ｓｔａｒｔ＿ｉｎ、ｄｉｖｉｄｅｎｄ＿ｉｎ［６３：０］、ｄｉｖｉｓｏｒ＿ｉｎ［３１：０］、ｑｕｏｔｉｅｎｔ＿ｂｉｔ＿ｉｎ［５：０］を受けて、信号ｑｐ［３１：０］を出力する。判定部５３は、近似商算出部５１の出力信号ｑａ［３１：０］、仮定商算出部５２の出力信号ｑｐ［３１：０］および外部入力信号ｄｉｖｉｄｅｎｄ＿ｂｉｔ＿ｉｎ［１０：０］を受けて、外部出力信号ｒｅｓｕｌｔ＿ｏｕｔを出力する。

外部入力信号ｓｔａｒｔ＿ｉｎは、倍数判定装置５０の動作開始を指示するための信号である。外部入力信号ｓｔａｒｔ＿ｉｎは、倍数判定装置５０を動作開始させる際に基準クロック（図示せず）の１サイクル分の期間だけ“１”に設定され、その他の期間では“０”に設定される。外部入力信号ｄｉｖｉｄｅｎｄ＿ｉｎ［１０２３：０］は、整数Ａの２進表現（１０２４ビット）に対応する信号である。外部入力信号ｄｉｖｉｄｅｎｄ＿ｂｉｔ＿ｉｎ［１０：０］は、整数Ａのビット数ａの２進表現（１１ビット）に対応する信号である。外部入力信号ｄｉｖｉｓｏｒ＿ｉｎ［３１：０］は、整数Ｎの２進表現（１０２４ビット）の下位３２ビットに対応する信号である。外部入力信号ｑｕｏｔｉｅｎｔ＿ｂｉｔ＿ｉｎ［５：０］は、商に関する算出ビット数ｉの２進表現（６ビット）に対応する信号である。

外部入力信号ｒｏｔａｔｉｏｎ＿ｃｎｔ＿ｉｎ［１０：０］は、２の０乗から２の（Ｎ−２）乗までを整数Ｎで割った場合の剰余の奇遇性に対応する値（（Ｎ−１）ビット）に基づいて２の（ａ−１）乗を整数Ｎで割った場合の商の下位（Ｎ−１）ビットの値を算出するときの右ローテーションのビット数の２進表現（１１ビット）に対応する信号である。外部入力信号ｍｏｄｅ＿ｉｎは、２のべき乗を整数Ｎで割った場合の商の算出にビットローテーションを使用するか否かを指示するための信号である。外部入力信号ｍｏｄｅ＿ｉｎは、２のａ乗を整数Ｎで割った場合の商Ｑｗのビット数が３３以上であり、２のべき乗を整数Ｎで割った場合の商の算出にビットローテーションを使用する場合に“１”に設定され、２のａ乗を整数Ｎで割った場合の商Ｑｗのビット数が３２以下であり、２のべき乗を整数Ｎで割った場合の商の算出にビットローテーションを使用しない場合に“０”に設定される。

近似商算出部５１の出力信号ｑａ［３１：０］は、整数Ａを整数Ｎで割った場合の真の商Ｑｔに対する近似の商Ｑａの２進表現の下位３２ビットに対応する信号である。仮定商算出部５２の出力信号ｑｐ［３１：０］は、整数Ａは整数Ｎで割り切れると仮定した場合の商Ｑｐの２進表現の下位３２ビットに対応する信号である。外部出力信号（判定部５３の出力信号）ｒｅｓｕｌｔ＿ｏｕｔは、判定結果に対応する信号である。外部出力信号ｒｅｓｕｌｔ＿ｏｕｔは、整数Ａは整数Ｎの倍数ではないと判定された場合に“１”に設定され、整数Ａは整数Ｎの倍数ではないと判定されなかった場合に“０”に設定される。

図１０は、近似商算出部の詳細を示している。近似商算出部５１は、メモリ（ＭＥＭ）１０１、右ローテーション回路（ＲＯＲ）１０２、セレクタ１０３、１０５、１０７、１１０、１１３、１１４、右シフト回路（ＳＨＲ）１０４、レジスタ（ＲＥＧ）１０６、１０８、１１１、１１５、左シフト回路（ＳＨＬ）１０９、加算回路（ＡＤＤ）１１２、１１６および出力回路（ＯＵＴ）１１７を有している。

メモリ１０１は、予め格納された値（ｘビット）を示す信号ｑ＿ｐｏｗｅｒ＿ｉｎ［ｘ−１：０］を出力する。２のａ乗を整数Ｎで割った場合の商Ｑｗのビット数が３２以下である場合（整数Ｎが比較的大きい場合に相当）には、商Ｑｗの２進表現（３２ビット）がメモリ１０１に予め格納される。一方、商Ｑｗのビット数が３３以上である場合（整数Ｎが比較的小さい場合に相当）には、２の０乗から２の（Ｎ−２）乗までを整数Ｎで割った場合の剰余の奇遇性に対応する値（（Ｎ−１）ビット）がメモリ１０１に予め格納される。なお、２のａ乗を整数Ｎで割った場合の商Ｑｗを算出する回路をメモリ１０１の代わりに設けてもよい。

右ローテーション回路１０２は、倍数判定装置５０の動作開始後における基準クロックの１サイクル目では、メモリ１０１の出力信号ｑ＿ｐｏｗｅｒ＿ｉｎ［ｘ−１：０］（ｘ＝Ｎ−１）が示す値（ｘビット）に対して外部入力信号ｒｏｔａｔｉｏｎ＿ｃｎｔ＿ｉｎ［１０：０］が示す値に相当するビット数分の右ローテーションを実施することにより、２の（ａ−１）乗を整数Ｎで割った場合の商の下位（Ｎ−１）ビットの値を算出する。メモリ１０１の出力信号ｑ＿ｐｏｗｅｒ＿ｉｎ［ｘ−１：０］のビット数ｘが３２以上である場合、右ローテーション回路１０２は、算出値（ｘビット）を出力基準値として保持し、出力基準値の下位３２ビットに対応する信号を出力する。一方、メモリ１０１の出力信号ｑ＿ｐｏｗｅｒ＿ｉｎ［ｘ−１：０］のビット数ｘが３２未満である場合、右ローテーション回路１０２は、算出値（ｘビット）が複数個並んだ３２ビット以上の値を生成して出力基準値として保持し、出力基準値の下位３２ビットに対応する信号を出力する。

右ローテーション回路１０２は、倍数判定装置５０の動作開始後における基準クロックの２サイクル目、３サイクル目、・・・、（ａ−３３）サイクル目では、１サイクル前の出力基準値（３２ビット以上）に対して１ビット分の右ローテーションを実施して出力基準値を更新し、更新後の出力基準値の下位３２ビットに対応する信号を出力する。右ローテーション回路１０２は、倍数判定装置５０の動作開始後における基準クロックの（ａ−３２）サイクル目、（ａ−３１）サイクル目、・・・、ａサイクル目では、１サイクル前の出力基準値（３２ビット以上）に対して１ビット分の右ローテーションを実施することなく、１サイクル前の出力信号（３２ビット）に対して１ビット分の右シフトを実施して得られる信号を出力する。

例えば、整数Ａのビット数ａ（外部入力信号ｄｉｖｉｄｅｎｄ＿ｂｉｔ＿ｉｎ［１０：０］が示す値）が１０２４であり、整数Ｎ（外部入力信号ｄｉｖｉｓｏｒ＿ｉｎ［３１：０］が示す値）が１１である場合、外部入力信号ｒｏｔａｔｉｏｎ＿ｃｎｔ＿ｉｎ［１０：０］が示す値は６になる。また、メモリ１０１の出力信号ｑ＿ｐｏｗｅｒ＿ｉｎ［ｘ−１：０］（ｘ＝１０）は、１０’ｂ１０００１０１１１０に設定される。このような場合、基準クロックの１サイクル目では、右ローテーション回路１０２は、１０’ｂ１０００１０１１１０に対して６ビット分の右ローテーションを実施することにより、２の１０２３乗を１１で割った場合の商の下位１０ビットの値として１０ｂ’１０１１１０１０００を算出する。そして、右ローテーション回路１０２は、算出値のビット数（１０）が３２未満であるため、算出値が４個並んだ４０ビットの値（４０ｂ’１０１１１０１０００＿１０１１１０１０００＿１０１１１０１０００＿１０１１１０１０００）を生成して出力基準値として保持し、出力基準値の下位３２ビットに対応する信号を出力する。

基準クロックの２サイクル目では、右ローテーション回路１０２は、基準クロックの１サイクル目における出力基準値（４０ビット）に対して１ビット分の右ローテーションを実施して出力基準値を更新し、更新後の出力基準値（４０ｂ’０１０１１１０１００＿０１０１１１０１００＿０１０１１１０１００＿０１０１１１０１００）の下位３２ビットに対応する信号を出力する。基準クロックの３サイクル目、４サイクル目、・・・、（１０２４−３３）サイクル目では、右ローテーション回路１０２は、基準クロックの２サイクル目と同様に、１サイクル前の出力基準値（４０ビット）に対して１ビット分の右ローテーションを実施して出力基準値を更新し、更新後の出力基準値の下位３２ビットに対応する信号を出力する。基準クロックの（１０２４−３２）サイクル目、（１０２４−３１）サイクル目、・・・、１０２４サイクル目では、右ローテーション回路１０２は、１サイクル前の出力基準値（４０ビット）に対して１ビット分の右ローテーションを実施することなく、１サイクル前の出力信号（３２ビット）に対して１ビット分の右シフトを実施して得られる信号を出力する。

セレクタ１０３は、外部入力信号ｓｔａｒｔ＿ｉｎが“１”に設定されている場合、メモリ１０１の出力信号ｑ＿ｐｏｗｅｒ＿ｉｎ［ｘ−１：０］（ｘ＝３２）を選択して出力する。セレクタ１０３は、外部入力信号ｓｔａｒｔ＿ｉｎが“０”に設定されている場合、レジスタ１０６の出力信号ｑ＿ｐｏｗｅｒ［３１：０］を選択して出力する。右シフト回路１０４は、セレクタ１０３の出力信号（３２ビット）に対して１ビット分の右シフトを実施して得られる信号（３２ビット）を出力する。セレクタ１０５は、外部入力信号ｍｏｄｅ＿ｉｎが“１”に設定されている場合、右ローテーション回路１０２の出力信号（３２ビット）を選択して出力する。セレクタ１０５は、外部入力信号ｍｏｄｅ＿ｉｎが“０”に設定されている場合、右シフト回路１０４の出力信号（３２ビット）を選択して出力する。レジスタ１０６は、基準クロックに同期して、セレクタ１０５の出力信号（３２ビット）を取り込んで信号ｑ＿ｐｏｗｅｒ［３１：０］として出力する。

セレクタ１０７は、外部入力信号ｓｔａｒｔ＿ｉｎが“１”に設定されている場合、外部入力信号ｄｉｖｉｄｅｎｄ＿ｉｎ［１０２３：０］を選択して出力する。セレクタ１０７は、外部入力信号ｓｔａｒｔ＿ｉｎが“０”に設定されている場合、左シフト回路１０９の出力信号ｄｉｖｉｄｅｎｄ＿ｎｅｘｔ［１０２３：０］を選択して出力する。レジスタ１０８は、基準クロックに同期して、セレクタ１０７の出力信号（１０２４ビット）を取り込んで信号ｄｉｖｉｄｅｎｄ［１０２３：０］として出力する。左シフト回路１０９は、レジスタ１０８の出力信号ｄｉｖｉｄｅｎｄ［１０２３：０］に対して１ビット分の左シフトを実施して得られる信号ｄｉｖｉｄｅｎｄ＿ｎｅｘｔ［１０２３：０］を出力する。セレクタ１１０は、外部入力信号ｓｔａｒｔ＿ｉｎが“１”に設定されている場合、３２ｄ’０に設定された固定値信号を選択して出力する。セレクタ１１０は、外部入力信号ｓｔａｒｔ＿ｉｎが“０”に設定されている場合、セレクタ１１３の出力信号ｑａ＿ｔｍｐ＿ｎｅｘｔ［３１：０］を選択して出力する。レジスタ１１１は、基準クロックに同期して、セレクタ１１０の出力信号（３２ビット）を取り込んで信号ｑａ＿ｔｍｐ［３１：０］として出力する。加算回路１１２は、レジスタ１１１の出力信号ｑａ＿ｔｍｐ［３１：０］が示す値にレジスタ１０６の出力信号ｑ＿ｐｏｗｅｒ［３１：０］が示す値を足した結果を示す信号（３２ビット）を出力する。セレクタ１１３は、レジスタ１０８の出力信号ｄｉｖｉｄｅｎｄ［１０２３］が“１”に設定されている場合、加算回路１１２の出力信号（３２ビット）を選択して信号ｑａ＿ｔｍｐ＿ｎｅｘｔ［３１：０］として出力する。セレクタ１１３は、レジスタ１０８の出力信号ｄｉｖｉｄｅｎｄ［１０２３］が“０”に設定されている場合、レジスタ１１１の出力信号ｑａ＿ｔｍｐ［３１：０］を選択して信号ｑａ＿ｔｍｐ＿ｎｅｘｔ［３１：０］として出力する。

セレクタ１１４は、外部入力信号ｓｔａｒｔ＿ｉｎが“１”に設定されている場合、 １１’ｄ０に設定された固定値信号を選択して出力する。セレクタ１１４は、外部入力信号ｓｔａｒｔ＿ｉｎが“０”に設定されている場合、加算回路１１６の出力信号ｌｏｏｐ＿ｃｎｔ＿ｎｅｘｔ［１０：０］を選択して出力する。レジスタ１１５は、基準クロックに同期して、セレクタ１１４の出力信号（１１ビット）を取り込んで信号ｌｏｏｐ＿ｃｎｔ［１０：０］として出力する。加算回路１１６は、レジスタ１１５の出力信号ｌｏｏｐ＿ｃｎｔ［１０：０］が示す値に１（１１ビットの固定値信号が示す値）を足した結果を示す信号ｌｏｏｐ＿ｃｎｔ＿ｎｅｘｔ［１０：０］を出力する。出力回路１１７は、レジスタ１１５の出力信号ｌｏｏｐ＿ｃｎｔ［１０：０］が示す値が外部入力信号ｄｉｖｉｄｅｎｄ＿ｂｉｔ＿ｉｎ［１０：０］が示す値と一致するのに伴って、レジスタ１１１の出力信号ｑａ＿ｔｍｐ［３１：０］を取り込んで信号ｑａ［３１：０］として出力する。以上のような構成により、近似商算出部５１は、図１の近似商算出処理（図５の処理フロー）を実現するハードウェアとして機能する。

図１１は、仮定商算出部の詳細を示している。仮定商算出部５２は、セレクタ（ＳＥＬ）２０１、２０４、２０６、レジスタ（ＲＥＧ）２０２、２０７、減算回路（ＳＵＢ）２０３、２０８、右シフト回路（ＳＨＲ）２０５および出力回路（ＯＵＴ）２０９を有している。セレクタ２０１は、外部入力信号ｓｔａｒｔ＿ｉｎが“１”に設定されている場合、外部入力信号ｄｉｖｉｄｅｎｄ＿ｉｎ［６３：０］を選択して出力する。セレクタ２０１は、外部入力信号ｓｔａｒｔ＿ｉｎが“０”に設定されている場合、右シフト回路２０５の出力信号ｄｉｖｉｄｅｎｄ＿ｎｅｘｔ［６３：０］を選択して出力する。レジスタ２０２は、基準クロックに同期して、セレクタ２０１の出力信号（６４ビット）を取り込んで信号ｄｉｖｉｄｅｎｄ［６３：０］として出力する。減算回路２０３は、レジスタ２０２の出力信号ｄｉｖｉｄｅｎｄ［６３：０］が示す値から外部入力信号ｄｉｖｉｓｏｒ＿ｉｎ［３１：０］が示す値を引いた結果を示す信号（６４ビット）を出力する。セレクタ２０４は、レジスタ２０２の出力信号ｄｉｖｉｄｅｎｄ［０］が“１”に設定されている場合、減算回路２０３の出力信号（６４ビット）を選択して出力する。セレクタ２０４は、レジスタ２０２の出力信号ｄｉｖｉｄｅｎｄ［０］が“０”に設定されている場合、レジスタ２０２の出力信号ｄｉｖｉｄｅｎｄ［６３：０］を選択して出力する。右シフト回路２０５は、セレクタ２０４の出力信号（６４ビット）に対して１ビット分の右シフトを実施して得られる信号ｄｉｖｉｄｅｎｄ＿ｎｅｘｔ［６３：０］を出力する。

セレクタ２０６は、外部入力信号ｓｔａｒｔ＿ｉｎが“１”に設定されている場合、外部入力信号ｑｕｏｔｉｅｎｔ＿ｂｉｔ＿ｉｎ［５：０］を選択して出力する。セレクタ２０６は、外部入力信号ｓｔａｒｔ＿ｉｎが“０”に設定されている場合、減算回路２０８の出力信号ｌｏｏｐ＿ｃｎｔ＿ｎｅｘｔ［５：０］を選択して出力する。レジスタ２０７は、基準クロックに同期して、セレクタ２０６の出力信号（６ビット）を取り込んで信号ｌｏｏｐ＿ｃｎｔ［５：０］として出力する。減算回路２０８は、レジスタ２０７の出力信号ｌｏｏｐ＿ｃｎｔ［５：０］が示す値から１（６ビットの固定値信号が示す値）を引いた結果を示す信号ｌｏｏｐ＿ｃｎｔ＿ｎｅｘｔ［５：０］を出力する。出力回路２０９は、基準クロックに同期して、３２ビットの内部レジスタに対して最下位ビットから順番にレジスタ２０２の出力信号ｄｉｖｉｄｅｎｄ［０］の値を格納する。出力回路２０９は、レジスタ２０７の出力信号ｌｏｏｐ＿ｃｎｔ［５：０］が６’ｄ０に設定されるのに伴って、内部レジスタの値（３２ビット）を示す信号ｑｐ［３１：０］を出力する。以上のような構成により、仮定商算出部５２は、図１の仮定商算出処理（図７の処理フロー）を実現するハードウェアとして機能する。

図１２、判定部の詳細を示している。判定部５３は、比較回路（ＣＭＰ）３０１、３０３および減算回路（ＳＵＢ）３０２を有している。比較回路３０１は、近似商算出部５１（図１０）の出力信号ｑａ［３１：０］が示す値が仮定商算出部５２（図１１）の出力信号ｑｐ［３１：０］が示す値以上である場合、出力信号を“１”に設定する。比較回路３０１は、近似商算出部５１の出力信号ｑａ［３１：０］が示す値が仮定商算出部５２の出力信号ｑｐ［３１：０］が示す値未満である場合、出力信号を“０”に設定する。減算回路３０２は、比較回路３０１の出力信号が“１”に設定されている場合、近似商算出部５１の出力信号ｑａ［３１：０］が示す値から仮定商算出部５２の出力信号ｑｐ［３１：０］が示す値を引いた結果を示す信号ｄｆ［３１：０］を出力する。減算回路３０２は、比較回路３０１の出力信号が“０”に設定されている場合、仮定商算出部５２の出力信号ｑｐ［３１：０］が示す値から近似商算出部５１の出力信号ｑａ［３１：０］が示す値を引いた結果を示す信号ｄｆ［３１：０］を出力する。比較回路３０３は、減算回路３０２の出力信号ｄｆ［３１：０］が示す値が外部入力信号ｄｉｖｉｄｅｎｄ＿ｂｉｔ＿ｉｎ［１０：０］が示す値より大きい場合、外部出力信号ｒｅｓｕｌｔ＿ｏｕｔを“１”に設定する。比較回路３０３は、減算回路３０２の出力信号ｄｆ［３１：０］が示す値が外部入力信号ｄｉｖｉｄｅｎｄ＿ｂｉｔ＿ｉｎ［１０：０］が示す値以下である場合、外部出力信号ｒｅｓｕｌｔ＿ｏｕｔを“０”に設定する。以上のような構成により、判定部５３は、図１の判定処理（図８の処理フロー）を実現するハードウェアとして機能する。

以上のように、本発明の一実施形態においては、近似商算出処理（ステップＳ１０）、仮定商算出処理（ステップＳ２０）および判定処理（ステップＳ３０）は除算や剰余算を使用することなく簡易な演算により実現されるため、少ない計算量で高速に倍数判定を実施することができる。なお、前述の実施形態では、整数Ａのビット数ａを商Ｑａ、Ｑｐの差の比較対象（所定の上限値）として使用し、整数Ａのビット数ａを２進表現した際のビット数ａ’以上の値を商に関する算出ビット数ｉ（所定のビット数）として使用しているが、商Ｑｔ、Ｑａの差の最大値を商Ｑａ、Ｑｐの差の比較対象として使用し、商Ｑｔ、Ｑａの差の最大値を２進表現した際のビット数以上の値を商に関する算出ビット数ｉとして使用してもよい。これにより、倍数判定の精度を向上させることが可能である。

以上、本発明について詳細に説明してきたが、前述の実施形態およびその変形例は発明の一例に過ぎず、本発明はこれらに限定されるものではない。本発明を逸脱しない範囲で変形可能であることは明らかである。

本発明の一実施形態を示す図である。 倍数判定処理を具現するハードウェアの構成例を示す図である。 ＭＰＥＧ−２ＴＳ伝送システムの一例を示す図である。 素数生成システムの一例を示す図である。 近似商算出処理の詳細を示す図である。 ２のべき乗を１１で割った場合の商および剰余の関係を示す図である。 仮定商算出処理の詳細を示す図である。 判定処理の詳細を示す図である。 倍数判定装置の一例を示す図である。 近似商算出部の詳細を示す図である。 仮定商算出部の詳細を示す図である。 判定部の詳細を示す図である。

符号の説明

５０‥倍数判定装置；５１‥近似商算出部；５２‥仮定商算出部；５３‥判定部；１０１‥メモリ；１０２‥右ローテーション回路；１０３、１０５、１０７、１１０、１１３、１１４‥セレクタ；１０４‥右シフト回路；１０６、１０８、１１１、１１５‥レジスタ；１０９‥左シフト回路；１１２、１１６‥加算回路；１１７‥出力回路；２０１、２０４、２０６‥セレクタ；２０２、２０７‥レジスタ；２０３、２０８‥減算回路；２０５‥右シフト回路；２０９‥出力回路；３０１、３０３‥比較回路；３０２‥減算回路

Claims (5)

1. 第１整数を第２整数で割った場合の真の商に対する近似の商について、２のべき乗を前記第２整数で割った場合の商を用いて、前記真の商および前記近似の商の関係に基づく所定のビット数分の下位ビットの値を算出する近似商算出工程と、
   前記第１整数は前記第２整数で割り切れると仮定した場合の商について、前記所定のビット数分の下位ビットの値を算出する仮定商算出工程と、
   前記近似商算出工程および前記仮定商算出工程の算出値の差が前記真の商および前記近似の商の前記関係に基づく所定の上限値より大きい場合に、前記第１整数は前記第２整数の倍数ではないと判定する判定工程とを含むことを特徴とする倍数判定方法。
2. 請求項１に記載の倍数判定方法において、
   前記所定の上限値は、前記第１整数のビット数であり、
   前記所定のビット数は、前記第１整数のビット数を２進表現した際のビット数以上であることを特徴とする倍数判定方法。
3. 請求項１に記載の倍数判定方法において、
   前記所定の上限値は、前記真の商および前記近似の商の差の最大値であり、
   前記所定のビット数は、前記真の商および前記近似の商の差の最大値を２進表現した際のビット数以上であることを特徴とする倍数判定方法。
4. 第１整数を第２整数で割った場合の真の商に対する近似の商について、２のべき乗を前記第２整数で割った場合の商を用いて、前記真の商および前記近似の商の関係に基づく所定のビット数分の下位ビットの値を算出する近似商算出部と、
   前記第１整数は前記第２整数で割り切れると仮定した場合の商について、前記所定のビット数分の下位ビットの値を算出する仮定商算出部と、
   前記近似商算出部および前記仮定商算出部の算出値の差が前記真の商および前記近似の商の前記関係に基づく所定の上限値より大きい場合に、前記第１整数は前記第２整数の倍数ではないと判定する判定部とを備えることを特徴とする倍数判定装置。
5. 第１整数を第２整数で割った場合の真の商に対する近似の商について、２のべき乗を前記第２整数で割った場合の商を用いて、前記真の商および前記近似の商の関係に基づく所定のビット数分の下位ビットの値を算出する近似商算出工程と、
   前記第１整数は前記第２整数で割り切れると仮定した場合の商について、前記所定のビット数分の下位ビットの値を算出する仮定商算出工程と、
   前記近似商算出工程および前記仮定商算出工程の算出値の差が前記真の商および前記近似の商の前記関係に基づく所定の上限値より大きい場合に、前記第１整数は前記第２整数の倍数ではないと判定する判定工程とをコンピュータに実行させることを特徴とする倍数判定プログラム。

Images