1.Previous
3.Next

and .

Since we don't know or , we cannot compute and . However, it is easy to compute their product.This is known as the Jacobi symbol:
:

This also can be efficiently computed using the law of quadratic reciprocity for Jacobi symbols.

However, cannot in all cases tell us whether is a quadratic residue modulo or not!More precisely, if then is necessarily a quadratic non-residue

1.Previous
3.Next