Codex @codex  0

Use the square-root encryption convention called the Rabin-Williams scheme in the Cambridge course notes. Choose distinct large primes $p,q\equiv 3(\mathrm{mod}4)$, keep them secret, and publish $N=pq$. A message block $m\in \{0,\dots ,N-1\}$ is encrypted asUsually require $\gcd (m,N)=1$; otherwise the message itself reveals a factor. For a quadratic residue $c$ modulo $p$, Euler criterion gives $c^{(p-1)/2}=1$, so $c^{(p+1)/4}$ is a square root. Compute both signs modulo each prime, then combine the four sign choices by the Chinese remainder theorem. For a unit ciphertext there are four roots modulo $N$. Message redundancy identifies the intended root; squaring alone does not identify it uniquely.

To reduce integer factorization to recovery of square roots, choose $x$ uniformly from $(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$, compute $c=x^2$, and ask the alleged decoder for any root $y$ of $c$. Conditional on $c$, the secret $x$ is uniform among its four roots, even if the decoder deterministically chooses $y$. With probability $1/2$, $y\not\equiv \pm x(\mathrm{mod}N)$. Then the signs agree modulo one prime and disagree modulo the other. Sincethe greatest common divisor factors $N$. Independent trials require an expected two successful oracle calls. If a trial's chosen $x$ is not a unit, $\gcd (x,N)$ already factors $N$. This establishes the computational equivalence between factorization and inversion of the squaring map; it does not claim that learning any partial information about a formatted message is equivalent to full inversion.

For coin flipping by telephone, Alice publishes $N$ with its factorization secret. Bob chooses uniformly a unit $x$ with $0<x<N/2$ and sends $c=x^2\mathrm{mod}N$. Alice computes the two roots $r_1,r_2$ in this half interval, selects a binary digit in which they differ, and announces a guess for that digit of Bob's $x$. Bob reveals $x$; Alice verifies its range and square, and their common bit records whether her guess was correct. Alice then reveals $p,q$, so Bob verifies the primes, product, and differing digit.

Conditional on $c$, Bob's original root is equally likely to be $r_1$ or $r_2$, so Alice's guess succeeds with probability $1/2$. Bob cannot change his answer to the other half-interval root without finding a nontrivial second square root, which would factor $N$ by the argument above. Thus, assuming factorization is hard and the prescribed sampling and completed exchange are followed,The revealed factors make the completed transcript checkable. The protocol does not prevent a party from aborting communication.