Jacobi's symbol

Jacobi's symbol is something a little more than Legendre's symbol, which indicates, whether for given a there exists t, such that t^2=a in Zp (where p is prime and given). In fact if the bottom number in Jacobi's symbol is prime, we in fact have Legendre's Symbol. If not, Jacobi's symbol really doesn't say nothing, but it has a few interesting properties:

1. (a/p)=((a mod p)/p)
2. ((a*b)/p)=(a/p)*(b/p)
3. (p/q)*(q/p)=(-1)^((p-1)/2)*(-1)^((q-1)/2)

Where (a/b) is Jacobi's symbol where a is on top and b at bottom. Thanks to those it's quite easy to compute Jacobi's symbol for given a and b.

The whole algorithm is implemented in bignumber unit. Here you can see a simple program, which just reads two number and using jacobi from bignumber unit computes Jacobi's symbol.

To see that it really works, use below:

MAIN