記憶位置抽出装置および記憶位置抽出方法
【課題】共通部分抽出に必要となる処理の並列化を可能とし、処理全体の効率化を図って処理時間を高速化することを課題とする。
【解決手段】共通アドレス抽出装置１０は、各バイトに対して篩処理一回目のログ加算処理を実施し、一回目のログ加算処理が終了した後の各バイトの値に対して、条件を満足するバイトのアドレスに付属するパリティビットをオンとする。続いて、共通アドレス抽出装置１０は、パリティビットの値を保持した状態のまま、各バイトに対して篩処理二回目のログ加算処理を実施する。そして、共通アドレス抽出装置１０は、二回目の篩処理が終了した後のバイトが保持する値それぞれに対して、条件を満足しないバイトのアドレスに付属するパリティビットをオフとする。その後、共通アドレス抽出装置１０は、対応するパリティビットの値が１であるバイトのアドレスを、条件を満足するメモリアドレスの共通部分として、抽出する。
【解決手段】共通アドレス抽出装置１０は、各バイトに対して篩処理一回目のログ加算処理を実施し、一回目のログ加算処理が終了した後の各バイトの値に対して、条件を満足するバイトのアドレスに付属するパリティビットをオンとする。続いて、共通アドレス抽出装置１０は、パリティビットの値を保持した状態のまま、各バイトに対して篩処理二回目のログ加算処理を実施する。そして、共通アドレス抽出装置１０は、二回目の篩処理が終了した後のバイトが保持する値それぞれに対して、条件を満足しないバイトのアドレスに付属するパリティビットをオフとする。その後、共通アドレス抽出装置１０は、対応するパリティビットの値が１であるバイトのアドレスを、条件を満足するメモリアドレスの共通部分として、抽出する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出装置および記憶位置抽出方法に関する。
【背景技術】
【０００２】
近年、インターネット等の広がりにより、決済や個人認証を、ネットワークを通じて電子的に行う必要性が増しているが、その情報セキュリティを保持するための基盤技術の一つとしてＲＳＡ暗号が用いられている。このＲＳＡ暗号の安全性は素因数分解問題の困難性に基づいており、この暗号を安全に利用するためには、ＲＳＡ暗号の安全性評価を精密に行い、その実装パラメータが適切に設定されているかを評価することが重要となっている。
【０００３】
このような評価のためには、現在知られている最も効率的な素因数分解アルゴリズムがどのくらいの計算量で実施できるのかを図る必要があり、素因数分解アルゴリズムをソフトウェアの面だけでなく、専用ハードウェアによる評価が欠かせない。
【０００４】
例えば、ＲＳＡ暗号の安全性を評価するうえで重要となる素因数分解アルゴリズムの中で、現時点で最も効率的な手法として知られている方法は一般数体篩法である。具体的に、一般数体篩法は、多項式選択ステップ、関係式探索ステップ、行列計算ステップおよび平方根計算ステップの四つのステップから構成される（非特許文献１参照）。
【０００５】
この一般数体篩法に必要な計算量として、上記のステップの中で最も本質的な部分は関係式探索ステップである。この関係式探索ステップは、さらに篩処理部と関係式検査部の２種類の処理から構成されているが、中でも篩処理が計算量の上で本質的であることが知られている。
【０００６】
この篩処理とは、メモリを初期化する操作ならびにログ加算と閾値判定を合わせた処理のことをいう。このログ加算処理では、各々１バイト（８ビット）のデータ容量を持つメモリ空間を準備し、用意された多数の素数各々について、一定の条件を満たすアドレスのデータに対して、素数の対数値を加算する処理を行う。また、閾値判定処理では、全ての素数に対しログ加算処理が行われたあと、あらかじめ決められた閾値以上となるメモリデータのアドレスを抽出する処理が行われる（特許文献１参照）。そして、この篩処理を複数回を実施する度毎に各々抽出されたメモリアドレスの共通部分を求める処理も重要であり、併せて効率的に実施される必要がある。
【０００７】
従来より、メモリアドレスの共通部分を求める手法としては、この共通部分を求める際に、複数の篩処理それぞれについて抽出されたアドレスを一旦外部記憶装置に蓄え、それらのデータを突き合わせることで、共通部分を求める方法が知られている。
【０００８】
具体的に説明すると、図９に示すように、一回目の篩処理が終了した後の各バイトの値に対して、閾値「６」以上であるかを判定し、閾値「６」以上の値を保持するバイトのアドレス「１」、「５」を装置外部のバッファに転送し、バッファに保持される。続いて、二回目の篩処理が終了した後に同様の処理を行って、閾値「６」以上の値を保持するバイトのアドレス「３」、「５」を転送し、同じくバッファに保持される。そして、各々のバッファに保持された結果から、共通部分「５」を抽出する。ここで、ハードウェアからバッファへデータ転送する処理およびバッファに保持された共通部分を抽出する処理は逐次処理となる。
【０００９】
【特許文献１】特開２００７−１８８２６３号公報
【非特許文献１】伊豆哲也、木田祐司「素因数分解の現状について」日本応用数理学会論文誌、Vol.13, No.2(20030625) pp. 289-303, 2003.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ところで、上記したバッファへのデータ転送を行ってメモリアドレスの共通部分を抽出する技術では、共通部分を抽出する際に、通常外部記憶装置への出力バスは単一であるため、篩処理結果を抽出する際、ならびに共通部分を抽出する際において、いずれも並列化が困難であるため、逐次処理によるデータ転送時間の増加や、処理時間の増加等の問題が発生し、処理全体の効率が低下するという課題があった。
【００１１】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、共通部分抽出に必要となる処理の並列化を可能とし、処理全体の効率化を図って処理時間を高速化することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するため、本発明は、複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出装置であって、前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶する記憶手段と、各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更手段と、前記変更手段により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出手段と、を備えたことを特徴とする。
【００１３】
また、本発明は、上記の発明において、初回の演算における演算結果のうち、前記所定の条件に満足する演算結果の演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、前記変更手段は、初回以後の演算において、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更することを特徴とする。
【００１４】
また、本発明は、上記の発明において、演算開始時点において、全ての演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、前記変更手段は、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更することを特徴とする。
【００１５】
また、本発明は、複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出方法であって、前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶する記憶工程と、各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更工程と、前記変更工程により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出工程と、を含んだことを特徴とする。
【発明の効果】
【００１６】
本発明によれば、演算装置内部にパリティビットをアドレス毎に準備し、本パリティビットを用いて抽出アドレス情報を処理することにより、共通部分抽出に必要となる処理の並列化を可能とし、処理全体の効率化を図って処理時間を高速化することが可能である。
【発明を実施するための最良の形態】
【００１７】
以下に添付図面を参照して、この発明に係る記憶位置抽出装置および記憶位置抽出方法の実施例を詳細に説明する。
【実施例１】
【００１８】
以下の実施例では、実施例１に係る共通アドレス抽出装置の概要および特徴、共通アドレス抽出装置の構成および処理の流れを順に説明し、最後に実施例１による効果を説明する。
【００１９】
［実施例１に係る共通アドレス抽出装置の概要および特徴］
まず最初に、図１を用いて、実施例１に係る共通アドレス抽出装置の概要および特徴を説明する。図１は、実施例１に係る共通アドレス抽出装置の概要および特徴を説明するための図である。
【００２０】
実施例１の共通アドレス抽出装置１０では、複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果のメモリアドレスを抽出することを概要とする。そして、この共通アドレス抽出装置１０では、処理全体の効率化を図って処理を高速化する点に主たる特徴がある。
【００２１】
この主たる特徴について具体的に説明すると、共通アドレス抽出装置１０は、アドレスごとのログ加算処理結果を記憶する１バイトの記憶領域と、ログ加算処理結果が選択条件に適合するか否かを示すフラグをアドレスごとに記憶する１ビットの記憶領域（パリティビット）とを対応付けて記憶するメモリを有する。
【００２２】
このような構成のもと、共通アドレス抽出装置１０は、各バイトに対して篩処理一回目のログ加算処理を実施する（図１の（１）参照）。そして、共通アドレス抽出装置１０は、一回目のログ加算処理が終了した後の各バイトの値に対して、条件を満足するバイトのアドレスに付属するパリティビットをオンとする（図１の（２）参照）。具体的には、共通アドレス抽出装置１０は、一回目のログ加算処理が終了した後にバイトが保持する値それぞれに対して、閾値以上であるか判定し、その結果、閾値以上の値を保持するバイトのアドレスのパリティビットを「１」とする。
【００２３】
続いて、共通アドレス抽出装置１０は、パリティビットの値を保持した状態のまま、各バイトに対して篩処理二回目のログ加算処理を実施する（図１の（３）参照）。そして、共通アドレス抽出装置１０は、二回目の篩処理が終了した後のバイトが保持する値それぞれに対して、条件を満足しないバイトのアドレスに付属するパリティビットをオフとする（図１の（４）参照）。具体的には、共通アドレス抽出装置１０は、二回目の篩処理が終了した後にバイトが保持する値それぞれに対して、閾値未満の値であるかを判定し、その結果、閾値未満の値を保持するバイトのアドレスのパリティビットを０とする。
【００２４】
その後、共通アドレス抽出装置１０は、対応するパリティビットの値が１であるバイトのアドレスを、条件を満足するメモリアドレスの共通部分として、抽出して格納する（図１の（５）参照）。なお、上記では、篩処理を二回実行して共通部分を抽出する場合を説明するが、篩処理を二回以上実行して共通部分を抽出するようにしてもよい。
【００２５】
このように、共通アドレス抽出装置１０は、共通部分抽出に必要となる処理の並列化を可能とする結果、上記した主たる特徴のごとく、処理全体の効率化を図って処理を高速化することが可能である。
【００２６】
［共通アドレス抽出装置１０の構成］
次に、図２を用いて、図１に示した共通アドレス抽出装置１０の構成を説明する。図２は、実施例１に係る共通アドレス抽出装置１０の構成を示すブロック図である。なお、以下では、ＦＰＧＡに共通アドレス抽出装置を適用した場合として説明する。
【００２７】
同図に示すように、この共通アドレス抽出装置１０は、演算部１１ａ〜１１ｎ、メモリ１２ａ〜１２ｎ、制御部１３を備え、因子基底データベース２０ａ、２０ｂとそれぞれ接続される。演算部１１ａ〜１１ｎには、メモリ１２ａ〜１２ｎがそれぞれ割当てられている。以下にこれらの各部の処理を説明する。
【００２８】
因子基底データベース２０ａ、２０ｂは、３つ組の自然数（ｐ、ｓ、ｌｏｇ）である因子基底の集合を記憶する。この因子基底とは、ｐが素数であり、ｓが０以上ｐ未満の自然数、ｌｏｇがｐの対数値ｌｏｇ２（ｐ）の小数点以下を切り上げた自然数である。因子基底データベース２０ａ、２０ｂでは、それぞれ異なる因子基底の集合が記憶され、因子基底データベース２０ａに格納された因子基底（ｐ、ｓ、ｌｏｇ）は、一回目の篩処理で用いられ、因子基底データベース２０ｂに格納された因子基底（ｐ、ｓ、ｌｏｇ）は、二回目の篩処理で用いられるものとする。なお、因子基底データベース２０ａ、２０ｂそれぞれは、因子基底の総数として、約５０００万個程度を記憶する。
【００２９】
演算部１１は、因子基底データベース２０から因子基底を読み出して、因子基底を用いてログ加算処理を行う。図３の例を用いて具体的に説明すると、まず、演算部１１ａは、各バイトの値を０に初期化し、因子基底データベース２０から（ｐ、ｓ、ｌｏｇ）を読み出す。そして、演算部１１ａは、ｓ＜Ｓであるか否か判定し（つまり、ｓの値がメモリサイズをはみ出すか否かを判定し）、ｓ＜Ｓである場合には、メモリ空間におけるバイト位置ｓのメモリ値を読み出し、その値にｌｏｇの値を加算し、その値を同じバイト位置に書き戻す。
【００３０】
そして、演算部１１ａは、ｓ＋ｐを改めてｓとし、メモリ１２ａのメモリサイズをはみ出すまで（つまり、ｓ＋ｐの値がＳ以上となるまで）、上記の処理を繰り返す。そして、演算部１１ａは、メモリサイズをはみ出した場合には、ｓ−Ｓを改めてｓとし、（ｐ、ｓ、ｌｏｇ）を演算部１１ｂに引き渡す。その後、全ての演算部１１ａ〜１１ｎが上記の処理を行うと、最後の演算部１１ｎは、一回目の篩処理を終了した旨（または、一回目以降の篩処理が終了した旨）を後述する閾値判定部１３ａに通知する。
【００３１】
ここで、図４を用いてログ加算処理の計算例について説明する。図４の例では、因子基底データベース２０に因子基底（ｐ、ｓ、ｌｏｇ）として、（３，０，２）、（５，０，３）、（７，４，３）,（１１，４，４），（１３，６，４），（１７，３，５），（１９，２，５）が記憶されている場合に、演算部１１ａは、その因子基底を順番に読み出して、ログ加算処理を行い、全ての因子基底を用いて行ったログ加算処理結果の合計をメモリ１２に記憶させる。つまり、図４の例では、ログ加算処理結果の合計として、アドレス０〜６には、それぞれ「５」、「０」、「５」、「７」、「７」、「３」、「６」が記憶されている。その後、後述する制御部１３が、ログ加算処理が終了した後にバイトが保持する値それぞれに対して、閾値「６」以上であるか判定し、その結果、閾値「６」以上の値を保持するバイトのアドレスであるアドレス「３」、「４」、「６」のパリティビットを１とする。
【００３２】
メモリ１２ａ〜１２ｎは、メモリ空間としてＳ＝２１９バイトをトータルで有し、アドレスごとのログ加算処理結果を記憶するデータ容量として１バイトの記憶領域と、ログ加算処理結果が選択条件に適合するか否かを示すフラグをアドレスごとに記憶する１ビットのパリティビットを有する。
【００３３】
制御部１３は、閾値判定部１３ａと共通アドレス抽出部１３ｂとを備える。この閾値判定部１３ａは、一回目の篩処理が終了した後の各メモリ１２ａ〜１２ｎのバイトの値に対して、閾値以上であるかを判定し、閾値以上であるバイトのアドレスに付属するパリティビットをオンとする。また、一回目の篩処理以後では、篩処理が終了した後の各バイトの値に対して、閾値未満であるかを判定し、閾値未満であるバイトのアドレスに付属するパリティビットをオフとする。
【００３４】
具体的には、閾値判定部１３ａは、演算部１１ｎから一回目の篩処理が終了した旨の通知を受け付けると、篩処理が終了した後の各バイトの値に対して、閾値以上であるか判定し、その結果、閾値判定部１３ａは、閾値以上の値を保持するバイトのアドレスのパリティビットを１とする。また、共通アドレス抽出装置１０は、演算部１１ｎから一回目以降の篩処理が終了した旨の通知を受け付けると、篩処理が終了した後の各バイトの値それぞれに対して、閾値未満の値であるかを判定し、その結果、閾値未満の値を保持するバイトのアドレスのパリティビットを０とする。
【００３５】
図５の例を用いて説明すると、閾値判定部１３ａは、一回目の篩処理が終了した後の各バイトの値に対して、閾値（図５の例では、閾値「６」）以上であるかを判定し、閾値以上であるアドレス「１」および「５」に付属するパリティビットを「１」とする。その後、二回目の篩処理が終了した後の各バイトの値に対して、閾値未満の値であるかを判定し、その結果、パリティビットが「１」であって閾値未満であるアドレス「１」に付属するパリティビットを「０」とする。その結果、篩処理１回目および篩処理２回目両方の結果の共通部分をパリティビットが「１」であるアドレス「５」として後述する共通アドレス１３ｂが抽出する。
【００３６】
共通アドレス抽出部１３ｂは、対応するパリティビットの値が１であるバイトのアドレスを、閾値以上であるメモリアドレスの共通部分として、抽出する。例えば、前述した図５の例を用いて説明すると、共通アドレス抽出部１３ｂは、同図に示すように、パリティビットが「１」であるアドレス「５」をメモリアドレスの共通部分として抽出する。
【００３７】
［共通アドレス抽出装置による処理］
次に、図６を用いて、実施例１に係る共通アドレス抽出装置１０による全体の処理の流れを説明する。図６は、実施例１に係る共通アドレス抽出装置１０の全体の処理動作を示すフローチャートである。
【００３８】
同図に示すように、共通アドレス抽出装置１０は、各バイトの値を０に初期化し（ステップＳ１０１）、一回目の篩処理（後に、図７を用いて詳述）を実行する（ステップＳ１０２）。そして、共通アドレス抽出装置１０は、一回目の篩処理が終了した後の各バイトの値に対して、閾値以上であるかを判定し、閾値以上であるバイトのアドレスに付属するパリティビットをオンとする（ステップＳ１０３）。
【００３９】
そして、共通アドレス抽出装置１０は、各バイトの値を０に初期化し（ステップＳ１０４）、二回目の篩処理を実行する（ステップＳ１０５）。その後、共通アドレス抽出装置１０は、二回目の篩処理が終了した後、篩処理が終了した後の各バイトの値に対して、閾値未満であるかを判定し、閾値未満であるバイトのアドレスに付属するパリティビットをオフとする（ステップＳ１０６）。
【００４０】
そして、共通アドレス抽出装置１０は、対応するパリティビットの値が１であるバイトのアドレスを、閾値以上であるメモリアドレスの共通部分として、抽出する（ステップＳ１０７）。
【００４１】
続いて、図７を用いて、実施例１に係る共通アドレス抽出装置１０による篩処理の流れを説明する。図７は、実施例１に係る共通アドレス抽出装置１０の篩処理の動作を示すフローチャートである。
【００４２】
同図に示すように、共通アドレス抽出装置１０の演算部１１ａは、因子基底データベース２０から因子基底（ｐ、ｓ、ｌｏｇ）を読み出す（ステップＳ２０１）。そして、演算部１１ａは、ｓ＜Ｓであるか否か判定し（ステップＳ２０２）、ｓ＜Ｓである場合には（ステップＳ２０２肯定）、メモリ空間におけるバイト位置ｓのメモリ値を読み出し、その値にｌｏｇの値を加算し、その値を同じバイト位置に書き戻す（ステップＳ２０３）。
【００４３】
そして、演算部１１ａは、ｓ＋ｐを改めてｓとし（ステップＳ２０４）、ステップＳ２０２に戻って、ｓ＜Ｓであるか否か（つまり、ｓ＋ｐの値がＳを超えたか否か）判定し、ｓ＜Ｓでないと判定されるまで上記したステップＳ２０２〜Ｓ２０５の処理を繰り返す。一方、ステップＳ２０２において、演算部１１ａは、ｓ＜Ｓでないと判定した場合には（ステップＳ２０２否定）、ｓ−Ｓを改めてｓとし、（ｐ、ｓ、ｌｏｇ）を演算部１１ｂに引き渡す（ステップＳ２０５）。ここで、演算部１１ｂに引き渡すと同時に、因子基底データベース２０に格納されている次の因子基底（ｐ、ｓ、ｌｏｇ）を読み出し、読み出した因子基底（ｐ、ｓ、ｌｏｇ）を用いて、上記したステップＳ２０２〜Ｓ２０５と同様の処理を行う。
【００４４】
その後、演算部１１ｂは、演算部１１ａから（ｐ、ｓ、ｌｏｇ）を受信すると、上記したステップＳ２０２〜Ｓ２０５と同様の処理を行い、次の演算部１１ｃに（ｐ、ｓ、ｌｏｇ）を引き渡し（ステップＳ２０６〜Ｓ２０９）、演算部１１ｎまで処理を繰り返す（ステップＳ２１０〜Ｓ２１２）。そして、演算部１１ｎは、因子基底データベース２０に格納されている全ての因子基底（ｐ、ｓ、ｌｏｇ）を用いたログ加算処理を行った後、上記したステップＳ１０３に移行する。なお、図６に示した一回目の篩処理と二回目の篩処理とは同様の処理を行うが、一回目の篩処理では、因子基底データベース２０ａに格納された因子基底（ｐ、ｓ、ｌｏｇ）を用いてログ加算処理を行い、二回目の篩処理では、因子基底データベース２０ｂに格納された因子基底（ｐ、ｓ、ｌｏｇ）を用いてログ加算処理を行う。
【００４５】
[実施例１の効果]
上述してきたように、共通アドレス抽出装置１０は、演算装置内部にパリティビットをアドレス毎に準備し、本パリティビットを用いて抽出アドレス情報を処理することにより、共通部分抽出に必要となる処理の並列化を可能とし、処理全体の効率化を図って処理時間を高速化することが可能である。
【００４６】
また、実施例１によれば、ハードウェアロジックとして実現することにより、閾値判定、共通項抽出の処理が並列に実行可能であり、またさらに閾値判定と同時に共通項の抽出およびメモリの初期化が可能となり、これにより共通項抽出処理にかかる時間が大幅に圧縮され、素因数分解における篩処理全体の演算効率が著しく向上する。また、ＦＰＧＡ（例えば、Ｖｉｒｔｅｘ４）に内蔵されているメモリロジックエレメントは、各１バイトエレメントに、１ビットのパリティを含んだ９ｂｉｔを単位としており、本アルゴリズムをハードウェア実装する際には特に有効である。
【実施例２】
【００４７】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では実施例２として本発明に含まれる他の実施例を説明する。
【００４８】
（１）パリティビット
本発明は、処理開始時点において全てのパリティビットをオンにし、各演算後に条件に適合しないアドレスに付属するパリティビットをオフとするようにしてもよい。具体的には、図８に示すように、共通アドレス抽出装置１０ａは、演算開始時点では、各バイトに付属するパリティビットを全て１とすると共に、各バイトの値を０に初期化する（図８、（１）参照）。そして、共通アドレス抽出装置１０ａは、パリティビットの値を保持した状態のまま、各バイトに対して篩処理一回目を実施する（図８の（２）参照）。
【００４９】
その後、共通アドレス抽出装置１０ａは、一回目の篩処理が終了した後の各バイトの値に対して、条件を満足するバイトのアドレス（閾値として定めた値である６以上の値を持つバイトのアドレス）については、パリティビットを「１」のまま変化させず、条件を満足しないバイトのアドレス（同じく6未満であるバイトのアドレス）に付属するパリティビットを「０」とし、同時に全てのバイトの値を０に初期化する（図８の（３）参照）。
【００５０】
続いて、共通アドレス抽出装置１０ａは、パリティビットの値を保持した状態のまま、各バイトに対して篩処理二回目を実施する（図８の（４）参照）。そして、共通アドレス抽出装置１０ａは、二回目の篩処理が終了した後の各バイトの値に対して、条件を満足するバイトのアドレス（閾値として定めた値である６以上の値を持つバイトのアドレス）については、パリティビットを変化させず、条件を満足しないバイトのアドレス（同じく６未満であるバイトのアドレス）に付属するパリティビットを０とし、同時に全てのバイトの値を０に初期化する（図８の（５）参照）。その後、対応するパリティビットの値が１であるバイトのアドレスを抽出する。
【００５１】
このように、処理開始時点において全てのパリティビットをオンにし、各演算後は、閾値未満の値を保持するバイトのアドレスに付属するパリティビットをオフにするので、回路の構造を単純化することが可能である。
【００５２】
（２）システム構成等
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、演算部１１と制御部１３を統合してもよい。
【００５３】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００５４】
（付記１）複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出装置であって、
前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶する記憶手段と、
各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更手段と、
前記変更手段により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出手段と、
を備えたことを特徴とする記憶位置抽出装置。
【００５５】
（付記２）初回の演算における演算結果のうち、前記所定の条件に満足する演算結果の演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、
前記変更手段は、初回以後の演算において、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする付記１に記載の記憶位置抽出装置。
【００５６】
（付記３）演算開始時点において、全ての演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、
前記変更手段は、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする付記１に記載の記憶位置抽出装置。
【００５７】
（付記４）前記演算結果記憶領域に対する演算を並列に行うことを特徴とする付記１〜３のいずれか一つに記載の記憶位置抽出装置。
【００５８】
（付記５）前記変更手段は、前記第一の情報を更新する処理を並列に行うことを特徴とする付記１〜４のいずれか一つに記載の記憶位置抽出装置。
【００５９】
（付記６）前記変更手段によって前記第一の情報が前記第二の情報に変更されると同時に、前記演算結果記憶領域を初期化する演算結果初期化手段をさらに備えることを特徴とする付記１〜５のいずれか一つに記載の記憶位置抽出装置。
【００６０】
（付記７）前記記憶手段は、前記演算結果記憶領域として、一バイトを一単位とすることを特徴とする付記１〜６のいずれか一つに記載の記憶位置抽出装置。
【００６１】
（付記８）前記記憶手段は、九バイトを一単位とし、そのうち八ビットを前記演算結果記憶領域とし、一ビットを前記第一の情報を記憶する領域とすることを特徴とする付記１〜７のいずれか一つに記載の記憶位置抽出装置。
【００６２】
（付記９）複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出方法であって、
前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶する記憶工程と、
各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更工程と、
前記変更工程により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出工程と、
を含んだことを特徴とする記憶位置抽出方法。
【００６３】
（付記１０）初回の演算における演算結果のうち、前記所定の条件に満足する演算結果の演算結果記憶領域に対応付けて前記第一の情報を設定する設定工程をさらに含み、
前記変更工程は、初回以後の演算において、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする付記９に記載の記憶位置抽出方法。
【００６４】
（付記１１）演算開始時点において、全ての演算結果記憶領域に対応付けて前記第一の情報を設定する設定工程をさらに含み、
前記変更工程は、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする付記９に記載の記憶位置抽出方法。
【００６５】
（付記１２）前記演算結果記憶領域に対する演算を並列に行うことを特徴とする付記９〜１１のいずれか一つに記載の記憶位置抽出方法。
【００６６】
（付記１３）前記変更工程は、前記第一の情報を更新する処理を並列に行うことを特徴とする付記９〜１２のいずれか一つに記載の記憶位置抽出方法。
【００６７】
（付記１４）前記変更工程によって前記第一の情報が前記第二の情報に変更されると同時に、前記演算結果記憶領域を初期化する演算結果初期化手段をさらに含んだことを特徴とする付記９〜１３のいずれか一つに記載の記憶位置抽出方法。
【００６８】
（付記１５）前記記憶工程は、前記演算結果記憶領域として、一バイトを一単位とすることを特徴とする付記９〜１４のいずれか一つに記載の記憶位置抽出方法。
【００６９】
（付記１６）前記記憶工程は、九バイトを一単位とし、そのうち八ビットを前記演算結果記憶領域とし、一ビットを前記第一の情報を記憶する領域とすることを特徴とする付記９〜１５のいずれか一つに記載の記憶位置抽出方法。
【産業上の利用可能性】
【００７０】
以上のように、本発明に係る記憶位置抽出装置および記憶位置抽出方法は複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する場合に有用であり、特に、共通部分抽出に必要となる処理の並列化を可能とし、処理全体の効率化を図って処理を高速化することに適する。
【図面の簡単な説明】
【００７１】
【図１】実施例１に係る共通アドレス抽出装置１０の概要および特徴を説明するための図である。
【図２】実施例１に係る共通アドレス抽出装置１０の構成を示すブロック図である。
【図３】ログ加算処理について説明するための図である。
【図４】ログ加算処理の計算例について説明するための図である。
【図５】閾値判定処理について説明するための図である。
【図６】実施例１に係る共通アドレス抽出装置１０の全体の処理動作を示すフローチャートである。
【図７】実施例１に係る共通アドレス抽出装置１０の篩処理の動作を示すフローチャートである。
【図８】実施例２に係る共通アドレス抽出装置１０ａを説明するための図である。
【図９】従来の篩処理を説明するための図である。
【符号の説明】
【００７２】
１０、１０ａ 共通アドレス抽出装置
１１ａ〜１１ｎ 演算部
１２ａ〜１２ｎ メモリ
１３ 制御部
１３ａ 閾値判定部
１３ｂ 共通アドレス抽出部
２０ａ、２０ｂ 因子基底データベース
【技術分野】
【０００１】
この発明は、複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出装置および記憶位置抽出方法に関する。
【背景技術】
【０００２】
近年、インターネット等の広がりにより、決済や個人認証を、ネットワークを通じて電子的に行う必要性が増しているが、その情報セキュリティを保持するための基盤技術の一つとしてＲＳＡ暗号が用いられている。このＲＳＡ暗号の安全性は素因数分解問題の困難性に基づいており、この暗号を安全に利用するためには、ＲＳＡ暗号の安全性評価を精密に行い、その実装パラメータが適切に設定されているかを評価することが重要となっている。
【０００３】
このような評価のためには、現在知られている最も効率的な素因数分解アルゴリズムがどのくらいの計算量で実施できるのかを図る必要があり、素因数分解アルゴリズムをソフトウェアの面だけでなく、専用ハードウェアによる評価が欠かせない。
【０００４】
例えば、ＲＳＡ暗号の安全性を評価するうえで重要となる素因数分解アルゴリズムの中で、現時点で最も効率的な手法として知られている方法は一般数体篩法である。具体的に、一般数体篩法は、多項式選択ステップ、関係式探索ステップ、行列計算ステップおよび平方根計算ステップの四つのステップから構成される（非特許文献１参照）。
【０００５】
この一般数体篩法に必要な計算量として、上記のステップの中で最も本質的な部分は関係式探索ステップである。この関係式探索ステップは、さらに篩処理部と関係式検査部の２種類の処理から構成されているが、中でも篩処理が計算量の上で本質的であることが知られている。
【０００６】
この篩処理とは、メモリを初期化する操作ならびにログ加算と閾値判定を合わせた処理のことをいう。このログ加算処理では、各々１バイト（８ビット）のデータ容量を持つメモリ空間を準備し、用意された多数の素数各々について、一定の条件を満たすアドレスのデータに対して、素数の対数値を加算する処理を行う。また、閾値判定処理では、全ての素数に対しログ加算処理が行われたあと、あらかじめ決められた閾値以上となるメモリデータのアドレスを抽出する処理が行われる（特許文献１参照）。そして、この篩処理を複数回を実施する度毎に各々抽出されたメモリアドレスの共通部分を求める処理も重要であり、併せて効率的に実施される必要がある。
【０００７】
従来より、メモリアドレスの共通部分を求める手法としては、この共通部分を求める際に、複数の篩処理それぞれについて抽出されたアドレスを一旦外部記憶装置に蓄え、それらのデータを突き合わせることで、共通部分を求める方法が知られている。
【０００８】
具体的に説明すると、図９に示すように、一回目の篩処理が終了した後の各バイトの値に対して、閾値「６」以上であるかを判定し、閾値「６」以上の値を保持するバイトのアドレス「１」、「５」を装置外部のバッファに転送し、バッファに保持される。続いて、二回目の篩処理が終了した後に同様の処理を行って、閾値「６」以上の値を保持するバイトのアドレス「３」、「５」を転送し、同じくバッファに保持される。そして、各々のバッファに保持された結果から、共通部分「５」を抽出する。ここで、ハードウェアからバッファへデータ転送する処理およびバッファに保持された共通部分を抽出する処理は逐次処理となる。
【０００９】
【特許文献１】特開２００７−１８８２６３号公報
【非特許文献１】伊豆哲也、木田祐司「素因数分解の現状について」日本応用数理学会論文誌、Vol.13, No.2(20030625) pp. 289-303, 2003.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ところで、上記したバッファへのデータ転送を行ってメモリアドレスの共通部分を抽出する技術では、共通部分を抽出する際に、通常外部記憶装置への出力バスは単一であるため、篩処理結果を抽出する際、ならびに共通部分を抽出する際において、いずれも並列化が困難であるため、逐次処理によるデータ転送時間の増加や、処理時間の増加等の問題が発生し、処理全体の効率が低下するという課題があった。
【００１１】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、共通部分抽出に必要となる処理の並列化を可能とし、処理全体の効率化を図って処理時間を高速化することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するため、本発明は、複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出装置であって、前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶する記憶手段と、各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更手段と、前記変更手段により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出手段と、を備えたことを特徴とする。
【００１３】
また、本発明は、上記の発明において、初回の演算における演算結果のうち、前記所定の条件に満足する演算結果の演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、前記変更手段は、初回以後の演算において、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更することを特徴とする。
【００１４】
また、本発明は、上記の発明において、演算開始時点において、全ての演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、前記変更手段は、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更することを特徴とする。
【００１５】
また、本発明は、複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出方法であって、前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶する記憶工程と、各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更工程と、前記変更工程により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出工程と、を含んだことを特徴とする。
【発明の効果】
【００１６】
本発明によれば、演算装置内部にパリティビットをアドレス毎に準備し、本パリティビットを用いて抽出アドレス情報を処理することにより、共通部分抽出に必要となる処理の並列化を可能とし、処理全体の効率化を図って処理時間を高速化することが可能である。
【発明を実施するための最良の形態】
【００１７】
以下に添付図面を参照して、この発明に係る記憶位置抽出装置および記憶位置抽出方法の実施例を詳細に説明する。
【実施例１】
【００１８】
以下の実施例では、実施例１に係る共通アドレス抽出装置の概要および特徴、共通アドレス抽出装置の構成および処理の流れを順に説明し、最後に実施例１による効果を説明する。
【００１９】
［実施例１に係る共通アドレス抽出装置の概要および特徴］
まず最初に、図１を用いて、実施例１に係る共通アドレス抽出装置の概要および特徴を説明する。図１は、実施例１に係る共通アドレス抽出装置の概要および特徴を説明するための図である。
【００２０】
実施例１の共通アドレス抽出装置１０では、複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果のメモリアドレスを抽出することを概要とする。そして、この共通アドレス抽出装置１０では、処理全体の効率化を図って処理を高速化する点に主たる特徴がある。
【００２１】
この主たる特徴について具体的に説明すると、共通アドレス抽出装置１０は、アドレスごとのログ加算処理結果を記憶する１バイトの記憶領域と、ログ加算処理結果が選択条件に適合するか否かを示すフラグをアドレスごとに記憶する１ビットの記憶領域（パリティビット）とを対応付けて記憶するメモリを有する。
【００２２】
このような構成のもと、共通アドレス抽出装置１０は、各バイトに対して篩処理一回目のログ加算処理を実施する（図１の（１）参照）。そして、共通アドレス抽出装置１０は、一回目のログ加算処理が終了した後の各バイトの値に対して、条件を満足するバイトのアドレスに付属するパリティビットをオンとする（図１の（２）参照）。具体的には、共通アドレス抽出装置１０は、一回目のログ加算処理が終了した後にバイトが保持する値それぞれに対して、閾値以上であるか判定し、その結果、閾値以上の値を保持するバイトのアドレスのパリティビットを「１」とする。
【００２３】
続いて、共通アドレス抽出装置１０は、パリティビットの値を保持した状態のまま、各バイトに対して篩処理二回目のログ加算処理を実施する（図１の（３）参照）。そして、共通アドレス抽出装置１０は、二回目の篩処理が終了した後のバイトが保持する値それぞれに対して、条件を満足しないバイトのアドレスに付属するパリティビットをオフとする（図１の（４）参照）。具体的には、共通アドレス抽出装置１０は、二回目の篩処理が終了した後にバイトが保持する値それぞれに対して、閾値未満の値であるかを判定し、その結果、閾値未満の値を保持するバイトのアドレスのパリティビットを０とする。
【００２４】
その後、共通アドレス抽出装置１０は、対応するパリティビットの値が１であるバイトのアドレスを、条件を満足するメモリアドレスの共通部分として、抽出して格納する（図１の（５）参照）。なお、上記では、篩処理を二回実行して共通部分を抽出する場合を説明するが、篩処理を二回以上実行して共通部分を抽出するようにしてもよい。
【００２５】
このように、共通アドレス抽出装置１０は、共通部分抽出に必要となる処理の並列化を可能とする結果、上記した主たる特徴のごとく、処理全体の効率化を図って処理を高速化することが可能である。
【００２６】
［共通アドレス抽出装置１０の構成］
次に、図２を用いて、図１に示した共通アドレス抽出装置１０の構成を説明する。図２は、実施例１に係る共通アドレス抽出装置１０の構成を示すブロック図である。なお、以下では、ＦＰＧＡに共通アドレス抽出装置を適用した場合として説明する。
【００２７】
同図に示すように、この共通アドレス抽出装置１０は、演算部１１ａ〜１１ｎ、メモリ１２ａ〜１２ｎ、制御部１３を備え、因子基底データベース２０ａ、２０ｂとそれぞれ接続される。演算部１１ａ〜１１ｎには、メモリ１２ａ〜１２ｎがそれぞれ割当てられている。以下にこれらの各部の処理を説明する。
【００２８】
因子基底データベース２０ａ、２０ｂは、３つ組の自然数（ｐ、ｓ、ｌｏｇ）である因子基底の集合を記憶する。この因子基底とは、ｐが素数であり、ｓが０以上ｐ未満の自然数、ｌｏｇがｐの対数値ｌｏｇ２（ｐ）の小数点以下を切り上げた自然数である。因子基底データベース２０ａ、２０ｂでは、それぞれ異なる因子基底の集合が記憶され、因子基底データベース２０ａに格納された因子基底（ｐ、ｓ、ｌｏｇ）は、一回目の篩処理で用いられ、因子基底データベース２０ｂに格納された因子基底（ｐ、ｓ、ｌｏｇ）は、二回目の篩処理で用いられるものとする。なお、因子基底データベース２０ａ、２０ｂそれぞれは、因子基底の総数として、約５０００万個程度を記憶する。
【００２９】
演算部１１は、因子基底データベース２０から因子基底を読み出して、因子基底を用いてログ加算処理を行う。図３の例を用いて具体的に説明すると、まず、演算部１１ａは、各バイトの値を０に初期化し、因子基底データベース２０から（ｐ、ｓ、ｌｏｇ）を読み出す。そして、演算部１１ａは、ｓ＜Ｓであるか否か判定し（つまり、ｓの値がメモリサイズをはみ出すか否かを判定し）、ｓ＜Ｓである場合には、メモリ空間におけるバイト位置ｓのメモリ値を読み出し、その値にｌｏｇの値を加算し、その値を同じバイト位置に書き戻す。
【００３０】
そして、演算部１１ａは、ｓ＋ｐを改めてｓとし、メモリ１２ａのメモリサイズをはみ出すまで（つまり、ｓ＋ｐの値がＳ以上となるまで）、上記の処理を繰り返す。そして、演算部１１ａは、メモリサイズをはみ出した場合には、ｓ−Ｓを改めてｓとし、（ｐ、ｓ、ｌｏｇ）を演算部１１ｂに引き渡す。その後、全ての演算部１１ａ〜１１ｎが上記の処理を行うと、最後の演算部１１ｎは、一回目の篩処理を終了した旨（または、一回目以降の篩処理が終了した旨）を後述する閾値判定部１３ａに通知する。
【００３１】
ここで、図４を用いてログ加算処理の計算例について説明する。図４の例では、因子基底データベース２０に因子基底（ｐ、ｓ、ｌｏｇ）として、（３，０，２）、（５，０，３）、（７，４，３）,（１１，４，４），（１３，６，４），（１７，３，５），（１９，２，５）が記憶されている場合に、演算部１１ａは、その因子基底を順番に読み出して、ログ加算処理を行い、全ての因子基底を用いて行ったログ加算処理結果の合計をメモリ１２に記憶させる。つまり、図４の例では、ログ加算処理結果の合計として、アドレス０〜６には、それぞれ「５」、「０」、「５」、「７」、「７」、「３」、「６」が記憶されている。その後、後述する制御部１３が、ログ加算処理が終了した後にバイトが保持する値それぞれに対して、閾値「６」以上であるか判定し、その結果、閾値「６」以上の値を保持するバイトのアドレスであるアドレス「３」、「４」、「６」のパリティビットを１とする。
【００３２】
メモリ１２ａ〜１２ｎは、メモリ空間としてＳ＝２１９バイトをトータルで有し、アドレスごとのログ加算処理結果を記憶するデータ容量として１バイトの記憶領域と、ログ加算処理結果が選択条件に適合するか否かを示すフラグをアドレスごとに記憶する１ビットのパリティビットを有する。
【００３３】
制御部１３は、閾値判定部１３ａと共通アドレス抽出部１３ｂとを備える。この閾値判定部１３ａは、一回目の篩処理が終了した後の各メモリ１２ａ〜１２ｎのバイトの値に対して、閾値以上であるかを判定し、閾値以上であるバイトのアドレスに付属するパリティビットをオンとする。また、一回目の篩処理以後では、篩処理が終了した後の各バイトの値に対して、閾値未満であるかを判定し、閾値未満であるバイトのアドレスに付属するパリティビットをオフとする。
【００３４】
具体的には、閾値判定部１３ａは、演算部１１ｎから一回目の篩処理が終了した旨の通知を受け付けると、篩処理が終了した後の各バイトの値に対して、閾値以上であるか判定し、その結果、閾値判定部１３ａは、閾値以上の値を保持するバイトのアドレスのパリティビットを１とする。また、共通アドレス抽出装置１０は、演算部１１ｎから一回目以降の篩処理が終了した旨の通知を受け付けると、篩処理が終了した後の各バイトの値それぞれに対して、閾値未満の値であるかを判定し、その結果、閾値未満の値を保持するバイトのアドレスのパリティビットを０とする。
【００３５】
図５の例を用いて説明すると、閾値判定部１３ａは、一回目の篩処理が終了した後の各バイトの値に対して、閾値（図５の例では、閾値「６」）以上であるかを判定し、閾値以上であるアドレス「１」および「５」に付属するパリティビットを「１」とする。その後、二回目の篩処理が終了した後の各バイトの値に対して、閾値未満の値であるかを判定し、その結果、パリティビットが「１」であって閾値未満であるアドレス「１」に付属するパリティビットを「０」とする。その結果、篩処理１回目および篩処理２回目両方の結果の共通部分をパリティビットが「１」であるアドレス「５」として後述する共通アドレス１３ｂが抽出する。
【００３６】
共通アドレス抽出部１３ｂは、対応するパリティビットの値が１であるバイトのアドレスを、閾値以上であるメモリアドレスの共通部分として、抽出する。例えば、前述した図５の例を用いて説明すると、共通アドレス抽出部１３ｂは、同図に示すように、パリティビットが「１」であるアドレス「５」をメモリアドレスの共通部分として抽出する。
【００３７】
［共通アドレス抽出装置による処理］
次に、図６を用いて、実施例１に係る共通アドレス抽出装置１０による全体の処理の流れを説明する。図６は、実施例１に係る共通アドレス抽出装置１０の全体の処理動作を示すフローチャートである。
【００３８】
同図に示すように、共通アドレス抽出装置１０は、各バイトの値を０に初期化し（ステップＳ１０１）、一回目の篩処理（後に、図７を用いて詳述）を実行する（ステップＳ１０２）。そして、共通アドレス抽出装置１０は、一回目の篩処理が終了した後の各バイトの値に対して、閾値以上であるかを判定し、閾値以上であるバイトのアドレスに付属するパリティビットをオンとする（ステップＳ１０３）。
【００３９】
そして、共通アドレス抽出装置１０は、各バイトの値を０に初期化し（ステップＳ１０４）、二回目の篩処理を実行する（ステップＳ１０５）。その後、共通アドレス抽出装置１０は、二回目の篩処理が終了した後、篩処理が終了した後の各バイトの値に対して、閾値未満であるかを判定し、閾値未満であるバイトのアドレスに付属するパリティビットをオフとする（ステップＳ１０６）。
【００４０】
そして、共通アドレス抽出装置１０は、対応するパリティビットの値が１であるバイトのアドレスを、閾値以上であるメモリアドレスの共通部分として、抽出する（ステップＳ１０７）。
【００４１】
続いて、図７を用いて、実施例１に係る共通アドレス抽出装置１０による篩処理の流れを説明する。図７は、実施例１に係る共通アドレス抽出装置１０の篩処理の動作を示すフローチャートである。
【００４２】
同図に示すように、共通アドレス抽出装置１０の演算部１１ａは、因子基底データベース２０から因子基底（ｐ、ｓ、ｌｏｇ）を読み出す（ステップＳ２０１）。そして、演算部１１ａは、ｓ＜Ｓであるか否か判定し（ステップＳ２０２）、ｓ＜Ｓである場合には（ステップＳ２０２肯定）、メモリ空間におけるバイト位置ｓのメモリ値を読み出し、その値にｌｏｇの値を加算し、その値を同じバイト位置に書き戻す（ステップＳ２０３）。
【００４３】
そして、演算部１１ａは、ｓ＋ｐを改めてｓとし（ステップＳ２０４）、ステップＳ２０２に戻って、ｓ＜Ｓであるか否か（つまり、ｓ＋ｐの値がＳを超えたか否か）判定し、ｓ＜Ｓでないと判定されるまで上記したステップＳ２０２〜Ｓ２０５の処理を繰り返す。一方、ステップＳ２０２において、演算部１１ａは、ｓ＜Ｓでないと判定した場合には（ステップＳ２０２否定）、ｓ−Ｓを改めてｓとし、（ｐ、ｓ、ｌｏｇ）を演算部１１ｂに引き渡す（ステップＳ２０５）。ここで、演算部１１ｂに引き渡すと同時に、因子基底データベース２０に格納されている次の因子基底（ｐ、ｓ、ｌｏｇ）を読み出し、読み出した因子基底（ｐ、ｓ、ｌｏｇ）を用いて、上記したステップＳ２０２〜Ｓ２０５と同様の処理を行う。
【００４４】
その後、演算部１１ｂは、演算部１１ａから（ｐ、ｓ、ｌｏｇ）を受信すると、上記したステップＳ２０２〜Ｓ２０５と同様の処理を行い、次の演算部１１ｃに（ｐ、ｓ、ｌｏｇ）を引き渡し（ステップＳ２０６〜Ｓ２０９）、演算部１１ｎまで処理を繰り返す（ステップＳ２１０〜Ｓ２１２）。そして、演算部１１ｎは、因子基底データベース２０に格納されている全ての因子基底（ｐ、ｓ、ｌｏｇ）を用いたログ加算処理を行った後、上記したステップＳ１０３に移行する。なお、図６に示した一回目の篩処理と二回目の篩処理とは同様の処理を行うが、一回目の篩処理では、因子基底データベース２０ａに格納された因子基底（ｐ、ｓ、ｌｏｇ）を用いてログ加算処理を行い、二回目の篩処理では、因子基底データベース２０ｂに格納された因子基底（ｐ、ｓ、ｌｏｇ）を用いてログ加算処理を行う。
【００４５】
[実施例１の効果]
上述してきたように、共通アドレス抽出装置１０は、演算装置内部にパリティビットをアドレス毎に準備し、本パリティビットを用いて抽出アドレス情報を処理することにより、共通部分抽出に必要となる処理の並列化を可能とし、処理全体の効率化を図って処理時間を高速化することが可能である。
【００４６】
また、実施例１によれば、ハードウェアロジックとして実現することにより、閾値判定、共通項抽出の処理が並列に実行可能であり、またさらに閾値判定と同時に共通項の抽出およびメモリの初期化が可能となり、これにより共通項抽出処理にかかる時間が大幅に圧縮され、素因数分解における篩処理全体の演算効率が著しく向上する。また、ＦＰＧＡ（例えば、Ｖｉｒｔｅｘ４）に内蔵されているメモリロジックエレメントは、各１バイトエレメントに、１ビットのパリティを含んだ９ｂｉｔを単位としており、本アルゴリズムをハードウェア実装する際には特に有効である。
【実施例２】
【００４７】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では実施例２として本発明に含まれる他の実施例を説明する。
【００４８】
（１）パリティビット
本発明は、処理開始時点において全てのパリティビットをオンにし、各演算後に条件に適合しないアドレスに付属するパリティビットをオフとするようにしてもよい。具体的には、図８に示すように、共通アドレス抽出装置１０ａは、演算開始時点では、各バイトに付属するパリティビットを全て１とすると共に、各バイトの値を０に初期化する（図８、（１）参照）。そして、共通アドレス抽出装置１０ａは、パリティビットの値を保持した状態のまま、各バイトに対して篩処理一回目を実施する（図８の（２）参照）。
【００４９】
その後、共通アドレス抽出装置１０ａは、一回目の篩処理が終了した後の各バイトの値に対して、条件を満足するバイトのアドレス（閾値として定めた値である６以上の値を持つバイトのアドレス）については、パリティビットを「１」のまま変化させず、条件を満足しないバイトのアドレス（同じく6未満であるバイトのアドレス）に付属するパリティビットを「０」とし、同時に全てのバイトの値を０に初期化する（図８の（３）参照）。
【００５０】
続いて、共通アドレス抽出装置１０ａは、パリティビットの値を保持した状態のまま、各バイトに対して篩処理二回目を実施する（図８の（４）参照）。そして、共通アドレス抽出装置１０ａは、二回目の篩処理が終了した後の各バイトの値に対して、条件を満足するバイトのアドレス（閾値として定めた値である６以上の値を持つバイトのアドレス）については、パリティビットを変化させず、条件を満足しないバイトのアドレス（同じく６未満であるバイトのアドレス）に付属するパリティビットを０とし、同時に全てのバイトの値を０に初期化する（図８の（５）参照）。その後、対応するパリティビットの値が１であるバイトのアドレスを抽出する。
【００５１】
このように、処理開始時点において全てのパリティビットをオンにし、各演算後は、閾値未満の値を保持するバイトのアドレスに付属するパリティビットをオフにするので、回路の構造を単純化することが可能である。
【００５２】
（２）システム構成等
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、演算部１１と制御部１３を統合してもよい。
【００５３】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００５４】
（付記１）複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出装置であって、
前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶する記憶手段と、
各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更手段と、
前記変更手段により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出手段と、
を備えたことを特徴とする記憶位置抽出装置。
【００５５】
（付記２）初回の演算における演算結果のうち、前記所定の条件に満足する演算結果の演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、
前記変更手段は、初回以後の演算において、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする付記１に記載の記憶位置抽出装置。
【００５６】
（付記３）演算開始時点において、全ての演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、
前記変更手段は、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする付記１に記載の記憶位置抽出装置。
【００５７】
（付記４）前記演算結果記憶領域に対する演算を並列に行うことを特徴とする付記１〜３のいずれか一つに記載の記憶位置抽出装置。
【００５８】
（付記５）前記変更手段は、前記第一の情報を更新する処理を並列に行うことを特徴とする付記１〜４のいずれか一つに記載の記憶位置抽出装置。
【００５９】
（付記６）前記変更手段によって前記第一の情報が前記第二の情報に変更されると同時に、前記演算結果記憶領域を初期化する演算結果初期化手段をさらに備えることを特徴とする付記１〜５のいずれか一つに記載の記憶位置抽出装置。
【００６０】
（付記７）前記記憶手段は、前記演算結果記憶領域として、一バイトを一単位とすることを特徴とする付記１〜６のいずれか一つに記載の記憶位置抽出装置。
【００６１】
（付記８）前記記憶手段は、九バイトを一単位とし、そのうち八ビットを前記演算結果記憶領域とし、一ビットを前記第一の情報を記憶する領域とすることを特徴とする付記１〜７のいずれか一つに記載の記憶位置抽出装置。
【００６２】
（付記９）複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出方法であって、
前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶する記憶工程と、
各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更工程と、
前記変更工程により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出工程と、
を含んだことを特徴とする記憶位置抽出方法。
【００６３】
（付記１０）初回の演算における演算結果のうち、前記所定の条件に満足する演算結果の演算結果記憶領域に対応付けて前記第一の情報を設定する設定工程をさらに含み、
前記変更工程は、初回以後の演算において、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする付記９に記載の記憶位置抽出方法。
【００６４】
（付記１１）演算開始時点において、全ての演算結果記憶領域に対応付けて前記第一の情報を設定する設定工程をさらに含み、
前記変更工程は、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする付記９に記載の記憶位置抽出方法。
【００６５】
（付記１２）前記演算結果記憶領域に対する演算を並列に行うことを特徴とする付記９〜１１のいずれか一つに記載の記憶位置抽出方法。
【００６６】
（付記１３）前記変更工程は、前記第一の情報を更新する処理を並列に行うことを特徴とする付記９〜１２のいずれか一つに記載の記憶位置抽出方法。
【００６７】
（付記１４）前記変更工程によって前記第一の情報が前記第二の情報に変更されると同時に、前記演算結果記憶領域を初期化する演算結果初期化手段をさらに含んだことを特徴とする付記９〜１３のいずれか一つに記載の記憶位置抽出方法。
【００６８】
（付記１５）前記記憶工程は、前記演算結果記憶領域として、一バイトを一単位とすることを特徴とする付記９〜１４のいずれか一つに記載の記憶位置抽出方法。
【００６９】
（付記１６）前記記憶工程は、九バイトを一単位とし、そのうち八ビットを前記演算結果記憶領域とし、一ビットを前記第一の情報を記憶する領域とすることを特徴とする付記９〜１５のいずれか一つに記載の記憶位置抽出方法。
【産業上の利用可能性】
【００７０】
以上のように、本発明に係る記憶位置抽出装置および記憶位置抽出方法は複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する場合に有用であり、特に、共通部分抽出に必要となる処理の並列化を可能とし、処理全体の効率化を図って処理を高速化することに適する。
【図面の簡単な説明】
【００７１】
【図１】実施例１に係る共通アドレス抽出装置１０の概要および特徴を説明するための図である。
【図２】実施例１に係る共通アドレス抽出装置１０の構成を示すブロック図である。
【図３】ログ加算処理について説明するための図である。
【図４】ログ加算処理の計算例について説明するための図である。
【図５】閾値判定処理について説明するための図である。
【図６】実施例１に係る共通アドレス抽出装置１０の全体の処理動作を示すフローチャートである。
【図７】実施例１に係る共通アドレス抽出装置１０の篩処理の動作を示すフローチャートである。
【図８】実施例２に係る共通アドレス抽出装置１０ａを説明するための図である。
【図９】従来の篩処理を説明するための図である。
【符号の説明】
【００７２】
１０、１０ａ 共通アドレス抽出装置
１１ａ〜１１ｎ 演算部
１２ａ〜１２ｎ メモリ
１３ 制御部
１３ａ 閾値判定部
１３ｂ 共通アドレス抽出部
２０ａ、２０ｂ 因子基底データベース
【特許請求の範囲】
【請求項１】
複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出装置であって、
前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶する記憶手段と、
各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更手段と、
前記変更手段により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出手段と、
を備えた記憶位置抽出装置。
【請求項２】
初回の演算における演算結果のうち、前記所定の条件を満足する演算結果の演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、
前記変更手段は、初回以後の演算において、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする請求項１に記載の記憶位置抽出装置。
【請求項３】
演算開始時点において、全ての演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、
前記変更手段は、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする請求項１に記載の記憶位置抽出装置。
【請求項４】
複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出方法であって、
前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶部に記憶する記憶工程と、
各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更工程と、
前記変更工程により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出工程と、
を含んだ記憶位置抽出方法。
【請求項１】
複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出装置であって、
前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶する記憶手段と、
各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更手段と、
前記変更手段により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出手段と、
を備えた記憶位置抽出装置。
【請求項２】
初回の演算における演算結果のうち、前記所定の条件を満足する演算結果の演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、
前記変更手段は、初回以後の演算において、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする請求項１に記載の記憶位置抽出装置。
【請求項３】
演算開始時点において、全ての演算結果記憶領域に対応付けて前記第一の情報を設定する設定手段をさらに備え、
前記変更手段は、前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、前記第二の情報に変更することを特徴とする請求項１に記載の記憶位置抽出装置。
【請求項４】
複数の演算結果記憶領域にそれぞれ記憶された各演算結果のうち所定の条件を満足する演算結果の記憶位置を抽出する記憶位置抽出方法であって、
前記所定の条件を満足する演算結果であることを示す第一の情報を演算結果記憶領域に対応付けて記憶部に記憶する記憶工程と、
各演算結果が更新されるごとに前記所定の条件を満足しなくなった演算結果に対応する第一の情報を、当該所定の条件を満足しないことを示す第二の情報に変更する変更工程と、
前記変更工程により変更された変更結果に基づいて前記所定の条件を満足する演算結果の記憶位置を抽出する抽出工程と、
を含んだ記憶位置抽出方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００９−５８６９０（Ｐ２００９−５８６９０Ａ）
【公開日】平成２１年３月１９日（２００９．３．１９）
【国際特許分類】
【出願番号】特願２００７−２２４８８１（Ｐ２００７−２２４８８１）
【出願日】平成１９年８月３０日（２００７．８．３０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成１８年度、独立行政法人情報通信研究機構、「素因数分解の困難性に基づく暗号の技術的評価に関する研究開発」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２１年３月１９日（２００９．３．１９）
【国際特許分類】
【出願日】平成１９年８月３０日（２００７．８．３０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成１８年度、独立行政法人情報通信研究機構、「素因数分解の困難性に基づく暗号の技術的評価に関する研究開発」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]