Общий вход: $ n$ - составное целое число.

1) Первый шаг проверяющего. Проверяющий $ V$ удостоверяется в том, что не является ни простым числом, ни степенью простого числа. Затем генерирует множество $ C$, состоящее из $ m$ случайных чисел, принадлежащих множеству $ J_n (1)=\{x\vert x \in Z^*_n , (\frac{x}{n})=1\}$, и отсылает его доказывающему.

2) Далее $ P$, используя протокол доказательства принадлежности числа мноежеству квадратных вычетов, доказывает проверяющему, что все квадраты, принадлежащие множеству $ C$, являются квадратичными вычетами по модулю $ n$.

3) Заключительный шаг провепяющего. Если количество всех квадратов из множества $ C$ $ k>\lfloor \frac{3}{8}m\rfloor$, $ V$ принимает доказательство, в противном случае отвергает.