Name | Type | Description |
---|---|---|
N | TNUM | The number for which to evaluate the Jacobi symbol. |
Modulus | TMOD | The modulus. |
#include <nttl/jacobi.h> ... long x = 12381273; short m = 13; if( Jacobi( x, m ) == 1 ) cout << "x is QR mod m" << endl; |
(-1/m) = (-1)^(m-1)/2 = / 1 if m==1 mod 4 \ -1 if m==3 mod 4 (2/m) = (-1)^(m^2-1)/8 = / 1 if m==+-1 mod 8 \ -1 if m==+-3 mod 8 (n/m) = (-1)^(m-1)(n-1)/2 = / (m/n) if m==1 or n==1 mod 4 \ -(m/n) if m==n==3 mod 4