こういう表現をすることは稀だと思いますが、構造としては同じだなと思ったのでそういう言い方を選びました。
16.0 / 9.0 として計算した double の値
$$
\begin{aligned}
16\oslash 9 &= \tfrac1{9}\cdot(16-2^{-50}) \\
&= {\small 1}.{\small 777777777777777}{\footnotesize 679091286699986}{\scriptsize 085295677185058}{\tiny 59375} \\
\end{aligned}
$$
があったとします。このとき、（主に誤差に対して甘いプログラムの撃墜ケースを見つけたい文脈で）$x\oslash y = 16\oslash 9$ かつ $\gcd(x, y) = 1$ かつ $(x, y) \ne (16, 9)$ なる組 $(x, y)$ を探したいことはしばしばあります*1。
用語
集合 $\mathcal X$, $K$ と関数 $h\colon \mathcal X\to K$ を考えます。
与えられた $k\in K$ に対し、$h(x) = k$ なる $x$ を $k$ の 原像 (preimage) または 第一原像 (first preimage) と言います[Glossary | CSRC]。
また、$x_1\in\mathcal X$ に対し、$h(x_1) = h(x_2)$ かつ $x_1\ne x_2$ なる $x_2\in\mathcal X$ を、$x_1$ の 第二原像 (second preimage) と言います[Glossary | CSRC]。
また、これらの原像を求めることを、それぞれ （第一）原像攻撃 ((first-)preimage attack)・第二原像攻撃 (second-preimage attack) と言います。セキュリティの文脈の用語なので、攻撃という言い方がなされるんだと思います。
この文脈の第一・第二というのは、原像として一つ目・二つ目という意味合いであって、甲種・乙種とか ①・②のような意味合いではないと思っています*2。
さて、特定の浮動小数点型に含まれる正の正規化数全体からなる集合を $F$ とし、$\Z_F = \Z\cap F$ とします。
このとき、$f\colon \Z_F^2\ni (x, y) \mapsto x\oslash y\in F$ で定義される $f$ に関しての第一・第二原像を求めていこうかな〜という話です。
考察
まず第一原像攻撃について考えていきます。
与えられた $z$ に対して $x\oslash y = z$ なる $(x, y)$ を求めたいです。
$\roundcirc{z'} = z$ なる $z'=\tfrac xy\in \Q$ を求めればよいわけで、そのような $z'$ は $\Q$ 上の区間になっていることに注意します。
特に、$[z-2^{e_-}\lldot z+2^{e_+}]$ のような形をしています。開区間か閉区間かは、仮数部の偶奇によって変わります。
分母が $k$ 以下の分数として表せる有理数全体からなる集合について、相異なる要素の差の絶対値は $k^{-2}$ で下から評価できることを踏まえると、閉区間のケースに帰着できると思います。
ということで、与えられた区間 $I$ に対して $I\cap\Q$ の要素を取ってこれればよいということになります。
取ってくる要素としては、分母が最小のものを持ってこれると実用上うれしそうです。
$I\cap\Z \ne \emptyset$ なら $\min{(I\cap\Z)}$ を持ってくればよいので、以下はそうでないと仮定します。
これはもう Stern–Brocot 木を考えてくれと言われているようなものです。適切に区間を狭めていくことで実現可能です。今回はそういう気分ではないので証明はしません。
続いて、第二原像攻撃について考えます。
$(x, y)$ が与えられて $z = x\oslash y$ としたとき、$[z-2^{e_-}\lldot z) \cap (z\lldot z+2^{e_+}]$ に属する有理数を取ってくればよいです。
二つの区間それぞれについてさっき考えた操作をすればよいので、これもできます。おわりです。
実装
preimage2.py
from fractions import Fraction
from math import ceil, floor, inf, nextafter
def _bisect(f):
assert f(0)
hi = 1
while f(hi):
hi *= 2
lo = hi // 2
while hi - lo > 1:
mid = lo + (hi - lo) // 2
if f(mid):
lo = mid
else:
hi = mid
return lo
def _mediant(x, y):
fracx, kx = x
fracy, ky = y
x0, x1 = fracx.numerator, fracx.denominator
y0, y1 = fracy.numerator, fracy.denominator
return Fraction(kx * x0 + ky * y0, kx * x1 + ky * y1)
def interval_fraction(min_: Fraction, max_: Fraction) -> Fraction:
"""Return p/q with minimum q such that min_ <= p/q <= max_."""
if min_ == max_:
return min_
if min_ <= 0 <= max_:
return Fraction(0, 1)
if max_ < 0:
return -interval_fraction(-max_, -min_)
assert 0 < min_ < max_
if min_.is_integer():
return min_
if ceil(min_) <= floor(max_):
return ceil(min_)
n = floor(min_)
min_, max_ = min_ - n, max_ - n
assert 0 < min_ < max_ < 1
lo = Fraction(0)
hi = Fraction(1)
while True:
assert lo < min_ < max_ < hi
med = _mediant((lo, 1), (hi, 1))
if min_ <= med <= max_:
return n + med
ky = _bisect(lambda k: _mediant((lo, 1), (hi, k)) < min_)
lo0 = _mediant((lo, 1), (hi, ky))
hi1 = _mediant((lo, 1), (hi, ky + 1))
assert lo0 < hi1
assert lo0 < min_ <= hi1
if hi1 <= max_:
return n + hi1
lo = lo0
assert lo < min_ < max_ < hi
med = _mediant((lo, 1), (hi, 1))
if min_ <= med <= max_:
return n + med
kx = _bisect(lambda k: _mediant((lo, k), (hi, 1)) > max_)
hi0 = _mediant((lo, kx), (hi, 1))
hi1 = _mediant((lo, kx + 1), (hi, 1))
assert hi1 <= max_ < hi0
if min_ <= hi1:
return n + hi1
hi = hi0
def preimage2(frac: Fraction) -> Fraction:
"""Return a second preimage for frac."""
if frac == 0:
return Fraction(0, 1)
if frac < 0:
return -preimage(-frac)
alpha = float(frac)
fl = Fraction(alpha)
tol = Fraction(1, 2**2048)
nextdown = nextafter(alpha, -inf)
lo = (Fraction(nextdown) + Fraction(alpha)) / 2
if float(lo) == nextdown:
lo += tol
nextup = nextafter(alpha, inf)
hi = (Fraction(nextup) + Fraction(alpha)) / 2
if float(hi) == nextup:
hi -= tol
x1 = interval_fraction(lo, frac - tol)
x2 = interval_fraction(frac + tol, hi)
return x1 if x1.denominator < x2.denominator else x2
assert preimage2(Fraction(16, 9)) == Fraction(941929333829127, 529835250278884)
assert preimage2(Fraction(9, 16)) == Fraction(633318697598980, 1125899906842631)
assert preimage2(Fraction(2, 3)) == Fraction(2401919801264265, 3602879701896398)
assert preimage2(Fraction(1, 10)) == Fraction(800639933754755, 8006399337547549)
具体例
冒頭の例について考えます。
$$
\begin{aligned}
16\oslash 9 &= \tfrac1{9}\cdot(16-2^{-50}) \\
&= {\small 1}.{\small 777777777777777}{\footnotesize 679091286699986}{\scriptsize 085295677185058}{\tiny 59375}
\end{aligned}
$$
に丸められる区間は
$$
[\tfrac1{9}\cdot(16-2^{-50}) - 2^{-53} \lldot \tfrac1{9}\cdot(16-2^{-50}) + 2^{-53}]
$$
で、
$$
\begin{aligned}
&\phantom{{}={}} \tfrac1{9}\cdot(16-2^{-50}) - 2^{-53} \\
&= \tfrac1{9} \cdot (16 - 2^{-50} - 9\cdot 2^{-53}) \\
&= \frac{16\cdot 2^{53} - 2^3 - 9}{9\cdot 2^{53}}
= \frac{144115188075855855}{81064793292668928} \\
&= {\small 1}.{\small 777777777777777}{\footnotesize 568068984237470}{\scriptsize 431253314018249}{\tiny 51171875}, \\
&\phantom{{}={}} \tfrac1{9}\cdot(16-2^{-50}) + 2^{-53} \\
&= \tfrac1{9} \cdot (16 - 2^{-50} + 9\cdot 2^{-53}) \\
&= \frac{16\cdot 2^{53} - 2^3 + 9}{9\cdot 2^{53}}
= \frac{144115188075855873}{81064793292668928} \\
&= {\small 1}.{\small 777777777777777}{\footnotesize 790113589162501}{\scriptsize 739338040351867}{\tiny 67578125}
\end{aligned}
$$
です。見つかった第二原像は $(941929333829127, 529835250278884)$ で、
$$
\begin{aligned}
&\phantom{{}={}} \frac{941929333829127}{529835250278884} \\
&= {\small 1}.{\small 777777777777777}{\footnotesize 568068984237471}{\scriptsize 269418025815571}{\tiny 204989570324110{\ldots}} \\
&= \tfrac9{16} - \tfrac1{4768517252509956}
\end{aligned}
$$
でした。他の例は値だけ載せておきます。
$$
\begin{aligned}
9 \oslash 16 &= 633318697598980 \oslash 1125899906842631, \\
2 \oslash 3 &= 2401919801264265 \oslash 3602879701896398, \\
1 \oslash 10 &= 800639933754755 \oslash 8006399337547549.
\end{aligned}
$$
あとがき
下記の記事の補足のような感じです。
rsk0315.hatenablog.com
ゆるゆるっとコードを書いて記事に出すくらいの気軽さを持つことがよさそうです。
Stern–Brocot 木は ABC でそこまで頻出ではないですが、そうした競プロで得た知識を競プロの横道の部分で活かせて面白いなぁと思いました。
反例の構成をする癖を続けていると、「この範囲には反例はあるだろうと思うが、実際に構成するのは自明ではなさそう」とか「既知の方法に帰着させて最小反例を構成できる」とかの感覚がついてきて楽しいなぁという気がします。既知の幅を広げていきたいです。
コンテスタント側であれば浮動小数点型を避ければいいだけですから、わざわざ反例について思いを馳せる必要はないですが、ジャッジ側として変な解法を落としたい場合には有用な内容だと思います。
浮動小数点型が使われているだけで嘘解法扱いして、実際の最小反例が制約の上限よりずっと大きいのに「これは嘘解法だ！」と決めつけるような人にはなりたくないですからね。
数値型として浮動小数点型しか備えていない独自言語でのみ提出可能な地獄のえびちゃんお誕生日コンテストとかどうでしょうか。嫌ですね。
JavaScript にも BigInt があるので、その問題用の言語を作る（例）必要があるかなと思いました。Educational 浮動小数点型 Contest というのはどうでしょう（？）
今年は 関数型まつり2026 に行こうかなと思っていたのですが、気づいたら一人で浮動小数点型まつり 2026 をやっていました。どうしてでしょう。
おわり
おわりです。
