Общий вход: натуральные числа $ n$ и $ x$ в двоичном представлении, $ x \in Z_n^*$, $ \vert x\vert=m$.

1) Первый шаг доказывающего. Используя случайные биты, $ P$ генерирует $ u$, случайный квадратичный вычет по модулю $ n$, и отправляет его проверяющему.

2) Первый шаг проверяющего. $ V$ получает $ u$. $ V$ проверяет выполняется ли $ u \in Z_n^*$, если нет, то он останавливается. $ V$ генерирует случайный бит $ \alpha$ и отправляет его доказывающему.

3) Второй шаг доказывающего. $ P$ получает $ \alpha$. Если $ \alpha=0$, то $ P$ использует случайные биты и генерирует $ v$, случайный квадратный корень из $ u$ по модулю $ n$, если $ \alpha=1$, то $ P$ использует случайные биты и генерирует $ v$, случайный квадратный корень из $ ux$ по модулю $ n$. $ P$ отравляет $ v$ проверяющему.

4) Второй шаг проверяющего. $ V$ получает $ v$. $ V$ проверяет выполняется ли $ v \in Z_n^*$ и или $ \alpha=0$ и $ v^2\pmod n$ $ =u$, или $ \alpha=1$ и $ v^2\pmod n$ $ =(ux)\pmod n$, если нет, то он останавливается.

5) $ P$ и $ V$ повторяют шаги 1) - 4) $ m$ раз.

Проверяющий принимает доказательство, если он завершит $ m$ итераций шагов 1) - 4). В противном случае, отвергает.