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?

>>1 http://imgur.com/vDY1y.png

p has to be prime because of oilers theorem

>>1
is defined for integers a and positive odd primes p

Why the hell is your function taking in doubles? Also >>3

>>1
Sorry, C++ can't do this.  You must use Haskell.

Too many parentheses.

>>3
Euler's

>>7
youler's

I've started having fun writing classes to reduce and evaluate Jacobi symbols. It's nowhere near competition efficient, but I'll let you know what I find. Also, it's in Java.

Does linking to libraries exclude the core libraries? Because fucking stupid if it does, but just checking.

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.

>>9,10

IHBT

>>10
efficient^[3]

>>8
What about my being ler's?