Budgeted Simon recovery with explicit failure branch

Input: A promised Simon oracle with $n\ge 1$, output width $m\ge n-1$, and a supplied rational failure tolerance $\delta =a\mathrm{/}b$ with positive binary integers $a<b$. Set $d=n-1$.

Instructions:

1. If $d=0$, return the unique nonzero one-bit string $1$ immediately, using zero queries.
2. Otherwise form $u=2db$ by binary shift-and-add multiplication, divide $u$ by $a$ using binary long division $u=ha+r$ with $0\le r<a$, and set $M=h$ if $r=0$ and $M=h+1$ otherwise. Start with an empty reduced row-echelon basis.
3. For at most $M$ trials, run One Simon Fourier-sampling sample once. Reduce its row against the current pivot rows in increasing pivot-column order. Discard it if the residual row is zero. Otherwise insert it at its least nonzero coordinate as a new pivot, clear that pivot column from the old rows by XOR, and maintain the pivot order. Stop sampling as soon as the basis reaches rank $d$.
4. If the basis reaches rank $d$, form the $(n-1)\times n$ matrix of its rows, call Gaussian elimination over F2 for Simon recovery, and output the returned vector. If all $M$ trials are used before rank $d$ is reached, return FAIL.

Every execution has at most $M$ oracle queries. Each sample uses $2n$ Hadamard gates and two finite measurements; no controlled or inverse query is used. Under the Classical bit-operation cost model, classical basis maintenance costs $O(M{n}^2)$ bit operations, the final row reduction costs $O(n^3)$, and computing $M$ by schoolbook integer arithmetic costs $O((B+\log n{)}^2)$ bit operations, where $B$ is the total binary input length of $a,b$. The total classical bit bound is therefore $O(M{n}^2+n^3+(B+\log n{)}^2)$. The correctness and failure bound are proved in Simon recovery succeeds with probability at least 1-delta.