# HUBO式による因数分解
:::{container} prog-cpp
## 2つの素数の積を因数分解するためのHUBO
2つの素数の積である**整数の因数分解**を考えます.
例えば,積 $pq = 35$ が与えられたとき,2つの素因数 $p=5$ と $q=7$ を求めることが目標です.
$\sqrt{35}=5.91$ かつ $35/2=17.5$ であるため,$p$ と $q$ の探索範囲を以下のように制限できます:
$$
\begin{aligned}
2 \leq &p \leq 5 \\
6 \leq &q \leq 17
\end{aligned}
$$
このような整数変数に対して,$35$ の因数分解問題は以下のペナルティ式を用いて定式化できます:
$$
\begin{aligned}\
f(p,q) &= (pq-35)^2
\end{aligned}
$$
整数変数 $p$ と $q$ はバイナリ変数の線形式として実装されるため,その積 $pq$ は2次式となり,したがって $f(p,q)$ は4次式になります.
明らかに,$f(p,q)$ は $p$ と $q$ が35の正しい因数であるとき,かつそのときに限り最小値0を達成します.
## 因数分解のためのHi-QUBOプログラム
以下のHi-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を達成します.`f` は制約式の `qbpp::Expr` で,展開後のペナルティ `qbpp::sqr(p * q - 35)` と元の式 `p * q` の両方を保持します.`f` 自身は式 `qbpp::sqr(p * q - 35)` を表し,`f.body()` は元の式 `p * q` を返します.`f.simplify_as_binary()` は `f` 自身（ペナルティ）と `f.body()`（元の式）の両方を同時に簡約します.
このプログラムの出力は以下の通りです:
```{include} /../programFiles/markDown/basic/hubo-factorization.md
:start-after:
:end-before:
```
出力から,式 `f` が4次の項を含んでおり,HUBO式であることが確認できます.
ソルバーは素因数 $p=5$ と $q=7$ を正しく求めています.
## 大きな数の素因数分解のための無制限の大きな係数
Hi-QUBOでは,式の係数とエネルギー値のデータ型はデフォルトでそれぞれ `int32_t` と `int64_t` です.
これらの型は **`INTEGER_TYPE_*`** マクロ（`INTEGER_TYPE_C32E32`,`INTEGER_TYPE_C32E64`（デフォルト）,`INTEGER_TYPE_C64E64`,`INTEGER_TYPE_C64E128`,`INTEGER_TYPE_C128E128`,`INTEGER_TYPE_CPP_INT`）のいずれかを定義することで切り替えられます — 詳細は [VAREXPR](../basic/variables-and-expressions.md#整数の範囲coeff_t-と-energy_t) 参照.
さらに,Hi-QUBOは任意の大きさの係数とエネルギー値を持つ式を **`INTEGER_TYPE_CPP_INT`** でサポートします.このマクロを定義すると `coeff_t` と `energy_t` の両方が **`qbpp::cpp_int`** になります.
以下のHi-QUBOプログラムは,2つの大きな素数の積を因数分解します:
```{literalinclude} /../programFiles/cppPrograms/basic/hubo-factorization-program2.cpp
:language: cpp
:caption: hubo-factorization-program2.cpp
```
`qbpp/qbpp.hpp` をインクルードする前に `INTEGER_TYPE_CPP_INT` を定義し,`coeff_t` と `energy_t` を任意精度整数 `cpp_int` に設定します.
定数整数は **`qbpp::integer()`** に10進文字列を渡して指定します（`int * int` の中間オーバーフローを避けるため,積は `qbpp::integer("1000039") * qbpp::integer("1000079")` と書いています）.
このプログラムは以下の結果を出力します:
```{include} /../programFiles/markDown/basic/hubo-factorization.md
:start-after:
:end-before:
```
式 `f` が非常に大きな係数を含んでおり,大きな合成数の因数分解が正しく得られたことがわかります.
>**TIP**
> 任意精度整数を使用するには,ヘッダのインクルード前に **`INTEGER_TYPE_CPP_INT`** を定義します（あるいは `-DINTEGER_TYPE_CPP_INT` をコンパイラフラグで渡します）.他の型は **`INTEGER_TYPE_C32E32`**,**`INTEGER_TYPE_C32E64`（デフォルト）**,**`INTEGER_TYPE_C64E64`**,**`INTEGER_TYPE_C64E128`**,**`INTEGER_TYPE_C128E128`** で選択します — 全対応表は [VAREXPR](../basic/variables-and-expressions.md#整数の範囲coeff_t-と-energy_t) 参照.
:::
:::{container} prog-python
## 2つの素数の積の素因数分解のための HUBO
2つの素数の積である**整数の素因数分解**を考えます.
例えば,積 $pq = 35$ が与えられたとき,2つの素因数 $p=5$ と $q=7$ を求めることが目標です.
$\sqrt{35}=5.91$ かつ $35/2=17.5$ であるため,$p$ と $q$ の探索範囲を以下のように制限できます:
$$
\begin{aligned}
2 \leq &p \leq 5 \\
6 \leq &q \leq 17
\end{aligned}
$$
このような整数変数に対して,$35$ の素因数分解問題はペナルティ式を用いて以下のように定式化できます:
$$
\begin{aligned}
f(p,q) &= (pq-35)^2
\end{aligned}
$$
整数変数 $p$ と $q$ はバイナリ変数の線形式として実装されるため,その積 $pq$ は2次式となり,したがって $f(p,q)$ は4次式になります.
明らかに,$f(p,q)$ は $p$ と $q$ が 35 の正しい因数であるときに限り最小値 0 を達成します.
## 素因数分解の PyQBPP プログラム
以下のプログラムは HUBO 式 $f(p,q)$ を構築し,Easy Solver を用いて最適化問題を解きます:
```{literalinclude} /../programFiles/pythonPrograms/basic/hubo-factorization-program1.py
:language: python
:caption: hubo-factorization-program1.py
```
このプログラムでは,`qbpp.var("p", between=(2, 5))` で値域 $\{2, 3, 4, 5\}$ をとる整数変数 $p$ を生成します（内部的にはバイナリ変数 `p[0]`, `p[1]` の線形結合として表現されます）.同様に,値域 $\{6, 7, \dots, 17\}$ をとる $q$ はバイナリ変数 `q[0]`, `q[1]`, `q[2]`, `q[3]` に展開されます.式 `(p * q == 35)` は自動的に `sqr(p * q - 35)` に変換され,等式が満たされたときにエネルギー値 0 を達成します.`f` は制約式で,展開後のペナルティ `sqr(p * q - 35)` と元の式 `p * q` の両方を保持します.`f` 自身は式 `sqr(p * q - 35)` を表し,`f.body` は元の式 `p * q` を返します.`f.simplify_as_binary()` は `f` 自身（ペナルティ）と `f.body`（元の式）の両方を同時に簡約します.整数変数は内部のバイナリ変数に対して線形なので,積 $pq$ は2次式となり,その2乗である $f(p,q)$ は4次式となります.
このプログラムの出力は以下の通りです:
```{include} /../programFiles/markDown/basic/hubo-factorization.md
:start-after:
:end-before:
```
出力から,式 `f` が4次の項を含むことが確認でき,これが 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.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.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` など）をインポートします.
:::