(57)【要約】      （修正有）【課題】ランダムモジュラー部分集合和問題を解く方法及びシステムを提供する。【解決手段】方法は、ランダムモジュラー部分集合和問題に関連する複数の乱整数、除数及び余りを取得し、イジングモデル連結重み行列“Ｗ”を生成する。行列“Ｗ”の少なくとも一部の要素は、複数の乱整数に基づいて決定される。方法はまた、イジングモデルバイアスベクトル“ｂ”を生成する。ベクトル“ｂ”の要素は、余りに基づいて決定される。また、イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに行列“Ｗ”及びベクトル“ｂ”を提供し、複数の乱整数のうちの一組の整数を表す出力をアニーリングシステムから取得し、一組の整数を、ランダムモジュラー部分集合和問題に対する解として使用する。【選択図】図３
2020071878.tif 000002
【特許請求の範囲】
【請求項１】
ランダムモジュラー部分集合和問題に関連する複数の乱整数、除数、及び余りを取得し、
イジングモデル連結重み行列“Ｗ”を生成し、該行列“Ｗ”の少なくとも一部の要素は、前記複数の乱整数に基づいて決定され、
イジングモデルバイアスベクトル“ｂ”を生成し、該ベクトル“ｂ”の要素は、前記余りに基づいて決定され、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに前記行列“Ｗ”及び前記ベクトル“ｂ”を提供し、
前記複数の乱整数のうちの一組の整数であり、当該一組の整数の和を前記除数で除算したものが整数商及び前記余りとなる一組の整数、を表す出力を前記アニーリングシステムから取得し、
前記一組の整数を、前記複数の乱整数、前記除数、及び前記余りによって規定される前記ランダムモジュラー部分集合和問題に対する解として使用する、
ことを有する方法。
【請求項２】
前記アニーリングシステムは、前記出力を生成するために使用されるエネルギー値を計算するように構成されたエネルギー値計算回路を含み、前記エネルギー値は、前記行列“Ｗ”の要素のうちの１つ以上の値に基づく、請求項１に記載の方法。
【請求項３】
命令を格納した１つ以上のコンピュータ読み取り可能記憶媒体であって、前記命令は、実行されることに応答してシステムに処理を実行させ、前記処理は、
ランダムモジュラー部分集合和問題に関連する複数の乱整数、除数、及び余りを取得し、
イジングモデル連結重み行列“Ｗ”を生成し、該行列“Ｗ”の少なくとも一部の要素は、前記複数の乱整数に基づいて決定され、
イジングモデルバイアスベクトル“ｂ”を生成し、該ベクトル“ｂ”の要素は、前記余りに基づいて決定され、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに前記行列“Ｗ”及び前記ベクトル“ｂ”を提供し、
前記複数の乱整数のうちの一組の整数であり、当該一組の整数の和を前記除数で除算したものが整数商及び前記余りとなる一組の整数、を表す出力を前記アニーリングシステムから取得し、
前記一組の整数を、前記複数の乱整数、前記除数、及び前記余りによって規定される前記ランダムモジュラー部分集合和問題に対する解として使用する、
ことを有する、１つ以上のコンピュータ読み取り可能記憶媒体。
【請求項４】
システムであって、
命令を格納した１つ以上のコンピュータ読み取り可能記憶媒体と、
前記１つ以上のコンピュータ読み取り可能記憶媒体に通信可能に結合され、前記命令の実行に応答して当該システムに処理を実行させるように構成された１つ以上のプロセッサと、
を有し、前記処理は、
ランダムモジュラー部分集合和問題に関連する複数の乱整数、除数、及び余りを取得し、
イジングモデル連結重み行列“Ｗ”を生成し、該行列“Ｗ”の少なくとも一部の要素は、前記複数の乱整数に基づいて決定され、
イジングモデルバイアスベクトル“ｂ”を生成し、該ベクトル“ｂ”の要素は、前記余りに基づいて決定され、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに前記行列“Ｗ”及び前記ベクトル“ｂ”を提供し、
前記複数の乱整数のうちの一組の整数であり、当該一組の整数の和を前記除数で除算したものが整数商及び前記余りとなる一組の整数、を表す出力を前記アニーリングシステムから取得し、
前記一組の整数を、前記複数の乱整数、前記除数、及び前記余りによって規定される前記ランダムモジュラー部分集合和問題に対する解として使用する、
ことを有する、システム。
【請求項５】
前記複数の乱整数、前記除数、及び前記余りは、暗号技術から取得される、請求項４に記載のシステム。
【請求項６】
前記行列“Ｗ”の第１の次元は、前記複数の乱整数の個数に等しく、前記行列“Ｗ”の第２の次元は、前記複数の乱整数の和を前記除数で除算したものを“ｙ”として、前記複数の乱整数の個数と“ｙ”の対数との和に等しい、請求項４に記載のシステム。
【請求項７】
決定された前記行列“Ｗ”の要素のうち第１の部分は前記複数の乱整数のみに基づき、決定された前記行列“Ｗ”の要素のうち第２の部分は前記除数のみに基づく、請求項４に記載のシステム。
【請求項８】
前記行列“Ｗ”の要素のうち第１の部分はゼロであり、前記行列“Ｗ”の要素のうち第２の部分は前記複数の乱整数のうちの１つ以上のみに基づき、前記行列“Ｗ”の要素のうち第３の部分は前記除数のみに基づき、前記行列“Ｗ”の要素のうち第４の部分は前記除数及び前記複数の乱整数のみに基づく、請求項４に記載のシステム。
【請求項９】
前記ベクトル“ｂ”の要素のうち第１の部分は前記余り及び前記複数の乱整数のみに基づき、前記ベクトル“ｂ”の要素のうち第２の部分は前記余り及び前記除数のみに基づく、請求項４に記載のシステム。
【請求項１０】
前記複数の乱整数の個数を前記除数の対数で除算したものが近似的に１に等しい、請求項４に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
ここに記載される実施形態は、ランダムモジュラー部分集合和問題を解く方法及び／又はシステムに関する。
【背景技術】
【０００２】
ランダムモジュラー部分集合和問題は、解くのが難しいと言い得る問題の類である。結果として、ランダムモジュラー部分集合和問題及びそれらの対応する解は、例えば暗号学及び暗号解析などの様々な技術分野で使用され得る。
【０００３】
ここに特許請求される事項は、上述のような環境でのみ問題を解決したり動作したりする実施形態に限定されるものではない。むしろ、この背景技術の説明は、ここに記載される実施形態が実施され得る技術領域の一例を示すために提供されているに過ぎないものである。
【発明の概要】
【０００４】
一実施形態の一態様によれば、方法は、ランダムモジュラー部分集合和問題に関連する複数の乱整数、除数、及び余りを取得し、イジングモデル連結重み行列“Ｗ”を生成することを含み得る。一部の実施形態において、行列“Ｗ”の少なくとも一部の要素は、前記複数の乱整数に基づいて決定され得る。この方法はまた、イジングモデルバイアスベクトル“ｂ”を生成することを含み得る。一部の実施形態において、ベクトル“ｂ”の要素は、前記余りに基づいて決定され得る。この方法はまた、イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに行列“Ｗ”及びベクトル“ｂ”を提供し、前記複数の乱整数のうちの一組の整数を表す出力をアニーリングシステムから取得することを含み得る。一部の実施形態において、一組の整数の和を前記除数で除算したものが整数商及び前記余りとなり得る。この方法はまた、前記一組の整数を、前記複数の乱整数、前記除数、及び前記余りによって規定されるランダムモジュラー部分集合和問題に対する解として使用することを含み得る。
【０００５】
実施形態の目的及び利点は、少なくとも請求項中に具体的に指し示される要素、機構及び組合せによって実現・達成されることになる。
【０００６】
以上の概略説明及び以下の詳細説明はどちらも、例として与えられ、説明的なものであり、特許請求される発明を限定するものではない。
【図面の簡単な説明】
【０００７】
以下の図を含む添付図面を使用して、実施形態例を更に具体的且つ詳細に記載・説明する。
【図１】ランダムモジュラー部分集合和（ＲＭＳＳ）問題を解くことに関する環境の一例を示す図である。
【図２】ＲＭＳＳ問題を解くように構成され得るコンピューティングシステムの一例を示す図である。
【図３】ＲＭＳＳ問題を解く方法の一例を示すフローチャートである。
【発明を実施するための形態】
【０００８】
ランダムモジュラー部分集合和（Random  Modular  Subset  Sum；ＲＭＳＳ）問題は、数ある中でもとりわけ暗号解析を含む多様な用途を持つ最適化問題の類を含み得る。また、デジタル及び量子アニーリングシステムは、古典的なコンピューティングシステム及び技術よりも速い手法で最適化問題に対する解を得るために発見的アプローチを使用し得る。従って、デジタル及び量子アニーリングシステムは、ＲＭＳＳ問題を解くのを助ける上で有用であり、それにより、例えば暗号解析などの幾つかの技術分野を向上させ得る。簡潔さの目的で、デジタル及び／又は量子アニーラへの言及を併せて“アニーラ”として言及することとする。
【０００９】
一部の形態において、ＲＭＳＳ問題を解くために典型的に使用される入力は、アニーリングシステムがＲＭＳＳ問題を効率的に解くことを可能にするようには構成されていないことがある。一部の形態において、ＲＭＳＳ問題を解くためにイジング（Ising）モデルが使用され得るが、ＲＭＳＳ問題及びイジングモデル問題を、入力を効率的に減らすようにして変換する必要があり得る。従って、本開示の１つ以上の態様によれば、１つ以上の処理をＲＭＳＳ問題に対して実行して、ＲＭＳＳ問題を解くために再入力し得るイジングモデル入力を取得し得る。
【００１０】
従って、本開示の１つ以上の実施形態によれば、ここに記載される処理が、元のＲＭＳＳ方程式及びイジングモデル問題の双方の効率的な削減を用いてアニーリングシステムがＲＭＳＳ問題を解くことを可能にする機構を提供することによって、アニーリングシステムの改良を可能にする。一部の実施態様において、方法の効率は、アニーラの効率に関係する。ここに記載される方法は、包括的な削減を組み込まなくてもよく、効率の指数関数的な低下をもたらし得るものであるインスタンスサイズにおける多項式的増大を回避し得る。
【００１１】
本開示の実施形態を、添付の図面を参照して説明する。
【００１２】
図１は、本開示にて記載される少なくとも１つの実施形態に従って構成された、アニーリングシステムを用いてＲＭＳＳ問題を解くことに関する環境１００の一例を表す図である。環境１００は、イジングモデル入力モジュール１０２（“入力モジュール１０２”）、イジングモデルモジュール１０６（“イジングモジュール１０６”）、及びイジングモデル出力モジュール１１２（“出力モジュール１１２”）を含み得る。
【００１３】
入力モジュール１０２、イジングモジュール１０６、及び／又は出力モジュール１１２は、それとともに記載される処理のうちの１つ以上をコンピューティング装置が実行することを可能にするように構成されたコード及びルーチンを含み得る。加えて、あるいは代えて、入力モジュール１０２、イジングモジュール１０６、及び／又は出力モジュール１１２は、あらゆるプロセッサ、（例えば、１つ以上の処理の実行を行う又は制御するための）マイクロプロセッサ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、又はこれらのうち２つ以上の好適な組み合わせを含むハードウェアを用いて実装されてもよい。
【００１４】
それに代えて、あるいは加えて、入力モジュール１０２、イジングモジュール１０６、及び／又は出力モジュール１１２は、ハードウェアとソフトウェアとの組み合わせを用いて実装されてもよい。本開示において、入力モジュール１０２、イジングモジュール１０６、及び／又は出力モジュール１１２によって実行されるとして記述される処理は、入力モジュール１０２、イジングモジュール１０６、及び／又は出力モジュール１１２が対応するシステムに指示して実行させ得る処理を含み得る。
【００１５】
一部の実施形態において、入力モジュール１０２、イジングモジュール１０６、及び出力モジュール１１２は各々、アニーリングシステム（例えば、デジタルアニーリングシステム又は量子アニーリングシステム）に含められ得る。加えて、あるいは代えて、イジングモジュール１０６は、アニーリングシステムに含められ、入力モジュール１０２及び出力モジュール１１２のうちの１つ以上は、アニーリングシステムとインタフェースをとるように構成された別個のシステムに含められてもよい。また、入力モジュール１０２、イジングモジュール１０６、及び出力モジュール１１２は、本開示の説明を容易にするために、別々の要素として図示及び説明される。従って、入力モジュール１０２、イジングモジュール１０６、及び出力モジュール１１２によって実行されるとして記載される処理を実行するように構成される如何なる好適なハードウェア及び／又はソフトウェア構成も、本開示の範囲内である。
【００１６】
ランダムモジュラー部分集合和（ＲＭＳＳ）問題は、ｎ個の乱（ランダム）整数の集合Ｓ｛ａ１，ａ２，…，ａｎ｝のうちの部分集合Ｔであって、Ｔの要素の和がｑを法としてｃであり、ｑは整数の除数であり、ｃは整数の余りであるような部分集合Ｔを探索することとして定義され得る。以上において、ｎは集合内の整数の個数を表し得る。例えば、集合｛１，３，４，７，９，１０，１１｝の場合、ｎは７に等しいとし得る。この集合において、ｑが３であり且つｃが２であるとすると、部分集合Ｔは｛１，３，４，９｝を含むことができる。何故なら、｛１，３，４，９｝の和は１７であり、１７ｍｏｄ３は余り２となるからである。
【００１７】
一部の実施形態において、部分集合Ｔは、集合Ｓのうちの１つ以上の整数を含み得る。ｎ個の整数の集合Ｓを所与として、変数Ｔ、ｑ、及びｃのいずれの１つも、他の変数が与えられれば決定され得る。
【００１８】
一部の実施形態において、ＲＭＳＳ問題は、非決定性多項式時間完全（ＮＰ−ｃｏｍｐｌｅｔｅ）問題であるとし得る。これら及び他の実施形態において、ＲＭＳＳ問題では、提示された解が妥当であるかを確認することは容易であり得るが、整数の集合に対して解が存在するかを判定することは困難であり得る。一部の実施形態において、解を決定することの困難さは、整数の集合内の要素の個数ｎと除数ｑとの間の関係に基づき得る。これら及び他の実施形態において、解を決定することにおける困難さは、ＲＭＳＳの密度に関係し得る。例えば、ＲＭＳＳの密度ｄは、次式：
【数１】
2020071878.tif 000003
に基づき得る。これら及び他の実施形態において、密度ｄがほぼ１に等しいときに、ＲＭＳＳ問題を解くことはいっそう困難であり得る。密度ｄが１から遠いとき、ＲＭＳＳ問題はいっそう容易に解かれることもあれば、もっともな解を持たないこともある。
【００１９】
一部の実施形態において、ＲＭＳＳ問題入力１０４は、ｎ個の乱整数の集合と、整数の除数ｑと、整数の余りｃとを含み得る。ＲＭＳＳ問題入力１０４は、入力モジュール１０２に提供され得る。
【００２０】
入力モジュール１０２は、イジングモデル入力１１０を生成するよう、ＲＭＳＳ入力１０４に対して１つ以上の処理を実行するように構成され得る。入力モジュール１０２は、ＲＭＳＳ問題を解くためにイジングモジュール１０６によって使用されるようなイジングモデル入力１１０を生成するように構成され得る。
【００２１】
例えば、イジングモジュール１０６は、次式（２）のイジングエネルギー：
【数２】
2020071878.tif 000004
においてイジングエネルギーを最小化する出力ベクトル“Ｘ”を見つけることによって、イジングエネルギーを最小化するために、マルコフチェーンモンテカルロ（Markov  Chain  Monte  Carlo；ＭＣＭＣ）確率的探索を実行するように構成され得る。ここで、ｘｉ∈｛０，１｝は状態変数又はビットであり、Ｘ＝（ｘ１，ｘ２，…，ｘＮ）は状態変数のベクトル表現であり、Ｎはビット数であり、“Ｗ”は、出力ベクトル“ｘ”の要素間の連結を重み付けるイジングモデル連結重み行列であり、“ｂ”は、イジングエネルギーを決定する際に使用されるバイアスベクトルである。
【００２２】
一部の実施形態において、イジングモジュール１０６は、１つ以上のイジングユニットを含み得る情報処理装置を含むことができる。イジングユニットは、例えばＤｅＧｌｏｒｉａアルゴリズムなどのアルゴリズムに基づいて、小規模ハードウェアによってニューラルネットワークのイジング型エネルギー関数の処理を実行するように構成され得る。行列Ｗの要素は、ニューラルネットワークのニューロン間の重み付け値を含み得る。例えば、行列Ｗの要素は、行列Ｗ内での行番号によって表される第１のニューロンと行列Ｗ内での列番号によって表される第２のニューロンとの間の重み付け値を含むことができ、ここで、行番号と列番号とで要素が特定される。この情報処理装置は、ニューラルネットワーク内のエネルギーを最小化するように動作することで、行列Ｗ及びベクトルｂによって表される問題に対する解を決定し得る。
【００２３】
イジングユニットを含む情報処理装置の一例が、２０１７年８月３０日に出願された米国特許出願公開第２０１８／００７５３４２号にて提供されており、その全体を本開示に援用する。米国特許出願公開第２０１８／００７５３４２号に記載されているように、イジングユニットは、エネルギー値計算回路及び状態遷移決定回路を含み得る。エネルギー値計算回路は、行列“Ｗ”の要素のうちの１つ以上の要素の値に基づくエネルギー値を計算するように構成されることができ、それが、情報処理装置の出力を生成するために使用され得る。その出力は、行列Ｗ及びベクトルｂによって表される問題に対する解を含み得る。状態遷移決定回路の更なる情報及び例が、２０１７年９月２８日に出願された米国特許出願公開第２０１８／０１０７１７２号にて提供されており、その全体を本開示に援用する。
【００２４】
一部の実施形態において、入力モジュール１０２は、ＲＭＳＳ問題入力１０４に基づいて、イジングモデル連結重み行列“Ｗ”及びバイアスベクトル“ｂ”を生成するように構成され得る。
【００２５】
行列“Ｗ”及びベクトル“ｂ”をもたらすようにＲＭＳＳ問題がどのように定義されるかの一例をここで提供する。なお、イジングモデルは、出力を最小化することによって機能する。
【００２６】
この例では、ｎ個の整数の集合Ｓのパラメータが（＜ａｉ＞ｎｉ＝１）によって表され得る。パラメータはまた、除数ｑ及び余りｃを含み得る。なお、ＲＭＳＳ問題に対する解は、Ｔの要素の和がｑを法としてｃであるというものである。しかしながら、この解はまた、Ｔの要素の和が、ｃを引かれるときに、余りなくｑで割り切れる値であるともみなし得る。この理解に基づき、ＲＭＳＳの問題入力を所与として、次式の量：
【数３】
2020071878.tif 000005
を考え得る。ここで、ｘｉ∈｛０，１｝である。この量において、合計でｃになる複数のａｉ値の部分集合が存在する場合、対応する複数のｘｉ値を１に等しいとし、残りの値を０に等しいとすることによって、Ｈ１は最小化されることになる。
【００２７】
加えて、ＲＭＳＳ問題において、Ｔの要素の和は、ｑを法として与えられ得る。例えば、ｑが１５である場合、数３０、４５、６０、７５、９０、１０５などはすべて、０  ｍｏｄ  ｑにマッピングされ得る。ｑの倍数に関するこの丸めを説明するために、式（３）のエネルギー関数は、次式（４）：
【数４】
2020071878.tif 000006
に適応され得る。ここで、ｘｉ∈｛０，１｝、ｙ∈Ｚである。この例において、変数ｙは、部分集合の和がそれ以上であるｑの最も近い倍数を表し得る。
【００２８】
一部の実施形態において、イジングモジュール１０６は、方程式が純粋なバイナリ最適化問題であるように、バイナリ入力に基づく処理を実行するように構成されてもよい。式（３）は、ｘｉ∈｛０，１｝としてバイナリ入力にある。しかしながら、項ｙｑはバイナリ入力にはない。項ｙｑをバイナリ入力へと変換するため、ｙの取り得る最大値が、次式（５）：
【数５】
2020071878.tif 000007
にて決定され得る。なお、ｙの最大値は、集合Ｓ全体を除数ｑで除算したものである。ｙのバイナリ表現は、次式（６）：
【数６】
2020071878.tif 000008
のｔによって規定され得る。ｙのバイナリ表現に基づいて、式（４）は、
【数７】
2020071878.tif 000009
のように適応され得る。
【００２９】
式（７）は、故に、二次のバイナリ最適化問題を表している。式（７）で解かれ得るバイナリ未知数はｎ＋ｔである。式（７）のバイナリ未知数は、ｘｉ及びｙｉを含み得る。式（７）に基づき、解ベクトルは、（ｘ１．．．ｘｎｙ．．．ｙｔ）Ｔとして表され得る。この解ベクトルにおいて、ｘｉ＝１のとき、対応する要素ａｉは解部分集合Ｔの一部であるとし得る。ｘｉ＝０のとき、対応する要素ａｉは解部分集合Ｔの一部ではないとし得る。解ベクトルからのｙはＲＭＳＳ問題の解の一部ではないとし得る。
【００３０】
式（７）で表される二次のバイナリ最適化問題と、与えられる解ベクトル表現、行列Ｗ、及びバイアスベクトルｂが、ａｉの集合Ｓ、ｑ、及びｃの関数であることと、解かれ得る未知数の数がｎ＋ｔを限度とすることとに基づき、行列Ｗｉｊの要素は：
【数８】
2020071878.tif 000010
として計算されることができ、ベクトルｂｉの要素は：
【数９】
2020071878.tif 000011
として計算されることができる。
【００３１】
計算される行列Ｗ及びベクトルｂは、イジングモデル入力１１０として計算され得る。これらイジングモデル入力１１０がイジングモジュール１０６に提供され得る。
【００３２】
これら又は他の実施形態において、入力モジュール１０２は、イジングモデル入力１１０をイジングモジュール１０６に提供するように構成され得る。イジングモジュール１０６は、上述のイジング最適化モデルに従って記述される最適化問題を解くように構成され得る。また、上でも示したように、イジングモジュール１０６はアニーリングシステムの一部であってもよく、その結果、アニーリングシステムは、イジング最適化モデルを用いて、古典的に構成されたコンピューティングシステムよりも遥かに速い手法で最適化問題を解くことができる。これら又は他の実施形態において、イジングモジュール１０６は、最適化問題に対する解としてイジングモデル出力１０８を生成するように構成され得る。
【００３３】
ａｉの集合Ｓ、ｑ、及びｃと、ＲＭＳＳ問題とに従って上述のように決定されるものである決定された重み行列“Ｗ”及び決定されたバイアスベクトル“ｂ”に基づいて、イジングモジュール１０６は、Ｔの要素の和がｑを法としてｃに等しいような部分集合Ｔの要素を表す出力ベクトル（ｘ１．．．ｘｎｙ．．．ｙｔ）Ｔを決定するように構成され得る。従って、アニーリングシステムは、入力モジュール１０２によって生成されたモデル入力１１０とイジングモジュール１０６とを用いて、ＲＭＳＳ問題を解くことができ得る。これら又は他の実施形態において、出力ベクトルは、イジングモデル出力１０８に含められ得る。
【００３４】
一部の実施形態において、イジングモジュール１０６は、イジングモデル出力１０８をバイナリ表現で生成するように構成され得る。これら又は他の実施形態において、出力モジュール１１２がイジングモデル出力を受け取り得る。出力モジュール１１２は、イジングモデル出力１０８をバイナリ表現から、ＲＭＳＳ問題解１１４として出力され得る１０進表現へと変換するように構成され得る。
【００３５】
一部の実施形態において、ＲＭＳＳ問題解１１４は、様々な状況で使用され得る。例えば、ＲＭＳＳ問題は暗号学において使用され得る。これら及び他の実施形態において、乱整数の集合が生成され得る。図１に関して説明したプロセスを用いて、乱整数の集合に関するＲＭＳＳ問題の解が決定され得る。解及び乱整数の集合がともに、暗号構成における公開鍵／秘密鍵として使用され得る。例えば、公開／秘密鍵暗号スキームが、Akash NagによってＭＥＣＳに２０１７年４月にオンラインにて公開された“A  Fast  Heuristic  Algorithm  for  High  Density  Subset  Sum  Problems”（http://www.mecs-press.net）、“Cryptanalysis  of  Knapsack  Cryptography”（Georgia  Tech  Fall  2013、https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf）、及びMandal、Avradip、Arnab  Royによる“Relational  Hash:  Probabilistic  hash  for  verifying  relations,  secure  against  forgery  and  more”（Annual  Cryptology  Conference、Springer,  Berlin,  Heidelberg,  2015）に記載されており、これら全ての全体をここに援用する。
【００３６】
それに代えて、あるいは加えて、ＲＭＳＳ問題解１１４は、ＲＭＳＳ解を使用する暗号構成を研究するために暗号解析にて使用され得る。これら及び他の実施形態において、ＲＭＳＳ問題解１１４は、数ある用途の中でもとりわけ、暗号構成に対する代替的に可能な解を決定するために使用され得る。
【００３７】
図１には、本開示の範囲を逸脱することなく、変更、付加又は省略が為され得る。例えば、環境１００は、本開示にて図示されて説明されるものよりも多い又は少ない要素を含み得る。
【００３８】
図２は、本開示の少なくとも１つの実施形態に従った、ＲＭＳＳ関連問題を解くように構成されたコンピューティングシステム２０２の一例のブロック図を示している。コンピューティングシステム２０２は、イジングモデル入力モジュール（例えば、図１の入力モジュール１０２）、イジングモデルモジュール（例えば、図１のイジングモジュール１０６）、及び／又はイジングモデル出力モジュール（例えば、図１の出力モジュール１１２）に関連する１つ以上の処理を実行又は指示するように構成され得る。一部の実施形態において、コンピューティングシステム２０２は、アニーリングシステムに含められてもよいし、その一部を形成してもよい。コンピューティングシステム２０２は、プロセッサ２５０、メモリ２５２、及びデータストレージ２５４を含み得る。プロセッサ２５０、メモリ２５２、及びデータストレージ２５４は、通信可能に結合され得る。
【００３９】
一般に、プロセッサ２５０は、様々なコンピュータハードウェア若しくはソフトウェアモジュールを含んだ、如何なる好適な専用又は汎用のコンピュータ、コンピューティングエンティティ又は処理装置を含んでいてもよく、何らかの適用可能なコンピュータ読み取り可能媒体に格納された命令を実行するように構成され得る。例えば、プロセッサ２５０は、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、又はプログラム命令を解釈及び／又は実行し且つ／或いはデータを処理するように構成されたその他のデジタル回路若しくはアナログ回路を含み得る。図２では単一のプロセッサとして示されているが、プロセッサ２５０は、本開示に記載される任意数の処理を個々あるいは集合的に実行する又はそれらの実行を指示するように構成された任意数のプロセッサを含んでいてもよい。さらに、それらのプロセッサのうちの１つ以上が、例えば異なるサーバなどの、１つ以上の異なるエレクトロニクス装置上に存在してもよい。
【００４０】
一部の実施形態において、プロセッサ２５０は、メモリ２５２、データストレージ２５４、又はメモリ２５２とデータストレージ２５４、に格納されたプログラム命令及び／又はデータについて、プログラム命令を解釈及び／又は実行し且つ／或いはデータを処理するように構成され得る。一部の実施形態において、プロセッサ２５０は、データストレージ２５４からプログラム命令をフェッチして該プログラム命令をメモリ２５２にロードし得る。プログラム命令がメモリ２５２にロードされた後、プロセッサ２５０が該プログラム命令を実行し得る。
【００４１】
メモリ２５２及びデータストレージ２５４は、コンピュータ実行可能命令又はデータ構造を担持する、あるいは格納した、コンピュータ読み取り可能記憶媒体を含み得る。そのようなコンピュータ読み取り可能記憶媒体は、例えばプロセッサ２５０などの汎用又は専用のコンピュータによってアクセスされ得る如何なる入手可能な非一時的媒体をも含み得る。限定ではなく例として、そのようなコンピュータ読み取り可能記憶媒体は、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、電気的消去・プログラム可能型読み出し専用メモリ（ＥＥＰＲＯＭ）、コンパクトディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）若しくはその他の光ディスクストレージ、磁気ディスクストレージ若しくはその他の磁気記憶装置、フラッシュメモリデバイス（例えば、ソリッドステートメモリデバイス）、又は、コンピュータ実行可能命令の形態の特定のプログラムコード若しくはデータ構造を担持あるいは格納するために使用されることができ且つ汎用若しくは専用のコンピュータによってアクセスされることが可能なその他の非一時的記憶媒体を含む、有形の又は非一時的なコンピュータ読み取り可能記憶媒体を含み得る。これら及び他の実施形態において、本開示にて説明される用語“非一時的な”は、Ｎｕｉｊｔｅｎ，５００  Ｆ．３ｄ  １３４６に関しての連邦巡回控訴裁判所の決定（Ｆｅｄ．Ｃｉｒ．２００７）において特許可能な主題の範囲外であることが判明したタイプの一時的媒体のみを除外するように解釈されるべきである。以上のものの組合せもコンピュータ読み取り可能媒体の範囲に含まれ得る。
【００４２】
以上のものの組合せもコンピュータ読み取り可能記憶媒体の範囲に含まれ得る。コンピュータ実行可能命令は、例えば、特定の処理又は処理群をプロセッサ２５０に実行させるように構成された命令及びデータを含み得る。
【００４３】
コンピューティングシステム２０２には、本開示の範囲を逸脱することなく、変更、付加又は省略が為され得る。例えば、一部の実施形態において、コンピューティングシステム２０２は、明示的には図示あるいは記載されていない任意数のその他のコンポーネントを含んでいてもよい。
【００４４】
図３は、本開示にて記載される少なくとも１つの実施形態に従った、ＲＭＳＳ問題を解く方法３００の一例のフローチャートを示している。方法３００は、如何なる好適なシステム、機器、又は装置によって実行されてもよい。例えば、図１の環境１００又は図２のコンピューティングシステム２０２が、方法３００に関連する処理のうちの１つ以上を実行し得る。別個のブロックとして図示されるが、具体的な実装に応じて、方法３００のブロックのうちの１つ以上と関連付けられるステップ及び処理が、更なるブロックへと分割され、より少ないブロックへと結合され、あるいは排除され得る。
【００４５】
方法３００は、ブロック３０２で開始することができ、そこで、ランダムモジュラー部分集合和問題に関連する複数の乱整数、除数、及び余りが取得され得る。一部の実施形態において、上記複数の乱整数の個数を除数の対数で除算したものが、ほぼ１に等しいとし得る。一部の実施形態において、除数及び余りはどちらも整数とし得る。
【００４６】
ブロック３０４にて、イジングモデル連結重み行列“Ｗ”が生成され得る。一部の実施形態において、行列“Ｗ”の少なくとも一部の要素は、上記複数の乱整数に基づいて決定され得る。
【００４７】
それに代えて、あるいは加えて、行列“Ｗ”の要素のうち第１の部分は、上記複数の乱整数のみに基づくとすることができ、行列“Ｗ”の要素のうち第２の部分は、除数のみに基づくとすることができる。これら及び他の実施形態において、行列“Ｗ”の要素のうち上記複数の乱整数のみに基づく第１の部分は、上記複数の乱整数の数学的操作を含み得る。それに代えて、あるいは加えて、行列“Ｗ”の要素のうち除数のみに基づく第２の部分は、除数の数学的操作を含み得る。
【００４８】
それに代えて、あるいは加えて、行列“Ｗ”の要素のうち第１の部分はゼロとすることができ、行列“Ｗ”の要素のうち第２の部分は、上記複数の乱整数のうちの１つ以上のみに基づくとすることができ、行列“Ｗ”の要素のうち第３の部分は、除数のみに基づくとすることができ、そして、行列“Ｗ”の要素のうち第４の部分は、除数及び上記複数の乱整数のみに基づくとすることができる。これら及び他の実施形態において、行列“Ｗ”の要素のうち上記複数の乱整数のうちの１つ以上のみに基づく第２の部分は、上記複数の乱整数の数学的操作を含み得る。それに代えて、あるいは加えて、行列“Ｗ”の要素のうち除数のみに基づく第３の部分は、除数の数学的操作を含み得る。それに代えて、あるいは加えて、行列“Ｗ”の要素のうち除数及び上記複数の乱整数のみに基づく第４の部分は、除数及び上記複数の乱整数の数学的操作を含み得る。
【００４９】
一部の実施形態において、行列“Ｗ”の第１の次元は、上記複数の乱整数の個数に等しいとすることができ、行列“Ｗ”の第２の次元は、上記複数の乱整数の個数と“ｙ”の対数との和に等しいとすることができる。これら及び他の実施形態において、“ｙ”は、上記複数の乱整数の和を除数で除算したものとし得る。
【００５０】
ブロック３０６にて、イジングモデルバイアスベクトル“ｂ”が生成され得る。一部の実施形態において、ベクトル“ｂ”の要素は、余りに基づいて決定され得る。一部の実施形態において、ベクトル“ｂ”の要素のうち第１の部分は、余り及び上記複数の乱整数のみに基づくとすることができ、ベクトル“ｂ”の要素のうち第２の部分は、余り及び除数のみに基づくとすることができる。
【００５１】
これら及び他の実施形態において、ベクトル“ｂ”の要素のうち余り及び上記複数の乱整数のみに基づく第１の部分は、余り及び上記複数の乱整数の数学的操作を含み得る。ベクトル“ｂ”の要素のうち余り及び除数のみに基づく第２の部分は、余り及び除数の数学的操作を含み得る。
【００５２】
ブロック３０８にて、イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに行列“Ｗ”及びベクトル“ｂ”が提供され得る。ブロック３１０にて、上記複数の乱整数のうちの一組の整数を表す出力がアニーリングシステムから取得され得る。一部の実施形態において、この一組の整数の和を上記除数で除算したものが整数商及び上記余りとなり得る。
【００５３】
ブロック３１２にて、上記複数の乱整数、上記除数、及び上記余りによって規定されるランダムモジュラー部分集合和問題に対する解として、上記一組の整数が使用され得る。一部の実施形態において、上記複数の乱整数、除数、及び余りは、暗号ハッシュ技術から取得されることができ、上記一組の整数を使用することは、システムへのアクセスを得るために、暗号ハッシュ技術を適用するシステムに上記一組の整数を提示することを含み得る。
【００５４】
方法３００には、本開示の範囲を逸脱することなく、変更、付加又は省略が為され得る。例えば、方法３００の処理は、異なる順序で実行されてもよい。加えて、あるいは代えて、２つ以上の処理が同時に実行されてもよい。また、概説した処理及びアクションは、単に例として提示したものであり、開示した実施形態の本質を逸脱することなく、これらの処理及びアクションの一部は、オプション必要に応じてのものにされ、より少ない処理やアクションへと結合され、あるいは更なる処理やアクションへと展開され得る。
【００５５】
ここで使用されるとき、用語“モジュール”又は“コンポーネント”は、モジュール若しくはコンポーネントの処理を実行するように構成された特定のハードウェア実装、及び／又は、コンピュータシステムの汎用ハードウェア（例えば、コンピュータ読み取り可能媒体、処理装置など）に格納され且つ／或いはそれによって実行され得るソフトウェアオブジェクト若しくはソフトウェアルーチンを意味し得る。一部の実施形態において、ここに記載された様々なコンポーネント、モジュール、エンジン及びサービスは、コンピュータシステム上で（例えば、別々のスレッドとして）実行される複数のオブジェクト又はプロセスとして実装され得る。ここに記載されたシステム及び方法の一部は概して、（汎用ハードウェアに格納され且つ／或いはそれによって実行される）ソフトウェアにて実装されるとして記述されているが、特有のハードウェア実装、又はソフトウェアと特有のハードウェアとの組み合わせ実装も可能であり且つ企図される。この記載において、“コンピューティングエンティティ”は、ここで先に規定されるような何らかのコンピューティングシステム、又はコンピューティングシステム上で実行される何らかのモジュール若しくは複数のモジュールの組み合わせとし得る。
【００５６】
本開示及び特に添付の請求項（例えば、添付の請求項の本体）で使用される用語は概して、“オープン”用語として意図している（例えば、用語“・・・を含んでいる”は、“・・・を含んでいるが、それに限定されない”として解釈されるべきであり、用語“・・・を有している”は、“少なくとも・・・を有している”として解釈されるべきであり、用語“・・・を含む”は、“・・・を含むが、それに限定されない”と解釈されるべきであり、等々）。
【００５７】
また、導入されるクレーム記載の具体数が意図される場合、そのような意図は、請求項中に明示的に記載されることになり、そのような記載がない場合、そのような意図は存在しない。例えば、理解の助けとして、以下に添付される請求項は、クレーム記載を導入するために“少なくとも１つの”及び“１つ以上の”という前置きフレーズの使用を含むことがある。しかしながら、このようなフレーズの使用は、例え同じクレームが“少なくとも１つの”及び“１つ以上の”という前置きフレーズと“ａ”又は“ａｎ”などの不定冠詞とを含んでいるときであっても、不定冠詞“ａ”又は“ａｎ”によるクレーム記載の導入が、そのように導入されたクレーム記載を含む何れか特定の請求項を、唯一のそのような記載を含む実施形態に限定することを意味するようには、解釈されるべきでない（例えば、“ａ”及び／又は“ａｎ”は、“少なくとも１つの”又は“１つ以上の”を意味するように解釈されるべきである）。同じことが、クレーム記載を導入するために使用される定冠詞の使用にもあてはまる。
【００５８】
さらに、導入されるクレーム記載の具体数が明示的に記載されている場合であっても、当業者が認識するように、そのような記載は、少なくとも記載の数を意味するように解釈されるべきである（例えば、他の修飾語句のない、そのまま“２つのもの”なる記載は、少なくとも２つのもの、又は２つ以上のものを意味する）。また、“Ａ、Ｂ、及びＣなどのうちの少なくとも１つ”又は“Ａ、Ｂ、及びＣなどのうちの１つ以上”に似た伝統的表現が使用されるものにおいては、一般に、そのような構文は、Ａのみ、Ｂのみ、Ｃのみ、ＡとＢを共に、ＡとＣを共に、ＢとＣを共に、又は、ＡとＢとＣを共に、などを含むことを意図している。さらに、用語“及び／又は”の使用は、このように解釈されることを意図している。
【００５９】
また、２つ以上の別の用語を提示する離接的な用語又はフレーズは、実施形態の説明、特許請求の範囲、又は図面の中の何れであろうと、それらの用語のうちの１つ、それらの用語のうちの何れか、又は双方の用語を含む可能性を意図しているように理解されるべきである。例えば、フレーズ“Ａ又はＢ”は、用語“及び／又は”が別のところに使用されていたとしても、“Ａ”若しくは“Ｂ”又は“Ａ及びＢ”の可能性を含むように理解されるべきである。
【００６０】
本開示にて記載された全ての例及び条件付きの言葉は、本開示と技術を前進させるために本願の発明者によって与えられる概念とを読者が理解することを支援するための教育的な目的を意図したものであり、そのように具体的に記載した例及び条件への限定ではないと解釈されるべきである。本開示の実施形態を詳細に説明したが、これらの実施形態には、本開示の精神及び範囲を逸脱することなく、様々な変形、代用及び改変が為され得る。
【００６１】
以上の説明に関し、更に以下の付記を開示する。
（付記１）  ランダムモジュラー部分集合和問題に関連する複数の乱整数、除数、及び余りを取得し、
イジングモデル連結重み行列“Ｗ”を生成し、該行列“Ｗ”の少なくとも一部の要素は、前記複数の乱整数に基づいて決定され、
イジングモデルバイアスベクトル“ｂ”を生成し、該ベクトル“ｂ”の要素は、前記余りに基づいて決定され、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに前記行列“Ｗ”及び前記ベクトル“ｂ”を提供し、
前記複数の乱整数のうちの一組の整数であり、当該一組の整数の和を前記除数で除算したものが整数商及び前記余りとなる一組の整数、を表す出力を前記アニーリングシステムから取得し、
前記一組の整数を、前記複数の乱整数、前記除数、及び前記余りによって規定される前記ランダムモジュラー部分集合和問題に対する解として使用する、
ことを有する方法。
（付記２）  前記アニーリングシステムは、前記出力を生成するために使用されるエネルギー値を計算するように構成されたエネルギー値計算回路を含み、前記エネルギー値は、前記行列“Ｗ”の要素のうちの１つ以上の値に基づく、付記１に記載の方法。
（付記３）  前記行列“Ｗ”の第１の次元は、前記複数の乱整数の個数に等しく、前記行列“Ｗ”の第２の次元は、前記複数の乱整数の和を前記除数で除算したものを“ｙ”として、前記複数の乱整数の個数と“ｙ”の対数との和に等しい、付記１に記載の方法。
（付記４）  決定された前記行列“Ｗ”の要素のうち第１の部分は前記複数の乱整数のみに基づき、決定された前記行列“Ｗ”の要素のうち第２の部分は前記除数のみに基づく、付記１に記載の方法。
（付記５）  前記行列“Ｗ”の要素のうち第１の部分はゼロであり、前記行列“Ｗ”の要素のうち第２の部分は前記複数の乱整数のうちの１つ以上のみに基づき、前記行列“Ｗ”の要素のうち第３の部分は前記除数のみに基づき、前記行列“Ｗ”の要素のうち第４の部分は前記除数及び前記複数の乱整数のみに基づく、付記１に記載の方法。
（付記６）  前記ベクトル“ｂ”の要素のうち第１の部分は前記余り及び前記複数の乱整数のみに基づき、前記ベクトル“ｂ”の要素のうち第２の部分は前記余り及び前記除数のみに基づく、付記１に記載の方法。
（付記７）  前記複数の乱整数の個数を前記除数の対数で除算したものが近似的に１に等しい、付記１に記載の方法。
（付記８）  命令を格納した１つ以上のコンピュータ読み取り可能記憶媒体であって、前記命令は、実行されることに応答してシステムに処理を実行させ、前記処理は、
ランダムモジュラー部分集合和問題に関連する複数の乱整数、除数、及び余りを取得し、
イジングモデル連結重み行列“Ｗ”を生成し、該行列“Ｗ”の少なくとも一部の要素は、前記複数の乱整数に基づいて決定され、
イジングモデルバイアスベクトル“ｂ”を生成し、該ベクトル“ｂ”の要素は、前記余りに基づいて決定され、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに前記行列“Ｗ”及び前記ベクトル“ｂ”を提供し、
前記複数の乱整数のうちの一組の整数であり、当該一組の整数の和を前記除数で除算したものが整数商及び前記余りとなる一組の整数、を表す出力を前記アニーリングシステムから取得し、
前記一組の整数を、前記複数の乱整数、前記除数、及び前記余りによって規定される前記ランダムモジュラー部分集合和問題に対する解として使用する、
ことを有する、１つ以上のコンピュータ読み取り可能記憶媒体。
（付記９）  前記複数の乱整数、前記除数、及び前記余りは、暗号技術から取得される、付記８に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１０）  前記行列“Ｗ”の第１の次元は、前記複数の乱整数の個数に等しく、前記行列“Ｗ”の第２の次元は、前記複数の乱整数の和を前記除数で除算したものを“ｙ”として、前記複数の乱整数の個数と“ｙ”の対数との和に等しい、付記８に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１１）  決定された前記行列“Ｗ”の要素のうち第１の部分は前記複数の乱整数のみに基づき、決定された前記行列“Ｗ”の要素のうち第２の部分は前記除数のみに基づく、付記８に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１２）  前記行列“Ｗ”の要素のうち第１の部分はゼロであり、前記行列“Ｗ”の要素のうち第２の部分は前記複数の乱整数のうちの１つ以上のみに基づき、前記行列“Ｗ”の要素のうち第３の部分は前記除数のみに基づき、前記行列“Ｗ”の要素のうち第４の部分は前記除数及び前記複数の乱整数のみに基づく、付記８に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１３）  前記ベクトル“ｂ”の要素のうち第１の部分は前記余り及び前記複数の乱整数のみに基づき、前記ベクトル“ｂ”の要素のうち第２の部分は前記余り及び前記除数のみに基づく、付記８に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１４）  システムであって、
命令を格納した１つ以上のコンピュータ読み取り可能記憶媒体と、
前記１つ以上のコンピュータ読み取り可能記憶媒体に通信可能に結合され、前記命令の実行に応答して当該システムに処理を実行させるように構成された１つ以上のプロセッサと、
を有し、前記処理は、
ランダムモジュラー部分集合和問題に関連する複数の乱整数、除数、及び余りを取得し、
イジングモデル連結重み行列“Ｗ”を生成し、該行列“Ｗ”の少なくとも一部の要素は、前記複数の乱整数に基づいて決定され、
イジングモデルバイアスベクトル“ｂ”を生成し、該ベクトル“ｂ”の要素は、前記余りに基づいて決定され、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに前記行列“Ｗ”及び前記ベクトル“ｂ”を提供し、
前記複数の乱整数のうちの一組の整数であり、当該一組の整数の和を前記除数で除算したものが整数商及び前記余りとなる一組の整数、を表す出力を前記アニーリングシステムから取得し、
前記一組の整数を、前記複数の乱整数、前記除数、及び前記余りによって規定される前記ランダムモジュラー部分集合和問題に対する解として使用する、
ことを有する、システム。
（付記１５）  前記複数の乱整数、前記除数、及び前記余りは、暗号技術から取得される、付記１４に記載のシステム。
（付記１６）  前記行列“Ｗ”の第１の次元は、前記複数の乱整数の個数に等しく、前記行列“Ｗ”の第２の次元は、前記複数の乱整数の和を前記除数で除算したものを“ｙ”として、前記複数の乱整数の個数と“ｙ”の対数との和に等しい、付記１４に記載のシステム。
（付記１７）  決定された前記行列“Ｗ”の要素のうち第１の部分は前記複数の乱整数のみに基づき、決定された前記行列“Ｗ”の要素のうち第２の部分は前記除数のみに基づく、付記１４に記載のシステム。
（付記１８）  前記行列“Ｗ”の要素のうち第１の部分はゼロであり、前記行列“Ｗ”の要素のうち第２の部分は前記複数の乱整数のうちの１つ以上のみに基づき、前記行列“Ｗ”の要素のうち第３の部分は前記除数のみに基づき、前記行列“Ｗ”の要素のうち第４の部分は前記除数及び前記複数の乱整数のみに基づく、付記１４に記載のシステム。
（付記１９）  前記ベクトル“ｂ”の要素のうち第１の部分は前記余り及び前記複数の乱整数のみに基づき、前記ベクトル“ｂ”の要素のうち第２の部分は前記余り及び前記除数のみに基づく、付記１４に記載のシステム。
（付記２０）  前記複数の乱整数の個数を前記除数の対数で除算したものが近似的に１に等しい、付記１４に記載のシステム。
【図１】
2020071878.tif 000012
【図２】
2020071878.tif 000013
【図３】
2020071878.tif 000014