Since no efficient factorization algorithm is known, but efficient modular exponentiation algorithms are, in general it is more efficient to use Legendre's original definition, e.g.
Since no efficient factorization algorithm is known, but efficient modular exponentiation algorithms are, in general it is more efficient to use Legendre's original definition, eg