Пусть A (Alice) и B (Bob) находятся на удалении друг от друга, и они не доверяют друг другу. Они хотят подбросить монетку по телефону.

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

2)  сообщает  свое предположение о числе : является ли оно квадратичным вычетом по модулю  или нет. 

3)  сообщает  о том, что его предположение правильно или нет, и называет ему числа и . 

4)  проверяет, что числа  и  простые и .