# HUBO式による因数分解 ## 2つの素数の積を因数分解するためのHUBO ここでは、2つの素数の積である整数の因数分解を考えます。 例えば、積 $pq=35$ が与えられたとき、その2つの素因数 $p=5$ と $q=7$ を求めることが目標になります。 $\sqrt{35}=5.91$ かつ $35/2=17.5$ であることから、探索範囲を次のように制限できます。 $$ 2 &≤ p ≤ 5,\\ 6 &≤ q ≤ 17. $$ このような整数変数に対して、35 の因数分解問題は次のペナルティ式を用いて定式化できます。 $$ f(p, q)=(pq − 35)² $$ 整数変数 $p$ および $q$ は2値変数の線形結合として実装されるため、その積 $pq$ は2次式になります。したがって $f(p, q)$ は4次式になります。$f(p, q)$ は、$p$ と $q$ が 35 の正しい因数であるときにちょうど最小値 0 をとります。
:::{container} prog-cpp ### 因数分解のためのQUBO++プログラム 以下のQUBO++プログラムは、HUBO式 $f(p, q)$ を構築し、Easy Solver を用いて最適化問題を解きます。 ```{literalinclude} ../../programFiles/cppPrograms/basic/hubo-factorization-program1.cpp :language: cpp :caption: hubo-factorization-program1.cpp ``` このプログラムでは、式 `p * q == 35` は自動的に `qbpp::sqr(p * q - 35)` に変換されます。そして、等式が満たされたときにエネルギー値 0 を達成します。 このプログラムの出力は次のとおりです。 ```{include} ../../programFiles/markDown/basic/hubo-factorization-program.md :start-after: :end-before: ``` 出力から、式 `f` には4次の項が含まれていることが確認できます。これにより、`f` がHUBO式であることが分かります。また、ソルバーは正しく素因数 $p=5$ および $q=7$ を見つけています。 ## 大きな数の素因数分解における無制限の大きな係数 デフォルトでは、QUBO++ における式の係数およびエネルギー値のデータ型は、それぞれ `int32_t` および `int64_t` です。これらの型は、マクロ `COEFF_TYPE` および `ENERGY_TYPE` を定義することで変更できます。 さらに、QUBO++ は任意に大きな係数およびエネルギー値を持つ式をサポートしています。このオプションを有効にするには、両方のマクロを `qbpp::cpp_int` に設定します。以下の QUBO++ プログラムは、2つの大きな素数の積を因数分解します。 ```{literalinclude} ../../programFiles/cppPrograms/basic/hubo-factorization-program2.cpp :language: cpp :caption: hubo-factorization-program2.cpp ``` `qbpp.hpp` をインクルードする前に、マクロ `COEFF_TYPE` と `ENERGY_TYPE` を `qbpp::cpp_int` に設定しています。整数定数は、文字列リテラルを引数とする `qbpp::cpp_int()` を用いて指定します。 このプログラムは、次のような出力を生成します。 ```{include} ../../programFiles/markDown/basic/hubo-factorization-program.md :start-after: :end-before: ``` 式 `f` には非常に大きな係数が含まれていることが分かります。また、大きな合成数の因数分解が正しく求められていることも確認できます。 > TIP: `COEFF_TYPE` および `ENERGY_TYPE` には、`int8_t`, `int16_t`, `int32_t`, `int64_t`, `qbpp::int128_t`, `qbpp::int256_t`, `qbpp::int512_t`, `qbpp::int1024_t`, `qbpp::cpp_int` を設定できます。 ::: :::{container} prog-python ### 因数分解のためのPyQBPPプログラム 以下のPyQBPPプログラムは、HUBO式 $f(p, q)$ を構築し、Easy Solver を用いて最適化問題を解きます。 ```{literalinclude} ../../programFiles/pythonPrograms/basic/hubo-factorization-program1.py :language: python :caption: hubo-factorization-program1.py ``` このプログラムでは、式 `p * q == 35` は自動的に `sqr(p * q - 35)` に変換されます。そして、等式が満たされたときにエネルギー値 0 を達成します。 このプログラムの出力は次のとおりです。 ```{include} ../../programFiles/markDown/basic/hubo-factorization-program.md :start-after: :end-before: ``` 出力から、式 `f` には4次の項が含まれていることが確認できます。これにより、`f` がHUBO式であることが分かります。また、ソルバーは正しく素因数 $p=5$ および $q=7$ を見つけています。 ## 大きな数の素因数分解のための無制限の大きな係数 PyQBPP のデフォルトモジュール `pyqbpp`（`pyqbpp.c32e64` の別名）は、32 ビット係数と 64 ビットエネルギー値を使用し、最も高速に動作します。大きな合成数の素因数分解では、ペナルティ式の係数が 32 ビット範囲を超える場合があります。そのような場合は `pyqbpp.cppint` をインポートすることで、任意精度整数演算（`coeff_t` と `energy_t` の両方を `cpp_int` に設定）へ切り替えることができます。 PyQBPP では、係数型・エネルギー型の選択をインポートするサブモジュール名（`pyqbpp.c32e64`、`pyqbpp.cppint` など）によって指定します。 以降の `qbpp.var`、`qbpp.constrain`、`qbpp.EasySolver` などの呼び出しは、選択した係数型・エネルギー型を一貫して使用します。 以下のプログラムは、2つの大きな素数の積を因数分解する例です。 ```{literalinclude} ../../programFiles/pythonPrograms/basic/hubo-factorization-program2.py :language: python :caption: hubo-factorization-program2.py ``` Python は任意精度整数をネイティブにサポートしているため、目標値 `1000039 * 1000079` は Python の `int` としてそのまま記述できます。pyqbpp.cppint をインポートすれば、PyQBPP は係数とエネルギー値をすべて Python の `int` として保持・操作するため、上限値 `2000000` や目標の積を Python 整数として自然に記述できます。 このプログラムは以下の結果を出力します: ```{include} ../../programFiles/markDown/basic/hubo-factorization-program.md :start-after: :end-before: ``` 式 `f` が非常に大きな係数（64ビットの範囲を大きく超える）を含み、大きな合成数の因数分解が $1000079 \times 1000039$ として正しく得られていることがわかります。整数変数 $p$ と $q$ はそれぞれ範囲 $[2, 2000000]$ をカバーするために21個のバイナリ変数（`p[0]-p[20]、q[0]-q[20]`）に展開されています。 > TIP: 任意精度整数を使用するには `import pyqbpp.cppint as qbpp` とします。他の整数型バリアントを使用する場合は、対応するサブモジュール（`pyqbpp.c64e64`、`pyqbpp.c128e128` など）をインポートします。 :::