The algorithm is described as follow,
Eisenstein proposed the following algorithm for computing the Jacobi symbol $(a|n)$ where $a$ and $n$ are odd numbers. Write $n = aq + er$ where $q = \lfloor n/a \rfloor$ if this is even, or $q = \lfloor n/a \rfloor + 1$ otherwise, and $e = \pm 1$ accordingly. Then $r$ is odd, and you can use the quadratic reciprocity law and the formula for $(-1|r)$ to continue by replacing the pair $n,a$ with the pair $a, r$.
I understand the Euler's algorithm (division), and got it to work correctly. Unfortunately, I have no idea how this algorithm works. Furthermore, what's the end condition of this algorithm? My guess was $r \neq 1$ is the end condition, but the result was completely wrong. An example to illustrate this algorithm would be greatly appreciated.
Edit This is my solution, written in C#
public int eisensteinAlgo( int a, int n ) { int parity = 1; int q = 0; int epsilon; int r = 0; while ( ( n % a ) == 0 ) { q = n / a; if ( ( q % 2 ) == 1 ) { q += 1; epsilon = -1; } else { epsilon = 1; } r = n - ( a * q ); r *= epsilon; parity *= ( int )Math.Pow( -1.0, ( r - 1 ) / 2 ); n = a; a = r; } return parity; }
Thank you,