Two-sample exact period recovery ($\hat{r}=N/\gcd (N,c_1,c_2)$)

Suppose a function has least period $r\mid N$ and distinct values on distinct period cosets. Two independent Fourier samples have the form $c_j=s_{j}N/r$ with uniform $s_j\in {\mathbb{Z}}_r$. The displayed candidate is $r/\gcd (r,s_1,s_2)$, so exact recovery occurs when no prime divisor of $r$ divides both residues. The Chinese remainder theorem gives probability ${\prod }_{\ell \mid r}(1-{\ell }^{-2})\ge 1/\zeta (2)=6/{\pi }^2$, using the Euler product. Unlike a single-sample coprimality probability, this bound is uniformly greater than one half. A candidate-period test makes successful recovery heralded when such a test is available.