解法

概要

LSB decryption oracle attackの類似をやるだけ (CTF暗号典型)

詳細

次の場合分けを考える:

  • $x \lt q$ の場合: $(x \bmod q) \equiv x \pmod{2}$
  • $\frac{x}{2} \lt q \le x$ の場合: $(x \bmod q) \equiv x - q \pmod{2}$

$\frac{x}{2} \lt q$ な奇数 $q$ を与えてやれば $x \lt q$ かどうかが得られる。 これで二分探索が可能。

メモ

わりと好き

実装

#!/usr/bin/env python3
import sys

def ask(q):
    print('?', q)
    sys.stdout.flush()
    s = input()
    return int(s == 'odd')

l = 1
r = 10 ** 9 + 1
parity = ask(10 ** 9)
while True:
    m = ((l + r) // 2) | 1
    if not (l < m < r):
        break
    if ask(m) != parity:
        l = m
    else:
        r = m
if l % 2 != parity:
    l += 1
print('!', l)