Общий вход: и - простые числа,
.
1) Первый шаг доказывающего. выбирает наугад
и вычисляет
,
,
. отправляет
проверяющему.
2) Первый шаг проверяющего. выбирает наугад
и отправляет его доказывающему.
3) Второй шаг доказывающего. вычисляет
,
,
,
,
и отправляет их проверяющему.
4) Второй шаг проверяющего. проверяет выполнение условий
,
,
. Если хотя бы одно не выполняется, останавливает проверку и отвергает доказательство.
5) и повторяют шаги 1) - 4) раз.
Проверяющий принимает доказательство, если он завершит итераций шагов 1) - 4). В противном случае, отвергает.