According to this algo, we need to find b -- any quadratic non_residue modulo n, such 1<=b<=n-1. In my first programs I wrote

do
{
b=rand()%n;
}while(legendre(b, n)==1);

, so, in this case 0<=b<=n-1, and all they sometimes printed right answers, sometimes -- wrong, on identical tests. Be careful with it, I spent a lot of hours to find this very  stupid mistake. Right finding b is

do
{
b=1+rand()%(n-1);
}while(legendre(b, n)==1);

Edited by author 15.04.2011 22:18

Edited by author 15.04.2011 22:19

Edited by author 15.04.2011 22:19