Approximate GCD の返り値の大きさについて、あるいは我々は何個のサンプルを取るべきか

最近の CTF では Approximate GCD を要求されることが多い。直近では 2024/10/26 の CTF (ISITDTU CTF QUALS 2024) で出題された。そのとき出題された Sign という問題において、解く側にはサンプルとなる署名を何個取るかの自由度があり、それによって Approximate GCD に渡す整数の個数が決まる。
Approximate GCD には以下のようなトレードオフがある。

正しさ: 整数の個数が少なすぎると正しい答えが出ない確率が高い。
速度: Approximate GCD は内部で LLL アルゴリズムを使っているので、一応多項式時間で動作はするものの整数の個数が多すぎると時間がかかる。

これにより、Approximate GCD に渡すべき整数の個数が分からなかったので調査した。

実験に使ったコードはコード置き場にある。またデータをまとめたスプレッドシートは Approximate GCD の返り値 - Google スプレッドシートにある。

結論

nums を長さ n の s ビット程度の整数列とする。Approximate GCD (approx_gcd.sage の approx_gcd(d: list[int], approx_error: int) -> int) を approx_gcd(nums, 2**b) の形で呼び出す時、返ってくる間違った値は (s-b)/n + b ビット程度である。d ビット程度の値が欲しい場合は、(s-b)/n + b < d となるように十分大きい n を選ぶべきである。(n > (s - b) / (d - b))
Sign の場合、s = 2048 * 11 = 22528, b = 256, d = 2048 であったので、n > (22528 - 256) / (2048-256) ~= 12.43 である必要があった。(実装の都合上、n = (サンプル数) - 1 だったので、(サンプル数) >= 14 が必要。)

前提知識

Approximate GCD というのは、以下のような問題、およびそれを解くアルゴリズムのことを意味している。

n 個の整数 nums が与えられる。nums[i] が全て g の倍数に近いような、最大の g を求めよ。(どの程度の差であれば「近い」とみなすのかは問題によって決まる。)

参考資料はなかなか見つかりにくいが、例えば以下を参考にされたい。

実装は approx_gcd.sage を参考にされたい。

実験

予備実験

筆者はまず、「n 個の整数を approx_gcd に与えるのであれば、失敗確率は $1-1/\zeta(n)$ で成功確率は $1/\zeta(n)$ だろう」と考え、実験した。(ζ はゼータ関数であり、なぜゼータ関数が登場するのかは任意に選んだn数が互いに素になる確率 | Mathlog などを参考にすること。失敗するのは欲しい gcd で割ったときの商がたまたま互いに素でなかったときである。)

結果は予想に反し、n <= 12 のとき (num_sigs <= 13 のとき) 確実に失敗し、n >= 13 のとき (num_sigs >= 14 のとき) 確実に成功した。
データについてはコード置き場の exp-0.sage, exp-0.log を見ること。

誤差の実験 (Sign)

num_sigs <= 13 のとき確実に失敗したので、gcd として得られた値が本来欲しい値と比べてどのくらい大きいかを実験した。
データについてはコード置き場の exp-1-error.sage, exp-1-error.log を見ること。
結果は以下のように、(反比例) + (定数) ビットという形になった。

誤差の実験 (10000 ビットのランダムな整数)

ランダムな整数については (反比例) + (定数) ビットという形になる可能性があると思い、10000 ビットのランダムな整数を num_nums 個与える実験をした。(2 <= num_nums <= 16)
データについてはコード置き場の exp-2.sage, exp-2.log を見ること。

結果はやはり (反比例) + (定数) ビットであった。

結論

nums を長さ n の s ビット程度のランダムな整数列とする。Approximate GCD (approx_gcd.sage の approx_gcd(d: list[int], approx_error: int) -> int) を approx_gcd(nums, 2**b) の形で呼び出す時、返ってくる値は (s-b)/n + b ビット程度である。
この結論は以下の理屈で正当化できる。また実験とも整合している。

b が十分に大きい場合、全ての整数を 2^b で割れば nums は 2^(s-b) 程度のランダムな実数列と見なせる。これに対して LLL をやって得られる結果の大きさは s-b のみに依存し、s や b そのものには依存しないはず。そのため最終的なビット長は (s-b の式) + b ビットになるはず。
ビット長は n に関して単調減少であるはず。