72.6. ДОВЕРЕННОЕ БРОСАНИЕ МОНЕТЫ

 
  THIS SECTION IS UNDER CONSTRUCTION  
 


Доверенное бросание монеты

Базируется на том, что 
	X^2 = A    имеет 2 корня на простом поле

	Alice
		выбирает простые большие p,q
		посылает бобу n = p * q
	Bob
		выбирает случайное число u в интервале [1, n/2]
		посылает Алисе z = u^2
	Alice
		используя p и q вычисляет четыре квадратных корня
			z mod n  (+-x, +-y)
		Выбирает корни между [1,n/2] их будет 2
			u - это один из них, но какой неизвестно
		Выбирает корень посылает Бобу следующую info
			Определяет наименьший i, такой что в корнях x,y
			для которого значение разряда i различается
		Посылает Бобу пару {i, значение бита[i] в корне выбранном алисой}
		(Алиса на может посылать весь корень).
	Bob
		Сообщает угадала ли Алиса и присылает u
	Alice
		Присылает Бобу p и q на проверку