n

y

x

square_root(n,x)

 

Low:= 0; High:=n-1; s:=1;

REPEAT

x:=4x mod n; b:=lsb_sqrt(x); s:=2s

IF b=0 THEN High:=High-n div s

   ELSE Low:=Low+n div s

UNTIL Low=High

RETURN( Low )