C++ - computing the Legendre's symbol

    I need help with computing the Legendre's symbol. I need it for my quadratic sieve to work.

    Wiki says I should do it like that Symbol(a,p)=a^((p-1)/2) mod p , unfortunately, it doesn't seem to work in C++. I'm writing my program for a coding competition so don't link me to any libraries - I can't use them.

    double Legendre(double a, double p)
    {

    return double(int(pow(a,((p-1)/2)))%int(p));

    }

    tl,dr How do I quickly check if Q is a Quadratic residue mod P?

oh, I'm retarded.
http://en.wikipedia.org/wiki/Jacobi_symbol#Calculating_the_Jacobi_symbol
that was much better a plan.
and it solves your problem too.