Пусть  - составное целое число. Пусть  знает разложение этого числа на два простых множителя.  хочет доказать  свое знание, не показывая само разложение. 

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

1) Первый шаг проверяющего. Проверяющий  удостоверяется в том, что не является ни простым числом, ни степенью простого числа. Затем генерирует множество , состоящее из  случайных чисел, принадлежащих множеству , и отсылает его доказывающему. 

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

3) Заключительный шаг провепяющего. Если количество всех квадратов из множества ,  принимает доказательство, в противном случае отвергает.