#NEWLINE# def legendre_symbol( a , p ) : #NEWLINE# #INDENT# " Compute the Legendre symbol a|p using\n    Euler's criterion. p is a prime, a is\n    relatively prime to p (if p divides\n    a, then a|p = 0)\n    \n    Returns 1 if a has a square root modulo\n    p, -1 otherwise.\n    " #NEWLINE# ls = pow ( a , ( ( p - 1 ) / 2 ) , ls ) #NEWLINE# return ( ( - 1 ) if ( ls == ( p - 1 ) ) else ls )